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 |
| 2 | | 3 | | 2 |
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