AOCP/Generating Functions - Revision history

Admin: Fix math syntax error: removed duplicate '=' sign in the align block (was '&=& =' now '&=&') (via update-page on MediaWiki MCP Server)

2026-06-06T01:01:45Z

Fix math syntax error: removed duplicate '=' sign in the align block (was '&=& =' now '&=&') (via update-page on MediaWiki MCP Server)

2019-03-17T21:46:38Z

Logarithm Series

← Older revision		Revision as of 21:46, 17 March 2019
Line 364:		Line 364:

	<math>		<math>
	\ln{ \left( \dfrac{1}{1-z} \right) } = z + \dfrac{1}{2} z^2 + \dfrac{1}{3} z^3 + \dots = \sum_{k \geq 1} dfrac{1}{k} z^k		\ln{ \left( \dfrac{1}{1-z} \right) } = z + \dfrac{1}{2} z^2 + \dfrac{1}{3} z^3 + \dots = \sum_{k \geq 1} \dfrac{1}{k} z^k
	</math>		</math>

2019-03-17T21:43:56Z

Volume 1

← Older revision		Revision as of 21:43, 17 March 2019
Line 1:		Line 1:
			=Before You Begin: Reading Notes=

			Knuth covers generating functions early in Volume 1, but with Knuth's Art of Computer Programming books, the length has no correlation to the difficulty. Some sections are long and can be skipped entirely with no impact, others are critical to and referenced throughout the entire 3-volume series.

			The sections preceding Generating Functions are crucial to understanding all of the material Knuth covers, but particularly to understanding generating functions. You absolutely, positively must read the preceding sections to follow Knuth's coverage of generating functions. There are a number of subtle steps that he moves through quite fast, as he is covering a huge amount of material. The generating functions section integrates material from 8 prior sections, which also cover a huge amount of material very fast. So there are many explicit and passing references to prior material.

	=Volume 1=		=Volume 1=

2017-07-24T08:14:13Z

← Older revision		Revision as of 08:14, 24 July 2017
Line 431:		Line 431:
	=Related=		=Related=

	See also: more notes on generating functions (an alternate presentation that is a little more intuition-based than Knuth's examples) ~~is at~~ [[Generating Functions]].		See also: more notes on generating functions (an alternate presentation that is a little more intuition-based than Knuth's examples):

			[[Generating Functions]]

	Other books covering generating functions include:		Other books covering generating functions include:

2017-07-24T08:11:44Z

← Older revision		Revision as of 08:11, 24 July 2017
Line 440:		Line 440:

	{{AOCPFlag}}		{{AOCPFlag}}

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

2017-07-22T10:23:29Z

Flags

← Older revision		Revision as of 10:23, 22 July 2017
Line 428:		Line 428:

	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>

			=Related=

			See also: more notes on generating functions (an alternate presentation that is a little more intuition-based than Knuth's examples) is at [[Generating Functions]].

			Other books covering generating functions include:
			* [[Analytic Combinatorics]]
			* [[Applied Combinatorics]]

	=Flags=		=Flags=

	{{AOCPFlag}}		{{AOCPFlag}}

2017-07-22T00:14:20Z

Chapter 1: Basic Concepts: Generating Functions

← Older revision		Revision as of 00:14, 22 July 2017
Line 130:		Line 130:

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

			For an alternative approach/additional coverage of generating functions, see [[Generating Functions]].

	Just as he did with [[AOCP/Binomial Coefficients]], after introducing the definition a generating function and its history, Knuth extensively details all of the operations that we can perform on these generating functions:		Just as he did with [[AOCP/Binomial Coefficients]], after introducing the definition a generating function and its history, Knuth extensively details all of the operations that we can perform on these generating functions:

2017-07-22T00:13:49Z

Knuth AOCP Section 1.2.9 Exercise 1

← Older revision		Revision as of 00:13, 22 July 2017
Line 361:		Line 361:
	=Example Problems=		=Example Problems=

	==Knuth AOCP Section 1.2.9 Exercise 1==		==AOCP Exercises==

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

2017-07-22T00:08:46Z

Knuth AOCP Section 1.2.9 Exercise 1

← Older revision		Revision as of 00:08, 22 July 2017
Line 424:		Line 424:

	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=

	{{AOCPFlag}}		{{AOCPFlag}}

2017-07-22T00:03:00Z

Logarithm Series

← Older revision		Revision as of 00:03, 22 July 2017
Line 348:		Line 348:

	====Logarithm Series====		====Logarithm Series====

			For logarithm series, we can use

	<math>		<math>
Line 354:		Line 356:

	<math>		<math>
	\ln{ \left( \dfrac{1}{1-z} \right) } = z + \dfrac{1}{2} zZ^2 + \dfrac{1}{3} z^3 + \dots = \sum_{k \geq 1} dfrac{1}{k} z^k		\ln{ \left( \dfrac{1}{1-z} \right) } = z + \dfrac{1}{2} z^2 + \dfrac{1}{3} z^3 + \dots = \sum_{k \geq 1} dfrac{1}{k} z^k
	</math>		</math>