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 1If p = 1 there is no question at all and the program rejects this case !

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) + ...) |

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 5Counting the number of cases which begin with a first heap =

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 1The 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) + ...) |

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 cConversely, to find the pattern at a given rank x is to find first the value of

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 1We 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 1001The 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}