Let $\alpha = (\alpha_1 , \dots , \alpha_n)$ be a vector with $\alpha_i \geq 0$ for all $1 \leq i \leq n$ and $|\alpha| := \sum_i \alpha_i = d$. Define the order $\leq$ by saying $\alpha ' \leq \alpha$ if $\alpha'_i \leq \alpha_i$ for all $1 \leq i \leq n$.

My question is the following: let $0 \leq \ell \leq d$. How can I count the number of $\alpha'$ such that $\alpha' \leq \alpha$ and $|\alpha'| = \ell$? If each $\alpha_i \geq \ell$, then this number is of course $\binom{n+\ell-1}{\ell}$ ("stars and bars"), but it seems to be a bit more subtle to count when some components are $< \ell$.

My suspicion is that this is a well known counting problem, but I am not particularly well versed in combinatorics. Thanks.

  • $\begingroup$ I think in the binomial coefficient both $d$s should be $\ell$s? And you have both $|\alpha|=d$ and $|\alpha|=\ell$; I suspect the second time you mean $|\alpha'|=\ell$? $\endgroup$ – joriki Feb 26 at 0:12

This is the problem of distributing balls in bins with limited capacity. It can be solved using inclusion–exclusion. The result is

$$ \sum_{S\subseteq[n]}(-1)^{|S|}\binom{n+\ell-\sum_{j\in S}(\alpha_j+1)-1}{n-1}\;, $$

where $[n]=\{1,\ldots,n\}$ and where, contrary to the usual convention, the binomial coefficient is taken to be zero if the upper index is negative.

| cite | improve this answer | |

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.