3
$\begingroup$

Let $a_n$ be the number of series of numbers between 1 and 6, such that their sum equals $n$. I need to find the generating function to the problem: $$f(x)=\sum_{n=0}^{\infty} a_n\cdot x^n$$ Note: $a_0 = 0$.

I thought about finding a generating function for each possible length of such series, $k$. then for some $k$ I have: $$\left[\frac{x\cdot (x^6-1)}{x-1}\right]^k$$

Then I summed up for $k$ from 1 to $n$ and got: $$\sum_{k=1}^{n}\left[\frac{x\cdot (x^6-1)}{x-1}\right]^k$$ Is it the right way to go? or am I missing something? this subject is pretty confusing... thanks.

$\endgroup$
1
  • $\begingroup$ For example, if n = 5, then a series with length 3 would be 1,2,2, and series with length 4 would be 1,1,1,2. $\endgroup$ – user401516 Jan 22 '17 at 6:04
0
$\begingroup$

Your solution is basically correct. The coefficient of $x^n$ in $$(x+x^2+x^3+x^4+x^5+x^6)^k$$ is the number of sequences of length $k$ in $\{1,2,3,4,5,6\}$ which sum to $n$. So number of all such sequences summing to $n$, of any length, is going to be the sum over all the possible lengths $k$. Therefore, the coefficient of $x^n$ in $$\sum_{k=1}^\infty (x+x^2+x^3+x^4+x^5+x^6)^k$$ is indeed the $a_n$ that you are after.

(Can you further simplify this infinite series using geometric series? The final answer is actually a rational function of $x$.)

$\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.