Répartition

Le problème est de répartir n objets indiscernables sur p tas, aucun tas n'étant vide et les tas identifiés A,B,C,...
On peut considérer que les n objets sont alignés, séparés par n-1 espaces donc.
Les répartir en p tas consiste ainsi à placer p-1 séparations sur ces n-1 espaces

O O O|O|O O O O|O O|O
  3   1    4     2  1

Si p = 1 la question ne se pose même pas, et le programme refuse !

Ces N répartitions sont alors listées en ordre lexicographique
1 : {1,1,1,...,1,7}
2 : {1,1,1,...,2,6}
...
N : {7,1,...,1,1,1}

Il s'agit de trouver une correspondance directe entre le rang dans la liste et la répartition {a,b,c,...}
On montre (1) que :

Rang de {a,b,c,..} = C(n-1, p-1) - (C(n-a-1,p-1) + C(n-a-b-1, p-2) + C(n-a-b-c-1, p-3) + ...)

avec C(n,m) = 0 si n<m

Annexe : démonstration

On note que le dernier tas est déterminé par la connaissance des p-1 premiers
Il suffit donc de considérer exclusivement ces p-1 premiers tas
Prenons un exemple avec 4 tas et 8 billes, soit C(7,3) = 35 cas que l'on peut encore examiner à la main :

rang  tas          intervalles       code binaire (3 bits à 1 parmi 7)

1   1+1+1+5      x|x|x|x x x x x     1110000
2   1+1+2+4      x|x|x x|x x x x     1101000
3   1+1+3+3      x|x|x x x|x x x     1100100
4   1+1+4+2      x|x|x x x x|x x     1100010
5   1+1+5+1      x|x|x x x x x|x     1100001
6   1+2+1+4      x|x x|x|x x x x     1011000
7   1+2+2+3      x|x x|x x|x x x     1010100
8   1+2+3+2      x|x x|x x x|x x     1010010
9   1+2+4+1      x|x x|x x x x|x     1010001
10  1+3+1+3      x|x x x|x|x x x     1001100
11  1+3+2+2      x|x x x|x x|x x     1001010
12  1+3+3+1      x|x x x|x x x|x     1001001
13  1+4+1+2      x|x x x x|x|x x     1000110
14  1+4+2+1      x|x x x x|x x|x     1000101
15  1+5+1+1      x|x x x x x|x|x     1000011     C(6,2) commencent par 1
----------------------------------------------------
16  2+1+1+4      x x|x|x|x x x x     0111000
17  2+1+2+3      x x|x|x x|x x x     0110100
18  2+1+3+2      x x|x|x x x|x x     0110010
19  2+1+4+1      x x|x|x x x x|x     0110001
20  2+2+1+3      x x|x x|x|x x x     0101100
21  2+2+2+2      x x|x x|x x|x x     0101010
22  2+2+3+1      x x|x x|x x x|x     0101001
23  2+3+1+2      x x|x x x|x|x x     0100110
24  2+3+2+1      x x|x x x|x x|x     0100101
25  2+4+1+1      x x|x x x x|x|x     0100011     C(5,2) commencent par 2
----------------------------------------------------
26  3+1+1+3      x x x|x|x|x x x     0011100
27  3+1+2+2      x x x|x|x x|x x     0011010
28  3+1+3+1      x x x|x|x x x|x     0011001
29  3+2+1+2      x x x|x x|x|x x     0010110
30  3+2+2+1      x x x|x x|x x|x     0010101
31  3+3+1+1      x x x|x x x|x|x     0010011     C(4,2) commencent par 3
----------------------------------------------------
32  4+1+1+2      x x x x|x|x|x x     0001110
33  4+1+2+1      x x x x|x|x x|x     0001101
34  4+2+1+1      x x x x|x x|x|x     0001011     C(3,2) commencent par 4
----------------------------------------------------
35  5+1+1+1      x x x x x|x|x|x     0000111     C(2,2) commencent par 5

Si on compte le nombre de configurations qui commencent par a, c'est le nombre de configurations de n-a billes sur p-1 tas, c'est à dire C(n-a-1, p-2)

Le rang (à partir de la fin) de la dernière de la série des { a, ...} est donc C(p-2, p-2) + C(p-1, p-2) + ... C(n-a-2, p-2)
C'est à dire la somme de tous les nombres de config pour a+1, a+2 ... n-p-1
Cette somme de combinaisons s'avère (récurrence sur les C(n, m)) être C(n-a-1, p-1)

Par exemple C(2,2) + C(3,2) + C(4,2) = C(5,3)
Sur un triangle de Pascal des C(k,m) on a :

