How many ways to get an odd number of each color in each bin?

Question

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)

Answer 1

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

Answer 2

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$).