Discussion :

[Amiral56]

Bonjour à tous,

Le calcul probabiliste et le dénombrement plus précisément étaient ma bête noire tout au long de mon cursus scolaire.
Aujourd'hui je sèche sur un problème qui m'a l'air très simple !

Mon problème on peut l'assimiler à une urne contenant 10 boules numérotés (le nombre de boules sera ensuite généralisé). Ensuite je fais 10 tirages sans remise.
Quelle est la probabilité de d'obtenir exactement deux boules adjacentes ? par exemple : 1 2 4 6 8 10 5 3 9 ou bien 1 5 4 6 8 10 3 9 2 etc ...
Quelle est la probabilité de d'obtenir exactement trois boules adjacentes ?

Je vous remercie par avance.
Bien cdt.

[dourouc05]

Quelle est ta définition de "boules adjacentes" ? Des boules dont le numéro ne se suivent pas (1 3 5 2 ne rentre pas dans cette définition) ?

Une manière générale pour calculer ces probabilités est de générer un arbre : depuis la racine, tu as dix choix pour les dix valeurs possibles et équiprobables de la première boule tirée ; ensuite, de chaque boule, tu auras neuf autres possibilités ; tu continues jusqu'à tirer toutes les boules dans toutes les branches (ce qui fait déjà un paquet ici) et tu comptes celles qui correspondent à ta définition. C'est faisable de manière algorithmique au besoin, mais il y a des manières plus rapides d'obtenir le même résultat.

[picodev]

Bonjour,

voilà un petit problème sympa qui fait picote les méninges

Dans le cas général tu cherches à compter les permutations de [1,…,n] avec exactement une «adjacence» [k;k+1]. Pour en créer une on observe que l'on peut commencer par placer n-1 éléments (les n privés de k+1) de manière à n'avoir aucune «adjacence» et de placer k+1 à la droite de k. Il y a n-1 façons de choisir ces éléments.

Si on note par S(n) le nombre de permutations sans «adjacences» de [1,…,n], Adj(n,2) le nombre de permutations avec exactement une adjacence de deux boules consécutives on obtient :
Adj(n,2)=(n-1)S(n-1) ou bien S(n)=Adj(n+1,2)/n

Reste à déterminer S(n) …
Essayons de trouver une relation récurrente en observant le fait que pour construire une permutation sans adjacence de [1,…,n+1] on peut partir d'une permutation sans adjacence de [1,…,n] et que l'on a n possibilités de placer n+1 (partout sauf à droite de n).
On ne les trouve pas toutes car il manque celle où justement on part d'une permutation de [1,…n] avec exactement une adjacence [k;k+1] pour créer [k,n+1,k+1] or il y en a Adj(n,2).

On obtient donc la relation S(n+1)=nS(n)+(n-1)S(n-1) que l'on réécrit S(n)=(n-1)S(n-1)+(n-2)S(n-2).
On a également S(1)=1 (il n'y a qu'une permutation de [1] et elle est sans adjacence : 1) et S(2)=1 (sur les permutations de [1,2] qui sont 12 et 21, seule 21 convient).

Et hop, un début d'algorithme pour la première partie de la question.

[Amiral56]

Bonjour à vous deux,

Je tiens à vous remercier pour votre aide.

Quelle est ta définition de "boules adjacentes" ?

Pour répondre à la question de ce qu'est l'adjacence : L'adjacence ce n'est autre que deux boules qui ont des numéros adjacents comme x x x x 7 6 x x x x ou x 1 2 x x x x x x x x etc ...

Si on note par S(n) le nombre de permutations sans «adjacences» de [1,…,n], Adj(n,2) le nombre de permutations avec exactement une adjacence de deux boules consécutives on obtient :
Adj(n,2)=(n-1)S(n-1) ou bien S(n)=Adj(n+1,2)/n

Reste à déterminer S(n) …

Cette piste me parait très séduisante !
Il doit forcément y avoir une relation de récurrence, il ne reste plus qu'à la déterminer !
Je vais creuser la question ce soir ! Je reste à toutes propositions
Merci à vous

[picodev]

Mon raisonnement ne tient que pour le cas x 1 2 x x x ...
Il faut ajouter les cas [k+1;k] dans ton cas.

[Amiral56]

Il ne suffit pas de multiplier par deux ?

[tbc92]

Si tu considères que 1 et 10 sont des nombres adjacents ( notion de cycle), ça simplifie bien le problème. Je vais faire quelques recherches, en prenant cette hypothèse.

Et question subsidiaire :
Si j'ai 1 2 4 5 3 7 9 6 8 10 , j'ai 1 2 qui sont adjacents, puis 4 5 qui sont adjacents --> combinaison refusée ?

[Amiral56]

Salut tc92,

Je te remercie pour ta contribution à ce sujet.

Pour répondre à ta question :

Si tu considères que 1 et 10 sont des nombres adjacents ( notion de cycle), ça simplifie bien le problème

On peut pas dire que 1 et 10 sont deux nombres adjacents. Deux nombres adjacents sont sous la forme de [i, i+1] ou [i+1, i] sans notion de cycle.

Je réponds aussi à ta question subsidiaire ...

Et question subsidiaire :
Si j'ai 1 2 4 5 3 7 9 6 8 10 , j'ai 1 2 qui sont adjacents, puis 4 5 qui sont adjacents --> combinaison refusée ?

Dans ce cas tu as deux couples adjacents [1,2] et [4,5] donc hélas combinaison refusée, car notre contrainte forte est un et unique couple adjacent dans la séquence.

Je continue à réfléchir ... j'ai l'impression que plus j'avance moins ça me parait simple. Je crois qu'il faudra reprendre l'idée de picodev, je crois qu'elle est très pertinente ...

Merci