k\m   0   1   2   3   4   5   6
0     1
1     1   1
2     1   2  (1)
3     1   3  (3)  1
4     1   4  (6)  4   1
5     1   5  10 (10)  5   1
6     1   6  15  20   15  6   1

La somme d'une colonne est l'élément de la ligne suivante et colonne suivante 1 + 3 + 6 = 10

Dans ce groupe commençant par a, l'indice toujours en partant de la fin, du dernier b va être de même C(n-a-b-1, p-3) (a billes de moins et un tas de moins)

D'où la formule générale pour l'indice, de 1 à N = C(n-1, p-1), c'est à dire à partir du début :

x = C(n-1, p-1) - (C(n-a-1,p-1) + C(n-a-b-1, p-2) + C(n-a-b-c-1, p-3) + ...)

Nota : C(n, m) = 0 si n < m

Exemples avec le tableau ci dessus

La configuration {3,1,2,2} est au rang

35 - (C(7-3, 3) + C(7-3-1, 2) + C(7-3-1-2, 1)) = 35 - (4 + 3 + 1) = 27
          a             b               c

En sens inverse, trouver la x ième configuration revient à trouver la valeur de a donnant le plus grand C(n-a-1,p-1) ≤ C(n-1, p-1) - x
Puis récursivement sur b avec ce qui reste etc

Exemple du tableau ci-dessus x = 20, C(n-1, p-1) - x = 35 - 20 = 15
Il faut chercher le plus grand C(k,3) ≤ 15
On va ici écrire un triangle de Pascal, mais algorithmiquement, il est inutile : soit on résoud l'équation algébrique de degré p-1 = 3, avec Newton par ex, soit on "balaye" les C(k,3) de proche en proche en multipliant par k/(k-3) pour passer au suivant, à partir de C(3,3) = 1 :
1, 1*4/1 = 4, 4*5/2 = 10, 10*6/3 = 20 ... bingo > 15 donc c'est 10 le plus grand

k               ↓ colonne des C(k,3)
0   1
1   1   1
2   1   2   1
3   1   3   3   1
4   1   4   6   4   1
5   1   5  10  10   5   1
6   1   6  15  20   15  6   1

On trouve donc le plus grand C(k,3) = 10 qui correspond à k = 5 = n-a-1 c'est à dire a = 2
Il reste dans les {2, ...} à trouver celui dont l'indice est 15 - 10 = 5 en partant de la fin, c'est à dire le plus grand C(k,2) ≤ 5 qui est C(3,2)=3 et donne b = n-a-1 - 3 = 2
Il reste dans les {2,2,...} à trouver celui dont l'indice est 15-10-3 = 2
c'est à dire le plus grand C(k,1) ≤ 2 qui est 2 = C(2,1) et donne c = n-a-b-1 - 2 = 1

La 20 ème config est donc {2,2,1,..} que l'on complète avec le dernier tas = ce qui reste n-a-b-c = 3 et {2,2,1,3}

Des valeurs plus grandes s'obtiennent sans difficulté "quasiment à la main" (avec un triangle de Pascal) même avec 15 billes et 5 tas, c'est à dire C(14,4) = 1001 répartitions.
Triangle de Pascal réduit à ce dont on a besoin :

 k                       ↓ colonne des C(k,4)
 0   1
 1   1    1
 2   1    2    1
 3   1    3    3    1
 4   1    4    6    4    1
 5   1    5   10   10    5
 6   1    6   15   20   15
 7   1    7   21   35   35
 8   1    8   28   56   70
 9   1    9   36   84  126
10   1   10   45  120  210
11   1   11   55  165  330
12   1   12   66  220  495
13   1   13   78  286  715
14   1   14   91  364 1001

La configuration {3,2,5,1,4} est ainsi la
1001 - C(11,4) - C(9,3) - C(4,2) - C(3,1) = 1001 - 330 - 84 - 6 - 3 = 578 ème

Inversement la 547 ème config est
Plus grand C(k,4) ≤ 1001 - 547 = 454 est C(11,4) = 330 donne a = 14 - 11 = 3
Plus grand C(k,3) ≤ 454 - 330 = 124 est C(10,3) = 120 donne b = 11 - 10 = 1
Plus grand C(k,2) ≤ 124 - 120 = 4 est C(3,2) = 3 donne c = 10 - 3 = 7
Plus grand C(k,1) ≤ 4 - 3 = 1 est C(1,1) = 1 donne d = 3 - 1 = 2

Et finalement e = 15 - a - b - c - d = 2
et la 547eme config est {3, 1, 7, 2, 2}

Tas =

Rang =