Generating Functions - Revision history

Unknown user: /* Example: Quicksort Recurrence */

2022-10-23T02:35:37Z

Example: Quicksort Recurrence

← Older revision		Revision as of 02:35, 23 October 2022
Line 301:		Line 301:

	<math>		<math>
	C_n = n + 1 + \dfrac{2}[n] \sum_{ 1 \leq k \leq n } C_{k-1}		C_n = n + 1 + \dfrac{2}{n} \sum_{ 1 \leq k \leq n } C_{k-1}
	</math>		</math>

	To ~~oslve~~ this, we can turn each term in the recurrence into a generating function. Start by multiplying both sides by <math>z^n</math> and then sum over all n:		To solve this, we can turn each term in the recurrence into a generating function. Start by multiplying both sides by <math>z^n</math> and then sum over all n:

	<math>		<math>

2022-10-23T02:34:43Z

Example: Quicksort Recurrence

← Older revision		Revision as of 02:34, 23 October 2022
Line 347:		Line 347:

	<math>		<math>
	C_n = \left[ z^n \right] \dfrac{2}{(1-z)^2} \ln \left(\dfrac{1}{(1-z)} \right} = 2 (n+1) (H_{n+1} - 1)		C_n = \left[ z^n \right] \dfrac{2}{(1-z)^2} \ln \left( \dfrac{1}{1-z} \right) = 2 (n+1) (H_{n+1} - 1)
	</math>		</math>

2017-08-11T00:46:35Z

Example: Quicksort Recurrence

2017-08-11T00:46:11Z

Example: Imaginary Roots

← Older revision		Revision as of 00:46, 11 August 2017
Line 293:		Line 293:

	<math>		<math>
	a_n = \dfrac{1}{2} \left( i^n + (-i)^n \right) = \dfrac{1]{2} i^n \left(1 + (-1)^n \right) \qquad \rightarrow \qquad 1, 0, -1, 0, 1, 0, -1, 0, 1, \dots		a_n = \dfrac{1}{2} \left( i^n + (-i)^n \right) = \dfrac{1}{2} i^n \left(1 + (-1)^n \right) \qquad \rightarrow \qquad 1, 0, -1, 0, 1, 0, -1, 0, 1, \dots
	</math>		</math>

2017-08-10T23:46:01Z

Example: Imaginary Roots

@@ Line 294: / Line 294: @@
 <math>
 a_n = \dfrac{1}{2} \left( i^n + (-i)^n \right) = \dfrac{1]{2} i^n \left(1 + (-1)^n \right) \qquad \rightarrow \qquad 1, 0, -1, 0, 1, 0, -1, 0, 1, \dots
 </math>

2017-08-10T23:36:48Z

Example: Imaginary Roots

← Older revision		Revision as of 23:36, 10 August 2017
Line 288:		Line 288:
	<math>		<math>
	G(z) = \dfrac{1}{2} \left( \dfrac{1}{1 - iz} + \dfrac{1}{1 + iz} \right)		G(z) = \dfrac{1}{2} \left( \dfrac{1}{1 - iz} + \dfrac{1}{1 + iz} \right)
			</math>

			Now the nth term of the series can be written as:

			<math>
			a_n = \dfrac{1}{2} \left( i^n + (-i)^n \right) = \dfrac{1]{2} i^n \left(1 + (-1)^n \right) \qquad \rightarrow \qquad 1, 0, -1, 0, 1, 0, -1, 0, 1, \dots
	</math>		</math>

2017-08-10T23:35:38Z

Example: Imaginary Roots

2017-08-10T23:35:05Z

Multiplication

← Older revision		Revision as of 23:35, 10 August 2017
Line 157:		Line 157:
	G_1(z) &=& \sum_{k \geq 0} a_k z^k \\		G_1(z) &=& \sum_{k \geq 0} a_k z^k \\
	G_2(z) &=& \sum_{k \geq 0} b_k z^k		G_2(z) &=& \sum_{k \geq 0} b_k z^k
			\end{align}
	</math>		</math>

Line 162:		Line 163:

	<math>		<math>
			\begin{align}
	G_1(z) G_2(z) &=& \sum_{k \geq 0} a_k z^k \sum_{m \geq 0} b_m z^m \\		G_1(z) G_2(z) &=& \sum_{k \geq 0} a_k z^k \sum_{m \geq 0} b_m z^m \\
	&=& \sum_{k \geq 0} \sum_{m \geq 0} a_k b_m z^{k+m} \\		&=& \sum_{k \geq 0} \sum_{m \geq 0} a_k b_m z^{k+m} \\
	&=& \sum_{k \geq 0} \sum_{m \geq k} a_k b_{m-k} z^m \\		&=& \sum_{k \geq 0} \sum_{m \geq k} a_k b_{m-k} z^m \\
	&=& \sum_{m \geq 0} \sum_{0 \leq k \leq m} a_k b_{m-k} z^m		&=& \sum_{m \geq 0} \sum_{0 \leq k \leq m} a_k b_{m-k} z^m
			\end{align}
	</math>		</math>

