Combinatoire

\[ \Omega \text{ : univers} \quad\supseteq\quad A \text{ : événement} \quad\supseteq\quad \omega \text{ : éventualité } \] \[ \varnothing \text{ : évén. impossible} \]
Expérience aléatoire \[ \begin{aligned} & \mathbb{P} \Bigg( \bigcup_{n \in \mathbb{N}} A_n \Bigg) && = && \sum_{n = 0}^{+ \infty} \Big( \mathbb{P} (A_n) \Big) \\[3em] & \mathbb{P} \Bigg( \bigcap_{n \in \mathbb{N}} A_n \Bigg) && = && \prod_{n = 0}^{+ \infty} \mathbb{P}(A_n) \end{aligned} \] \[ A_i \cup A_j = \varnothing \]

Formules

Coefficient biniomial \[ C_k^n = \binom{n}{k} = \frac{n!}{k!(n-k)!} \]
par extension... \[ \overline{C}_k^n = \binom{n + k - 1}{k} = \frac{(n + k - 1)!}{k!(n - 1)!} \]
Partitions d'entiers avec répétition \[ x_1 + x_2 + ... + x_n = k \quad ; \quad x_i \ge 0 \quad \Rightarrow \overline{C}_k^n \text{ solutions} \]
Coefficient multiniomial \[ \binom{n}{k_1, k_2, ..., k_n} = \frac{n!}{k_1! ~ k_2! ... k_n!} \]
Binôme de Newton \[ (x + y)^n = \sum_{k=0}^n \binom{a}{b} x^{n-k} y^k \\[2em] \] Exemple \[ (x + y)^5 \quad = \quad 1x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3 + 5xy^4 + 1y^5 \]
Nombre de Stirling de première espèce \[ \left[ \begin{matrix} n+1 \\ k \end{matrix} \right] = n \left[ \begin{matrix} n \\ k \end{matrix} \right] + \left[ \begin{matrix} n \\ k-1 \end{matrix} \right] \]
Nombre de Stirling de deuxième espèce \[ \left\{ \begin{matrix} n+1 \\ k \end{matrix} \right\} = k \left\{ \begin{matrix} n \\ k \end{matrix} \right\} + \left\{ \begin{matrix} n \\ k-1 \end{matrix} \right\} \]
Nombre de Bell \[ B_n = \sum_{k=1}^n \left\{ \begin{matrix} n \\ k \end{matrix} \right\} \quad\quad\quad B_{n+1} = \sum_{k=0}^n \binom{n}{k} B_k \]
Formules générales Combinatoire
Arrangements \[ \sum_{\substack{ x_1 + x_2 + ... + x_{|\mathbf{o}|} = e \\[0.2em] 0 ~\leq~ x_i ~\leq~ o_i }} ~~ \frac{e!}{\prod_{i=1}^{|\mathbf{o}|} x_i!} \]
Combinaisons \[ [z^e] \prod_{i=1}^{n} \sum_{j=0}^{o_i} z^j \]
\( \mathbf{o} \) est le vecteur des objets, chaque entier \( o_i \) représente le nombre d'objets indiscernables à disposition
\( e \) est le nombre d'emplacements, le nombre d'objet à prendre dans \( \mathbf{o} \)
\( |\mathbf{o}| \) est le cardinal \( \mathbf{o} \), soit de le nombre d'objets différents
\( \mathbf{1}^\top \mathbf{x} \) est la somme des entiers de \( \mathbf{o} \), soit le nombre d'objets total à disposition, tous types confondus
\( \mathbf{x} \) représente "un échantillon" de \( \mathbf{o} \)

Classification des situations combinatoires

vecteur des objets \( \mathbf{o} \)
nombre d'objets total \( o = \mathbf{o}^\top 1 \)
nombre de types d'objets \( t = |\mathbf{o}| \)
objets tous différents \[ o = t \] certains objets répétés \[ o \gt t \] objets identiques illimités \[ \gray{ o_i = \infty \Rightarrow } \\ o_i = e \]
On les prend tous On les arrange tous On les prend tous On les arrange tous On les prend tous On les arrange tous
\[ \gray{ 1 } \] \[ o! \] \[ \gray{ 1 } \] \[ \frac{o!}{o_1!~o_2!~...} \] \[ \gray{ \infty } \] \[ \gray{ \infty } \]
On en prend \(e\) On en arrange \(e\) On en prend \(e\) On en arrange \(e\) On en prend \(e\) On en arrange \(e\)
\[ \frac{t!}{e!(t - e)!} \] \[ \frac{t!}{(t - e)!} \] \[ * \] \[ * \] \[ \frac{(t + e - 1)!}{e!(t - 1)!} \] \[ t^e \]

