2

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

aaadddaaa
  • 83
  • Can the first cell be empty? – yberman Jul 03 '15 at 13:51
  • Would love to know a general answer-what happens if it's empty and if it doesn't – aaadddaaa Jul 03 '15 at 13:52
  • condition 2 includes condition 1 so condition 1 is redundant – WW1 Jul 03 '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 03 '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 03 '15 at 14:02
  • For 1) it's the number of subsets of $\mathbb N$ such that $|A|=\sum_{i\in A}1=n$ (or $n+1$ if we allow one to be empty) and $\sum_{i\in A}i=k$. There is no explicit formula for this number – Elaqqad Jul 03 '15 at 15:00

1 Answers1

0

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;

        expand(1/n*add((-1)^(l-1)*
        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.

Community
  • 1
Marko Riedel
  • 61,317