Crea sito
COMBINATORICS-3


This is about counting the ways to distribute K indistinguishable items in to M indistinguishable boxes.

One can put K identical items into three identical boxes in several ways.
There are 11 ways to put 7 items into 3 boxes. For example,

    a)  | 2 |   | 2 |   | 3 |
    b)  | 1 |   | 2 |   | 4 |
The distribution
        | 2 |   | 3 |   | 2 |
coincides with (a) since the boxes are indistinguishable.

The following table lists the number of ways to distribute K items into 3 boxes, N3(K), and in 4 boxes, N4(K):

K 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 ...
N3 1 2 3 4 5 7 8 10 12 14 16 19 21 24 27 30 33 37 40 ...
N4 1 2 3 5 6 9 11 15 18 23 27 34 39 47 54 64 72 84 94 ...

These numbers are determined by the formulas

N3( 6 b + a ) = ( 3 b + a) (b + 1) + d(a,0) ,
 
  where b=K/6;   a=K%6.
 
N4( 12 a + 4 b + c) = 12 a3 + 15 a2 + 6 a + 1 + b (12 a2 + 14 a +3 )
  + (1+c) (b2 + b)/2 + c (3 a2 + 3 a + 2 a b + 1 )
  + (8 a +5) d(b,2) - (a + 1) d(c,1) - d(b,0) (d(c,2) + d(c,3)) ,
 
  where a = K/12;  b=(K%12)/4;  c=k%4.

Where d(a,b) is the Kroneker delta, which is zero unless a=b for which it is 1.

Can you prove (or disprove) these formulas ?
I got them exploiting the patterns that appear in the differences between the N for consecutives K's.

Can you find a general formula for NM(K) ?

Marco Corvi - 2004