Exponential Generating Functions - Revision history

Admin at 21:59, 4 August 2017

2017-08-04T21:59:17Z

← Older revision		Revision as of 21:59, 4 August 2017
Line 124:		Line 124:
	3^n + 1		3^n + 1
	</math>		</math>






			=Flags=

			{{CombinatoricsFlag}}

			{{AlgorithmsFlag}}

			[[Category:Generating Functions]]
			[[Category:Recursion]]
			[[Category:Combinatorics]]
			[[Category:Probability]]

Admin: /* Generating functions for choices */

2017-08-04T21:57:38Z

Generating functions for choices

← Older revision		Revision as of 21:57, 4 August 2017
Line 60:		Line 60:

	<math>		<math>
	1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + \dots		E_0(x) = 1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + \dots
	</math>		</math>

Admin: /* Counting Ternary Strings */

2017-08-04T21:56:44Z

Counting Ternary Strings

← Older revision		Revision as of 21:56, 4 August 2017
Line 37:		Line 37:


			===Generating functions for choices===

			Start by writing generating functions for each possible choice.

	For 1s and 2s, we have as many digits as we would like, so the generating functions are the normal 1, 1, 1, 1 series:		For 1s and 2s, we have as many digits as we would like, so the generating functions are the normal 1, 1, 1, 1 series:
Line 86:		Line 88:
	E_0(x) = \dfrac{e^x + e^{-x}}{2} = \sum_{k \geq 0} \dfrac{x^{2k}}{(2k)!}		E_0(x) = \dfrac{e^x + e^{-x}}{2} = \sum_{k \geq 0} \dfrac{x^{2k}}{(2k)!}
	</math>		</math>

			===Overall generating function===

			The overall generating function is obtained by multiplying all of the above generating functions together.

	Now the overall generating function becomes:		Now the overall generating function becomes:

Admin: /* Counting Ternary Strings */

2017-08-04T21:55:32Z

Counting Ternary Strings

← Older revision		Revision as of 21:55, 4 August 2017
Line 29:		Line 29:
	Suppose we have ternary strings (numbers consisting of the digits 0, 1, and 2) of length n, and we wish to know how many of these strings have an <u>even number of 0s</u>.		Suppose we have ternary strings (numbers consisting of the digits 0, 1, and 2) of length n, and we wish to know how many of these strings have an <u>even number of 0s</u>.

	~~To solve this problem, we apply a formulaic procedure:~~

	~~First, we determine~~ the generating function for each of ~~the~~ possible choices (0, 1, 2 ~~in this case)~~.		Solving this problem can be done with the following procedure:

			'''FIRST:''' Determine the generating function for each of our possible choices. In this case, a ternary string can be 0, 1, or 2. Each discrete choice has its own generating function.

			'''SECOND:''' Multiply the generating functions together to get the overall generating function.



	~~Then, we multiply the generating functions together to get the overall generating function.~~

	For 1s and 2s, we have as many digits as we would like, so the generating functions are the normal 1, 1, 1, 1 series:		For 1s and 2s, we have as many digits as we would like, so the generating functions are the normal 1, 1, 1, 1 series:

Admin at 21:54, 4 August 2017

2017-08-04T21:54:06Z

← Older revision		Revision as of 21:54, 4 August 2017
Line 23:		Line 23:


	===~~EXAMPLE~~ Counting Ternary Strings===		=Examples=

			==Counting Ternary Strings==

	Suppose we have ternary strings (numbers consisting of the digits 0, 1, and 2) of length n, and we wish to know how many of these strings have an <u>even number of 0s</u>.		Suppose we have ternary strings (numbers consisting of the digits 0, 1, and 2) of length n, and we wish to know how many of these strings have an <u>even number of 0s</u>.

Admin at 21:53, 4 August 2017

2017-08-04T21:53:47Z

