10个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问有多少种排列方式?我们可以先把这10个人从低到高排列,然后,选择5个人排在第一排,那么剩下的5个人肯定是在第二排.用0表示对应的人在第一排,用1表示对应的人在第二排,那么含有5个0,5个1的序列,就对应一种方案.
比如0000011111就对应着第一排:0 1 2 3 4第二排:5 6 7 8 90101010101就对应着第一排:0 2 4 6 8第二排:1 3 5 7 9所以,看到问题相应的转换为,这样的满足条件的01序列有多少个.
观察规律我们发现1的出现前边必须有一个相应的0对应,所以从左到右的所有序列中0的个数要一直大于1的个数.那这种数列有多少种排列方式呢?那么我们从左往右扫描,第一次出现1的个数等于0的个数是第k位,那么在此之前,0的个数是大于1的个数的.在此之后,0的个数也是大于1的个数的.所以第k位0和1的个数第一次相等的排列有他们这两部分的个数相称的结果.那么所有的k有多少种,则把它们相加起来,就是最后的排列数.这是一个递归的问题.即a(n)=a(0)×a(n-1)+a(1)*a(n-2)+...+a(n-1)*a(0)
卡特兰数非常经典,很多现实的问题都是卡特兰数,如合法的入栈出栈序列有多少种就是卡特兰数,为什么呢?我们可以把0看成入栈操作,1看成出栈操作,即0的累计个数不小于1的排列有多少种.还有很多其他的问题都是卡特兰数,如二叉树的个数,有序树的个数,多边形分成三角形的个数等.
卡特兰数的通项是c(2n, n)/(n+1).
注意组合数学中的运算:A(m, n) = m! /(m-n)!, C(m, n) = A(m, n) / n! =m! / ((m-n)!*n!),因此卡特兰数的通项:
C(2n,n)/(n+1) = (2n!) / ((2n - n)! * n!) / (n + 1) = (2n!) / (n! * n!) / (n +1)
卡特兰数的问题应用:
圆周上有标号为1,2,3,4,......,2n的共计2n个点,这2n个点配对可连成n条弦,且这些弦两两不相交的方式数为卡特兰数Cn游乐园门票1元一张,每人限购一张.现在有10个小朋友排队购票,其中5个小朋友每人只有1元的钞票一张,另5个小朋友每人只有2元的钞票一张,售票员没有准备零钱.问:有多少种排队方法,使售票员总能找的开零钱?
甲乙两人比赛乒乓球,最后结果为20:20,问比赛过程中甲始终领先乙的计分情形的种数.
即甲在得到1分到19分的过程中始终领先乙,其种数是卡特兰数饭后,姐姐洗碗,妹妹把姐姐洗过的碗一个一个放进碗橱摞成一摞.一共有n个不同的碗,洗前也是摞成一摞的,也许因为小妹贪玩而使碗拿进碗橱不及时,姐姐则把洗过的碗摞在旁边,问:小妹摞起的碗有多少种可能的方式?
答:得数是第n个卡特兰数Cn.
·一个汽车队在狭窄的路面上行驶,不得超车,但可以进入一个死胡同去加油,然后再插队行驶,共有n辆汽车,问共有多少种不同的方式使得车队开出城去?
括号化问题.一个合法的表达式由()包围,()可以嵌套和连接,如(())()也是合法表达式;现在有 6 对(),它们可以组成的合法表达式的个数为矩阵连乘: P=a1×a2×a3×......×an,依据乘法结合律,不改变其顺序,只用括号表示成对的乘积,试问有几种括号化的方案?(h(n)种)
出栈次序问题.一个栈(无穷大)的进栈序列为1,2,3,..n,有多少个不同的出栈序列?类似:有2n个人排成一行进入剧场.入场费5元.其中只有n个人有一张5元钞票,另外n人只有10元钞票,剧院无其它钞票,问有多少中方法使得只要有10元的人买票,售票处就有5元的钞票找零?(将持5元者到达视作将5元入栈,持10元者到达视作使栈中某5元出栈)
将多边行划分为三角形问题.将一个凸N+2多边形区域分成三角形区域的方法数?类似:一位大城市的律师在她住所以北n个街区和以东n个街区处工作.每天她走2n个街区去上班.如果她从不穿越(但可以碰到)从家到办公室的对角线,那么有多少条可能的道路?类似:在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?给顶节点组成二叉树的问题.给定N个节点,能构成多少种不同的二叉树,(能构成h(N)个)Catalan数的解法Catalan数的组合公式为 Cn=C(2n,n) / (n+1);
7.此数的递归公式为 h(n ) =h(n-1)*(4*n-2) / (n+1)
卡特兰数真是一个神奇的数字,很多组合问题的数量都和它有关系,例如:
Cn= n对括号正确匹配组成的字符串数,例如 3对括号能够组成:
((())) ()(())()()() (())() (()())
Cn= n+1个数相乘,所有的括号方案数.例如, 4个数相乘的括号方案为:
Cn= 拥有 n+1 个叶子节点的二叉树的数量.例如 4个叶子节点的所有二叉树形态:
oCn=n*n的方格地图中,从一个角到另外一个角,不跨越对角线的路径数,例如, 4×4方格地图中的路径有:
oCn= n+2条边的多边形,能被分割成三角形的方案数,例如 6边型的分割方案有:
oCn= 圆桌周围有 2n个人,他们两两握手,但没有交叉的方案数.
下面是一些大公司的笔试题先来一道阿里巴巴的笔试题目:说16个人按顺序去买烧饼,其中8个人每人身上只有一张5块钱,另外8个人每人身上只有一张10块钱.烧饼5块一个,开始时烧饼店老板身上没有钱.16个顾客互相不通气,每人只买一个.问这16个人共有多少种排列方法能避免找不开钱的情况出现.
2012腾讯实习招聘笔试题在图书馆一共6个人在排队,3个还"面试宝典"一书,3个在借"面试宝典"一书,图书馆此时没有了面试宝典了,求他们排队的总数?