On the Combinatorics of Placing Balls into Ordered Bins

Abstract

In this paper, we use techniques of enumerative combinatorics to study the following problem: we count the number of ways to split $n$ balls into nonempty, ordered bins so that the most crowded bin has exactly $k$ balls. We find closed forms for three of the different cases that can arise: $k>\frac{n}{2}$, $k=\frac{n}{2}$, and when there exists $j<k$ such that $n=2k+j$. As an immediate result of our proofs, we find a closed form for the number of positive integer solutions to $x_1+x_2+\cdots +x_{\ell }=n$ with the attained maximum of $\{x_1,x_2,\dots ,x_{\ell }\}$ being equal to $k$, when $n$ and $k$ have one of the aforementioned algebraic relationships to each other. The problem is generalized to find a formula that enumerates the total number of ways without specific conditions on $n,\ell ,k$. Subsequently, various additional identities and estimates related to this enumeration are proven and interpreted.

33 pages, 2 figures

References in corpus (5)

• On the number of summands in Zeckendorf decompositions
• Central Limit Theorems for Gaps of Generalized Zeckendorf Decompositions
• Estimating Bernoulli trial probability from a small sample
• Proofs of some binomial identities using the method of last squares
• Laplace transform asymptotics and large deviation principles for longest success runs in Bernoulli trials