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, 2017 at 6:04

1 Answer 1

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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .