5. 卡特兰数(Catalan)公式、证明、代码、典例. |
您所在的位置:网站首页 › 卡特的R怎么用 › 5. 卡特兰数(Catalan)公式、证明、代码、典例. |
1. 定义
卡特兰数(卡塔兰数),英文名Catalan number,是组合数学中一个常出现在各种计数问题中出现的数列。 其前几项为(从第零项开始) : C0 = 1, C1 = 1, C2 = 2, C3 = 5, C4 = 14, C5 = 42, C6 = 132, C7 = 429, C8 = 1430, C9 = 4862, C10 = 16796, C11 = 58786, C12 = 208012, C13 = 742900, C14 = 2674440, C15 = 9694845, C16 = 35357670, C17 = 129644790, C18 = 477638700, C19 = 1767263190, C20 = 6564120420, ... 2. 公式通项公式1: C n = 1 1 + n ( 2 n n ) = 1 1 + n C 2 n n = ( 2 n ) ! ( n + 1 ) ! n ! C_n=\frac{1}{1+n}{2n \choose n}=\frac{1}{1+n}C_{2n}^n=\frac{(2n)!}{(n+1)!n!} Cn=1+n1(n2n)=1+n1C2nn=(n+1)!n!(2n)! 通项公式2: C n = 1 n + 1 ∑ i = 0 n ( n i ) 2 = 1 n + 1 ∑ i = 0 n ( C n i ) 2 C_n=\frac{1}{n+1}\sum_{i=0}^n{n \choose i}^2=\frac{1}{n+1}\sum_{i=0}^n(C_n^i)^2 Cn=n+11∑i=0n(in)2=n+11∑i=0n(Cni)2 递推公式1: C n + 1 = 2 ( 2 n + 1 ) n + 2 C n C_{n+1}=\frac{2(2n+1)}{n+2}C_n Cn+1=n+22(2n+1)Cn 且 C 0 = 1 C_0=1 C0=1 递推公式2: C n + 1 = ∑ i = 0 n C i C n − i C_{n+1}=\sum_{i=0}^{n}C_iC_{n-i} Cn+1=∑i=0nCiCn−i 且 C 0 = 1 C_0=1 C0=1 且 n ; = 0 n;=0 n>=0 性质: C n = ( 2 n n ) − ( 2 n n − 1 ) = C 2 n n − C 2 n n − 1 C_n={2n \choose n}-{2n \choose n-1}=C_{2n}^n-C_{2n}^{n-1} Cn=(n2n)−(n−12n)=C2nn−C2nn−1 渐近增长: C n ∼ 4 n n 3 2 π C_n\sim\frac{4^n}{n^{\frac{3}{2}}\sqrt{\pi}} Cn∼n23π 4n 3. Catalan公式推导我们根据递推公式2: C n + 1 = ∑ i = 0 n C i C n − i C_{n+1}=\sum_{i=0}^{n}C_iC_{n-i} Cn+1=∑i=0nCiCn−i 且 C 0 = 1 C_0=1 C0=1 且 n ; = 0 n;=0 n>=0 可以得到这样一个函数: h n = ∑ k = 1 n − 1 h k h n − k h_n=\sum_{k=1}^{n-1}h_kh_{n-k} hn=∑k=1n−1hkhn−k 且 n ; = 2 n;=2 n>=2 由于这个递推关系不是线性的, h n h_n hn并不依赖于其前面的某个固定值,而依赖于前面的所有值,所以递推公式2就用不上了。 不妨令生成函数: g ( x ) = h 1 x + h 2 x 2 + h 3 x 3 + … … + h n x n + … … g(x)=h_1x+h_2x^2+h_3x^3+……+h_nx^n+…… g(x)=h1x+h2x2+h3x3+……+hnxn+…… 将g(x)与自己相乘: [ g ( x ) ] 2 = h 1 2 x 1 2 + ( h 1 h 2 + h 2 h 1 ) x 3 + ( h 1 h 3 + h 2 h 2 + h 3 h 1 ) x 4 + … … + ( h 1 h n − 1 + h 2 h n − 2 + … … + h n − 1 h 1 ) x n + … … [g(x)]^2=h_1^2x_1^2+(\color{fuchsia}h_1h_2+h_2h_1\color{black})x^3+(\color{red}h_1h_3+h_2h_2+h_3h_1\color{black})x^4+……+(h_1h_{n-1}+h_2h_{n-2}+……+h_{n-1}h_1)x^n+…… [g(x)]2=h12x12+(h1h2+h2h1)x3+(h1h3+h2h2+h3h1)x4+……+(h1hn−1+h2hn−2+……+hn−1h1)xn+…… 又根据卡特兰数前两项均为1,即 h 1 = h 2 = 1 h_1=h_2=1 h1=h2=1,以及上面得到的 h n h_n hn的递推关系代入得到: [ g ( x ) ] 2 = h 2 x 2 + h 3 x 3 + h 4 x 4 + … … + h n x n + … … = g ( x ) − h 1 x = g ( x ) − x [g(x)]^2=h_2x^2+h_3x^3+h_4x^4+……+h_nx^n+……=g(x)-\color{blue}h_1x\color{black}=g(x)-x [g(x)]2=h2x2+h3x3+h4x4+……+hnxn+……=g(x)−h1x=g(x)−x 于是有: [ g ( x ) ] 2 − g ( x ) + x = 0 [g(x)]^2-g(x)+x=0 [g(x)]2−g(x)+x=0 解得: g 1 ( x ) = 1 + 1 − 4 x 2 g_1(x)=\frac{1+\sqrt{1-4x}}{2} g1(x)=21+1−4x g 2 ( x ) = 1 − 1 − 4 x 2 g_2(x)=\frac{1-\sqrt{1-4x}}{2} g2(x)=21−1−4x 由g(x)的定义知道 g ( 0 ) = 0 g(0)=0 g(0)=0,验证上述根只有 g 2 ( x ) g_2(x) g2(x)成立,所以生成函数: g ( x ) = g 2 ( x ) = 1 − 1 − 4 x 2 = 1 2 − 1 2 ( 1 − 4 x ) 1 / 2 g(x)=g_2(x)=\frac{1-\sqrt{1-4x}}{2}=\frac{1}{2}-\frac{1}{2}(1-4x)^{1/2} g(x)=g2(x)=21−1−4x =21−21(1−4x)1/2 根据牛顿二项式定理: ( 1 + z ) 1 2 = 1 + ∑ n = 1 ∞ ( − 1 ) n − 1 n ∗ 2 2 n − 1 ( 2 n − 2 n − 1 ) z n \begin{aligned} (1+z)^{\frac{1}{2}} ;= 1+\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{n*2^{2n-1}}{2n-2\choose n-1} z^n\end{aligned} (1+z)21=1+n=1∑∞n∗22n−1(−1)n−1(n−12n−2)zn 将g(x)中的项展开: ( 1 − 4 x ) 1 2 = 1 + ∑ n = 1 ∞ ( − 1 ) n − 1 n ∗ 2 2 n − 1 ( 2 n − 2 n − 1 ) ( − 4 x ) n = 1 + ∑ n = 1 ∞ ( − 1 ) n − 1 n ∗ 2 2 n − 1 ( 2 n − 2 n − 1 ) 2 2 n x n = 1 − ∑ n = 1 ∞ 2 n ( 2 n − 2 n − 1 ) x n = 1 − 2 ∑ n = 1 ∞ 1 n ( 2 n − 2 n − 1 ) x n ( ∣ x ∣ ; 1 4 ) \begin{aligned} (1-4x)^{\frac{1}{2}} ;= 1+\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{n*2^{2n-1}}{2n-2\choose n-1}(-4x)^n\\ ;= 1+\sum_{n=1}^{\infty}\frac{(-1)^{n-1}}{n*2^{2n-1}}{2n-2\choose n-1}2^{2n}x^n \\ ;= 1-\sum_{n=1}^{\infty}\frac{2}{n}{2n-2\choose n-1}x^n\\ ;= 1-2\sum_{n=1}^{\infty}\frac{1}{n}{2n-2\choose n-1}x^n ;(|x|;\frac{1}{4})\end{aligned} (1−4x)21=1+n=1∑∞n∗22n−1(−1)n−1(n−12n−2)(−4x)n=1+n=1∑∞n∗22n−1(−1)n−1(n−12n−2)22nxn=1−n=1∑∞n2(n−12n−2)xn=1−2n=1∑∞n1(n−12n−2)xn(∣x∣=1) 即: h n = 1 1 + n ( 2 n n ) h_n=\frac{1}{1+n}{2n \choose n} hn=1+n1(n2n), ( n ; = 0 ) (n;=0) (n>=0) 4. 卡特兰数的代码实现 //函数功能: 计算Catalan的第n项 //函数参数: n为项数 //返回值: 第n个Catalan数 int Catalan(int n) { if(n |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |