10
$\begingroup$

Suppose there are $40$ balls with $10$ red, $10$ blue, $10$ green, and $10$ yellow. All balls with the same color are deemed identical. Now all balls are supposed to be put into $4$ identical baskets, such that each basket has $10$ balls. What is the number of ways to partition these balls?

I tried this problem, but it seems very complicated to correctly formulate, because the number of a particular color in a basket determines the partition of other baskets. I wonder someone can help figure out a quick and clean way to solve this problem?

$\endgroup$
3
$\begingroup$

Consider the problem of $4n$ balls with $n$ balls of each of the four colors being distributed into four indistinguishable baskets where each basket holds exactly $n$ balls. The naive approach here would be to use the Polya Enumeration Theorem (twice). Surprisingly enough this is sufficient to compute the initial segment of the sequence using the recurrence by Lovasz for the cycle index $Z(S_n)$ of the multiset operator $\mathfrak{M}_{=n}$ on $n$ slots, which is

$$Z(S_n) = \frac{1}{n} \sum_{l=1}^n a_l Z(S_{n-l}) \quad\text{where}\quad Z(S_0) = 1.$$

This recurrence lets us calculate the cycle index $Z(S_n)$ very easily. The answer is then given by

$$[A^n B^n C^n D^n] Z(S_4)(Z(S_n)(A+B+C+D)).$$

Using Maple and a reasonable amount of computational resources this yields the sequence

$$1, 17, 93, 465, 1746, 5741, 16238, 41650, 97407, 212412, 434767, \\ 845366, 1569344, 2801696, 4828140, 8069053, \\ 13114785, 20796651, 32242621, 48986553, 73052382, 107114645, \\ 154621230, 220021932, 308940815,\ldots$$

In particular the value for $n=10$ is given by $$212412.$$

This is OEIS A253259 where we discover a variation of the problem definition that confirms the validity of these results. Oddly enough no recurrence relation or other indication of how these numbers were computed is given in the OEIS entry. Perhaps we will see a recurrence now that there are enough test data to verify its correctness, if indeed it exists.

The Maple code for the above is quite straightforward.

with(combinat);

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;

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

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

V :=
proc(n)
    option remember;
    local comb, gf, var;

    comb := pet_varinto_cind(A+B+C+D, pet_cycleind_symm(n));
    gf := 
    expand(pet_varinto_cind(comb, pet_cycleind_symm(4)));

    for var in [A,B,C,D] do
        gf := coeff(gf, var, n);
    od;

    gf;
end;

Addendum. I realized I had overlooked an additional OEIS link to A257463 when I wrote the above several hours ago. It proposes a simple algorithm which uses the isomorphism between the problem and factorizations of $p_1^n p_2^n p_3^n p_4^n$ into four factors $q$ all of which have $\Omega(q) = n.$ The algorithm generates all of these using the observation that uniqueness of factorizations can be guaranteed by generating the factors in non-increasing order. It uses memoization to speed this up. Nonetheless when I pasted it verbatim into Maple and tried it on several test cases it performed very poorly compared to what I have above. I will therefore keep the post for now. The quest continues.

Addendum II. As per request by @WillOrrick I am posting the code for the general problem of $k$ colors.

V :=
proc(n, k)
    option remember;
    local base, comb, gf, var;

    base := add(Q[p], p=1..k);

    comb := pet_varinto_cind(base, pet_cycleind_symm(n));
    gf :=
    expand(pet_varinto_cind(comb, pet_cycleind_symm(k)));

    for var in [seq(Q[p], p=1..k)] do
        gf := coeff(gf, var, n);
    od;

    gf;
end;

We thus obtain for five colors the sequence $$1, 73, 1417, 19834, 190131, 1398547, 8246011, 40837569, 174901563, \\ 664006236, 2274999093, 7139338769, 20758868781, 56466073587, \\ 144806582536, 352420554194, 818441723112, 1822255658908,\ldots$$

Addendum III. Granting Maple several hours of computation time and 5GB of memory we get for four colors:

$$1, 17, 93, 465, 1746, 5741, 16238, 41650, 97407, 212412, 434767, \\ 845366, 1569344, n2801696, 4828140, 8069053, 13114785, 20796651, \\ 32242621, 48986553, 73052382, 107114645, 154621230, 220021932, \\ 308940815, 428492880, 587520315, 797019526, 1070458096, 1424339518, \\ 1878618620, 2457435561, 3189651885, 4109787687, 5258703597,\ldots$$

This confirms the generating function by @WillOrrick.

$\endgroup$
  • $\begingroup$ According to some of the linked entries on the OEIS page you cite, there is a rational generating function in the cases of two or three colors, and the denominators are products of relatively small powers of the first few cyclotomic polynomials. In hopes that that pattern continues, I tried multiplying the generating function for four colors (to the order given in the OEIS) by powers of the first four cyclotomic polynomials, and it appears to be the case that the generating function is $\endgroup$ – Will Orrick Feb 7 '16 at 2:44
  • $\begingroup$ $$\begin{aligned}&\frac{1}{(1-x)^{10} (1+x)^5 \left(1+x+x^2\right)^3\left(1+x^2\right)}\\ &\times\left(x^{18}+6 x^{17}+58 x^{16}+213 x^{15}+646 x^{14}+1415 x^{13}+2515 x^{12}+3554 x^{11}+4296 x^{10}\right.\\ &\quad\left.+4248 x^9+3578 x^8+2452 x^7+1421 x^6+628 x^5+240 x^4+61 x^3+12 x^2-x+1\right).\end{aligned}$$ $\endgroup$ – Will Orrick Feb 7 '16 at 2:46
  • $\begingroup$ Very good indeed. Can you break up this formula over multiple lines using exponent minus one instead of the fraction? This way it does not break the vertical alignment on the page. Would you be interested in seeing some code for the computation of the case of five or six colors to see if you can spot the generating function? $\endgroup$ – Marko Riedel Feb 7 '16 at 2:50
  • $\begingroup$ I hope the formatting is better now. I would be interested in seeing what can be done for five colors. How long does it take to get to order 30? Unfortunately, I suspect that one would have to go to much higher order than that to see something for five colors. $\endgroup$ – Will Orrick Feb 7 '16 at 2:54
  • $\begingroup$ Consult my post above which unfortunately tests the limits of the resources available on my machine (memory allocation). Signing off for the day. $\endgroup$ – Marko Riedel Feb 7 '16 at 3:16
1
$\begingroup$

Now as you have edited ofcourse answer changes so the answer is creating equal groups of 4 . There are m objects to be divided in $a...d$ where they are same (baskets)so the ways are $\frac{40!}{(10!)^4.4!}$ you can reason out why $4!$

$\endgroup$
  • $\begingroup$ $π$ represents product $\endgroup$ – Archis Welankar Feb 5 '16 at 6:38
  • $\begingroup$ Modified formula to be more standard. $\endgroup$ – Henno Brandsma Feb 5 '16 at 6:43
  • 3
    $\begingroup$ Thanks for the reply. I have to add that all balls with the same color are identical. Therefore I don't think the answer is correct, because it does not consider the redundancy in balls. $\endgroup$ – sciencemonk Feb 5 '16 at 6:45

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.