EfCeBa a écrit:

Une petite énigme de dénombrement/probabilité et sa généralisation.

Oh p*tain, une énigme d'EfCeBa ! Hosannah

1/ [latex]\frac{2}{N-1}[/latex] à mon avis : on tire un point au hasard sur le cercle, il reste donc N-1 points dont 2 sont voisins du premier. Le choix du premier point n'est pas vraiment un choix, puisque la situation à l'issue de ce "choix" est toujours exactement la même à une petite rotation près.

2a / Soit le deuxième point est déjà à côté du premier (proba [latex]\frac{2}{N-1}[/latex]) ;

soit il est espacé du premier de seulement un point (proba [latex]\frac{2}{N-1}[/latex]), auquel cas il reste trois positions du troisième point qui vérifient les contraintes de voisinage (proba [latex]\frac{3}{N-2}[/latex])

soit il est plus loin que ça (proba [latex]\frac{N-5}{N-1}[/latex]) et il y a quatre positions du troisième point qui assurent le "voisinage" demandé (proba [latex]\frac{4}{N-2}[/latex])

D'où une proba, après simplification, de [latex]\frac{6(N-3)}{(N-1)(N-2)}[/latex]

2b / Avec la même démarche :
[TeX]\frac{2}{N-1} \times \frac{2}{N-2} + \frac{2}{N-1} \times {1}{N-2}[/TeX]
soit [latex]\frac{6}{(N-1)(N-2)}[/latex]

3 / Ouhlà, pas ce soir, j'ai la migraine Pour la deuxième, ça sent le [latex]\frac{n!(N-n)!}{(N-1)!}[/latex]. Ca colle pour [latex]n=3[/latex], mais aussi pour [latex]n=N-2[/latex] (ça donne [latex]\frac{2}{N-1}[/latex] pour une simple raison de symétrie : choisir [latex]N-2[/latex] points qui sont tous consécutifs revient à choisir les 2 points restants voisins. Et pour [latex]n=N-1[/latex], ça fait 1, bonne nouvelle. Ca ne marche plus pour le choix de N points parmi N, mais disons 1, en gros. Je tente la récurrence demain, si je me sens d'attaque.

Bonjour

Si N <= 2 alors le problème est trivial.
Supposons N > 2.

1/
Le nombre de façon possible de choisir 2 points parmi N est [latex]{N\choose 2} = {N(N-1)\over 2}[/latex]

Le nombre de paires de points consécutifs est exactement N.

Donc la probabilité d'avoir deux points consécutifs est [latex]{N\over N(N-1)/2} = {2\over N-1}[/latex]

3/ (et 2b pour n=3).
De manière générale si on remplace 2 par un n quelconque, n < N alors la probabilité d'avoir n points consécutifs est [latex]N\over{N\choose n}[/latex].


2/a
Pour chaque paire de point consécutifs, j'ai N-2 choix pour le troisième points.
Donc le nombre de triplets qui contient deux point consécutifs est N(N-2).
Edit:  arghhh, non comme ça j'en compte trop, en fait il y en a N(N-3)

Donc la probabilité qu'en choisissant 3 points j'en ai au moins deux consécutifs est :

[latex]{N(N-3)\over {N\choose 3}} = {N(N-3)\over {N(N-1)(N-2)/3!}} = {6(N-3)\over (N-1)(N-2)}[/latex] avec N > 3.

3/
De manière générale si on remplace 3 par n, n < N et 2 par k, 2<= k < n alors la probabilité d'avoir au moins k points consécutifs en en tirant n est :

[latex]N(N-k-1)\over {N\choose n}[/latex] avec N > k.

Pour la 3a je trouve pour [latex]n \geq 2[/latex] :

Il faut avoir [latex]2n \leq N[/latex]

et alors la probabilité d'avoir au moins 2 points consécutifs est :
[TeX]1-\frac{(N-n-1) \times ... \times (N-2n+1)}{(N-1)\times ... \times (N-n+1)}[/TeX]
Voici mon raisonnement :

On choisit une orientation sur le cercle.
On tire un premier point sur le cercle, le point n°0. Ce point n°0 et l'orientation du cercle fournissent un repère pour l'emplacement des [latex]n-1[/latex] points suivants. On procède ensuite successivement au tirage des points n°1 à [latex]n-1[/latex].

Voici un exemple de tirage avec N=10 et n=4 : 0XX3X21XXX

On dénombre tout d'abord le nombre de façons de tirer ces [latex]n-1[/latex] points :

Il y a [latex]N-1[/latex] possibilités pour le point n°1, puis [latex]N-2[/latex] possibilités pour le point n°2, ... et enfin [latex]N-n+1[/latex] possibilités pour le point n°[latex]n-1[/latex]. Ce qui donne au total [latex](N-1)\times ... \times (N-n+1)[/latex] tirages possibles.

Parmi tous ces tirages possibles, on va à présent dénombrer ceux où il n'y a pas 2 points consécutifs. Pour cela, on compte le nombre de façons d'assembler des "dominos" doubles du type iX pour i variant de 1 à [latex]n-1[/latex] ainsi que des "dominos" simples X.

Par exemple le tirage sans 2 points consécutifs 0XX3X2X1XX correspond à la suite de dominos 0X-X-3X-2X-1X-X.

Il y a [latex]n-1[/latex] dominos à placer du type iX et [latex]N-2n[/latex] dominos X, ce qui fait au total [latex]N-n-1[/latex] dominos à placer. Une suite de dominos est déterminée par les rangs des dominos du type iX dans cette suite, rangs compris entre 1 et [latex]N-n-1[/latex]. Pour le domino 1X il y a [latex]N-n-1[/latex] possibilités, Pour le domino 2X il y a [latex]N-n-2[/latex] possibilités, ... et enfin pour le domino (n-1)X il y a [latex]N-2n+1[/latex] possibilités. Ce qui donne au total [latex](N-n-1) \times ... \times (N-2n+1)[/latex] tirages sans 2 points consécutifs.

La probabilité d'avoir un tirage sans 2 points consécutifs est donc
[TeX]\frac{(N-n-1) \times ... \times (N-2n+1)}{(N-1)\times ... \times (N-n+1)}[/TeX]
et la probabilité d'avoir un tirage avec au moins 2 points consécutifs est donc
[TeX]1-\frac{(N-n-1) \times ... \times (N-2n+1)}{(N-1)\times ... \times (N-n+1)}[/TeX]
CQFD.

titoufred, apparemment tes formules, qui s'écrivent aussi
[TeX]\frac{(N-n-1)!(N-n)!}{(N-1)!(N-2n)}[/TeX]
et dont ta réponse
[TeX]1-\frac{(N-n-1)!(N-n)!}{(N-1)!(N-2n)}[/TeX]
sont équivalentes aux miennes, on retrouve bien les mêmes valeurs, bravo !