Calculette combinatoire

objets de objets de valeur
emplacements
Extraction du coefficient multinomial

La formule classique :

\[ \text{Coeff}(\mathbf{o},e) = [z^e] \prod_{i=1}^{n} \frac{1-z^{o_i+1}}{1-z} \]

Je préfère celle-ci :

\[ \text{Coeff}(\mathbf{o},e) = [z^e] \prod_{i=1}^{n} \sum_{j=0}^{o_i} z^j \]

Méthode rapide (convolution)

Exemple avec \( \mathbf{o} = \{ 5, 2, 1, 3 \}, e = 5 \).

On aurait alors

\( (1 + z + z^2 + z^3 + z^4 + z^5) (1 + z + z^2) (1 + z) (1 + z + z^2 + z^3) \)

Qu'on va reprsenter comme ça : \( (111111)(111)(11)(1111) \) 

(1 1 1 1 1 1)(1 1 1)
1   1   1   1   1   1
    1   1   1   1   1   1
        1   1   1   1   1   1
1   2   3   3   3   3   2   1

(1 2 3 3 3 3 2 1)(1 1)
1   2   3   3   3   3   2   1
    1   2   3   3   3   3   2   1
1   3   5   6   6   6   5   3   1

(1 3 5 6 6 6 5 3 1)(1 1 1 1)
1   3   5   6   6   6   5   3   1
    1   3   5   6   6   6   5   3   1
        1   3   5   6   6   6   5   3   1
            1   3   5   6   6   6   5   3   1
1   4   9   15  20  23  23  20  15  9   4   1
                    ^^
0   1   2   3   4   5   6   7   8   9   10  11

\( \text{Coeff}(\mathbf{o},e) = 23\)

Exercices

3D6 = 9

On tire 3 dés et on veut faire 9, on a donc :

\[ \begin{aligned} & dé_1 + dé_2 + dé_3 = 9 \quad && 1 \le dé \le 6 \quad && dé \ge 1 \\ & && && \orange{dé \ge 0} && \quad \Leftarrow \text{ mais c'est ça qu'on voudrait}\\ & o_1 + o_2 + o_3 = 6 && 0 \le o \le 5 \quad && o \ge 0 && \quad \Leftarrow \quad o = dé - 1 \\[1em] \end{aligned} \]

On peut alors poser :

\[ \overline{C}_6^3 = \frac{(6 + 3 - 1)!}{3!(6 - 1)!} = \underline{\underline{56}} \]

3D6 = 15

3 méthodes

Hardcore

On tire 3 dés et on veut faire 15, on a donc :

\[ \begin{aligned} & dé_1 + dé_2 + dé_3 = 15 \quad && 1 \le dé \le 6 \quad && dé \ge 1 \\ & && && \orange{dé \ge 0} && \quad \Leftarrow \text{ mais c'est ça qu'on voudrait} \\ & o_1 + o_2 + o_3 = 12 && 0 \le o \le 5 \quad && o \ge 0 && \quad \Leftarrow \quad o = dé - 1 \\[1em] \end{aligned} \]

On peut poser :

\[ \begin{aligned} & \overline{C}_{3}^{12} = \frac{(3 + 12 - 1)!}{12!(3 - 1)!} = 91 \\ \end{aligned} \]

Mais problème : y a des solutions comme 1 + 1 + 12 et ça existe pas comme face de dé, 12...

On peut dresser la liste des solutions de manières ensembliste :

= - - - + + + -
Ce qui correspond à : \[ |S| = |\Omega| - |A_1| - |A_2| - |A_3| + |A \cap B| + |B \cap C| + |C \cap A| + |A \cap B \cap C| \]
est l'ensemble de toutes les solutions (incluant les solutions impossibles comme 1 + 1 + 12) et dont le cardinal précédemment calculé vaut 91.
est l'ensemble des solutions possibles (sans dés dont une face vaut plus que 6).
sont les ensembles de solutions avec au moins un dé qui vaut plus que 6, respectivement pour le dé 1, 2 et 3.
sont les ensembles de solutions avec au moins 2 dés qui valent plus que 6.
est l'ensemble avec les solutions où les 3 dés valent plus que 6. Pour ce dernier, on sait qu'il est vide car on aurait un résultat plus grand que 15 et on est dans un sous-ensemble de solutions où la somme vaut 15.

