My Math Forum Generating functions - (1-x-x^2-x^3-x^4-x^5-x^6)^-1

May 1st, 2010, 03:23 AM   #1
Newbie

Joined: May 2010

Posts: 3
Thanks: 0

Generating functions - (1-x-x^2-x^3-x^4-x^5-x^6)^-1

Hi all!

I've got this problem here:
Quote:
 Show that (1 - x - x^2 - x^3 - x^4 - x^5 - x^6)^-1 is the generating function for the number of ways a sum of r can occur if a die is rolled any number of times.
It's a homework problem, but it's past due, so I am just trying to figure it out because I think I may have missed something important that I need to solve this.

I was able to solve this with recurrence relations:
C0 = 1 (there is 1 way to roll a sum of 0), and CN = CN-1 + CN-2 + CN-3 + CN-4 + CN-5 + CN-6.
I used that to get h(x) - x - 2x^2 - 4x^3 - 8x^4 - 16x^5 - 32x^6 = x (h(x) - x - 2x^2 - 4x^3 - 8x^4 - 16x^5) + x^2 (h(x) - x - 2x^2 - 4x^3 - 8x^4) + x^3 (h(x) - x - 2x^2 - 4x^3) + x^4 (h(x) - x - 2x^2) + x^5 (h(x) - x) + x^6 (h(x)), where g(x) = h(x) + 1, because h(x) does not include the 1 * x^0 term. This works out fine.

But there should be some way to verify this without recurrence relations. I'm not sure how to convert the generating function to a sum, or how to reconstruct (build) the generating function, but there should be some way to do either of those.

Hopefully someone here can give some advice.
Thanks.

 May 1st, 2010, 01:35 PM #2 Member   Joined: Apr 2010 Posts: 65 Thanks: 0 Re: Generating functions - (1-x-x^2-x^3-x^4-x^5-x^6)^-1 Taylor expansion $\frac{1}{1-X-X^2-X^3-X^4-X^5-X^6}=$ $1 + X + 2 X^2 + 4 X^3 + 8 X^4 + 16 X^5 + 32 X^6 + 63 X^7 + 125 X^8 + 248 X^9 +\cdots$ (Sloane's A001592) $\sum_{j=1}^{\infty}\left(\sum_{i=1}^{6}x^i\right)^ j\\$
 May 1st, 2010, 06:40 PM #3 Newbie   Joined: May 2010 Posts: 3 Thanks: 0 Re: Generating functions - (1-x-x^2-x^3-x^4-x^5-x^6)^-1 Thanks for the reply! Now I understand that this is the generating function for the problem: $\sum_{j=1}^{\infty}\left(\sum_{i=1}^{6}x^i\right)^ j\\$ And I understand that it expands like this: $1 + X + 2 X^2 + 4 X^3 + 8 X^4 + 16 X^5 + 32 X^6 + 63 X^7 + 125 X^8 + 248 X^9+\cdots$ But I'm not quite sure how to convert between that and $\frac{1}{1-X-X^2-X^3-X^4-X^5-X^6}=$. Could you please explain that? Thanks.
 May 3rd, 2010, 06:00 AM #4 Senior Member   Joined: Jun 2009 Posts: 150 Thanks: 0 Re: Generating functions - (1-x-x^2-x^3-x^4-x^5-x^6)^-1 Do you know the power series expantion for $\frac{1}{1-Y}$ in powers of Y ?
 May 3rd, 2010, 08:47 AM #5 Newbie   Joined: May 2010 Posts: 3 Thanks: 0 Re: Generating functions - (1-x-x^2-x^3-x^4-x^5-x^6)^-1 Well, I understand this: But I'm not sure how it relates to $\frac{1}{1-Y-Y^2}$, $\frac{1}{1-Y-Y^2-Y^3}$, etc. Again, I'm not exactly sure what I'm missing here. :S I'm not sure how to show this: $\frac{1}{1-X-X^2-X^3-X^4-X^5-X^6}=\sum_{j=1}^{\infty}\left(\sum_{i=1}^{6}x^i\ri ght)^j\\$ It'd be nice if you could explain that.

,

### show that is the generating function for the number of ways a sum of r can occur if a die is rolled any number of times

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post carlos43 Applied Math 0 April 6th, 2013 01:01 PM mahjk17 Applied Math 4 June 19th, 2012 02:53 PM mathrookie2012 Applied Math 1 March 24th, 2012 05:48 AM proglote Calculus 10 September 14th, 2011 05:32 PM rez Applied Math 0 May 3rd, 2011 06:18 AM

 Contact - Home - Top