10
$\begingroup$

Suppose you have $n$ white balls and $n$ blacks balls.

Let us define $f(n)$ to be the number of different ways there are of putting the balls into unlabelled 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, so $f(3) = 2$. You either put them all in one bin or one white and one black in each of $3$ bins. For $5$ white and $5$ black balls there are $4$ different ways so $f(5) = 4$. These are:

(wwwwwbbbbb)
(wwwbbb)(wb)(wb)
(wwwb)(wbbb)(wb)
(wb)(wb)(wb)(wb)(wb)

I am interested in the following question.

What is $f(n)$ asymptotic to?

For the task of computing the exact value of $f(n)$, very nice answers were given by Marko Riedel and Christian Sievers. I reproduce them here:


The first answer was in reply to a question with only odd $n$ and says:

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 second answer says:

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.


By computer calculation of the coefficients, the ratio of successive answers (for $m=n$ as in the original question), seems to tend slowly towards 1. Therefore it's not even clear that the answer is asymptotic to $c^n$ for any $c>1$.

For odd $n$ the sequence is https://oeis.org/A302919 .

$\endgroup$
  • $\begingroup$ Should it be "... into unlabeled bins .." ? $\endgroup$ – G Cab Apr 18 '18 at 20:58
  • $\begingroup$ @GCab Thank you. Added that edit. $\endgroup$ – Anush Apr 18 '18 at 21:23
  • 1
    $\begingroup$ OEIS A002774 describes the unrestricted case. They mention the paper On partitions of bipartite numbers by F. C. Auluck which derives asymptotics for that problem from the g.f. $\sum_{r,s\geq0,r+s>0}(1-x^ry^s)^{-1}$. It might be possible to adapt the methods used in that paper. $\endgroup$ – Christian Sievers Apr 26 '18 at 12:54
  • $\begingroup$ @ChristianSievers That would be really great! $\endgroup$ – Anush Apr 26 '18 at 12:56
  • $\begingroup$ Too late to edit, but the sum should be a product. - @Anush I already tried, but I didn't get far $\endgroup$ – Christian Sievers Apr 26 '18 at 13:06
4
+50
$\begingroup$

It turns out that, indeed, $f(n)=o(c^n)$ for any $c>1$.

In fact, one can prove that $\log(f(n))=O\left(n^{2/3}\cdot\sqrt[3]{\log n}\right)$.

One can also prove that $\log(f(n))=\Omega(n^{2/3})$.


To prove $\log(f(n))=O\left(n^{2/3}\cdot\sqrt[3]{\log n}\right)$, let $w(n)$ be the number of distinct ways one can distribute the white balls; and let $b(n)$ be the maximum number of distinct ways one can distribute the black balls for any one given placement of the white balls. Clearly $\log(f(n))\leq \log(w(n))+\log(b(n))$. Note that once the white balls are placed, the bins become at least partially "distiguishable", so it it should not be surprising that $b(n)$ turns out to be significantly larger than $w(n)$.

Let us first focus on $w(n)$. Obviously $w(n)\leq p(n)$, where $p(n)=\Theta\left(\frac{1}{n}\exp\left(\sqrt{\frac{2n}{3}}\right)\right)$ is the number of partitions of $n$ - the number of ways one can place $n$ balls into unlabelled bins so that each bin contains at least one ball (without any requisite on the parity of balls in each bin).

Since $\log(w(n))=O(n^{1/2})$, all we have to prove is that $\log(b(n))=O(n^{2/3}\log^{1/3}n)$ - writing $\log^x n$ instead of $(\log x)^n$ to reduce the number of parentheses. To this end, let us partition the set of bins into equivalence classes based on the number of white balls, with class $C_w$ containing all bins with exactly $w$ white balls. Consider the set $C^+$ of "large" classes, with at least $n^{1/3}\log^{-4/3}n$ bins; and the set $C^-$ of "small" classes, with less than $n^{1/3}\log^{-4/3}n$ bins - more formally, let $C^+=\{C_i:|C_i|\geq n^{1/3}\log^{-4/3}n\}$ and $C^-=\{C_i:|C_i|< n^{1/3}\log^{-4/3}n\}$. Note that the number of distinct ways one can place the black balls cannot exceed the number of ways one can place the black balls into the large classes times the number of ways one can place the black balls into the small classes.

