# Counting number of $n$-tuples with component-wise boundedness

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.

• 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$? – joriki Feb 26 at 0:12

$$\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.