Asymptotics of number of ways of putting balls into bins with constraints

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