0
$\begingroup$

Since I don’t feel very confident when dealing with generating functions as of yet, I’d like to make sure whether my solution to the following simple problem is correct.

Let $P(n, k, a, b)$ denote the number of arrangements of $n$ indistinguishable balls into $k$ distinct buckets so that there’s no less than $a$ and no more than $b$ balls in each bucket. Which value is higher: $P(28, 19, 1, 2)$ or $P(30, 10, 2, 7)$?

Ok, so the generating function for $P(n, 19, 1, 2)$ is

\[ (x + x^2)^{19} = x^{19}(x+1)^{19} = x^{19}\bigg( {19\choose 0} + \ldots + {19\choose 9}x^9 + \ldots + {19 \choose 19}x^{19} \bigg) \]

and then the coefficient of $x^{28}$ is ${19 \choose 9}$.

Similarly $P(n, 10, 2, 7)$:

\[ (x^2 + x^3 + x^4 + x^5 + x^6 + x^7)^{10} = x^{20}(1 + x + x^2 + x^3 + x^4 + x^5)^{10}. \]

Apparently I can't think of a smart way to find the coefficient of $x^{10}$ in the second factor (any idea?). Wolfram says it's $85228$ (less than ${19 \choose 9} = 92378$).

1 Answers 1

1

You can get the coefficients of $(1+x+x^2+x^3+x^4+x^5)^{10}$ by rewriting it as

$\left({1-x^6\over 1-x}\right)^{10}=(1-x^6)^{10}(1-x)^{-10} =\sum_{j=0}^\infty {10\choose j}(-1)^j x^{6j} \,\sum_{k=0}^\infty {9+k\choose k} x^k.$

We need to pick out the coefficients where $6j+k=10$. There are only two choices $j=0,k=10$ and $j=1,k=4$, so we get ${10\choose 0}{19\choose 10}-{10\choose 1}{13\choose 4}=85228. $