0
$\begingroup$

Given the problem from: extended stars-and-bars problem(where the upper limit of the variable is bounded)

If $\mathbf{r} = (r_1, r_2, \ldots, r_n)\in \mathbb{N}^n_0$, i.e. $r_i$ is a non-negative integer for each $i=1,\ldots,n$, what is the number of solutions $\mathbf{a}=(a_1,a_2,\ldots,a_n) \in \mathbb{N}^n_0$ satisfying $|\mathbf{a}| = \sum_{i=1}^n a_i = N$ and $a_i \leq r_i$ for each $i=1,\ldots,n$.

I would like to find a sharp bound for the number of solutions to this problem which holds for each $\mathbf{r}\in \mathbb{N}_0^n$ such that $|\mathbf{r}|=j$ for some fixed $j\in \mathbb{N}_0$. The bound should also be dependent on $N$. Let $C(\mathbf{r},N)$ denote the coefficient in the polynomial function \begin{align*} P(X) = \frac{\prod_{i=1}^n (1-X^{r_i+1})}{(1-X)^n} \end{align*} for $X^N$. Is it true that \begin{align*} C(\mathbf{r},N) \leq { j \choose N } \end{align*} for every $\mathbf{r}\in\mathbb{N}_0^n$ such that $|\mathbf{r}|=j$? Is there a sharper bound? Note that when $\mathbf{r} = (1,1,\ldots,1) \in \mathbb{N}^n_0$ and $|\mathbf{r}| = n$, then ${ |\mathbf{r}| \choose N } = C(\mathbf{r},N)$.

Proof: When $\mathbf{r} = (1,1,\ldots,1)$ and $|\mathbf{r}|=n$, then \begin{align*} P(X) = \frac{\prod_{i=1}^n (1-X^2)}{(1-X)^n} = \frac{((1+X)(1-X))^n}{(1-X)^n} = (1+X)^n = \sum_{k=0}^n { n \choose k } x^k \end{align*} by the binomial theorem, and since $n = |\mathbf{r}|$, we see the result is true for the $N$-th term in the sum.

I would also like to obtain a reference or derivation for the polynomial function \begin{align*} P(X) = \frac{\prod_{i=1}^n (1-X^{r_i+1})}{(1-X)^n} \end{align*} given by user Marc van Leeuwen in counting solutions to this problem.

$\endgroup$
0
$\begingroup$

Yes $C(r,N) \leq { |r| \choose N }$ as it is easy to come up with a surjective function from the selection ${ |r| \choose N }$ of balls to solutions $a_1 + a_2 + \ldots + a_n = N$. Out of the $|r|$ balls, label $r_i$ of them the number $i$. Given the $N$ chosen balls, assign to $a_i$ the number of balls chosen with the label $i$. It is clear that this always leads to a solution and that every solution is attainable in atleast one way, hence $C(r,N) \leq { |r| \choose N }$.

The formula for $P(x)$ is just a simplified expression of

$$ \left(1+x+\ldots+x^{r_1}\right)\, \left(1 + x + \ldots + x^{r_2}\right) \ldots \left(1 + x + \ldots + x^{r_n}\right)$$

for which the coefficients are in bijection with solutions $\boldsymbol{a}$ by taking $a_i$ to be the exponent taken from the $i$th bracket.

A little trick that I find particularly useful when solving these types of problems. Suppose $|r| = N+\eta$ for some small $\eta$. Then by making the change of variables $r_i - b_i = a_i$ for each $i$, we find that we only need to count the number of nonnegative integer solutions $b_1 + \ldots + b_n = \eta$ where vector $r$ remains unchanged. This can be realized combinatorially as well (balls that you don't choose).

$\endgroup$
  • $\begingroup$ Could you please provide a reference for the formula for P(x)? $\endgroup$ – user129334 Jun 1 '15 at 16:01
  • $\begingroup$ @user129334 Any combinatorics book will have it as an example in their generating functions section. Perhaps an example will help clarify. Suppose N=6 and r=(3,3,3). We have P(x)=(1+...+x^3) (1+...+x^3) (1+...+x^3). Note this can be rewritten as ((1-x^4)/(1-x))^3 but ignore this form as it is less intuitive. When you multiply this out, we are looking for the coefficient of x^6. Each solution contributes to this coefficient. For example, a=(2,3,1) picks out (x^2)(x^3)(x). $\endgroup$ – Andrew Szymczak Jun 1 '15 at 17:38
  • $\begingroup$ Thank you, giving P(x) a name and your example helped me find more information. $\endgroup$ – user129334 Jun 1 '15 at 18:06

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.