ACOP/Generating Functions - Revision history

Admin: Redirected page to AOCP/Generating Functions

2019-03-17T21:44:58Z

Redirected page to AOCP/Generating Functions

← Older revision		Revision as of 21:44, 17 March 2019
Line 1:		Line 1:
	~~=Knuth: Volume 1: Fundamental Algorithms=~~		#REDIRECT [[AOCP/Generating Functions]]

	~~==Chapter 1: Basic Concepts: Generating Functions==~~

	You absolutely, positively must read the preceding chapters to follow Knuth here. There are a number of subtle steps that he moves through quite fast, about as quickly as he moves through the other material, except he's now integrating his method of presenting all 8 prior sections, including both explicit and passing references to prior material.

	~~As with the binomial coefficients...~~




	~~=Example Problems=~~

	~~==Knuth AOCP Section 1.2.9 Exercise 1==~~

	~~'''Exercise 1.''' What is the generating function for <math>\langle2^n + 3^n\rangle = \{ 2, 5, 13, 35, \dots \}</math>?~~

	For this problem, don't be fooled by the complexity of the preceding section - it's back to the basics. This sequence of numbers looks a lot like, oh, I dunno, two sequences of numbers added together. Specifically,

	~~<pre>~~
	~~2 4 8 16 32~~
	~~3 9 27 81 243~~
	~~</pre>~~

	~~If we can find the generating function for 2^n, and find the generating function for 3^n, we can use the addition property of generating functions to combine them.~~

	~~To find the generating function for <math>2^n</math>:~~

	~~<math>~~
	~~\begin{align}~~
	~~G_{2^n}(z) &=& 1 + 2z + 4z^2 + \dots \\~~
	~~z G_{2^n}(z) &=& 0 + z + 2z^2 + \dots \\~~
	~~2z G_{2^n}(z) &=& 0 + 2z + 4z^2 + \dots~~
	~~\end{align}~~
	~~</math>~~

	~~Now subtracting the first and last quantities gives:~~

	~~<math>~~
	~~(1-2z) G_{2^n}(z) = 1 + 0 + 0 + 0 + \dots~~
	~~</math>~~

	~~which yields the generating function for <math>2^n</math>:~~

	~~<math>~~
	~~G_{2^n}(z) = \dfrac{1}{1 - 2z}~~
	~~</math>~~

	~~Repeating the process for <math>3^n</math> gives:~~

	~~<math>~~
	~~G_{3^n}(z) = \dfrac{1}{1 - 3z}~~
	~~</math>~~

	~~Now to get the overall generating function for <math>\langle 2^n + 3^n \rangle</math> we add these two functions together and combine into a single rational expression:~~

	~~<math>~~
	~~G(z) = \dfrac{1}{1-2z} + \dfrac{1}{1 - 3z} = \dfrac{2-5x}{1-5x+6x^2}~~
	~~</math>~~

	Now for the cool part. If we do a Taylor Series expansion of <math>G(z)</math>, we can compute <math>2^n + 3^n</math> simply by obtaining the <math>n^{th}</math> coefficient of the Taylor Series polynomial. While this may seem like a pointless mathematical trick for a function like <math>2^n + 3^n</math>, the real utility of the method comes when we apply this approach to much more general functions.

	[[~~Image:MathematicaGeneratingFunction1.png\|500px]]~~

	~~If we evaluate the 500th term of the Taylor Series expansion, which we can denote <math>G_n(z)[500]</math>, we get:~~

	~~<math>~~
	~~\begin{align}~~
	~~G_n(z)[500] = 3636029179586993684238526707954331911802338502600162304034603583258060 \\~~
	~~0191583895484198511536369996679450049715724100683352008148159059109207 \\~~
	~~7819142079301219138181759224025267202176687407229640966567179316611617 \\~~
	~~95984554271383193123905199377~~
	~~\end{align}~~
	~~</math>~~

	~~which, in case you did not already notice, is <math>2^{500} + 3^{500}<~~/~~math>~~

	~~=Flags=~~

	~~{{AOCPFlag}}~~

	~~[[Category:~~Generating Functions]]
	~~[[Category:Combinatorics]]~~
	~~[[Category:Math]]~~
	~~[[Category:Binomial~~]]

Admin at 08:11, 24 July 2017

2017-07-24T08:11:27Z

← Older revision		Revision as of 08:11, 24 July 2017
Line 83:		Line 83:
	[[Category:Combinatorics]]		[[Category:Combinatorics]]
	[[Category:Math]]		[[Category:Math]]
			[[Category:Binomial]]

Admin: /* Example Problems */

2017-07-20T22:21:12Z

Example Problems

