Calcul élémentaire

did63 · April 2019

Bonjour, un problème qui me parait simple et que je n'arrive pas à résoudre.

On tire au hasard 18 numéros parmi 5000 boules. Quelle est la probabilités que 3 d’entre eux soient consécutifs.

did63 · April 2019

C'est bon en fait j'ai trouvé

marsup · April 2019

Moi, je n'ai pas trouvé...

Si quelqu'un veut bien expliquer !

lourrran · April 2019

Idem, le calcul me paraît très compliqué. En tout cas, je ne vois pas de formule 'de cours' qui donnerait le résultat. On va donc devoir recenser tous les cas 1 par 1, ça va être très long (18, c'est beaucoup). Ou lancer une simulation par ordinateur, en répétant l'opération 1000000 de fois, pour avoir une bonne estimation du résultat.

Blueberry · April 2019

Non pas si compliqué que ça:
Il y a 4998 ensembles de 3 numéros consécutifs (1,2,3 ; 2,3,4 ;... ; 4998,4999,5000). Une fois ces numéros choisi il y a $\begin{pmatrix} 4998\\15 \end{pmatrix}$ façons de choisir les 15 autres.
Enfin il y a en tout $\begin{pmatrix} 5000\\18 \end{pmatrix}$ façons de choisir les 18 boules parmi 5000.
D'où la probabilité $\dfrac {4998\times\begin{pmatrix} 4998\\15 \end{pmatrix}}{\begin{pmatrix} 5000\\18 \end{pmatrix}}$.

marsup · April 2019

Tu es sûr de ne pas compter plusieurs fois certains tirages dans ton $(5000-2) \times \binom{5000-2}{18-3}$ ?

(d'ailleurs je pense que c'est plutôt $\binom{5000-3}{18-3}$)

Ceux dans lesquels il y aurait plusieurs triplets consécutifs ?

Blueberry · April 2019

Ah oui tu as bien raison... Car par exemple pour un tirage $\{ 1,2,3\}$ puis 15 autres boules et $\{ 4,5,6\}$ puis 15 autres boules, on pourrait tomber sur la même chose.

LOU16 · May 2019

Bonjour
Voilà ce que j'ai trouvé:
Pour tous entiers $n$ et $k$ tels que $0\leqslant k \leqslant n$, je note $A(n,k)$ le nombre de parties à $k$ éléments de $[\![1;n]\!]$ qui ne contiennent pas trois entiers consécutifs. La probabilité cherchée est donc: $\:\:\boxed{\displaystyle
\mathbb P(n ,k) =1- \dfrac {A(n,k)}{\binom nk} }$
Les $A(n,k)$ obéissent alors à la récurrence suivante; $ \forall n,k \in \N \:\text{tels que}\: n,k \geqslant 2 \:\: $ $$A(n+1,k) = A(n,k) + A(n-1, k-1) + A(n-2, k-2)$$ de sorte que ces nombres apparaissent ligne $n$, colonne $k$ du tableau suivant où les lignes et les colonnes sont numérotées de $0$ à $9$.
$$\begin{array} {lllllllll}1
\\ 1&1\\1&2&1\\ 1&3&3&0 \\ 1&4&6&2&0 \\1&5&10&7&1&0 \\1&6&15&16&6&0&0 \\1&7&21&30&19&3&0&0 \\1&8&28&50&45&16&1&0&0 \\1&9&36&77&90&51&10&0&0&0\\ \end{array}$$
Définissons la suite $(Q_n)_{n\in\N}$ d"éléments de $\Z[X]$ par: $\:\: Q_0 = 1;\:\: Q_1= X+1; \:\:Q_2 = X^2 +2X+1,\:\:$ et
$ \forall n \in \N, \:n\geqslant 2, \:\: Q_{n+1}= Q_n +X Q_{n-1}+X^2Q_{n-2}.\:$ Alors, les $A(n,k)$ peuvent être caractérisés par:
$$\boxed{\forall n \in \N,\:\: Q_n = \displaystyle \sum _{k=0}^n A(n,k) X^k}\quad\quad \big(\text{deg} Q_n =\Big \lceil \dfrac {2n}3 \Big \rceil \big)$$
Il peut être intéressant de noter que $\displaystyle \sum_{k=0}^{+\infty} A(n+k,k) =3 ^{n+1}$, mais aussi de remarquer que la suite $(S_n)_{n\in \N}$ où $S_n := \displaystyle \sum _{k=0}^n A(n,k)$ est le nombre de parties de $[\![1;n]\!]$ ne contenant pas trois entiers consécutifs, peut être également définie par:
$$ S_0=1;\:\: S_1=2;\:\: S_2=4;\:\:\quad \forall n \in\N \:\text{tel que}\: n\geqslant 2, \:\:\: S_{n+1} =S_n+S_{n-1}+ S_{n-2} $$
On peut aussi accéder à une expression polynomiale de $A(n,18)$ en considérant la suite de séries formelles $\left( T_k(X)\right)_{k\geqslant 0}$ où $T_k(X) =\displaystyle \sum _{n=0}^{+\infty} A(n,k)X^n$. Cette dernière est en effet gouvernée par la relation de récurrence: $\forall n\geqslant 3,\quad T_n(X) = \dfrac {X^2 T_{n-1}(X) +X^3 T_{n-2}(X)}{1-X}.\:\:\:\:$ Ainsi: $\displaystyle \:A(n,0) =1 ,\:\:\: A(n,1) = n,\:\:\: A( n,2) =\binom n2 , \:\:\: $
$\displaystyle A (n,3) =2\binom {n-1}3 -\binom {n-2}3, \:\: A(n,4) = \binom {n-1}4 +\binom {n-2}4 -\binom {n-3}4,\:\:\:\displaystyle A(n,5)=3\binom{n-2}5 -2 \binom{n-3}5$.

bisam · May 2019

Bon, c'est l'occasion de faire un peu de programmation dynamique...

def a(n: int, k: int) -> int:
    """Renvoie le nombre A(n,k)  de parties à k éléments de [[1;n]] 
    qui ne contiennent pas trois entiers consécutifs."""

    if n<0 or k<0 or n<k:
        return 0

    tab = [[1] + [0]*k, [1,1] + [0]*(k-1), [1,2,1] + [0]*(k-2)]
    for i in range(3, n+1):
        l = [1]
        for v in range(1, k+1):
            c = tab[-1][v] + tab[-2][v-1]
            if v>1:
              c += tab[-3][v-2]
        l.append(c)
        tab = tab[1:] + [l]
    return tab[-1 if n>1 else n][-1]

def binom(n: int, p: int) -> int:
    """Renvoie le coefficient binomial C(n,p)"""

    num = denom = 1
    if p > n - p:
        p = n - p
    for i in range(1, p + 1):
        num *= n - i + 1
        denom *= i
    return num // denom

def p(n: int, k: int) -> float:
    """Renvoie la probabilité qu'un lot de k boules piochées parmi n 
    contienne 3 boules consécutives"""

    return 1 - a(n,k)/binom(n,k)

Je trouve $P(5000, 18) \approx 1,95 \times 10^{-4}$.

Calcul élémentaire

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 9