Calculer le cardinal des 3 premiers ensembles A :

\[ \begin{aligned} & \text{remarque :} \quad |A_1| = |A_2| = |A_3| \\ & dé_1 + dé_2 + dé_3 + 6 = 15 \quad && 1 \le dé \le 6 \quad && dé \ge 1 \\ & && && \orange{dé \ge 0} && \quad \Leftarrow \\ & o_1 + o_2 + o_3 + 6 = 12 && 0 \le o \le 5 \quad && o \ge 0 \\ & o_1 + o_2 + o_3 = 6 && 0 \le o \le 5 \quad && o \ge 0 \\ \end{aligned} \]

On peut poser :

\[ \begin{aligned} & |A_1| = \overline{C}_{3}^{6} = \frac{(3 + 6 - 1)!}{6!(3 - 1)!} = 28 \\ \end{aligned} \]

Calculer le cardinal des 3 ensembles suivants :

\[ \begin{aligned} & \text{même remarque :} \quad |A \cap B| = |B \cap C| = |C \cap A| \\ & dé_1 + dé_2 + dé_3 + 6 + 6 = 15 \quad && 1 \le dé \le 6 \quad && dé \ge 1 \\ & && && \orange{dé \ge 0} && \quad \Leftarrow \\ & o_1 + o_2 + o_3 + 6 + 6 = 12 && 0 \le o \le 5 \quad && o \ge 0 \\ & o_1 + o_2 + o_3 = 0 && 0 \le o \le 5 \quad && o \ge 0 \\ \end{aligned} \]

On peut poser :

\[ \begin{aligned} & |A \cap B| = \overline{C}_{3}^{0} = 1 \\ \end{aligned} \]
\[ \begin{aligned} & |\Omega| - |A_1| - |A_2| - |A_3| + |A \cap B| + |B \cap C| + |C \cap A| + |A \cap B \cap C| \\[1em] & \text{devient :} \\[1em] & 91 - 28 - 28 - 28 + 1 + 1 + 1 - 0 \quad = \quad \underline{\underline{10}} \end{aligned} \]

Facile

Il n'y a que ces 3 manières d'obtenir 15 avec 3D6:
  • 6 + 6 + 3, les permutations donnent 3 arrangements
  • 6 + 5 + 4, les permutations donnent 6 arrangements
  • 5 + 5 + 5, un seul arrangement
3 + 6 + 1 = 10

Faussement simple

(car on tombe vite dans un piège ou deux...)

L'idée est de voir qu'il y a autant de chances de faire 15 que 6.
Comment ce fait-ce ?

Avec 2D6, c'est plus probable de faire 7 (valeur médiane) que 12 ou 2.
Et les chances de faire 12 ou 2 sont les mêmes.
Par extrapolation : la probabilité de 3 = probabilité de 11, p de 4 = p de 10, etc.
On peut dresser le tableau :
2 3 4 5 6 7 8 9 10 11 12

De la même manière, pour 3D6 on a :
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 16 17 18
probabilité de 15 = probabilité de 6 car à la même distance du centre
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 16 17 18
Donc on va calculer la probabilité pour 6 vu que c'est la même que pour 15 :

\[ \begin{aligned} & dé_1 + dé_2 + dé_3 = 6 && 1 \leq dé_i \leq 6 \\[1em] & x_1 + x_2 + x_3 = 3 && 0 \leq x_i \leq 5 \\[1em] \end{aligned} \] Les combinaisons sont alors au nombre de \( \overline{C}_3^3 \) \[ \overline{C}_3^3 ~~=~~ C_3^{3 + 3 - 1} ~~=~~ C_3^5 ~~=~~ \frac{5!}{3!(5-3)!} ~~=~~ \frac{5!}{3!2!} ~~=~~ \frac{4 \cdot 5}{2} ~~=~~ \underline{\underline{10}} \]

Bonus : probabilité

\[ \begin{aligned} & \mathbb{P} = \frac{10}{6^3} \simeq 4,63 \% \end{aligned} \]