← Older revision		Revision as of 22:21, 20 July 2017
Line 74:		Line 74:
	</math>		</math>

	which, in case you did not already notice, is <math>2^500 + 3^500</math>		which, in case you did not already notice, is <math>2^{500} + 3^{500}</math>

	=Flags=		=Flags=

Admin: /* Knuth AOCP Section 1.2.9 Exercise 1 */

2017-07-20T22:20:49Z

Knuth AOCP Section 1.2.9 Exercise 1

← Older revision		Revision as of 22:20, 20 July 2017
Line 73:		Line 73:
	\end{align}		\end{align}
	</math>		</math>

			which, in case you did not already notice, is <math>2^500 + 3^500</math>

	=Flags=		=Flags=

Admin: /* Knuth AOCP Section 1.2.9 Exercise 1 */

2017-07-20T22:17:49Z

Knuth AOCP Section 1.2.9 Exercise 1

← Older revision		Revision as of 22:17, 20 July 2017
Line 14:		Line 14:
	==Knuth AOCP Section 1.2.9 Exercise 1==		==Knuth AOCP Section 1.2.9 Exercise 1==

	'''Exercise 1.''' What is the generating function for <math><2^n + 3^n> = \{ 2, 5, 13, 35, \dots \}</math>?		'''Exercise 1.''' What is the generating function for <math>\langle2^n + 3^n\rangle = \{ 2, 5, 13, 35, \dots \}</math>?

	For this problem, don't be fooled by the complexity of the preceding section - it's back to the basics. This sequence of numbers looks a lot like, oh, I dunno, two sequences of numbers added together. Specifically,		For this problem, don't be fooled by the complexity of the preceding section - it's back to the basics. This sequence of numbers looks a lot like, oh, I dunno, two sequences of numbers added together. Specifically,
Line 53:		Line 53:
	</math>		</math>

	Now to get the overall generating function for <math><2^n + 3^n></math> we add these two functions together and combine into a single rational expression:		Now to get the overall generating function for <math>\langle 2^n + 3^n \rangle</math> we add these two functions together and combine into a single rational expression:

	<math>		<math>
Line 63:		Line 63:
	[[Image:MathematicaGeneratingFunction1.png\|500px]]		[[Image:MathematicaGeneratingFunction1.png\|500px]]

	If we evaluate the 500th term of the Taylor Series expansion, which we can denote <math>~~[n]~~G_n(z)</math>, we get:		If we evaluate the 500th term of the Taylor Series expansion, which we can denote <math>G_n(z)[500]</math>, we get:

	<math>		<math>
	~~[50]~~G_n(z) = 3636029179586993684238526707954331911802338502600162304034603583258060\		\begin{align}
	0191583895484198511536369996679450049715724100683352008148159059109207\		G_n(z)[500] = 3636029179586993684238526707954331911802338502600162304034603583258060 \\
	7819142079301219138181759224025267202176687407229640966567179316611617\		0191583895484198511536369996679450049715724100683352008148159059109207 \\
			7819142079301219138181759224025267202176687407229640966567179316611617 \\
	95984554271383193123905199377		95984554271383193123905199377
			\end{align}
	</math>		</math>




	=Flags=		=Flags=

Admin: /* Example Problems */

2017-07-20T22:15:42Z

Example Problems

← Older revision		Revision as of 22:15, 20 July 2017
Line 60:		Line 60:

	Now for the cool part. If we do a Taylor Series expansion of <math>G(z)</math>, we can compute <math>2^n + 3^n</math> simply by obtaining the <math>n^{th}</math> coefficient of the Taylor Series polynomial. While this may seem like a pointless mathematical trick for a function like <math>2^n + 3^n</math>, the real utility of the method comes when we apply this approach to much more general functions.		Now for the cool part. If we do a Taylor Series expansion of <math>G(z)</math>, we can compute <math>2^n + 3^n</math> simply by obtaining the <math>n^{th}</math> coefficient of the Taylor Series polynomial. While this may seem like a pointless mathematical trick for a function like <math>2^n + 3^n</math>, the real utility of the method comes when we apply this approach to much more general functions.

			[[Image:MathematicaGeneratingFunction1.png\|500px]]

			If we evaluate the 500th term of the Taylor Series expansion, which we can denote <math>[n]G_n(z)</math>, we get:

			<math>
			[50]G_n(z) = 3636029179586993684238526707954331911802338502600162304034603583258060\
			0191583895484198511536369996679450049715724100683352008148159059109207\
			7819142079301219138181759224025267202176687407229640966567179316611617\
			95984554271383193123905199377
			</math>




			=Flags=

			{{AOCPFlag}}

			[[Category:Generating Functions]]
			[[Category:Combinatorics]]
			[[Category:Math]]

Admin: /* Knuth AOCP Section 1.2.9 Exercise 1 */

