京东网站的建设目的,推广普通话于1982年写入,莱芜网络公司网站,塘沽网吧Catalan数应用 Catalan数应用原理卡特兰数经典应用括号化买票找零组合数与阶乘计算 卡特兰数又称卡塔兰数#xff0c;是组合数学中一个常出现在各种计数问题中的数列。由以比利时的数学家欧仁查理卡塔兰 (1814–1894)命名。 其前几项为 : 1, 2, 5, 14, 42, 132, 429, 1430,…Catalan数应用 Catalan数应用原理卡特兰数经典应用括号化买票找零组合数与阶乘计算 卡特兰数又称卡塔兰数是组合数学中一个常出现在各种计数问题中的数列。由以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。 其前几项为 : 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, … Catalan数是许多计数问题的最终形式。
原理
令h(0)1,h(1)1catalan数满足递推式 h(n)h(0)∗h(n−1)h(1)∗h(n−2)...h(n−1)∗h(0)(n2)h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2)另类递推公式: h(n)h(n−1)∗(4∗n−2)/(n1) h(n)=h(n-1)*(4*n-2)/(n+1)x(2nn)n1(n0,1,2,⋯) x = \dfrac{\binom{2n}{n}}{n+1} \quad(n=0,1,2,\cdots) h(n)(2nn)−(2nn−1)(n0,1,2,⋯)h(n)=\binom {2n}{n}-\binom{2n}{n-1}\quad(n=0,1,2,\cdots)
公式中(nm)n!(n−m)!\binom{n}{m}=\dfrac{n!}{(n-m)!}
卡特兰数经典应用
括号化 矩阵链乘 f(n)a1×a2×a3×⋯×anf(n)=a_1×a_2×a_3×\cdots×a_n依据乘法结合律不改变其顺序只用括号表示成对的乘积试问有几种括号化的方案 思路可以这样考虑首先通过括号化将公式分成两个部分然后分别对两个部分进行括号化。比如分成(a1)×(a2×a3×⋯×an)(a_1)×(a_2×a_3×\cdots×a_n)然后再对(a1)(a_1)和(a2×a3×⋯×an)(a_2×a_3×\cdots×a_n)分别括号化又如分成(a1×a2)×(a3×⋯×an)(a_1×a_2)×(a_3×\cdots×a_n)然后再对(a1×a2)(a_1×a_2)和 (a3×⋯×an)(a_3×\cdots×a_n)括号化;以此类推得公式 f(n)f(1)f(n−1)f(2)f(n−2)f(3)f(n−3)⋯f(n−1)f(1)f(n) = f(1)f(n-1)+f(2)f(n-2)+f(3)f(n-3)+\cdots+f(n-1)f(1)f(1) 1, f(2) 1, f(3) 2, f(4) 5,结合递归式不难发现f(n)h(n-1)。
买票找零
原题描述如下 2n个人排队买票其中n个人持50元n个人持100元。每张票50元且一人只买一张票。初始时售票处没有零钱找零。请问这2n个人一共有多少种排队顺序不至于使售票处找不开钱 思路队伍的序号标为0,1,…,2n-1,并把50元看作左括号100元看作右括号合法序列即括号能完成配对的序列。对于一个合法的序列第0个一定是左括号它必然与某个右括号配对记其位置为k。那么从1到k-1、k1到2n-1也分别是两个合法序列。那么k必然是奇数1到k-1一共有偶数个设k2i1。那么剩余括号的合法序列数为f(2i)*f(2n-2i-2)个。取i0到n-1累加即可。 f(2n)∑i0n−1f(2i)f(2n−2i−2)(n≥1)
f(2n)=\sum_{i=0}^{n-1} f(2i)f(2n-2i-2)\quad(n\geq1)另f(0)0f(0)=0,(00)0\binom{0}{0}=0,即可得 f(2n)(2nn)n1(n≥1)
f(2n)=\dfrac{\binom{2n}{n}}{n+1}\quad(n\geq1)公式推导如下出自从《编程之美》买票找零问题说起娓娓道来卡特兰数——兼爬坑指
构造生成函数:
g(x)h0x2h2x4⋯h2n−2x2nh2nx2n2⋯
g(x)=h_0x^2+h_2x^4+\cdots+h_{2n-2}x^{2n}+h_{2n}x^{2n+2}+\cdots 其中h2nf(2n)∑n−1i0f(2i)f(2n−2i−2)(n≥1)h_{2n}=f(2n)=\sum_{i=0}^{n-1} f(2i)f(2n-2i-2)\quad(n\geq1)生成函数平方
[g(x)]2h0x2h2x4⋯h2n−2x2nh2nx2n2⋯h20x4(h0h2h2h0)x6⋯(h0h2n−2h2h2n−4⋯h2n−2h0)x2n2⋯
\begin{eqnarray}
[g(x)]^2
[g(x)]2−g(x)h20x4−h2x4−h0x2
[g(x)]^2-g(x)=h_0^2x^4-h_2x^4-h_0x^2对于题目,假设h0f(0)0h_0=f(0)=0,则根据递推公式后续项全为0不合题意那么h0f(0)1h_0=f(0)=1,可以推出h2f(2)1h_2=f(2)=1,带入公式则有:
[g(x)]2−g(x)x20
[g(x)]^2-g(x)+x_2=0解得g(x)1±1−4x2−−−−−−√2g(x) = \dfrac{1 \pm \sqrt{1 - 4x^2}}{2} 根据生成函数的各项系数为非负舍去其一在根据
(1z)1/21∑n1∞(−1)n−1n×22n−1(2n−2n−1)zn
(1+z)^{1/2 } = 1+\sum_{n=1}^{\infty}\dfrac{(-1)^{n-1}}{n\times2^{2n-1}}\binom{2n-2}{n-1}z^n可以得到 g(x)∑n1∞1n(2n−2n−1)x2n
g(x) = \sum_{n=1}^{\infty}\dfrac{1}{n}\binom{2n-2}{n-1}x^{2n}则 h2n1n1(2nn)
h_{2n} = \dfrac{1}{n+1}\binom{2n}{n}组合数与阶乘计算
#!/usr/bin/env python
# -*- coding: utf-8 -*-import operatorfactorial function:阶乘函数;也可用math.factorial
def factorial(n):return reduce(operator.mul, range(1, int(n1)));combinational calculation:组合计算
def comb(n, m):return reduce(operator.mul, range(n-m1, n1)) / factorial(m)calculation on the arrangement:排列组合计算
def arr(n, m):return factorial(n) / factorial(n-m)if __name__ __main__:print factorial(10)print comb(6,3)print arr(10,7)
参考
http://www.cnblogs.com/wuyuegb2312/p/3016878.html
