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

  • $\begingroup$ Can the first cell be empty? $\endgroup$ – yberman Jul 3 '15 at 13:51
  • $\begingroup$ Would love to know a general answer-what happens if it's empty and if it doesn't $\endgroup$ – aaadddaaa Jul 3 '15 at 13:52
  • $\begingroup$ condition 2 includes condition 1 so condition 1 is redundant $\endgroup$ – WW1 Jul 3 '15 at 13:55
  • $\begingroup$ For (2) divide the answer for (1) by $n!$. Maybe that is what you meant. But I would lean towards solving (2) first. $\endgroup$ – André Nicolas Jul 3 '15 at 13:57
  • $\begingroup$ (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. $\endgroup$ – 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 :=
        local p, s;
        option remember;

        if n=0 then return 1; fi;

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

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 :=

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

        res := subs(subs2, res);


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);

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

| cite | improve this answer | |
  • $\begingroup$ i wished there was a simpler way of doing this ;) $\endgroup$ – aaadddaaa Jul 19 '15 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.