|
|
gameludere.com/2020/02/03/euler-polygon-triangulation-problem有类似的推导。希望对你有帮助
\[ E_{n}= E_{2}E_{n-1} + E_{3}E_{n-2} + \cdots + E_{n-1}E_{2}\]where we place for uniformity \(E_{2} = 1 \). This recurrence formula was introduced by Segner in 1758.
Now let’s compute the generating function of the numbers \(E_ {n} \):
\[ F(x) = E_{0} + E_{1}\cdot x + E_{2} \cdot x^2 + E_{3}\cdot x^{3}+ \cdots \]where \(E_{0} = E_{1} = 0 \).
If we calculate the square of the \(F (x) \), with the product rule between two polynomials, we have:
\[ (F(x))^{2} = E_{3}\cdot x^{4} + E_{4}\cdot x^{5} + E_{5} \cdot x^{6} + \cdots\]by virtue of the recurrence equation satisfied by the coefficients \(E_ {n} \). With simple steps we can write the functional equation satisfied by the function \(F (x) \):
\[ F(x)^2 – xF(x) + x^{3} = 0 \]The initial conditions are \(F (0) = 0 \) and \(F’ (0) = 0 \), where the symbol \(F’ (0) \) denotes the derivative calculated at the point \(x = 0\). Solving with respect to \(F (x) \) and taking into account the initial conditions, we find the following solution (the other with the positive sign is discarded):
\[F(x)= x \left(\frac{1- \sqrt{1- 4x}}{2}\right)\]We now use the Taylor-McLaurin series development of the function \(\sqrt{1-4x} \), that is Newton’s binomial formula, valid for \(| x | <1 \) and for every real number \(\alpha \):
\[\begin{array}{l} (1+t)^{\alpha} &= \sum\limits_{k=0}^{\infty} \dbinom{\alpha}{k} t^{k} \\ &= 1 + \alpha t + \dfrac{\alpha \cdot (\alpha -1)t^{2}}{2!}+ \dfrac{\alpha \cdot (\alpha -1)(\alpha -2)t^{3}}{3!} + \cdots \\\end{array}\]In our case \(\alpha = \frac{1}{2}\) and \(t = -4x \). The binomial coefficient \(\dbinom{\frac {1}{2}}{n} \) has the following expression:
\[\dbinom{\frac {1}{2}}{n} =\frac{\left(\frac{1}{2}\right)\left(\frac{-1}{2}\right)\left(\frac{-3}{2}\right) \cdots \left(\frac{-(2n-3)}{2 }\right)}{n!}=\frac{(-1)^{n-1}}{2^{2n-1}n}\binom{2n-2}{n-1}\]where we used the following formula, which is easily proved by the induction method:
\[ 1 \cdot 3 \cdot 5 \cdots \cdot (2n-1)= \frac {(2n)!}{2^{n}n!}\]Continuing we have:
\[\binom {\frac {1}{2}}{n}(-4)^{n}=\left(\frac{-2}{n}\right)\binom {2n-2}{n-1}\]Finally, putting together what we have found, we have that the coefficient of the power \(x^{n}\) in the generating function \(F (x) \) is:
\[ E(n)=\frac {1}{n-1} \binom {2n-4}{n-2}\] |
|
hbghlyj
发表于 2024-10-6 20:05