← Older revision		Revision as of 21:53, 4 August 2017
Line 1:		Line 1:
	=~~==Exponential Generating Functions==~~=		=Notes=

	~~What we've seen so far is pretty cool. But~~ the case of marbles in a can, or boxes to pack in a truck, is independent of order. What do we do if we have a problem in which order matters?		==Trotter Chapter 8==

			Also see: [[Generating Functions#Trotter Chapter 8: Generating Functions]]

			In the case of marbles in a can, or boxes to pack in a truck, is independent of order. What do we do if we have a problem in which order matters?

	In these situations we want to use exponential generating functions. We define an analogous function to <math>\dfrac{1}{1-x}</math> to generate the sequence 1,1,1,1,...: we use the series expansion		In these situations we want to use exponential generating functions. We define an analogous function to <math>\dfrac{1}{1-x}</math> to generate the sequence 1,1,1,1,...: we use the series expansion

Admin: Created page with "===Exponential Generating Functions=== What we've seen so far is pretty cool. But the case of marbles in a can, or boxes to pack in a truck, is independent of order. What do..."

2017-08-04T21:52:54Z

Created page with "===Exponential Generating Functions=== What we've seen so far is pretty cool. But the case of marbles in a can, or boxes to pack in a truck, is independent of order. What do..."

New page

===Exponential Generating Functions===

What we've seen so far is pretty cool. But the case of marbles in a can, or boxes to pack in a truck, is independent of order. What do we do if we have a problem in which order matters?

In these situations we want to use exponential generating functions. We define an analogous function to <math>\dfrac{1}{1-x}</math> to generate the sequence 1,1,1,1,...: we use the series expansion

<math>
e^x = \sum_{n \geq 0} \dfrac{x^n}{n!}
</math>

which gives a basic exponential generating function of:

<math>
E(x) = \sum_{n \geq 0} \dfrac{x^n}{n!}
</math>

As before, we will seek to put all functions/sequences of interest in terms of this base function.

===EXAMPLE Counting Ternary Strings===

Suppose we have ternary strings (numbers consisting of the digits 0, 1, and 2) of length n, and we wish to know how many of these strings have an <u>even number of 0s</u>.

To solve this problem, we apply a formulaic procedure:

First, we determine the generating function for each of the possible choices (0, 1, 2 in this case).

Then, we multiply the generating functions together to get the overall generating function.

For 1s and 2s, we have as many digits as we would like, so the generating functions are the normal 1, 1, 1, 1 series:

<math>
\begin{align}
E_1(x) &=& e^x \\
E_1(x) &=& \sum_{n \geq 0} \dfrac{x^n}{n!}
\end{align}
</math>

<math>
\begin{align}
E_2(x) &=& e^x \\
E_2(x) &=& \sum_{n \geq 0} \dfrac{x^n}{n!}
\end{align}
</math>

For the 0s, we can only have an even number of terms, so we need the series

<math>
1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + \dots
</math>

Unlike with linear generating functions, where complex numbers eliminate particular terms, exponential functions make this a little easier to do.

Start by writing out the exponential sequence that we are using:

<math>
e^{x} = 1 + \dfrac{x}{1!} + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \dfrac{x^4}{4!} + \dots
</math>

then substitute -x for x, to get a slightly different series:

<math>
e^{-x} = 1 - \dfrac{x}{1!} + \dfrac{x^2}{2!} - \dfrac{x^3}{3!} + \dfrac{x^4}{4!} - \dots
</math>

If we add these two series together, the odd terms will cancel out, and we will have precisely the terms we want. This identity can be written:

<math>
\dfrac{e^x + e^{-x}}{2} = 1 + \dfrac{x^2}{2!} + \dfrac{x^4}{4!} + \dots
</math>

Now we have the generating function for the 0 digit:

<math>
E_0(x) = \dfrac{e^x + e^{-x}}{2} = \sum_{k \geq 0} \dfrac{x^{2k}}{(2k)!}
</math>

Now the overall generating function becomes:

<math>
\begin{align}
E(x) &=& E_0(x) E_1(x) E_2(x) \\
&=& (e^x) (e^x) \left( \dfrac{e^x+e^{-x}}{2} \right) \\
&=& \dfrac{e^{3x} + e^x}{2}
\end{align}
</math>

Now the exponential functions can be converted to infinite series, and the series can be combined and simplified to yield the series form of the generating function.

<math>
\begin{align}
\dfrac{e^{3x}+e^x}{2} &=& \dfrac{1}{2} \left( \sum_{n \geq 0} \dfrac{(3x)^n}{n!} + \sum_{k \geq 0} \dfrac{(x)^n}{n!} \right) \\
&=& \dfrac{1}{2} \left( \sum_{k \geq 0} \dfrac{ 3^n x^n + x^n}{n!} \right) \\
&=& \dfrac{1}{2} \left( \sum_{k \geq 0} (3^n + 1) \dfrac{x^n}{n!} \right)
\end{align}
</math>

What this means, in the end, is that the coefficient of the nth term of the infinite series expansion of our generating function is

<math>
\dfrac{3^n+1}{n!}
</math>

and we can obtain a closed-form expression for the total number of ternary strings of length n having an even number of 0s. It is:

<math>
3^n + 1
</math>