5.5 Les partitions d’un entier (3 cas)

Pour les trois problèmes suivants, nous allons maintenant nous intéresser aux partitions d’un entier. Attention à ne pas les confondre avec les partitions d’un ensemble, car ce sont deux notions complètement différentes. Une partition d’un entier k\displaystyle k est un ensemble non ordonné d’entiers dont la somme est k\displaystyle k. Comme pour les problèmes de composition, on peut bien entendu ajouter des contraintes sur le nombre de termes, ou bien sur les termes eux-mêmes. En utilisant la même idée que pour les problèmes de composition, ces problèmes sont équivalents à placer des boules identiques dans des urnes. Cependant, comme l’ordre n’est pas important, les urnes sont considérées comme toutes identiques. Comme nous l’avons fait dans la section précédente, nous allons commencer par donner un nom à la solution, puis étudier plus en détail ces familles de nombres par la suite.

Définition 5.5.1.

On définit les deux familles de nombres suivantes:

  1. 1.
    ​

    On définit les nombres de partitions p⁢(k,n)\displaystyle p(k,n) comme étant le nombre de façons de placer k\displaystyle k boules identiques dans n\displaystyle n urnes identiques si les urnes ne peuvent pas être vides.

  2. 2.
    ​

    On définit les nombres de partitions p⁢(k)\displaystyle p(k) comme étant le nombre de façons de placer k\displaystyle k boules identiques dans des urnes identiques si les urnes ne peuvent pas être vides.

Il faut faire attention, car ces deux familles de nombres portent le nom de « nombres de partition ». Cependant, lorsque cela est nécessaire pour les différencier, on parlera alors des nombres de partition à un paramètre ou des nombres de partition à deux paramètres.

Combien y a-t-il de façons de placer k\displaystyle k boules identiques dans n\displaystyle n urnes identiques si les urnes ne peuvent pas être vides?

D’après notre définition des nombres de partitions, ce problème est maintenant trivial. Il s’agit tout simplement de p⁢(k,n)\displaystyle p(k,n).

Combien y a-t-il de façons de placer k\displaystyle k boules identiques dans des urnes identiques si les urnes ne peuvent pas être vides?

À nouveau, ce problème est maintenant trivial. Il s’agit tout simplement de p⁢(k)\displaystyle p(k).

Combien y a-t-il de façons de placer k\displaystyle k boules identiques dans n\displaystyle n urnes identiques?

Il est maintenant facile de résoudre ce problème. Il s’agit de remarquer qu’on peut placer les k\displaystyle k boules dans une seule urne, les placer dans deux urnes sans qu’aucune des deux ne soit vide, les placer dans trois urnes sans qu’aucune ne soit vide, etc… jusqu’à un maximum de n\displaystyle n urnes. Il s’agit donc de faire la somme des nombres de partition. La solution est donc:

∑i=1np⁢(k,i)\displaystyle\sum_{i=1}^{n}p(k,i)

Une formule de récurrence pour les nombres de partitions p⁢(k,n)\displaystyle p(k,n)

Nous allons maintenant chercher une formule de récurrence pour les nombres de partitions. Normalement, c’est la méthode de l’élément distingué que nous utilisons pour ce type de récurrence, mais ici une grande difficulté se pose. Nous ne pouvons pas prendre une boule comme élément distingué, car toutes les boules sont identiques. Il est donc impossible d’en choisir une en particulier. Le même problème se pose avec les urnes, que nous ne pouvons pas utiliser non plus comme élément distingué. Nous allons donc procéder de manière un peu différente. Comme toutes les boules et toutes les urnes sont identiques, seul le nombre d’éléments contenus dans chaque urne est important. Nous pouvons donc diviser le problème en deux cas (disjoints). Dans un premier temps, nous allons considérer le cas où au moins une urne ne contient qu’une seule boule, et ensuite, nous allons traiter le cas où toutes les urnes contiennent au moins deux boules.

Cas 1: Si au moins une urne ne contient qu’une seule boule, alors on prend une boule que l’on met dans une urne, puis on met ensuite cette urne de côté. Il nous faut ensuite placer les k−1\displaystyle k-1 boules restantes dans les n−1\displaystyle n-1 urnes restantes, ce qui peut être accompli de p⁢(k−1,n−1)\displaystyle p(k-1,n-1) façons.

Cas 2: Si toutes les urnes contiennent au moins deux boules, alors on commence par placer une boule dans chaque urne. Comme toutes les urnes contiennent exactement une boule, elles sont donc toujours identiques. Ensuite, nous allons ignorer le fait qu’une boule se trouve déjà dans chaque urne et distribuer les k−n\displaystyle k-n boules restantes dans les n\displaystyle n urnes sans qu’aucune d’entre elles ne soit vide (c’est-à-dire qu’il y aura donc au moins deux boules dans chaque urne si l’on inclut la boule déjà présente). Ceci peut donc être accompli de p⁢(k−n,n)\displaystyle p(k-n,n) façons.