2017-07-20T22:13:46Z

Knuth AOCP Section 1.2.9 Exercise 1

← Older revision		Revision as of 22:13, 20 July 2017
Line 45:		Line 45:
	<math>		<math>
	G_{2^n}(z) = \dfrac{1}{1 - 2z}		G_{2^n}(z) = \dfrac{1}{1 - 2z}
	<math>		</math>

	Repeating the process for <math>3^n</math> gives:		Repeating the process for <math>3^n</math> gives:
Line 51:		Line 51:
	<math>		<math>
	G_{3^n}(z) = \dfrac{1}{1 - 3z}		G_{3^n}(z) = \dfrac{1}{1 - 3z}
	<math>		</math>

	Now to get the overall generating function for <math><2^n + 3^n></math> we add these two functions together and combine into a single rational expression:		Now to get the overall generating function for <math><2^n + 3^n></math> we add these two functions together and combine into a single rational expression:

Admin: /* Example Problems */

2017-07-20T22:13:28Z

Example Problems

← Older revision		Revision as of 22:13, 20 July 2017
Line 25:		Line 25:
	If we can find the generating function for 2^n, and find the generating function for 3^n, we can use the addition property of generating functions to combine them.		If we can find the generating function for 2^n, and find the generating function for 3^n, we can use the addition property of generating functions to combine them.

	To find the generating ~~funciton~~ for <math>2^n</math>:		To find the generating function for <math>2^n</math>:

	<math>		<math>
Line 32:		Line 32:
	z G_{2^n}(z) &=& 0 + z + 2z^2 + \dots \\		z G_{2^n}(z) &=& 0 + z + 2z^2 + \dots \\
	2z G_{2^n}(z) &=& 0 + 2z + 4z^2 + \dots		2z G_{2^n}(z) &=& 0 + 2z + 4z^2 + \dots
			\end{align}
	</math>		</math>

Admin: Created page with "=Knuth: Volume 1: Fundamental Algorithms= ==Chapter 1: Basic Concepts: Generating Functions== You absolutely, positively must read the preceding chapters to follow Knuth her..."

2017-07-20T22:13:04Z

Created page with "=Knuth: Volume 1: Fundamental Algorithms= ==Chapter 1: Basic Concepts: Generating Functions== You absolutely, positively must read the preceding chapters to follow Knuth her..."

New page

=Knuth: Volume 1: Fundamental Algorithms=

==Chapter 1: Basic Concepts: Generating Functions==

You absolutely, positively must read the preceding chapters to follow Knuth here. There are a number of subtle steps that he moves through quite fast, about as quickly as he moves through the other material, except he's now integrating his method of presenting all 8 prior sections, including both explicit and passing references to prior material.

As with the binomial coefficients...

=Example Problems=

==Knuth AOCP Section 1.2.9 Exercise 1==

'''Exercise 1.''' What is the generating function for <math><2^n + 3^n> = \{ 2, 5, 13, 35, \dots \}</math>?

For this problem, don't be fooled by the complexity of the preceding section - it's back to the basics. This sequence of numbers looks a lot like, oh, I dunno, two sequences of numbers added together. Specifically,

<pre>
2 4 8 16 32
3 9 27 81 243
</pre>

If we can find the generating function for 2^n, and find the generating function for 3^n, we can use the addition property of generating functions to combine them.

To find the generating funciton for <math>2^n</math>:

<math>
\begin{align}
G_{2^n}(z) &=& 1 + 2z + 4z^2 + \dots \\
z G_{2^n}(z) &=& 0 + z + 2z^2 + \dots \\
2z G_{2^n}(z) &=& 0 + 2z + 4z^2 + \dots
</math>

Now subtracting the first and last quantities gives:

<math>
(1-2z) G_{2^n}(z) = 1 + 0 + 0 + 0 + \dots
</math>

which yields the generating function for <math>2^n</math>:

<math>
G_{2^n}(z) = \dfrac{1}{1 - 2z}
<math>

Repeating the process for <math>3^n</math> gives:

<math>
G_{3^n}(z) = \dfrac{1}{1 - 3z}
<math>

Now to get the overall generating function for <math><2^n + 3^n></math> we add these two functions together and combine into a single rational expression:

<math>
G(z) = \dfrac{1}{1-2z} + \dfrac{1}{1 - 3z} = \dfrac{2-5x}{1-5x+6x^2}
</math>

Now for the cool part. If we do a Taylor Series expansion of <math>G(z)</math>, we can compute <math>2^n + 3^n</math> simply by obtaining the <math>n^{th}</math> coefficient of the Taylor Series polynomial. While this may seem like a pointless mathematical trick for a function like <math>2^n + 3^n</math>, the real utility of the method comes when we apply this approach to much more general functions.