Resulta que, de hecho, $f(n)=o(c^n)$ cualquier $c>1$.
De hecho, se puede demostrar que $\log(f(n))=O\left(n^{2/3}\cdot\sqrt[3]{\log n}\right)$.
También se puede demostrar que $\log(f(n))=\Omega(n^{2/3})$.
Para demostrar $\log(f(n))=O\left(n^{2/3}\cdot\sqrt[3]{\log n}\right)$, vamos a $w(n)$ el número de maneras distintas en las que uno puede distribuir las bolas blancas; y deje $b(n)$ ser el número máximo de distintas maneras en que uno puede distribuir las bolas negras para cualquiera dada la colocación de las bolas blancas. Claramente $\log(f(n))\leq \log(w(n))+\log(b(n))$. Tenga en cuenta que una vez que las bolas blancas se colocan los cubos de basura de convertirse, al menos parcialmente, "distiguishable", por lo que no debería resultar sorprendente que $b(n)$ resulta ser significativamente mayor que $w(n)$.
Enfoquémonos en $w(n)$. Obviamente $w(n)\leq p(n)$ donde $p(n)=\Theta\left(\frac{1}{n}\exp\left(\sqrt{\frac{2n}{3}}\right)\right)$ es el número de particiones de $n$ - el número de maneras en que uno puede colocar $n$ bolas en sin etiquetar recipientes, de manera que cada compartimiento contiene al menos una bola (sin ningún tipo de requisito en la paridad de bolas en cada bin).
Desde $\log(w(n))=O(n^{1/2})$, todo lo que debemos probar es que el $\log(b(n))=O(n^{2/3}\log^{1/3}n)$ escritura $\log^x n$ en lugar de $(\log x)^n$ a reducir el número de paréntesis. Para ello, nos vamos a particionar el conjunto de contenedores en clases de equivalencia basada en el número de bolas blancas, con clase $C_w$ que contiene todas las bandejas con exactamente $w$ bolas blancas. Consideremos el conjunto a $C^+$ de los "grandes" de clases, con al menos $n^{1/3}\log^{-4/3}n$ papeleras; y el conjunto de $C^-$ "pequeñas" de las clases, con menos de $n^{1/3}\log^{-4/3}n$ papeleras - más formalmente, vamos a $C^+=\{C_i:|C_i|\geq n^{1/3}\log^{-4/3}n\}$$C^-=\{C_i:|C_i|< n^{1/3}\log^{-4/3}n\}$. Tenga en cuenta que el número de distintas maneras en que uno puede colocar las bolas negras no pueden exceder el número de maneras en que uno puede colocar las bolas negras en las grandes clases de veces el número de maneras en que uno puede colocar las bolas negras en las clases pequeñas.
Vamos a comenzar con las clases grandes, señalando que son menos de $2n^{1/3}\log^{2/3}n$, ya que el $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$. Deje $m^+_i$ el número de bolas negras que se coloca en el $i^{th}$ de la clase, y $b^+_i(m^+_i)$ el número de maneras diferentes se puede colocar las bolas (teniendo en cuenta que los contenedores en la misma clase no son "distinguible"). Entonces, el número de maneras en que uno puede colocar las bolas negras en las clases grandes no puede exceder el número de maneras en que uno puede elegir $m^+_1,\dots,m^+_{|C^+|}$ veces el máximo (más de todas las opciones de $m^+_1,\dots,m^+_{|C^+|}$)$\Pi_{i=1}^{|C^+|} b^+_i(m^+_i)$. El número de maneras en que uno puede elegir el $m^+_i$ está delimitado por $n^{|C^+|}$, por lo que su logaritmo es $O(2n^{1/3}\log^{2/3}n \cdot \log n)=O(n^{1/3}\log^{5/3}n)$. Como para $\Pi_{i=1}^{|C^+|} b^+_i(m^+_i)$, ya que el $b^+_i(m^+_i)\leq p(m^+_i)$, $\Pi_{i=1}^{|C^+|} b^+_i(m^+_i) \leq \Pi_{i=1}^{|C^+|} p(m^+_i)$ y, desde $\log(p(m))=O(m^{1/2})$ $m^{1/2}$ es cóncava, $\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)$.
Pasemos ahora a las clases pequeñas, y que nos permiten contar el total de número de contenedores en ellos, $\sum_{C_i \in C^-} |C_i|$. Es inmediato ver que $\sum_{C_i \in C^-} |C_i|< 2n^{2/3}\log^{-2/3}n$, ya que si ordenamos los contenedores en función del número de bolas blancas que llevan, la $i^{th}$ bin debe llevar, al menos, $\lceil\frac{i}{n^{1/3}\log^{-4/3}n}\rceil$ bolas blancas (pasar de una clase a la siguiente aumenta el número de bolas por lo menos $1$) y $\sum_{i=1}^{2n^{2/3}\log^{-2/3}n}\frac{i}{n^{1/3}\log^{-4/3}n} > n$. Ya podemos colocar bolas negras en cada bin de cada uno de los pequeños de la clase en la mayoría de los $n$ formas, las bolas negras en las clases pequeñas contribuir a $\log(f(n))$ una cantidad que es en la mayoría de las $\log\left(n^{2n^{2/3}\log^{-2/3}n}\right)=O(n^{2/3}\log^{1/3}n)$.
A continuación, $\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)$.
El límite anterior es casi ajustado, ya que se puede probar que $\log(f(n))=\Omega(n^{2/3})$ mediante la elección de un $\ell=\Omega(n^{1/3})$ que es lo suficientemente pequeño para llevar a cabo los pasos siguientes. En primer lugar, hemos dividido las bolas blancas en $\ell$ clases de $\ell$ papeleras de cada uno (con todas las bandejas en la misma clase con el mismo, impar, el número de bolas blancas); esto hace que cada clase "distinguible" de los demás y, obviamente, requiere de $O(\ell^3)$ bolas blancas. A continuación, se le asigna un número suficiente de bolas negras para cada clase, de manera que dentro de cada clase de cada contenedor tiene un número impar de bolas estrictamente mayor que el siguiente bin; de hecho, lo suficientemente grande para que cada una de las $i$ también podemos barajar un par de pelotas entre el $(2i-1)^{th}$ $(2i)^{th}$ bin, por lo que la podemos obtener al menos $2^2$ diferentes configuraciones para el par. Este rendimientos $(2^2)^{\ell/2}=2^\ell$ configuraciones para esa clase, para un total de $(2^\ell)^\ell = 2^{\Omega(n^{2/3})}$ configuraciones. Obviamente, se puede hacer esto con $O(\ell^2)$ bolas negras por clase, y por lo tanto un total de $O(\ell^3)$ bolas negras.
A continuación, $\log(f(n))=\Omega(n^{2/3})$.