Let us begin with the large classes, noting that they are less than $2n^{1/3}\log^{2/3}n$, since $1\cdot (n^{1/3}\log^{-4/3}n)+2\cdot (n^{1/3}\log^{-4/3}n)+\dots+2n^{1/3}\log^{2/3}n\cdot (n^{1/3}\log^{-4/3}n)>n$. Let $m^+_i$ be the number of black balls placed into the $i^{th}$ class, and $b^+_i(m^+_i)$ the number of different ways one can place those balls (noting that the bins in the same class are not "distinguishable"). Then, the number of ways one can place the black balls into the large classes cannot exceed the number of ways one can choose $m^+_1,\dots,m^+_{|C^+|}$ times the maximum (over all choices of $m^+_1,\dots,m^+_{|C^+|}$) of $\Pi_{i=1}^{|C^+|} b^+_i(m^+_i)$. The number of ways one can choose the $m^+_i$ is bounded by $n^{|C^+|}$, so its logarithm is $O(2n^{1/3}\log^{2/3}n \cdot \log n)=O(n^{1/3}\log^{5/3}n)$. As for $\Pi_{i=1}^{|C^+|} b^+_i(m^+_i)$, since $b^+_i(m^+_i)\leq p(m^+_i)$, then $\Pi_{i=1}^{|C^+|} b^+_i(m^+_i) \leq \Pi_{i=1}^{|C^+|} p(m^+_i)$ and, since $\log(p(m))=O(m^{1/2})$ and $m^{1/2}$ is concave, $\log\left(\Pi_{i=1}^{|C^+|} p(m^+_i)\right) = O\left(2n^{1/3}\log^{2/3}n\cdot \left(\frac{n}{2n^{1/3}\log^{2/3}n}\right)^{1/2}\right)=O(n^{2/3}\log^{1/3}n)$; basically, the upper bound on $\Pi_{i=1}^{|C^+|} p(m^+_i)$ is maximized by maximimizing $|C^+|$ and taking all $m^+_i$ equal. So, the black balls in the large classes contribute to $\log(f(n))$ a quantity that is at most $O(n^{1/3}\log^{5/3}n+n^{2/3}\log^{1/3}n)=O(n^{2/3}\log^{1/3}n)$.

Let us now turn to the small classes, and let us count the total number of bins in them, $\sum_{C_i \in C^-} |C_i|$. It is immediate to see that $\sum_{C_i \in C^-} |C_i|< 2n^{2/3}\log^{-2/3}n$, since if we sort the bins according to how many white balls they carry, the $i^{th}$ bin must carry at least $\lceil\frac{i}{n^{1/3}\log^{-4/3}n}\rceil$ white balls (moving from one class to the next increases the number of balls by at least $1$) and $\sum_{i=1}^{2n^{2/3}\log^{-2/3}n}\frac{i}{n^{1/3}\log^{-4/3}n} > n$. Since we can place black balls into each bin of each small class in at most $n$ ways, the black balls in the small classes contribute to $\log(f(n))$ a quantity that is at most $\log\left(n^{2n^{2/3}\log^{-2/3}n}\right)=O(n^{2/3}\log^{1/3}n)$.

Then, $\log(f(n))= O(n^{1/2})+O(n^{2/3}\log^{1/3}n)+O(n^{2/3}\log^{1/3}n)=O\left(n^{2/3}\cdot \sqrt[3]{\log n}\right)$.


The bound above is almost tight, since one can prove that $\log(f(n))=\Omega(n^{2/3})$ by choosing an $\ell=\Omega(n^{1/3})$ that is sufficiently small to carry out the following steps. First, we split the white balls into $\ell$ classes of $\ell$ bins each (with all bins in the same class having the same, odd, number of white balls); this makes each class "distinguishable" from the others and obviously requires $O(\ell^3)$ white balls. Then, we assign a sufficient number of black balls to each class, so that within each class each bin has an odd number of balls strictly larger than the next bin; in fact, sufficiently larger that for each $i$ we can also shuffle a few balls between the $(2i-1)^{th}$ and $(2i)^{th}$ bin, so that the we can obtain at least $2^2$ different configurations for the pair. This yields $(2^2)^{\ell/2}=2^\ell$ configurations for that class, for a total of $(2^\ell)^\ell = 2^{\Omega(n^{2/3})}$ configurations. Obviously, we can do this with $O(\ell^2)$ black balls per class, and thus a total of $O(\ell^3)$ black balls.

Then, $\log(f(n))=\Omega(n^{2/3})$.

$\endgroup$
  • 1
    $\begingroup$ This looks very interesting! Thank you. $\endgroup$ – Anush Apr 24 '18 at 18:39
  • $\begingroup$ +1, very nice! I don't think the statement is quite right about how many ways there are to distribute the black balls among the $O(n^{1/3}\log^{2/3}n)$ large classes. The bins in each large class are indistinguishable; but the large classes themselves are distinguishable, so it's not obvious that this is bounded by $p(n)$, as you state, is it? $\endgroup$ – mjqxxxx Apr 25 '18 at 14:45
  • $\begingroup$ I get the idea, and the grammar is fine :). But say you have two large classes ... $C_{10}$, a large set of bins with $10$ white balls each, and $C_{11}$ ... putting $m_1$ black balls into $C_{10}$ and $m_2$ black balls into $C_{11}$ is distinguishable from putting $m_2$ black balls into $C_{10}$ and $m_1$ into $C_{11}$. You're dividing at most $n$ black balls into at most $O^{*}(n^{1/3})$ distinguishable large bins; you need a different bound than $p(n)$. $\endgroup$ – mjqxxxx Apr 25 '18 at 15:33
  • $\begingroup$ @mjqxxxx You are right! I see your point now. Thank you for pointing it out. I've edited the proof so that hopefully it's correct. Basically: you can choose $m^+_1,..m^+_{|C^+|}$ in at most $n^{|C^+|}$ ways, and the logarithm is then $|C^+|\log n=\tilde{O}(n^{1/3})$. $\endgroup$ – Anonymous Apr 25 '18 at 16:08

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.