6
$\begingroup$

Suppose you have an odd number of white balls and the same number of blacks balls.

How many different ways are there of putting the balls into bins so that you have an odd number of each color in each bin?

For example, if you have $3$ white and $3$ black there are $2$ different ways. You either put them all in one bin or one white and one black in each of $3$ bins. For $5$ white and $5$ white balls there are $4$ different ways. These are:

(wwwwwbbbbb)
(wwwbbb)(wb)(wb)
(wwwb)(wbbb)(wb)
(wb)(wb)(wb)(wb)(wb)
$\endgroup$
  • 1
    $\begingroup$ Generating function: $\sum\limits_{k=1}^\infty(x+x^3+x^5+x^7+\dots)^k(y+y^3+y^5+\dots)^k$ and looking at the coefficient of $x^ay^b$ where $a$ is the number of white balls and $b$ is the number of black balls. $\endgroup$ – JMoravitz Apr 14 '18 at 16:13
  • $\begingroup$ @JMoravitz Does this give you 12 for $a = b = 7$? $\endgroup$ – Anush Apr 14 '18 at 17:28
  • $\begingroup$ No, it gives much more than that. My initial comment assumes that the bins are each labeled. For 5 balls each I come to a total of 11 outcomes (one outcome each for one bin or five bins, and then with 3 bins it is broken into cases of which bin gets the three balls of each color for 9 more cases) If you intend the bins to be unlabeled, then my approach doesn't work. $\endgroup$ – JMoravitz Apr 14 '18 at 17:39
  • $\begingroup$ For 7 black and 7 white, if my mental calculations are correct I get 63 outcomes. $\endgroup$ – JMoravitz Apr 14 '18 at 17:41
  • 1
    $\begingroup$ Dropping the odd requirement gives OEIS A108469. $\endgroup$ – Christian Sievers Apr 14 '18 at 23:41
5
$\begingroup$

The cycle index $Z(S_n)$ of the symmetric group (multiset operator $\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\textsc{MSET}$) has $Z(S_0)=1$ and the recurrence

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

Extracting coefficients from this Maple will produce

$$1, 2, 4, 12, 32, 85, 217, 539, 1316, 3146, 7374, 16969, 38387, 85452, \\ 187456, 405659, 866759, 1830086, 3821072, 7894447, 16148593, \\ 32723147, 65719405, 130871128, 258513076, 506724988, \ldots$$ where we have used memoization.

The repertoire here was $$f(W, B) = \sum_{p_1=0}^q \sum_{p_2=0}^q W^{2p_1+1} B^{2p_2+1},$$

the substitution $a_l = f(W^l, B^l)$ and the coefficient being extracted

$$\sum_{k=1}^{2q+1} [W^{2q+1}] [B^{2q+1}] Z(S_k)(f(W,B)).$$

The Maple code runs as follows.

X :=
proc(n, q, q1, q2)
option remember;

    if n = 0 then
        if q1 = 0 and q2 = 0 then
            return 1;
        else
            return 0;
        fi;
    fi;

    add(add(add(X(n-l, q, q1-(2*p1+1)*l, q2-(2*p2+1)*l),
                p2=0..floor((q2/l-1)/2)),
            p1=0..floor((q1/l-1)/2)),
        l=1..n)/n;
end;

R := q -> add(X(k, q, 2*q+1, 2*q+1), k=1..2*q+1);
$\endgroup$
  • $\begingroup$ Thanks for this! What do you think the asymptotics might be? $\endgroup$ – Anush Apr 15 '18 at 20:30
3
$\begingroup$

More general, the coefficient of $x^my^n$ in

$$ \prod_{i,j\geq 0}(1-x^{2i+1}y^{2j+1})^{-1} $$

tells you how many ways there are to distribute $m$ white and $n$ black balls into bins such that each bin contains an odd number of white and an odd number of black balls.

There is a correspondance between the partitions of a number into odd numbers and those of the same number into different numbers. The same idea gives a correspondance between the ways to put balls into bins according to the given rules and the ways to put the balls into bins such that no two bins have the same contents and, for each bin, the number of white balls and the number of black balls is divisible by the same power of two (they have the same $2$-adic valuation). For example, a bin with $6$ and $10$ balls is allowed, but a bin with $6$ and $12$ balls isn't.

Hence the generating function can also be expressed as

$$ \prod (1+x^iy^j) $$

where the product is over all pairs of positive integers $i$ and $j$ such that $i$ and $j$ have the same $2$-adic valuation (i.e. there is an integer $k$ such that $(i,j)=2^k\cdot (r,s)$ for some odd integers $r$ and $s$).

$\endgroup$
  • $\begingroup$ Can you explain the $-1$ exponent? $\endgroup$ – qwr Apr 15 '18 at 2:51
  • 1
    $\begingroup$ @qwr Recall the geometric series $(1-z)^{-1}=1+z+z^2+\dots$ and let $z=x^ry^s$ for some odd $r$ and $s$. The corresponding factor will allow for any number of bins having $r$ white and $s$ black balls. $\endgroup$ – Christian Sievers Apr 15 '18 at 8:28
  • $\begingroup$ What do you think the asymptotics might be if $m = n$? It seems it might be asymptotic to $\sqrt{2}^n$ but it's hard to tell. $\endgroup$ – Anush Apr 15 '18 at 20:28
  • 1
    $\begingroup$ @Anush Extracting information about asymptotics from generating functions seems to be much more difficult in the multivariate case. From other series involving partitions I expect something more complicated. $\endgroup$ – Christian Sievers Apr 16 '18 at 11:27
  • $\begingroup$ @Anush $f(501)/f(499)\approx 1.39$ $\endgroup$ – Christian Sievers Apr 17 '18 at 9:25

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.