En combinant les deux cas précédents, on obtient donc la récurrence suivante pour les nombres de partitions :

p⁢(k,n)=p⁢(k−1,n−1)+p⁢(k−n,n)\displaystyle p(k,n)=p(k-1,n-1)+p(k-n,n)

Maintenant, pour pouvoir utiliser cette expression, il nous faut déterminer des valeurs initiales. Pour ce faire, il est facile de voir que:

p⁢(k⁢,1)=1,p⁢(k,k)=1 et p⁢(k,n)=0⁢ si ⁢k<n\displaystyle p(k,1)=1,\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ p(k,k)=1\leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \textrm{ et }\leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ p(k,n)=0\textrm% { si }k<n

Remarquez que la dernière contrainte est nécessaire, car dans la récurrence, nous avons besoin d’évaluer p⁢(k−n,n)\displaystyle p(k-n,n). Il devient alors tout à fait possible que k−n\displaystyle k-n soit plus petit que n\displaystyle n, ce qui causerait un problème avec nos valeurs initiales. À partir de ces informations, il nous est maintenant possible d’évaluer la valeur de tous les nombres de partition p⁢(k,n)\displaystyle p(k,n). Remarquez enfin que, bien que travailler directement avec cette récurrence puisse sembler long et pénible, il s’agit de notre meilleure option. Aucune formule explicite simple n’est connue pour les nombres de partitions. Pour ce qui est d’une fonction génératrice, il est possible d’en trouver une, mais elle dépasse le niveau de difficulté du cours.

Nous allons maintenant regarder rapidement un exemple de calcul des nombres de partitions. Nous allons utiliser comme exemple le nombre p⁢(5,3)\displaystyle p(5,3).

p⁢(5,3)\displaystyle\displaystyle p(5,3) =\displaystyle\displaystyle= p⁢(4,2)+p⁢(2,3)\displaystyle\displaystyle p(4,2)+p(2,3)
=\displaystyle\displaystyle= p⁢(3,1)+p⁢(2,2)+0\displaystyle\displaystyle p(3,1)+p(2,2)+0
=\displaystyle\displaystyle= 1+1=2\displaystyle\displaystyle 1+1=2

Comme le nombre de possibilités est très petit, il est intéressant de comparer notre réponse avec ce que donnerait une simple énumération de tous les cas. Si l’on souhaite distribuer 5\displaystyle 5 boules identiques dans 3\displaystyle 3 urnes identiques sans que les urnes ne soient vides, alors on peut soit mettre deux boules dans deux urnes et une seule dans la troisième urne, soit placer 3\displaystyle 3 boules dans une urne et une seule boule dans les deux autres. Ce qui peut être visualisé comme suit:

Cas 1: ∙∙∙∙∙\displaystyle\textrm{Cas 1: \leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ }\bullet\bullet% \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \bullet\bullet\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \bullet
Cas 2: ∙∙∙∙∙\displaystyle\textrm{Cas 2: \leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ }\bullet\bullet% \bullet\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \bullet\leavevmode\nobreak\ % \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode% \nobreak\ \bullet

Cet exemple peut donner l’impression que le calcul des nombres de partitions est particulièrement simple, mais la réalité est en fait différente. La méthode elle même n’est pas très compliquée, mais le calcul peut devenir rapidement très, très long à la main. Il devient donc presque essentiel d’utiliser Python pour les évaluer.

Listing 27: Nombres de partition à deux paramètres
⬇

                1
                
                
                
              from sympy import *


                2
                
                
                
              from pandas import *


                3
                
                
                
              init_printing()


                4
                
                
                
              


                5
                
                
                
              def p(k,n):


                6
                
                
                
                  if n == 1:


                7
                
                
                
                      return 1


                8
                
                
                
                  if n == k:


                9
                
                
                
                      return 1


                10
                
                
                
                  if k < n:


                11
                
                
                
                      return 0


                12
                
                
                
                  else:


                13
                
                
                
                      return p(k-1,n-1) + p(k-n,n)


                14
                
                
                
              


                15
                
                
                
              A = []


                16
                
                
                
              for k in range(1,11):


                17
                
                
                
                  ligne = [p(k,n) for n in range(1,11)]


                18
                
                
                
                  A.append(ligne)


                19
                
                
                
              tableau = DataFrame(A)


                20
                
                
                
              tableau.index = [i for i in range(1,11)]


                21
                
                
                
              tableau.columns = [i for i in range(1,11)]


                22
                
                
                
              tableau