Line 171:		Line 174:

	<math>		<math>
	G_1(z) G_2(z) \rightarrow a_0 b_0, (a_1 b_0 + a_1 b_0), (a_2 b_0 + a_1 b_1 + a_0 b_2), \dots		G_1(z) G_2(z) \qquad \rightarrow \qquad a_0 b_0, (a_1 b_0 + a_1 b_0), (a_2 b_0 + a_1 b_1 + a_0 b_2), \dots
	</math>		</math>

Line 177:		Line 180:

	<math>		<math>
	\dfrac{1}{1-z} \rightarrow 1, 1, 1, 1, 1, \dots		\dfrac{1}{1-z} \qquad \rightarrow \qquad 1, 1, 1, 1, 1, \dots
	</math>		</math>

	<math>		<math>
	\dfrac{1}{(1-z)^2} = \dfrac{1}{1-z} \dfrac{1}{1-z} = \sum_{k \geq 0} (k+1) z^k \rightarrow 1, 2, 3, 4, 5, \dots		\dfrac{1}{(1-z)^2} = \dfrac{1}{1-z} \dfrac{1}{1-z} = \sum_{k \geq 0} (k+1) z^k \qquad \rightarrow \qquad 1, 2, 3, 4, 5, \dots
	</math>		</math>

2017-08-10T23:34:27Z

Partial Sum Of Prior Terms

← Older revision		Revision as of 23:34, 10 August 2017
Line 144:		Line 144:
	\begin{align}		\begin{align}
	\dfrac{1}{1-z} &=& \sum_{k \geq 0} z^k \qquad \rightarrow \qquad 1, 1, 1, 1,1 ,1, \dots \\		\dfrac{1}{1-z} &=& \sum_{k \geq 0} z^k \qquad \rightarrow \qquad 1, 1, 1, 1,1 ,1, \dots \\
	\ln \left( \dfrac{1}{1-z} \right) &=& \sum_{k \geq 1} \dfrac{z^k}{k} \qquad \rightarrow \qquad 0, 1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \dots		\ln \left( \dfrac{1}{1-z} \right) &=& \sum_{k \geq 1} \dfrac{z^k}{k} \qquad \rightarrow \qquad 0, 1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \dots \\
	~~\end{align}~~ \\
	\frac{1}{1-z} \ln \left( \frac{1}{1-z} \right) &=& \sum_{k \geq 1} H_k z^k \qquad \rightarrow \qquad 1, 1 + \frac{1}{2}, 1 + \frac{1}{2} + \frac{1}{3}, 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4}, \dots		\frac{1}{1-z} \ln \left( \frac{1}{1-z} \right) &=& \sum_{k \geq 1} H_k z^k \qquad \rightarrow \qquad 1, 1 + \frac{1}{2}, 1 + \frac{1}{2} + \frac{1}{3}, 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4}, \dots
			\end{align}
	</math>		</math>

2017-08-10T23:33:31Z

Partial Sum Of Prior Terms

← Older revision		Revision as of 23:33, 10 August 2017
Line 143:		Line 143:
	<math>		<math>
	\begin{align}		\begin{align}
	\dfrac{1}{1-z} &=& \sum_{k \geq 0} z^k \rightarrow 1, 1, 1, 1,1 ,1, \dots \\		\dfrac{1}{1-z} &=& \sum_{k \geq 0} z^k \qquad \rightarrow \qquad 1, 1, 1, 1,1 ,1, \dots \\
	\ln \left( \dfrac{1}{1-z} \right) &=& \sum_{k \geq 1} \dfrac{z^k}{k} \rightarrow 0, 1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \dots \\		\ln \left( \dfrac{1}{1-z} \right) &=& \sum_{k \geq 1} \dfrac{z^k}{k} \qquad \rightarrow \qquad 0, 1, \frac{1}{2}, \frac{1}{3}, \frac{1}{4}, \dots
	\frac{1}{1-z} \ln \left( \frac{1}{1-z} \right) &=& \sum_{k \geq 1} H_k z^k \rightarrow 1, 1 + \frac{1]{2}, 1 + \frac{1}{2} + \frac{1}{3}, 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4}, \dots		\end{align} \\
	~~\end{align}~~		\frac{1}{1-z} \ln \left( \frac{1}{1-z} \right) &=& \sum_{k \geq 1} H_k z^k \qquad \rightarrow \qquad 1, 1 + \frac{1}{2}, 1 + \frac{1}{2} + \frac{1}{3}, 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4}, \dots
	</math>		</math>