# stars-and-bars problem with an upper limit uppon the number of stars between between 2 bars

Can't be more precise than the title of my question!

How many possibilities to put N balls in n bags with the additional constraint that each bag can contain no more than $r_i$ ($r_1$, $r_2$, ... $r_n$) balls?

I saw this question at different places and I also read a nice answer here.

I'd love to ask the person who answered to comment a little bit on his last formula (what are $e_i$ and $c_i$?)! Unfortunately, I am a newbie on this forum so I can't comment, I can only post questions!

So if someone can help me, comment a little bit, it would be nice!

Thanks!

• why don't you comment on his answer then? It is more likely he will see your activity if you do it on his answer – Jorge Fernández Hidalgo Dec 2 '14 at 16:43
• @JorgeFernández "Unfortunately, I am a newbie on this forum so I can't comment, I can only post questions!" – Jason Knapp Dec 2 '14 at 17:49

Marc has the polynomial

$$P(X)=\left(1-X^{r_1+1}\right)\left(1-X^{r_2+1}\right)\ldots\left(1-X^{r_n+1}\right)\;.$$

Imagine that you’ve multiplied it out; the result is just some polynomial in $X$ with coefficients $c_0,c_1,\ldots,c_m$, where $m$ is the degree of $P$:

$$P(X)=\sum_{k=0}^ma_kX^k\;.\tag{1}$$

Some of these coefficients may well be $0$. If there are $\ell$ non-zero coefficients, say $a_{k_1},\ldots,a_{k_\ell}$, we can relabel them as $c_1,\ldots,c_\ell$, and for $i=1,\ldots,\ell$ we can let $e_i=k_i$. Then $(1)$ reduces to

$$P(X)=\sum_{i=1}^\ell a_{k_i}X^{k_i}=\sum_{i=1}^\ell c_iX^{e_i}\;,$$

as in Marc’s answer (except that I’ve given a name, $\ell$, to the number of non-zero terms).

• Perfect! Thanks a lot! – Tikoloche Dec 3 '14 at 7:44
• @user197046: You're welcome! – Brian M. Scott Dec 3 '14 at 8:08