compléments et résumé :
On répartit n billes en p tas (ex 15 billes en 5 tas), et les
configurations (que l'on appellera ici des "répartitions", ou
compositions) sont rangées en ordre lexicographique :
1 : {1, 1, 1, 1, 11}
2 : {1, 1, 1, 2, 10}
...
N-1 : {10, 2, 1, 1, 1}
N : {11, 1, 1, 1, 1}
1) nombre de répartitions N = C(n-1, p-1)
2) correspondance directe entre la répartition {a, b, c.. } et son
rang dans la liste, de 1 à N, c'est à dire à partir du début en
ordre croissant :
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
Détails et démonstrations (long)
===============================
La 1ère question se règle de suite en plaçant p-1 séparations dans les
n-1 intervalles entre billes d'une rangée de n billes.
comme signalé dans mon post précédent
Post by Philippe 92considérons les 15 billes alignées avec un espace entre chaque bille
Il y a donc 14 espaces
Faire 5 tas revient à placer 4 "séparateurs" dans ces espaces
tas 3 +1+1+ 6 + 4
. O O O|O|O|O O O O O O|O O O O
. ^ ^ ^ ^
il y a donc C(14,4) = 14*13*12*11/(4*3*2*1) = 1001 cas
de façon générale avec n billes en p tas C(n-1, p-1)
Post by pierre=========
peut-on trouver une formule qui en fonction d'un nombre en entrée me
donne la [permutation] correspondante en sortie ?
Entretemps j'ai un peu avancé, mais c'est pas encore au point.
Un truc du genre avec les tas de a,b,c,d,e billes
L'indice du tas (dans un ordre judicieux et à un décalage près) est
une somme de C(p,q), dans le genre (
x = C(n-a, 4) + C(n-a-b, 3) + C(n-a-b-c, 2) + C(n-a-b-c-d, 1)
reste à peaufiner ça
effectivement, cette formule n'était pas juste, seulement une piste.
Donc voila le résulat de mes cogitations :
(long car détails et exemples)
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 :
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 OK
. 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 V 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 d'indice 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}, en accord avec le tableau
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 V 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}
Un programme éditant ces 1001 configurations (c'est encore accessible
en une fraction de seconde) confirme.
Cordialement.
--
Philippe C. mail chephip à free.fr
site divertissement mathématiques http://mathafou.free.fr