Inscription / Connexion Nouveau Sujet
Combinaison "topologique"
Bonjour à tous 
,
Je bute sur un problème de Dénombrement.
Je voudrais connaître le nombre de combinaisons de k éléments pris parmi n, avec pour condition que chaque élément k ai un écart de minimum 1 avec les autres. je m'explique..
Prenons un Exemple :
Soit l'univers 
= {1,2,3,4,5,6}, donc n = 6, et Choisissons k = 3
Donc avec la formule :, on obtient
Si on essaie de lister les Combinaisons on aurait :
1,2,3
1,2,4
etc..
4,5,6
Mon objectif est de trouver une formule générale capable de dénombrer ici les combinaisons spécifiques :
1,3,5
1,3,6
1,4,6
2,4,6
C'est-à-dire, les combinaisons avec un écart de minimum 1 entre chaque élément k. On aurait ici combinaisons
Voici à titre indicatif quelques autres valeurs calculées "expérimentalement" :
Voila. Le cœur du problème est qu'il s'agit bien d'une situation de combinaison sans répétition mais avec une notion de topologie en plus.
Malheureusement, je ne connais pas de formule résolvant ce type de problème, et les tentatives essayant d'en "créer" une ont lamentablement échouées :/
Ma question est donc de savoir si il en existe une, car, in fine, je voudrais calculer pour des valeurs beaucoup plus grandes.
Merci d'avance.
Il ne me semble pas que ce sujet soit vraiment un sujet de Terminale.
Sinon, il y a une bijection facile entre les combinaisons de k parmi n avec des écarts d'au moins 1 et les combinaisons de k parmi n-k+1 : la bijection consiste à faire disparaître un élément après chaque élément de la combinaison à écarts (sauf le dernier).
Exemple : donne
.
On a donc (avec les notations que tu emploies)
La section Terminale m'a semblé appropriée du fait que la Combinatoire est présente au programme de Terminale.
Cependant il est vrai qu'il ne s'agit pas d'un exercice habituel.
Sinon, la formule que tu propose concerne également les Combinaisons avec répétition et fonctionne parfaitement merci
Étrangement je l'avais testée, par acquis de conscience, et il m'avait semblé qu'elle ne fonctionnait pas. Erreur de ma part :p
Ce que tu considères dans le cas des combinaisons avec répétition n'est pas très clair (difficile de maintenir un écart d'au moins 1 si on répète).
Ce problème est très intéressant et peut se rapporter au niveau terminale sans problème.
Choisir p éléments parmi n avec un écart de 1 au moins entre chaque peut être vu comme placer n-p éléments non identifiés et choisir ensuite quels endroits on choisis pour insérer des éléments. Comme je ne suis pas sûr d'être clair, voici un exemple.
J'ai 7 éléments, je veux en choisir 3. Je place 4 éléments anonymes (représentés par des E ci-dessous). Choisir mes 3 éléments parmi les 7 reviens à choisir 3 emplacements parmi les 5 (représentés par des x).
x E x E x E x E x
Et on s'est donc ramené à un simple problème de combinaison.
Ainsi, comme il y a n-p+1 emplacements x (1 de plus que d'éléments anonymes) on a:
On peut voir le problème autrement, en définissant par récurrence (je vous laisse gérer les cas p=0, p=1, n=p nécessaires pour l'arrêt). Pour passer de n-1 à n, il faut considérer tous les choix possible de p éléments parmi les n-1 premiers et y ajouter tous les choix possibles comptant le nème élément, c'est à dire les choix de p-1 éléments parmi les n-2 premiers:
Cette méthode par récurrence permet de facilement généraliser la formule aux combinaisons de p éléments parmi n avec un écart d'au moins k entre chaque (ton cas étant le cas particulier k=1):
Merci pour ce problème intéressant !
Annuler
connectez vous