Nombres de partition à deux paramètres

k\n\displaystyle k\backslash n 1 2 3 4 5 6 7 8 9 10
1 1 0 0 0 0 0 0 0 0 0
2 1 1 0 0 0 0 0 0 0 0
3 1 1 1 0 0 0 0 0 0 0
4 1 2 1 1 0 0 0 0 0 0
5 1 2 2 1 1 0 0 0 0 0
6 1 3 3 2 1 1 0 0 0 0
7 1 3 4 3 2 1 1 0 0 0
8 1 4 5 5 3 2 1 1 0 0
9 1 4 7 6 5 3 2 1 1 0
10 1 5 8 9 7 5 3 2 1 1

Les nombres de partitions p⁢(k)\displaystyle p(k)

On peut calculer facilement les nombres de partition à un seul paramètre à partir des nombres de partitions à deux paramètres. En effet, si l’on veut distribuer k\displaystyle k boules identiques dans des urnes non vides, on peut les placer dans une seule urne, les placer dans deux urnes sans qu’aucune ne soit vide, etc. Au maximum, nous aurons besoin de k\displaystyle k urnes pour placer toutes les boules, car les urnes ne peuvent pas être vides par hypothèse. On a donc:

p⁢(k)=∑i=1kp⁢(k,i),∀k≥1\displaystyle p(k)=\sum_{i=1}^{k}p(k,i),\leavevmode\nobreak\ \leavevmode% \nobreak\ \leavevmode\nobreak\ \forall k\geq 1

Le cas particulier où k=0\displaystyle k=0 est défini comme étant p⁢(0)=1\displaystyle p(0)=1. Nous allons maintenant chercher une fonction génératrice pour les nombres de partitions. Pour ce faire, il s’agit de remarquer que pour partitionner un nombre k\displaystyle k, on peut d’abord choisir le nombre de 1\displaystyle 1 que l’on souhaite, puis le nombre de 2\displaystyle 2, puis de 3\displaystyle 3, etc…. Ceci nous amène donc à affirmer que:

∑k=0∞p⁢(k)⁢xk\displaystyle\displaystyle\sum_{k=0}^{\infty}p(k)x^{k} =\displaystyle\displaystyle= (1+x+x2+x3+x4+….)(1+x2+x4+x6+x8+…)(1+x3+x6+x9+x12+…)…..\displaystyle\displaystyle(1+x+x^{2}+x^{3}+x^{4}+....)(1+x^{2}+x^{4}+x^{6}+x^{% 8}+...)(1+x^{3}+x^{6}+x^{9}+x^{12}+...).....
=\displaystyle\displaystyle= 11−x⋅11−x2⋅11−x3⋅…\displaystyle\displaystyle\frac{1}{1-x}\cdot\frac{1}{1-x^{2}}\cdot\frac{1}{1-x% ^{3}}\cdot...
=\displaystyle\displaystyle= ∏i=1∞11−xi\displaystyle\displaystyle\prod_{i=1}^{\infty}\frac{1}{1-x^{i}}

Il existe aussi une récurrence permettant de calculer les nombres de partition à un paramètre. Il s’agit du théorème des nombres pentagonaux. Cette approche est de loin la plus efficace pour les calculer, mais elle dépasse malheureusement le niveau de notre cours.

Listing 28: Nombres de partition à deux paramètres
⬇

                1
                
                
                
              from sympy import *


                2
                
                
                
              from pandas import *


                3
                
                
                
              init_printing()


                4
                
                
                
              


                5
                
                
                
              def p(k,n):


                6
                
                
                
                  if n == 1:


                7
                
                
                
                      return 1


                8
                
                
                
                  if n == k:


                9
                
                
                
                      return 1


                10
                
                
                
                  if k < n:


                11
                
                
                
                      return 0


                12
                
                
                
                  else:


                13
                
                
                
                      return p(k-1,n-1) + p(k-n,n)


                14
                
                
                
              


                15
                
                
                
              def partition(k):


                16
                
                
                
                  return sum([p(k,n) for n in range(1,k+1)])


                17
                
                
                
              


                18
                
                
                
              tableau = DataFrame([[partition(k) for k in range(1,11)]])


                19
                
                
                
              tableau.columns = [k for k in range(1,11)]


                20
                
                
                
              tableau.index = ["Partition"]


                21
                
                
                
              tableau

Nombres de partition à un paramètre

k\displaystyle k 1 2 3 4 5 6 7 8 9 10
p⁢(k)\displaystyle p(k) 1 2 3 5 7 11 15 22 30 42