0
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Jorge Fernández Hidalgo Dec 2 '14 at 16:43
  • $\begingroup$ @JorgeFernández "Unfortunately, I am a newbie on this forum so I can't comment, I can only post questions!" $\endgroup$ – Jason Knapp Dec 2 '14 at 17:49
1
$\begingroup$

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).

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

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.