Compositions

The question is to set n identical objects on p heaps, with no empty heap, and named heaps A,B,C,...
We may as well consider that the n objects are in a line, with n-1 spaces.
The composition over p heaps is similar to settle p-1 walls on these n-1 spaces
O O O|O|O O O O|O O|O
  3   1    4     2  1
If p = 1 there is no question at all and the program rejects this case !

Total number of compositions N = C(n-1, p-1)
   n =    p =        
Generate the full list

These N compositions are then listed in increasing "alphabetic" order.
1 : {1,1,1,...,1,7}
2 : {1,1,1,...,2,6}
...
N : {7,1,...,1,1,1}

The question is to find a direct correspondance between the rank in the list and the heaps composition {a,b,c,...}
We may prove (1) that :

Rank of {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) + ...)
with C(n,m) = 0 si n<m
Heaps =
      
Rank =    
 

Appendix : Proofs

First note that the last heap is fully defined by the p-1 others
We may just consider these first p-1 heaps
Let's show an example with 4 heaps from 8 objects, that is C(7,3) = 35 cases, which can still be examined by hand :
rank  heaps         intervals       binary code (3 bits to 1 in 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) begin with 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) begin with 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) begin with 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) begin with 4
----------------------------------------------------
35  5+1+1+1      x x x x x|x|x|x     0000111     C(2,2) begin with 5
Counting the number of cases which begin with a first heap = a, it is the number of compositions of n-a objects on p-1 heaps, that is C(n-a-1, p-2)

The rank (from the end) of the last case in the set of { a, ...} is therefore C(p-2, p-2) + C(p-1, p-2) + ... C(n-a-2, p-2)
That is the sum of all the cases which begin with a+1, a+2 ... n-p-1
This sum of combinations is just C(n-a-1, p-1) (from the recurrence on the C(n, m))

For example C(2,2) + C(3,2) + C(4,2) = C(5,3)
On a Pascal triangle of the C(k,m) we get :

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
The sum of a collumn is the element in the next row and the next collumn 1 + 3 + 6 = 10

In this set of patterns beginning with a, the rank, still from the end of this set, of the last b is similarily C(n-a-b-1, p-3) (a objects less and 1 heap less)

Hence the general formula for the rank, in 1 to N = C(n-1, p-1), that is from the beginning :

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) + ...)
Note : C(n, m) = 0 if n < m

Examples from the above list

The pattern {3,1,2,2} is at rank

35 - (C(7-3, 3) + C(7-3-1, 2) + C(7-3-1-2, 1)) = 35 - (4 + 3 + 1) = 27
          a             b               c
Conversely, to find the pattern at a given rank x is to find first the value of a giving the largest C(n-a-1,p-1) ≤ C(n-1, p-1) - x
Then recursively on b with the remainder etc

Example from the previous list x = 20, C(n-1, p-1) - x = 35 - 20 = 15
We have to search for the largest C(k,3) ≤ 15
We shall write a Pascal triangle, but generally this is useless : either we solve the polynomial equation of degree p-1 = 3, for instance using Newton, either we "scan" the C(k,3) step by step multiplying by k/(k-3) to get the next one, from C(3,3) = 1 :
1, 1*4/1 = 4, 4*5/2 = 10, 10*6/3 = 20 ... bingo > 15 hence 10 is the larger.

k               ↓ collumn of 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
We find then the larger C(k,3) = 10 corresponding to k = 5 = n-a-1 that is a = 2
Remains in the set of {2, ...} to find the one which rank is 15 - 10 = 5 from the end of the bloc, that is the largest C(k,2) ≤ 5 which is C(3,2)=3 resulting into b = n-a-1 - 3 = 2
Then in the set of {2,2,...} to find the one with rank 15-10-3 = 2
that is the largest C(k,1) ≤ 2 which is 2 = C(2,1) resulting into c = n-a-b-1 - 2 = 1

The 20th pattern is then {2,2,1,..} that we complete with the last heap = the remainder n-a-b-c = 3 and {2,2,1,3}

Higher values can be obtained in the same way "by the hand" (with the help of a Pascal triangle) even with 15 objects in 5 heaps, that is C(14,4) = 1001 cases.
A Pascal triangle, reduced to the usefull part :

 k                       ↓ collumn of 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
The pattern {3,2,5,1,4} is then the
1001 - C(11,4) - C(9,3) - C(4,2) - C(3,1) = 1001 - 330 - 84 - 6 - 3 = 578 th

Inversely the 547th pattern is
Larger C(k,4) ≤ 1001 - 547 = 454 is C(11,4) = 330 giving a = 14 - 11 = 3
Larger C(k,3) ≤ 454 - 330 = 124 is C(10,3) = 120 giving b = 11 - 10 = 1
Larger C(k,2) ≤ 124 - 120 = 4 is C(3,2) = 3 giving c = 10 - 3 = 7
Larger C(k,1) ≤ 4 - 3 = 1 is C(1,1) = 1 giving d = 3 - 1 = 2

And finally e = 15 - a - b - c - d = 2
so that the 547th pattern is {3, 1, 7, 2, 2}

 

 

Home Arithmetic Geometric Misc Topics Scripts Games Exercices Mail Version Française Next topic