Analyse combinatoire et dénombrement

Le coefficient multinomial :

Nous avons vu ce qu’était le coefficient binomial, à présent, nous allons étendre la formule au cas général.

On va tout de suite prendre un exemple concret pour savoir de quoi nous parlons.
Imaginons que nous ayons un groupe de 10 militaires. Parmi ce groupe de militaires, on veut former 5 patrouilles qui patrouillent les rues, deux qui s’occupent des papiers, et 3 qui iront au restaurant…

De combien de façon peut on faire cela ?

\begin{pmatrix}10 \\ 5 \end{pmatrix} \cdot \begin{pmatrix}10-5 \\ 2 \end{pmatrix} \cdot \begin{pmatrix}10-5-2 \\ 3 \end{pmatrix}=\displaystyle{\frac{10{!}}{5{!}5{!}} \cdot \frac{5{!}}{2{!}3{!}} \cdot \frac{3{!}}{3{!}0{!}}=\frac{10{!}}{5{!}2{!}3{!}}=2520}

Nous avons utilisé la règle multiplicative. Dans le premier terme, on a donc considéré les 5 patrouilles parmi les 10, dans le deuxième, on a retiré 5 patrouilles, puisqu’on considère que 5 patrouilles sont déjà dans les rues. Dans le troisième élément, on retire évidemment les 5 patrouilles dans la rue, ainsi que les deux patrouilles que nous avons déjà choisi s’occupant des papiers.

En fait, ceci revient à compter le nombre de permutation distinctes du mot « MMMMMPPRRR ».

On peut constater quelque chose. En effet, on voit que dans l’avant dernier terme, on se retrouve avec des factorielles dont la somme est égale à n, ceci n’est pas un hasard, et d’ailleurs, grâce à cela, on va pouvoir construire la définition qui suit.

Soit, k_1,k_2,...,k_r, des entiers positifs, et soit k_1+k_2+...+k_r=n, alors :

\displaystyle{\begin{pmatrix} n \\ k_1,k_2,...,k_r \end{pmatrix}=\frac{n{!}}{k_1{!} \cdot k_2{!} \cdot ... \cdot k_r{!}}=\begin{pmatrix} n \\ k_1 \end{pmatrix} \cdot \begin{pmatrix} n-k_1 \\ k_2 \end{pmatrix} \cdot \begin{pmatrix} n-k_1-k_2 \\ k_3 \end{pmatrix} \cdot ... \cdot \begin{pmatrix} n-\Big{(}\sum_{i=1}^{r-i} k_i \Big{)} \\ k_r \end{pmatrix}}

Ceci est appelé le coefficient multinomial. En réalité, le coefficient binomial n’est qu’un cas particulier du coefficient multinomial.
En effet, lorsque r=2, nous sommes exactement dans le cas du coefficient binomial, qui, si on se base sur la formule que l’on vient d’écrire, se défini ainsi :

\displaystyle{\begin{pmatrix} n \\ k \end{pmatrix}= \begin{pmatrix} n \\ k,n-k \end{pmatrix}=\frac{n{!}}{k{!}(n-k){!}}}

On se rend bien compte que si on fixe n-k=k_2, on a bien la même écriture que pour le coefficient multinomial lorsque r=2, et donc, ceci est bien un cas particulier de ce dernier.

Publicité
Pages : 1 2 3 4 5 6 7