# Distribution of K balls in N Cells with limitations

In how many ways can i distribute $k$ balls in $n$ numbered cells with the following limitations:

1.Each cell has different number of balls in it

2.Given each cell has more balls than the cell before it (My guess was that it is the soulution for 1 divided by 2)

For example the answer for $k=5$ $n=3$ for 1. will be 4 and for 2. will be 2

• Can the first cell be empty? – yberman Jul 3 '15 at 13:51
• Would love to know a general answer-what happens if it's empty and if it doesn't – aaadddaaa Jul 3 '15 at 13:52
• condition 2 includes condition 1 so condition 1 is redundant – WW1 Jul 3 '15 at 13:55
• For (2) divide the answer for (1) by $n!$. Maybe that is what you meant. But I would lean towards solving (2) first. – André Nicolas Jul 3 '15 at 13:57
• (2) is the number of partitions of $k$ into $n$ distinct parts, plus (if you allow zero balls) the number of partitions of $k$ into $n-1$ distinct parts. – rogerl Jul 3 '15 at 14:02

By way of enrichment I would like to point out that using the Polya Enumeration Theorem the closed form is also given by

$$n! [z^k] Z(P_n)\left(\frac{z}{1-z}\right)$$

where $Z(P_n) = Z(A_n)-Z(S_n)$ is the difference between the cycle index of the alternating group and the cycle index of the symmetric group. This cycle index is known in species theory as the set operator $\mathfrak{P}_{=n}$ and the species equation here is

$$\mathfrak{P}_{=n}\left(\mathcal{Z} + \mathcal{Z}^2 + \mathcal{Z^3} + \cdots\right).$$

Here we have chosen the interpretation where none of the cells are empty.

Recall the recurrence by Lovasz for the cycle index $Z(P_n)$ of the set operator $\mathfrak{P}_{=n}$ on $n$ slots, which is $$Z(P_n) = \frac{1}{n} \sum_{l=1}^n (-1)^{l-1} a_l Z(P_{n-l}) \quad\text{where}\quad Z(P_0) = 1.$$ This recurrence lets us calculate the cycle index $Z(P_n)$ very easily.

For example when $n=3$ the cycle index is $$Z(P_3) = 1/6\,{a_{{1}}}^{3}-1/2\,a_{{2}}a_{{1}}+1/3\,a_{{3}}$$ and the generating function becomes $$1/6\,{\frac {{z}^{3}}{ \left( 1-z \right) ^{3}}}-1/2\,{\frac {{z}^{ 3}}{ \left( -{z}^{2}+1 \right) \left( 1-z \right) }}+1/3\,{\frac { {z}^{3}}{-{z}^{3}+1}}$$ which gives the sequence $$0, 0, 0, 0, 0, 6, 6, 12, 18, 24, 30, 42, 48, 60, 72,\ldots$$ which is six times OEIS A069905.

Similarly when $n=5$ we get the cycle index $$Z(P_5) = {\frac {{a_{{1}}}^{5}}{120}}-1/12\,a_{{2}}{a_{{1}}}^{3}+1/6\,a_{{ 3}}{a_{{1}}}^{2}+1/8\,a_{{1}}{a_{{2}}}^{2}\\-1/4\,a_{{4}}a_{{1}}-1/ 6\,a_{{2}}a_{{3}}+1/5\,a_{{5}}$$ and the generating function becomes $${\frac {{z}^{5}}{120\, \left( 1-z \right) ^{5}}}-1/12\,{\frac {{z}^ {5}}{ \left( -{z}^{2}+1 \right) \left( 1-z \right) ^{3}}}+1/6\,{ \frac {{z}^{5}}{ \left( -{z}^{3}+1 \right) \left( 1-z \right) ^{2} }}\\+1/8\,{\frac {{z}^{5}}{ \left( 1-z \right) \left( -{z}^{2}+1 \right) ^{2}}}-1/4\,{\frac {{z}^{5}}{ \left( -{z}^{4}+1 \right) \left( 1-z \right) }}\\-1/6\,{\frac {{z}^{5}}{ \left( -{z}^{2}+1 \right) \left( -{z}^{3}+1 \right) }}+1/5\,{\frac {{z}^{5}}{-{z}^{ 5}+1}}$$ which gives the sequence $$\ldots,120, 120, 240, 360, 600, 840, 1200, 1560, 2160, 2760, 3600,\ldots$$ which is $120$ times OEIS A001401.

There are many more related links at MSE Meta on Burnside/Polya.

The Maple code for these was as follows.

pet_cycleind_set :=
proc(n)
local p, s;
option remember;

if n=0 then return 1; fi;

a[l]*pet_cycleind_set(n-l), l=1..n));
end;

pet_varinto_cind :=
proc(poly, ind)
local subs1, subs2, polyvars, indvars, v, pot, res;

res := ind;

polyvars := indets(poly);
indvars := indets(ind);

for v in indvars do
pot := op(1, v);

subs1 :=
[seq(polyvars[k]=polyvars[k]^pot,
k=1..nops(polyvars))];

subs2 := [v=subs(subs1, poly)];

res := subs(subs2, res);
od;

res;
end;

q :=
proc(n, k)
option remember;
local gf;

gf := pet_varinto_cind(z/(1-z), pet_cycleind_set(n));
n!*coeftayl(gf, z=0, k);
end;


This MSE link has a computation that is just about the same.

• i wished there was a simpler way of doing this ;) – aaadddaaa Jul 19 '15 at 20:04