5 koalas 3 éléphants

Les 4 koalas sont allés chercher des fruits pour en donner un à chacun des 3 éléphants.

Chacun des koala a une seule sorte de fruit en une quantité qui lui est propre.

La répartition est la suivante :

koala fruit(s)
Amandine 5 bananes
Thor 3 cerise
Nikita 1 orange
Will Smith 1 tomate

Note : Amandine a 5 bananes, mais elle ne pourra jamais en donner plus que 3, vu qu'il y a 3 éléphants et que chacun n'aura droit qu'à un seul fruit.
De manière générale : on plafonne les éléments du vecteur à \( e \). Donc \( \{ 5,3,1,1 \} \) devient \( \{ 3,3,1,1 \} \)

La formule est \[ \sum_{\substack{ x_1 + x_2 + x_3 + x_4 ~=~ 3 \\[0.5em] 0 ~\leq~ x_i ~\leq~ o_i }} \frac{3!}{\prod_{i=1}^4 x_i!} \quad;\quad \mathbf{o} = \{ 3,3,1,1 \} \quad;\quad e = 3 \]

On cherche les types partitions ; les manières de partitionner le don de 3 fruits par les 4 koalas.
Il peut être trouvé avec la formule des partitions avec le plus grand nombre du vecteur ( \( p(o_{max}) \), ici \( p(3) = 3 \), mais c'est vite des formules compliquées).
Ici on les pose (les trois) à la main.

Types \[ p(3) = 3 \] Un koala donne ses trois fruits : \[ 3,0,0,0 \] Un koala donne deux fruits et un autre un fruit : \[ 2,1,0,0 \] Trois koalas donnent un fruit chacun : \[ 1,1,1,0 \]
Combinaisons possibles \[ 20 \] Combinaisons valides \[ \text{Coeff}(\{ 3,3,1,1 \}, 3) \\[.5em] = 12 \] \[ 3,0,0,0 \\[.5em] 0,3,0,0 \gray{ \\[.5em] \sout{0,0,3,0}\\[.5em] \sout{0,0,0,3} } \] \[ \begin{array}{l} 2,1,0,0 \\[.5em] 2,0,1,0 \\[.5em] 2,0,0,1 \\[1em] 1,2,0,0 \\[.5em] 0,2,1,0 \\[.5em] 0,2,0,1 \\[1em] \end{array} \gray{ \begin{array}{l} \sout{ 1,0,2,0 } \\[.5em] \sout{ 0,1,2,0 } \\[.5em] \sout{ 0,0,2,1 } \\[1em] \sout{ 1,0,0,2 } \\[.5em] \sout{ 0,1,0,2 } \\[.5em] \sout{ 0,0,1,2 } \\[1em] \end{array} } \] \[ 1,1,1,0 \\[.5em] 1,1,0,1 \\[.5em] 1,0,1,1 \\[.5em] 0,1,1,1 \]
Arrangements \[ 2 \frac{3!}{3!~0!~0!~0!} = 2 \] \[ 6 \frac{3!}{2!~1!~0!~0!} = 18 \] \[ 4 \frac{3!}{1!~1!~1!~0!} = 24 \]
\[ \sum_{\substack{ x_1 + x_2 + x_3 + x_4 ~=~ 3 \\[0.5em] 0 ~\leq~ x_i ~\leq~ o_i }} \frac{3!}{\prod_{i=1}^4 x_i!} \quad=\quad 2 + 18 + 24 \quad=\quad \underline{\underline{44}} \]

Alors, c'était pas si compliqué. Le plus dur c'est surtout de faire en sorte que les koalas ne manges pas les fruits.

Prendre 4 parmi 3x3

Combien y a-t-il d'arrangements possibles de 4 lettres parmi AAABBBCCC ?

Variables (3 A, 3 B et 3 C) :

\[ \begin{aligned} & \mathbf{o} = \{ 3,3,3 \} \quad;\quad e = 4 \\[2em] \end{aligned} \]

Formule :

\[ \begin{aligned} & \sum_{ \begin{matrix} x_1 + x_2 + x_3 = 4 \\ 0 \leq x_i \leq o_i \end{matrix} } ~~~ \frac{ 4! }{ \prod_{i=1}^3 x_i! } \end{aligned} \]

Estimation de la complexité de l'exercice :

\[ \begin{aligned} & x_1 + x_2 + x_3 = 4 \quad\Rightarrow\quad \overline{C}_4^3 = 15 \\ \end{aligned} \]

Donc 15 termes (maximum) à additionner : faisable

Enumération / définition des groupes de termes :

\[ \begin{aligned} & 3,1,0 \Rightarrow 3! = 6 \quad;\quad 2,2,0 \Rightarrow \frac{3!}{2!} = 3 \quad;\quad 2,1,1 \Rightarrow \frac{3!}{2!} = 3 \\[1em] & 6 + 3 + 3 = 12 \text{ termes} \end{aligned} \]

Formule finale :

\[ \begin{aligned} & 6 \frac{4!}{3! 1! 0!} + 3 \frac{4!}{2! 2! 0!} + 3 \frac{4!}{2! 1! 1!} \quad=\quad \underline{\underline{ 78 }} \end{aligned} \]

Cadenas mode hard

La formule la plus simple c'est évidemment \( 10^3 (= 1000) \), et on va la garder sous le coude pour vérifier à la fin si on a bien le même résultat.
Mais donc ici on est en mode hard, c'est-à-dire qu'on va utiliser \[ \begin{aligned} & \sum_{ \begin{matrix} x_1 + x_2 + ... x_k = e \\ 0 \leq x_i \leq o_i \end{matrix} } ~~~ \frac{ e! }{ \prod_{i=1}^k x_i! } \end{aligned} \] et il faut bien poser le problème...

A votre avis, quelles sont les bonnes variables à poser ?

\[ \begin{aligned} & 1. && \mathbf{o} = \{ 10,10,10 \} ; && e = 3 \\[1em] & 2. && \mathbf{o} = \{ 3,3,3,3,3,3,3,3,3,3 \} ; && e = 3 \\[1em] & 3. && \mathbf{o} = \{ \infty,\infty,\infty,\infty,\infty,\infty,\infty,\infty,\infty,\infty, \} ; && e = 3 \end{aligned} \]

Pourquoi j'ai posé ces trois-cis ?

La première est une erreur qui (en tout cas chez moi) vient tout de suite de manière intuitive : on a trois chiffres qui chacun peuvent avoir 10 valeurs.

Mais c'est bien la deuxième formule qui est correcte pour exprimer le problème : on a une collection de 30 chiffres répartis en 10 catégories distinctes.

On pourrait (devrait) même prendre la troisième : on a une infinité de chiffres à disposition mais de 10 types différents.

Mais alors pourquoi la 2. et pas la 3. ?

Comment pour l'exerice des koalas : on ne pourra jamais prendre plus que 3 chiffres identiques étant donné qu'on a que trois emplacements à disposition. On va donc "clamper" les valeurs à 3.

Il y a 3 manières (Types) de prendre trois chiffres :
- 3 chiffres identiques
- 2 chiffres identiques et 1 autre
- 3 chiffres différents

\[ \begin{aligned} & \{ 3,0,0,0,0,0,0,0,0,0 \} \Rightarrow P = \frac{10!}{1!9!} && = 10 \\[1em] & \{ 2,1,0,0,0,0,0,0,0,0 \} \Rightarrow P = \frac{10!}{1!1!8!} = 9 \cdot 10 && = 90 \\[1em] & \{ 1,1,1,0,0,0,0,0,0,0 \} \Rightarrow P = \frac{10!}{3!7!} = \frac{8 \cdot 9 \cdot 10}{2 \cdot 3} && = 120 \end{aligned} \]

La formule donne donc :

\[ \begin{aligned} & 10 \frac{3!}{ 3! \gray{0!0!0!0!0!0!0!0!0!} } + 90 \frac{3!}{ 2! \gray{1!0!0!0!0!0!0!0!0!} } + 120 \frac{3!}{ \gray{1!1!1!0!0!0!0!0!0!0!} } = \\[2em] & 10 \quad+\quad 90 \cdot 3 \quad+\quad 120 \cdot 6 \quad=\quad 10 + 270 + 720 \quad=\quad \underline{\underline{1000}} \end{aligned} \]

By the way, le nombre de combinaisons totales ( \( 220 \) ) es bien donné par la somme des combinaisons ( \( 10 + 90 + 120 \) )
Vérification, prendre 3 parmis 10 avec répétition : \[ \overline{C}_{3}^{10} ~~=~~ C_{3}^{12} ~~=~~ \frac{12!}{3!9!} ~~=~~ \frac{10 ~ 11 ~ \sout{12} ~ 2}{\sout{3 ~ 2}} ~~=~~ 220 \]

Quelques triangles utiles

Pascal

1
1   1
1   2   1
1   3   3   1
1   4   6   4   1
1   5  10  10   5   1
\[ \binom{n}{k} \quad=\quad \binom{n-1}{k} + \binom{n-1}{k-1} \]

Stirling de première espèce

1
0   1
0  -1   1
0   2  -3   1
0  -6  11  -6   1
0  24 -50  35 -10   1
\[ s(n,k) \quad=\quad (n-1)s(n-1,k) + s(n-1,k-1) \]

Stirling de seconde espèce

1
1   1
1   3   1
1   7   6   1
1  15  25  10   1
1  31  90  65  15   1
\[ S(n,k) \quad=\quad kS(n-1,k) + S(n-1,k-1) \]

Partitions

1 1
2 1, 1 2
3 2, 1 1, 1, 1 3
4 3, 1 2, 2 2, 1, 1 1, 1, 1, 1 4
5 4, 1 3, 2 3, 1, 1 2, 2, 1 2, 1, 1, 1 1, 1, 1, 1, 1 7
\[ p(n) = \sum_{k=1}^{\infty} (-1)^{k+1} \left[ p \left( n - \frac{k(3k - 1)}{ 2 } \right) + p \left( n - \frac{k(3k + 1)}{ 2 } \right) \right] \]
Un truc compliqué pour faire un algo optimisé

Ici le but est de pouvoir résoudre n'importe quel problème pouvant être décrit par les variables \( \mathbf{o} \) et \( e\), ce qui en fait potentiellement une ch... beaucoup.

Plus spécifiquement, le but est de faire un algorithme qui puisse boucler sur chaque possibilité sans passer par des cas inexistants ; on souhaite seulement faire les calculs nécessaires et aucun de plus.

\[ \begin{aligned} & \mathbf{o} = \{ 3,2,1 \} \quad;\quad e = 4 \\[1em] & \sum_{\substack{ x_1 + x_2 + x_3 = 4 \\[0.2em] 0 ~\leq~ x_i ~\leq~ o_i }}~~ \frac{4!}{\prod_{i=1}^3 o_i!} \end{aligned} \]
Manières

\( |m| \leq p(o_{max}) = 3 \) 		\( P m_{max} = p(o_{max})! \) Combinaisons

\( |c| \leq \overline{C}_4^3 = \binom{4+3-1}{3} = 20 \)

\( |c| \leq |m| \cdot |m|! = 18 \)

\( bN(\mathbf{o}) = [z^4] \prod_{i=1}^{|\mathbf{o}|} \frac{1-z^{o_i+1}}{1-z} = 5 \)

\( |c| = \sum_{i=1}^{|m|} | P^* m_i | = 5 \)

 Arrangements

\( |a| \leq \)
\( m_1 = \{ 3,1,0 \} \)
XXXY
\( P^* m_1 = 2 \) \( c_{1_1} = 3,1,0 \)
AAAB
\( c_{1_2} = 3,1,0 \)
AAAC
AAAB AABA ABAA BAAA
AAAC AACA ACAA CAAA
\( m_2 = \{ 2,2,0 \} \)
XXYY
\( P^* m_2 = 1 \) \( c_{2_1} = 2,2,0 \)
AABB
AABB ABAB ABBA BAAB BABA BBAA
\( m_3 = \{ 2,1,1 \} \)
XXYZ
\( P^* m_3 = 2 \) \( c_{3_1} = 2,1,1 \)
AABC
\( c_{3_2} = 1,2,1 \)
ABBC
AABC AACB ABAC ABCA ACAB ACBA
BABC BACB BBAC BBCA BCAB BCBA
\( p(n) \) : partitions
\( P^* \) : permutations conditionnelles, dans cet exemple \( | P^* m_1 | = | \{ \{ 3,1,0 \}, \{ 3,0,1 \}, \sout { \{ 1,3,0 \} }, \sout {\{ 1,0,3 \} }, \sout {\{ 0,3,1 \} }, \sout {\{ 0,1,3 \} }, \} | = 2 \)