12-4 Number of different binary trees
Let b n b_n b n n n n b n b_n b n
a. Show that b 0 = 1 b_0 = 1 b 0 = 1 n ≥ 1 n \ge 1 n ≥ 1
b n = ∑ k = 0 n − 1 b k b n − 1 − k . b_n = \sum_{k = 0}^{n - 1} b_k b_{n - 1 - k}. b n = k = 0 ∑ n − 1 b k b n − 1 − k .
b. Referring to Problem 4-4 for the definition of a generating function, let B ( x ) B(x) B ( x )
B ( x ) = ∑ n = 0 ∞ b n x n . B(x) = \sum_{n = 0}^\infty b_n x^n. B ( x ) = n = 0 ∑ ∞ b n x n .
Show that B ( x ) = x B ( x ) 2 + 1 B(x) = xB(x)^2 + 1 B ( x ) = x B ( x ) 2 + 1 B ( x ) B(x) B ( x )
B ( x ) = 1 2 x ( 1 − 1 − 4 x ) . B(x) = \frac{1}{2x} (1 - \sqrt{1 - 4x}). B ( x ) = 2 x 1 ( 1 − 1 − 4 x ) .
The Taylor expansion f ( x ) f(x) f ( x ) x = a x = a x = a
f ( x ) = ∑ k = 0 ∞ f ( k ) ( a ) k ! ( x − a ) k , f(x) = \sum_{k = 0}^\infty \frac{f^{(k)}(a)}{k!} (x - a)^k, f ( x ) = k = 0 ∑ ∞ k ! f ( k ) ( a ) ( x − a ) k ,
where f ( k ) ( x ) f^{(k)}(x) f ( k ) ( x ) k k k f f f x x x
c. Show that
b n = 1 n + 1 ( 2 n n ) b_n = \frac{1}{n + 1} \binom{2n}{n} b n = n + 1 1 ( n 2 n )
(the n n n Catalan number 1 − 4 x \sqrt{1 - 4x} 1 − 4 x x = 0 x = 0 x = 0 n n n n n n k k k ( n k ) \binom{n}{k} ( k n ) n ( n − 1 ) ⋯ ( n − k + 1 ) / k ! n(n - 1) \cdots (n - k + 1) / k! n ( n − 1 ) ⋯ ( n − k + 1 ) / k ! k ≥ 0 k \ge 0 k ≥ 0 0 0 0
d. Show that
b n = 4 n π n 3 / 2 ( 1 + O ( 1 / n ) ) . b_n = \frac{4^n}{\sqrt{\pi}n^{3 / 2}} (1 + O(1 / n)). b n = π n 3/2 4 n ( 1 + O ( 1/ n )) .
a. A root with two subtree.
b.
B ( x ) 2 = ( b 0 x 0 + b 1 x 1 + b 2 x 2 + ⋯ ) 2 = b 0 2 x 0 + ( b 0 b 1 + b 1 b 0 ) x 1 + ( b 0 b 2 + b 1 b 1 + b 2 b 0 ) x 2 + ⋯ = ∑ k = 0 0 b k b 0 − k x 0 + ∑ k = 0 1 b k b 1 − k x 1 + ∑ k = 0 2 b k b 2 − k x 2 + ⋯
\begin{aligned}
B(x)^2 & = (b_0 x^0 + b_1 x^1 + b_2 x^2 + \cdots)^2 \\
& = b_0^2 x^0 + (b_0 b_1 + b_1 b_0) x^1 + (b_0 b_2 + b_1 b_1 + b_2 b_0) x^2 + \cdots \\
& = \sum_{k = 0}^0 b_k b_{0 - k} x^0 + \sum_{k = 0}^1 b_k b_{1 - k} x^1 + \sum_{k = 0}^2 b_k b_{2 - k} x^2 + \cdots
\end{aligned}
B ( x ) 2 = ( b 0 x 0 + b 1 x 1 + b 2 x 2 + ⋯ ) 2 = b 0 2 x 0 + ( b 0 b 1 + b 1 b 0 ) x 1 + ( b 0 b 2 + b 1 b 1 + b 2 b 0 ) x 2 + ⋯ = k = 0 ∑ 0 b k b 0 − k x 0 + k = 0 ∑ 1 b k b 1 − k x 1 + k = 0 ∑ 2 b k b 2 − k x 2 + ⋯
x B ( x ) 2 + 1 = 1 + ∑ k = 0 0 b k b 1 − 1 − k x 1 + ∑ k = 0 2 b k b 2 − 1 − k x 3 + ∑ k = 0 2 b k b 3 − 1 − k x 2 + ⋯ = 1 + b 1 x 1 + b 2 x 2 + b 3 x 3 + ⋯ = b 0 x 0 + b 1 x 1 + b 2 x 2 + b 3 x 3 + ⋯ = ∑ n = 0 ∞ b n x n = B ( x ) .
\begin{aligned}
xB(x)^2 + 1 & = 1 + \sum_{k = 0}^0 b_k b_{1 - 1 - k} x^1 + \sum_{k = 0}^2 b_k b_{2-1 - k} x^3 + \sum_{k = 0}^2 b_k b_{3-1 - k} x^2 + \cdots \\
& = 1 + b_1 x^1 + b_2 x^2 + b_3 x^3 + \cdots \\
& = b_0 x^0 + b_1 x^1 + b_2 x^2 + b_3 x^3 + \cdots \\
& = \sum_{n = 0}^\infty b_n x^n \\
& = B(x).
\end{aligned}
x B ( x ) 2 + 1 = 1 + k = 0 ∑ 0 b k b 1 − 1 − k x 1 + k = 0 ∑ 2 b k b 2 − 1 − k x 3 + k = 0 ∑ 2 b k b 3 − 1 − k x 2 + ⋯ = 1 + b 1 x 1 + b 2 x 2 + b 3 x 3 + ⋯ = b 0 x 0 + b 1 x 1 + b 2 x 2 + b 3 x 3 + ⋯ = n = 0 ∑ ∞ b n x n = B ( x ) .
x B ( x ) 2 + 1 = x ⋅ 1 4 x 2 ( 1 + 1 − 4 x − 2 1 − 4 x ) + 1 = 1 4 x ( 2 − 2 1 − 4 x ) − 1 + 1 = 1 2 x ( 1 − 1 − 4 x ) = B ( x ) .
\begin{aligned}
x B(x)^2 + 1 & = x \cdot \frac{1}{4x^2} (1 + 1 - 4x - 2\sqrt{1 - 4x}) + 1 \\
& = \frac{1}{4x} (2 - 2\sqrt{1 - 4x}) - 1 + 1 \\
& = \frac{1}{2x} (1 - \sqrt{1 - 4x}) \\
& = B(x).
\end{aligned}
x B ( x ) 2 + 1 = x ⋅ 4 x 2 1 ( 1 + 1 − 4 x − 2 1 − 4 x ) + 1 = 4 x 1 ( 2 − 2 1 − 4 x ) − 1 + 1 = 2 x 1 ( 1 − 1 − 4 x ) = B ( x ) .
c. Let f ( x ) = 1 − 4 x f(x) = \sqrt{1 - 4x} f ( x ) = 1 − 4 x
2 ⋅ ( 1 ⋅ 2 ) ⋅ ( 3 ⋅ 2 ) ⋅ ( 5 ⋅ 2 ) ⋯ = 2 k ⋅ ∏ i = 0 k − 2 ( 2 k + 1 ) = 2 k ⋅ ( 2 ( k − 1 ) ) ! 2 k − 1 ( k − 1 ) ! = 2 ( 2 ( k − 1 ) ) ! ( k − 1 ) ! .
\begin{aligned}
2 \cdot (1 \cdot 2) \cdot (3 \cdot 2) \cdot (5 \cdot 2) \cdots
& = 2^k \cdot \prod_{i = 0}^{k - 2} (2k + 1) \\
& = 2^k \cdot \frac{(2(k - 1))!}{2^{k - 1}(k - 1)!} \\
& = \frac{2(2(k - 1))!}{(k - 1)!}.
\end{aligned}
2 ⋅ ( 1 ⋅ 2 ) ⋅ ( 3 ⋅ 2 ) ⋅ ( 5 ⋅ 2 ) ⋯ = 2 k ⋅ i = 0 ∏ k − 2 ( 2 k + 1 ) = 2 k ⋅ 2 k − 1 ( k − 1 )! ( 2 ( k − 1 ))! = ( k − 1 )! 2 ( 2 ( k − 1 ))! .
f ( x ) = 1 − 2 x − 2 x 2 − 4 x 3 − 10 x 4 − 28 x 5 − ⋯ . f(x) = 1 - 2x - 2x^2 - 4 x^3 - 10x^4 - 28x^5 - \cdots. f ( x ) = 1 − 2 x − 2 x 2 − 4 x 3 − 10 x 4 − 28 x 5 − ⋯ .
The coefficient is 2 ( 2 ( k − 1 ) ) ! k ! ( k − 1 ) ! \frac{2(2(k - 1))!}{k!(k - 1)!} k ! ( k − 1 )! 2 ( 2 ( k − 1 ))!
B ( x ) = 1 2 x ( 1 − f ( x ) ) = 1 + x + 2 x 2 + 5 x 3 + 14 x 4 + ⋯ = ∑ n = 0 ∞ ( 2 n ) ! ( n + 1 ) ! n ! x = ∑ n = 0 ∞ 1 n + 1 ( 2 n ) ! n ! n ! x = ∑ n = 0 ∞ 1 n + 1 ( 2 n n ) x .
\begin{aligned}
B(x) & = \frac{1}{2x}(1 - f(x)) \\
& = 1 + x + 2x^2 + 5x^3 + 14x^4 + \cdots \\
& = \sum_{n = 0}^\infty \frac{(2n)!}{(n + 1)!n!} x \\
& = \sum_{n = 0}^\infty \frac{1}{n + 1} \frac{(2n)!}{n!n!} x \\
& = \sum_{n = 0}^\infty \frac{1}{n + 1} \binom{2n}{n} x.
\end{aligned}
B ( x ) = 2 x 1 ( 1 − f ( x )) = 1 + x + 2 x 2 + 5 x 3 + 14 x 4 + ⋯ = n = 0 ∑ ∞ ( n + 1 )! n ! ( 2 n )! x = n = 0 ∑ ∞ n + 1 1 n ! n ! ( 2 n )! x = n = 0 ∑ ∞ n + 1 1 ( n 2 n ) x .
b n = 1 n + 1 ( 2 n n ) . b_n = \frac{1}{n + 1} \binom{2n}{n}. b n = n + 1 1 ( n 2 n ) .
d.
b n = 1 n + 1 ( 2 n ) ! n ! n ! ≈ 1 n + 1 4 π n ( 2 n / e ) 2 n 2 π n ( n / e ) 2 n = 1 n + 1 4 n π n = ( 1 n + ( 1 n + 1 − 1 n ) ) 4 n π n = ( 1 n − 1 n 2 + n ) 4 n π n = 1 n ( 1 − 1 n + 1 ) 4 n π n = 4 n π n 3 / 2 ( 1 + O ( 1 / n ) ) .
\begin{aligned}
b_n & = \frac{1}{n + 1} \frac{(2n)!}{n!n!} \\
& \approx \frac{1}{n + 1} \frac{\sqrt{4 \pi n}(2n / e)^{2n}}{2 \pi n (n / e)^{2n}} \\
& = \frac{1}{n + 1} \frac{4^n}{\sqrt{\pi n} } \\
& = (\frac{1}{n} + (\frac{1}{n + 1} - \frac{1}{n})) \frac{4^n}{\sqrt{\pi n}} \\
& = (\frac{1}{n} - \frac{1}{n^2 + n}) \frac{4^n}{\sqrt{\pi n}} \\
& = \frac{1}{n} (1 - \frac{1}{n + 1}) \frac{4^n}{\sqrt{\pi n}} \\
& = \frac{4^n}{\sqrt{\pi}n^{3 / 2}} (1 + O(1 / n)).
\end{aligned}
b n = n + 1 1 n ! n ! ( 2 n )! ≈ n + 1 1 2 πn ( n / e ) 2 n 4 πn ( 2 n / e ) 2 n = n + 1 1 πn 4 n = ( n 1 + ( n + 1 1 − n 1 )) πn 4 n = ( n 1 − n 2 + n 1 ) πn 4 n = n 1 ( 1 − n + 1 1 ) πn 4 n = π n 3/2 4 n ( 1 + O ( 1/ n )) .