Étapes d'analyse
Transformation du problème
Le nombre de partitions d'un entier naturel p, en au plus q parties. Ce problème peut être présenté comme le problème de répartition de p billes, en au plus q tas indifférenciés.
Exemple : Répartir 5 billes, en au plus 3 tas.
Les possibilités sont 5, 4+1, 3+2, 3+1+1, 2+2+1. Nous avons 1 répartition en 1 tas, 2 répartitions en 2 tas et 2 répartitions en 3 tas. Le dénombrement est donc de 5. On notera d(5,3)=5.
Méthode : • La décomposition
Les cas simples :
Si p=0, alors il n'y a qu'une répartition, en au plus q tas, à savoir q tas vides. On a donc d(0,q)=1.
Il n'y a pas de répartition de p billes (avec p>0), en au plus 0 tas, donc d(p+1,0)= 0.
Un cas particulier :
Si p<q, il n'y a pas de répartition de p billes en exactement q tas, donc le nombre de répartitions de p, en au plus q tas, est le nombre de partitions de p billes, en au plus p tas, ce qui s'écrit : si p<q alors d(p,q)= d(p,p).
Le cas général :
On voit facilement que le nombre de répartitions de p billes, en au plus q tas, est le nombre de répartitions de p billes en exactement q tas (dx(p, q)), plus le nombre de partitions de p billes, en au plus q-1 tas. Donc :
d(p,q) = dx(p,q) + d(p,q-1).
Or, si la répartition a exactement q tas, cela veut dire que tous ces tas comprennent un nombre positif de billes. On peut donc leur en retirer une. Si on en retire une à chaque tas, on obtient une répartition de p-q, en au plus q tas, d'où :
dx(p,q) = d(p-q, q).
Et finalement :
d(p,q) = d(p-q,q) + d(p,q-1).
Autrement dit, si p≥q, le nombre de répartitions de p billes, en au plus q tas, est le nombre de répartitions de p-q billes, en au plus q tas, plus le nombre de partitions de p billes, en au plus q-1 tas.
On a bien un énoncé récursif.