3.5 Le problème du Mississippi

Nous allons maintenant nous pencher sur la question de savoir de combien de façons différentes on peut ordonner les lettres du mot MISSISSIPPI. Comme le mot contient $\displaystyle 11$ lettres, à première vue, la solution semble être $\displaystyle 11!$ . Le problème ici est que plusieurs lettres sont identiques ; nous avons donc compté plusieurs configurations deux fois (ou plus). Il nous faut donc appliquer le principe d’équivalence. Pour ce faire, commençons par établir un tableau indiquant la fréquence de chacune des lettres.

Lettre	Fréquence
M	$\displaystyle 1$
I	$\displaystyle 4$
S	$\displaystyle 4$
P	$\displaystyle 2$
Total	$\displaystyle 11$

Comme les $\displaystyle 4$ I peuvent être permutés de $\displaystyle 4!$ façon, les $\displaystyle 4$ S peuvent être permutés de $\displaystyle 4!$ façons, et les deux P peuvent être permutés de $\displaystyle 2$ façons, on a donc que chacune des configurations donne lieu à $\displaystyle 4!\cdot 4!\cdot 2=1152$ configurations équivalentes. Le principe d’équivalence nous indique donc que le nombre de configurations est donné par:

\displaystyle\frac{11!}{4!\cdot 4!\cdot 2}=\frac{39\leavevmode\nobreak\ 916% \leavevmode\nobreak\ 800}{1152}=34\leavevmode\nobreak\ 650\leavevmode\nobreak% \ \textrm{mots}

Le problème du MISSISSIPPI peut facilement être généralisé à la question de savoir de combien de façons différentes peut-on ordonner $\displaystyle n$ objets si parmi les $\displaystyle n$ objets il y a $\displaystyle n_{1}$ objets de type $\displaystyle 1$ , $\displaystyle n_{2}$ objets de type $\displaystyle 2$ , $\displaystyle n_{3}$ objets de type $\displaystyle 3$ , …, $\displaystyle n_{k}$ objets de type $\displaystyle k$ . La solution de ce problème porte le nom de coefficient multinomial. En utilisant la même méthode que précédemment, ce dernier nous est donné par la formule suivante:

\displaystyle\frac{(n_{1}+n_{2}+n_{3}+...+n_{k})!}{n_{1}!\cdot n_{2}!\cdot n_{% 3}!\cdot...\cdot n_{k}!}

Dans le problème précédent, nous nous sommes intéressés à trouver le nombre de mots que nous pouvons former en utilisant toutes les lettres du mot MISSISSIPPI. Nous allons maintenant regarder comment trouver le nombre de mots que nous pouvons former en utilisant seulement $\displaystyle k$ des $\displaystyle 11$ lettres de ce même mot. Bien que le problème soit très similaire au précédent, cette fois nous n’avons pas d’autre choix que d’utiliser les fonctions génératrices exponentielles. Comme nous avons un $\displaystyle M$ , quatre $\displaystyle I$ , quatre $\displaystyle S$ et deux $\displaystyle P$ , on obtient donc la fonction génératrice suivante:

			$\displaystyle\displaystyle\left(\sum_{n=0}^{1}\frac{x^{n}}{n!}\right)\left(% \sum_{n=0}^{4}\frac{x^{n}}{n!}\right)\left(\sum_{n=0}^{4}\frac{x^{n}}{n!}% \right)\left(\sum_{n=0}^{2}\frac{x^{n}}{n!}\right)$
		$\displaystyle\displaystyle=$	$\displaystyle\displaystyle\left(1+\frac{x}{1!}\right)\left(1+\frac{x^{1}}{1!}+% \frac{x^{2}}{2!}+\frac{x^{3}}{3!}+\frac{x^{4}}{4!}\right)\left(1+\frac{x^{1}}{% 1!}+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+\frac{x^{4}}{4!}\right)\left(1+\frac{x^{% 1}}{1!}+\frac{x^{2}}{2!}\right)$
		$\displaystyle\displaystyle=$	$\displaystyle\displaystyle 34650\frac{x^{11}}{11!}+34650\frac{x^{10}}{10!}+214% 20\frac{x^{9}}{9!}+10430\frac{x^{8}}{8!}+4340\frac{x^{7}}{7!}+1610\frac{x^{6}}% {6!}+550\frac{x^{5}}{5!}+176\frac{x^{4}}{4!}+53\frac{x^{3}}{3!}+...$
			$\displaystyle\displaystyle...+15\frac{x^{2}}{2!}+4\frac{x^{1}}{1!}+1$

Comme nous l’avons déjà trouvé précédemment, nous avons $\displaystyle 34\leavevmode\nobreak\ 650$ mots de $\displaystyle 11$ lettres que nous pouvons former en utilisant (toutes) les lettres du mot MISSISSIPPI. Cette nouvelle approche nous permet cependant d’aller beaucoup plus loin. Par exemple, basé sur notre calcul ci-dessus, nous avons $\displaystyle 550$ mots de $\displaystyle 5$ lettres que nous pouvons former en utilisant les lettres du mot MISSISSIPPI. Le code Python ci-dessous nous permet de résoudre automatiquement le problème.

Listing 23: Problème du MISSISSIPPI

⬇


              1
              
              
              
            from sympy import *


              2
              
              
              
            from pandas import *


              3
              
              
              
            init_printing()


              4
              
              
              
            


              5
              
              
              
            x = Symbol(’x’)


              6
              
              
              
            p1 = sum([x**i/factorial(i) for i in range(0,2)])


              7
              
              
              
            p2 = sum([x**i/factorial(i) for i in range(0,5)])


              8
              
              
              
            p3 = sum([x**i/factorial(i) for i in range(0,5)])


              9
              
              
              
            p4 = sum([x**i/factorial(i) for i in range(0,3)])


              10
              
              
              
            polynome = Poly(p1*p2*p3*p4).all_coeffs()


              11
              
              
              
            polynome.reverse()


              12
              
              
              
            for i in range(0,len(polynome)):


              13
              
              
              
                polynome[i] = polynome[i] * factorial(i)


              14
              
              
              
            tableau = DataFrame([polynome])


              15
              
              
              
            tableau.index = ["Valeurs"]


              16
              
              
              
            tableau

Nombre de lettre	0	1	2	3	4	5	6	7	8	9	10	11
Nombre de mots	1	4	15	53	176	550	1610	4340	10430	21420	34650	34650