2
$\begingroup$

This is from generating functionology by Herbert S Wilf. Here a rule is given as let f $\longleftrightarrow$ {$a_n$}$^{\infty}_0$ is a ordinary power series generating function and let k be a positive integer,then $$f^k \longleftrightarrow [ \sum_{n_1+n_2+\cdots+n_k=n}{a_{n_1}a_{n_2}\ldots a_{n_k}}]_{n=0}^\infty $$ As an example for it a function f(n,k) is taken which denote the number of ways that the nonnegative integer n can be written as an ordered sum of k nonnegative integers. Then he takes the power series $\frac{1}{1-x} \longleftrightarrow $ {1} and uses the above rule to conclude $\frac{1}{(1-x)^k} \longleftrightarrow {f(n,k)}^\infty_{n=0} $ and then says f(n,k) = ${n+k-1} \choose {n}$ , I cant understand how he did the last step, I know this formula $\sum_{k}\binom {n}{k}x^k= (1+x)^n$ , however can't see how he applied it to get that last step

$\endgroup$
2
$\begingroup$

The last step simply follows from calculating the coefficient of $x^{n}$ in the power series expansion of $\dfrac{1}{(1-x)^k}$: \begin{align} \dfrac{1}{n!} \cdot \text{$n$-th derivative of } \dfrac{1}{(1-x)^k} &= \dfrac{1}{n!} \cdot (-1)^{n} (-k) (-k-1) \dots (-k -n+ 1) \\&= \dfrac{(n + k - 1) \dots (k+1) k}{n!} \\=& \dfrac{(n+k-1)!}{n! (k-1)!}\\&= \binom{n+k-1}{n}. \end{align}

$\endgroup$
  • $\begingroup$ Ty, very nicely explained! $\endgroup$ – Cloverr May 15 '15 at 10:51
1
$\begingroup$

The answer is not immediately obvious but you can do it combinatorially as follows. Firtly, $f(n,k)$ counts the number of solutions to the equation $n_1+\cdots+n_k = n$ in non-negative integers. To see the value of $f(n,k)$ consider the classic argument of separating $n$ balls into $k$ bins with $k-1$ separators. For example with $n = 5$ and $k = 4$, one configuration is

$$\bullet||\bullet|\bullet\bullet|\bullet$$ We can show that there is a one-to-one correspondence between the number of ways to count these ball/bin arrangements and $f(n,k)$ $-$ the separators define how big the $n_i$'s will be.

To actually find $f(n,k)$ is a basic counting. We have $n+k-1$ objects but $n$ of them are the same and the rest ($k-1$) are also the same so we have have

$$f(n,k) = \frac{(n+k-1)!}{n!(k-1)!} = \binom{n+k-1}{n}$$.

$\endgroup$

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.