1
$\begingroup$

I'm trying to verify my answer to this problem by going back and solving the same problem using methods I've used before learning about generating functions, but I'm not quite sure how to do it in this case:

Find the coefficient of $x^{47}$ in $(x^{10}+x^{11}+\cdots+x^{25})(x+x^{2}+\cdots+x^{15})(x^{20}+\cdots+x^{45})$.

I'm looking at this problem as if it were saying

Given 47 identical objects and 3 distinct boxes, how many ways can the objects be placed into the boxes given that the first box must hold at least 10 and at most 25 objects, the second box must hold at least one and at most 15 objects, and the third box must hold at least 20 and at most 45 objects.

This can be translated to solving the equation

\begin{align} e_1+e_2+e_3=47\\10\leq e_1\leq 25\\1\leq e_2\leq 15,\\20\leq e_3\leq 45\end{align}

If there were no upper limits on the capacity of the boxes, I'd say that the solution is ${47-10-1-20+2\choose 2}={18\choose 2}$. I get this by placing 2 "walls" between the three groups to separate the one group of 18 into 3, but I don't know how to do this considering there are upper bounds. The solution I got through solving directly from the generating function, the coefficient of $x^{47}$ is

$$(-1){2\choose 2}+(-1){3\choose 2}+(1){18\choose 2}$$

so where do those extra binomial coefficients come from?

$\endgroup$
1
$\begingroup$

There's a nice simplification: define a related triple $(d_1, d_2, d_3)$ by $$ \left\{ \begin{align} d_1 &= e_1 - 10 \\ d_2 &= e_2 - 1 \\ d_3 &= e_3 - 20 \end{align} \right. $$ Then you have the system of equations and inequalities: $$ \begin{align} d_1 + d_2 + d_3 &= 16 \\ 0 \le d_1 &\le 15 \\ 0 \le d_2 &\le 14 \\ 0 \le d_3 &\le 25 \end{align} $$

Without the upper bounds, you have correctly calculated $\binom{18}{2}$ possibilities. However, a small number of these have $d_1 = 16$ ($1$ way) or $15 \le d_2 \le 16$ ($3$ ways). You have to subtract these to maintain the sum of $16$.

By the way, the change from $e$ variables to $d$ variables amounts to factoring $$ \begin{align} &(x^{10} + x^{11} + \cdots + x^{25}) (x + x^{2} + \cdots + x^{15}) (x^{20} + \cdots + x^{45}) \\ &= x^{10}(1 + x + \cdots + x^{15}) x(1 + x + \cdots + x^{14}) x^{20}(1 + x + \cdots + x^{25}) \\ &= x^{31}(1 + x + \cdots + x^{15}) (1 + x + \cdots + x^{14}) (1 + x + \cdots + x^{25}). \end{align} $$ Finding the $x^{47}$ coefficient of this last polynomial is clearly equivalent to finding the $x^{47 - 31} = x^{16}$ coefficient of $$ (1 + x + \cdots + x^{15}) (1 + x + \cdots + x^{14}) (1 + x + \cdots + x^{25}). $$

$\endgroup$
0
$\begingroup$

Using the lower bounds, write $e_1 = 9 + f_1$, similarly $e_2 = f_2$ and $e_3 = 19 + f_3$. Then you want positive-integer solutions to $f_1 + f_2 + f_3 = 19$ with $f_1 \le 16$, $f_2 \le 15$, and $f_3 \le 26$. The last of these is redundant (as $f_3 \le 19-2$ in any case), so drop it.

The number of positive-integer solutions to $f_1 + f_2 + f_3 = 19$ is $\binom{18}{2}$, by "stars-and-bars": the number of ways to insert two "bars" in the $18$ gaps between $19$ "stars".

From this we must subtract solutions in which $f_1 > 16$ or $f_2 > 15$ (not both are possible simultaneously, so that simplifies matters a little). The only possible way we can have $f_1 > 16$ is when $f_1 = 17$, which case the number of solutions to $f_2 + f_3 = 2$ is exactly $1$. There are two ways in which $f_2 > 15$ can happen: either $f_2 = 17$, in which case the number of solutions to $f_1 + f_3 = 2$ is $1$, or $f_2 = 16$, in which case the number of solutions to $f_1 + f_3 = 3$ is $2$.

So the answer turns out to be $\binom{18}{2} - 1 - 1 - 2$, which is the same as your expression.

$\endgroup$
  • $\begingroup$ In full generality, you'd go for inclusion/exclusion $\endgroup$ – vonbrand Apr 3 '14 at 2:51
0
$\begingroup$

You want (freely simplifying by getting rid of terms that can't affect the result): \begin{align} [x^{47}](x^{10}+x^{11}&+\cdots+x^{25})(x+x^{2}+\cdots+x^{15})(x^{20}+\cdots+x^{45}) \\ &= [x^{47}] \; x^{10} (1 + x + \cdots + x^{10}) \cdot x (1 + x + \cdots + x^{14}) \cdot x^{20} (1 + x + \cdots + x^{25})\\ &= [x^{16}] \frac{1 - x^{11}}{1 - z} \cdot \frac{1 - x^{15}}{1 - z} \cdot \frac{1}{1 - z} \\ &= [x^{16}] (1 - x^{11} - x^{15} + x^{26}) (1 - x)^{-3} \\ &= [x^{16}](1 - x)^{-3} - [x^{5}] (1 - x)^{-3} - [x](1 - x)^{-3} \\ &= (-1)^{16} \binom{-3}{16} - (-1)^5 \binom{-3}{5} - (-1) \binom{-3}{1} \\ &= \binom{16 + 3 - 1}{3 - 1} - \binom{5 + 3 - 1}{3 - 1} - \binom{1 + 3 - 1}{3 - 1} \\ &= 129 \end{align}

$\endgroup$
  • 1
    $\begingroup$ Nice. :-) But I think from the question that the OP was asking for a combinatorial "counting" method, not via generating functions. $\endgroup$ – ShreevatsaR Apr 2 '14 at 3:58

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.