showcraft

回ys老，第一种非空情况，确实就是C（9,3），也就是等价于10个小孩中的9个空当，有三个小孩去占领。
第二种可以为空的情况复杂点，按照ross的方法，他还是利用了第一种，做了变量代换：
x1+x2+x3+x4=10，x1到x4各 ...
showcraft 发表于 2012-10-26 10:17

忽然发现，我这里出了个大bug，ross的方法中x1到x4并无各不相同的要求，我写错了。

showcraft

再作下总结吧，算是给第一章做个小结：

问题1：
对于正整数x1，x2，x3，x4，有x1+x2+x3+x4=10，求解向量（x1，x2，x3，x4）的个数。
这个比较好理解，可以认为等价于10个不可区分的球排成队列，中间空出9个空当，用3块
隔板去划分，答案为C（9,3）。
推广开来，x1+x2+x3+...+xr=n，解向量个数为C（n-1，r-1）。

问题2：
对于非负整数x1，x2，x3，x4，有x1+x2+x3+x4=10，求解向量（x1，x2，x3，x4）的个数
。
可以在一的基础上用变量代换的方法解决。
设y1=x1+1，y2=x2+1，...，yr=xr+1，则
y1+y2+y3...+yr=n+r，解向量个数为C（n+r-1，r-1）
其中的y1到yr大于等于1，等价于相应的x1到xr大于等于0。也可以这样考虑，即在n个不可
区分球的队列中任意再添加r个球，然后再划分r组，划好后每组至少有1个球，每组再拿去
1个球，即为所求答案。

问题3（前两问为Ross原书所载，此问为笔者扩充）：
对于正整数x1〈x2〈x3〈x4，有x1+x2+x3+x4=15，求解向量（x1，x2，x3，x4）的个数。
这次不展开了，直接推广到x1 + x2 + x3 +...+ xr = n的正整数解的组数，要求：x1〈x
2〈x3〈...<xr。
还是变量代换：
设y2=x2-x1，y3=x3-x2，...，yr=xr-x（r-1）（下标），y2到yr均为正整数，于是式子化
为
y2+y3+...+yr=xr-x1，而xr-x1的取值范围是关键
上限情况，x1=1，x2=2，...，x（r-1）=r-1，xr=m-r（r-1）/2，
此时xr-x1=m-1-r（r-1）/2
下限情况，设x1=a，x2=a+1，...，xr=a+r-1，全部相加有ra+r（r-1）/2=m，a=m/r-(r-1
)/2（若a非正整数，应就近取整），此时对应了，若a为整数，则下限为r-1，否则为r
确定了xr-x1的取值范围，令下限为正整数p，上限为正整数q，则对y2+y3+...+yr=xr-x1在
区间[p,q]上套用Ross的方法即可，答案为C（p-1，r-2）+C（p，r-2）+...+C（q-1，r-2
）
在本题中，m取15，则p为4，q为8，答案为C（3,2）+C（4,2）+...+C(8,2)，具体数字我就
不算了。

问题4：
对于各不相同的正整数x1，x2，x3，x4，有x1+x2+x3+x4=15，求解向量（x1，x2，x3，x4
）的个数。
所谓磨刀不误砍柴工，前人种树后人乘凉。推广到n，r的情况下，此问只需在第3问得出的
结果再乘以Pr，即r的全排列即可。

showcraft

sorry，问题3，问题4我完全想错了，某种划分情况下，不定方程是求不出正整数解的。
这个问题，我再考虑下，不好意思。

ys1937

**

    不好意思，似乎是在有意为难人了。
    对学生（也对老师）来说，没有标准答案的排组题，是在解天书。
    这四个题，我也是凭空想出来的，没有标准答案。
    2、 求不定方程 x1 + x2 + x3 + x4 = 10 的正整数解的组数，要求：x1〈x2〈x3〈x4 。
    解：只有一组解，即（1，2，3，4）；
    1、 求不定方程 x1 + x2 + x3 + x4 = 10 的正整数解的组数，但是要求：x1、 x2、x3、 x4 都不相等 ；
    解：由于要求“各不相同”，因此，只能是1、2、3、4四个数，所以，答案是 A（4，4）。
    后面二个问题较难，容再思量。
    原因是，题1、2的解法属“SARS”类，无法推广到题3、4。
    难就难在“各不相同”。

ys1937

**

    下面是问题3、4的一种解法，仍然是掰手指式的非典型解法，并不理想。
    4、 求不定方程 x1 + x2 + x3 + x4 = 15 的正整数解的组数，要求：x1〈x2〈x3〈x4 。
    解：X1 从最小数开始计算：
    （1，2，3，9）
    （1，2，4，8）
    （1，2，5，7）
    （1，2，6，？）（不可能了）
    （1，3，4，7）
    （1，3，5，6）
    （1，3，6，？）（不可能了）
    （1，4，5，？）（不可能了）
    （2，3，4，6）
    （2，3，5，？）（不可能了）
    X1 不可能取3，因为：3 + 4 + 5 + 6 已经大于15了。
    所以，此题答案是：6

    3、 求不定方程 x1 + x2 + x3 + x4 = 15 的正整数解的组数，但是要求：x1、 x2、x3、 x4 都不相等 ；
    解：由问题 4中的每组解，来个全排列，就得到问题 3的所有解。
    所以，此题答案是：6*A（4，4）= 144

菜农

10# 菜农  

菜农前辈，我有拙见：没有认知，世界的存在对人类或其它动物而言是没有意义的。
psyzjs 发表于 2012-10-26 19:13

你这话，放之四海而皆准的。

其他动物，有没有认知？
这个问题在燕谈争得一塌糊涂。

psyzjs

你这话，放之四海而皆准的。

其他动物，有没有认知？
这个问题在燕谈争得一塌糊涂。
菜农 发表于 2012-10-28 11:24

不知原帖何处？谢谢。

showcraft

多谢ys老指点。
下面继续：
假设那10名燕友是可互相区别的，将他们划分到4个不可区分的队伍中去，每队非空，求划分方案数。如果能推广位n名可互相区别的燕友划分到m个不可区分的非空队伍中去的方案数，则更佳。
比如说，就以3人划为2队为例，老程，菜农，大树三位互相之间当然可以区分，如果队伍之间也可区分，则老程菜农到A队，大树到B队，与老程菜农到B队，大树到A队是两种方案。但现在队伍不可区分，只需要知道老程菜农一队，大树一队，即可。

psyzjs

多谢ys老指点。
下面继续：
假设那10名燕友是可互相区别的，将他们划分到4个不可区分的队伍中去，每队非空，求划分方案数。如果能推广位n名可互相区别的燕友划分到m个不可区分的非空队伍中去的方案数，则更佳。
比 ...
showcraft 发表于 2012-10-30 11:36

这思想并不奇怪啊，玻尔兹曼的统计物理学不就是这样子的吗？

ys1937

    1、 假设那10名燕友是可互相区别的，将他们划分到 4个不可区分的队伍中去，每队非空，求划分方案数。
    2、 如果能推广位 n名可互相区别的燕友划分到 m个不可区分的非空队伍中去的方案数，则更佳。
showcraft 发表于 2012-10-30 11:36

**

    我只能用最笨的方法来解决第一个问题，而且这一解法无法解决第二个问题。
    这一方法就是“非典型”（SARS式的）的“掰手指（加脚指）的方法。
    我的推理方法分三段进行：统一的假设是：这四个组的人数分别是X1、X2、X3、X4。
    01、 X1 ≤ X2 ≤ X3 ≤ X4，且四数之和为10，并且这十个元素是不可区分的；
    02、 四数之和为10，并且这10个元素是不可区分的；
    03、 四数之和为10，且十个元素是可区分的——即我们要解决的问题。

问题01的解决

    有八种分组方法，它们是：
    （1，1，1，7）
    （2，2，2，4）
    （1，3，3，3）
    （1，1，4，4）
    （2，2，3，3）
    （1，1，2，6）
    （1，1，3，5）
    （1，2，2，5）
    （1，2，3，4）
    从上面的排列方法，可以看到，这八种分组法实际上分成四类：
    1、 有三组人数相同；
    2、 有二个二组人数相同；
    3、 有二组人数相同，另两组人数不同；
    4、 四组人数都不同。

ys1937

**

问题02的解决

    这就要分开四组分别讨论了。
    1、 有三组人数相同；
    实际是就是那单一不同的数放在那个位置上了。
    因此，问题01中每一个分组法又可以衍生成四组。
    共计 3*4 = 12 组。

    2、 有二个二组人数相同；
    实际上就是一个数怎样放在二个位置上，因此有 C（4，2）= 6 种衍生法。
    共计 2*6 = 12组。

    3、 有二组人数相同，另两组人数不同；
    一个数要放在二个位置上，另外二个数又分别放在两个不同的位置上。
    有 C（4，2）*A（2，2）= 12种衍生法。
    所以共有 3*12 = 36组。

    4、 四组人数都不同。
    四个不同的数放在四个不同的位置上，是一个全排列：A（4，4）= 24组。

    四个数字合起来是：12  + 12 + 36 + 24 = 84。
    这也就是一开始就得到的 C（9，3），即三个小孩去插入九个空档的划分法。

ys1937

**

问题03的答案

    （1，1，1，7）：4*A（10，3）
    （2，2，2，4）：4*C（10，2）*C（8，2）*C（6，2）
    （1，3，3，3）：4*C（10，3）*C（7，3）*C（4，3）
    （1，1，4，4）：6*A（10，2）*C（8，4）
    （2，2，3，3）：6*C（10，2）*C（8，2）*C（6，3）
    （1，1，2，6）：12*A（10，2）*C（8，2）
    （1，1，3，5）：12*A（10，2）*C（8，3）
    （1，2，2，5）：12*C（10，1）*C（9，2）*C（7，2）
    （1，2，3，4）：24*C（10，1）*C（9，2）*C（7，3）
    把右边这些数加起来，就是答案。
    请示 S版，是否有巧妙的解法？

showcraft

回ys老，这其实就是第二类斯特灵数。偷懒了，就wiki直接转一段
http://zh.wikipedia.org/wiki/%E6%96%AF%E7%89%B9%E7%81%B5%E6%95%B0
第二类Stirling数是个元素的集定义k个等价类的方法数目。常用的表示方法有。
换个较生活化的说法，就是有个人分成组的分组方法的数目。例如有甲、乙、丙、丁四人，若所有人分成1组，只有所有人在同一组这个方法，因此；若所有人分成4组，只可以人人独立一组，因此；若分成2组，可以是甲乙一组、丙丁一组，或甲丙一组、乙丁一组，或甲丁一组、乙丙一组，或其中三人同一组另一人独立一组，即是：

• {A,B},{C,D}
• {A,C},{B,D}
• {A,D},{B,C}
• {A},{B,C,D}
• {B},{A,C,D}
• {C},{A,B,D}
• {D},{A,B,C}

因此。

• 给定，有递归关系
• 
• 
• 
• 

是二项式系数，B_n是贝尔数。

showcraft

也可以看看这里
http://hi.baidu.com/greenwicher/item/078845c5dbbcfd54bdef69c8
p1210 盒子与球 斯特灵数
stirling数　　将n个有区别的球的球放入k个无标号的盒子中( n>=k>=1，且盒子不允许为空)的方案数就是stirling数.(即含 n 个元素的集合划分为 k 个集合的情况数)
　　递推公式:
　　S(n,0) = 0
　　S(n,1) = 1 (k = 1)
　　S(n,n) = 1
　　S(n,k) = 0 (k > n)
　　S(n,k) = S(n-1,k-1)+k*S(n-1,k) (n >= k >= 2)
　　分析：设有n个不同的球，分别用b1,b2,...,bn表示。从中取出一个球bn，bn的放法有以下两种：
　　1.bn独占一个盒子，那么剩下的球只能放在k-1个盒子里，方案数为S（n-1,k-1);
　　2.bn与别的球共占一个盒子，那么可以将b1,b2,...,bn-1这n-1个球放入k个盒子里，然后将bn放入其中一个盒子中，方案数为k*S(n-1,k).

showcraft

继续：
12位高矮不同的燕友排成两排，每排6人且必须是从矮到高排列，而且第二排比对应的第一排的人高。问排列方式有多少种？

ys1937

**

    等价的问题是：
    把 1到12这十个数分成两组：（X1、X2、X3、X4、X5、X6）、（Y1、Y2、Y3、Y4、Y5、Y6），要求是：
    1、 X1 ‹ X2 ‹  X3 ‹  X4 ‹  X5 ‹  X6;
    2、 Y1 ‹  Y2 ‹  Y3 ‹  Y4 ‹  Y5 ‹  Y6；
    3、 Xn ‹  Yn，n = 1，2，3，4，5，6

    S 版提的这个问题里有一点没交代清楚：只说“分成两组”，应加上“每组六人”。

    先解决一个小点：X1 = 1，Y6 = 12
    理由是：X1是所有 X系数中最小的；Y1是所有 Y系数中最小的；而且 X1小于Y1；结论是X1是所有十二数中最小的。
    同理，Y6应是所有十二数中最大数。

showcraft

首先，欢迎晓梦兄，分析的都对，只是结合起来肯定要复杂些。
其次，ys老提醒的对，我已经改了，您等价的也没问题。
再考虑考虑吧，确实不容易的题目，谁让ys老先动用了大规模杀伤性武器呢？
咱只好进口点飞毛腿反击了，呵呵，晚点我再公布答案。

showcraft

晓梦兄的答案是正确的，不知道你用的什么语言，方便的话，你可以贴下代码。
再等等ys老，呵呵。或者你有啥概率方面的趣题也可以拿出来，大家一块看看。

ys1937

**

     嘿，别等了，在看电视《火兰刀锋》呢。
    还没学到周伯通的一心二用功夫啊！

showcraft

这道题和卡特兰数相关。依然偷懒，转现成的。

http://topic.csdn.net/u/20091017 ... 9-d8d0b9fcaada.html
作者:baihacker
来源:http://hi.baidu.com/feixue http://hi.csdn.net/baihacker

问题描述:
12个高矮不同的人,排成两排,每排必须是从矮到高排列,而且第二排比对应的第一排的人高,问排列方式有多少种?
这个笔试题,很YD,因为把某个递归关系隐藏得很深.

问题分析:
我们先把这12个人从低到高排列,然后,选择6个人排在第一排,那么剩下的6个肯定是在第二排.
用0表示对应的人在第一排,用1表示对应的人在第二排,那么含有6个0,6个1的序列,就对应一种方案.
比如000000111111就对应着
第一排:0 1 2 3 4 5
第二排:6 7 8 9 10 11
010101010101就对应着
第一排:0 2 4 6 8 10
第二排:1 3 5 7 9 11
问题转换为,这样的满足条件的01序列有多少个.
观察1的出现,我们考虑这一个出现能不能放在第二排,显然,在这个1之前出现的那些0,1对应的人
要么是在这个1左边,要么是在这个1前面.而肯定要有一个0的,在这个1前面,统计在这个1之前的0和1的个数.
也就是要求,0的个数大于1的个数.
OK,问题已经解决.
如果把0看成入栈操作,1看成出栈操作,就是说给定6个元素,合法的入栈出栈序列有多少个.
这就是catalan数,这里只是用于栈,等价地描述还有,二叉树的枚举,多边形分成三角形的个数,圆括弧插入公式中的
方法数,其通项是c(2n, n)/(n+1).

在<<计算机程序设计艺术>>,第三版,Donald E.Knuth著,苏运霖译,第一卷,508页,给出了证明:
问题大意是用S表示入栈,X表示出栈,那么合法的序列有多少个(S的个数为n)
显然有c(2n, n)个含S,X各n个的序列,剩下的是计算不允许的序列数(它包含正确个数的S和X,但是违背其它条件).
在任何不允许的序列中,定出使得X的个数超过S的个数的第一个X的位置.然后在导致并包括这个X的部分序列中,以
S代替所有的X并以X代表所有的S.结果是一个有(n+1)个S和(n-1)个X的序列.反过来,对一垢一种类型的每个序列,我们都能
逆转这个过程,而且找出导致它的前一种类型的不允许序列.例如XXSXSSSXXSSS必然来自SSXSXXXXXSSS.这个对应说明,不允许
的序列的个数是c(2n, n-1),因此an = c(2n, n) - c(2n, n-1).[Comptes Rendus Acad.Sci.105(Paris, 1887), 436~437]

验证:
其中F表示前排,B表示后排,在枚举出前排的人之后,对应的就是后排的人了,然后再验证是不是满足后面的比前面对应的人高的要求.
C/C++ code
#include <iostream>
using namespace std;

int bit_cnt(int n)
{
    int result = 0;
    for (; n; n &= n-1, ++result);
    return result;
}

int main()
{
    int F[6], B[6];
    int ans = 0;
    for (int state = 0; state < (1 << 12); ++state) if (bit_cnt(state) == 6)
    {
        int i = 0, j = 0;
        for (int k = 0; k < 12; ++k) if (state&(1<<k)) F[i++] = k; else B[j++] = k;
        int ok = 1;
        for (int k = 0; k < 6; ++k) if (B[k] < F[k]) {ok = 0; break;}
        ans += ok;
    }
    cout << ans << endl;
    return 0;
}

结果:132
而c(12, 6)/7 = 12*11*10*9*8*7/(7*6*5*4*3*2) = 132
注意:c(2n, n)/(n+1) = c(2n, n) - c(2n, n-1)

估计出题的人也读过<<计算机程序艺术>>吧.

PS:
另一个很YD的问题:
有编号为1到n(n可以很大,不妨在这里假定可以达到10亿)的若干个格子,从左到右排列.
在某些格子中有一个棋子,不妨设第xi格有棋子(1<=i<=k, 1<=k<=n)
每次一个人可以把一个棋子往左移若干步,
但是不能跨越其它棋子,也要保证每个格子至多只有一个棋子.
两个人轮流移动,移动不了的为输,问先手是不是有必胜策略.

ys1937

    所以符合45楼要求的是，C（12，6）- C（12，5）= 924-792 = 132
晓梦 发表于 2012-11-1 08:48

**

    1、 把1、2两个数分成两组，每组一个数；（X1）（Y1）；
    要求：X1 ? Y1。
    有多少种分法？
    答：1 种：
    （1）
    （2）

    2、 把1、2、3、4四个数分成两组，每组二个数；（X1，X2）（Y1，Y2）；
    要求：Xn ? Yn （n = 1, 2）
    有多少种分法？
    答：2 种。
    （1，2）          （1，3）
    （3，4）          （2，4）

    3、 把1、2、3、4、5、6六个数分成两组，每组三个数；（X1，X2，X3）（Y1，Y2，Y3）；
    要求：Xn ? Yn （n = 1, 2，3）
    有多少种分法？
    答：5 种。   
    我们分两轮进行分组：
    第一轮先每组放入二个数：
    （1，2）、（1，3）、（1，4）、（1，5）
    如果这四组都是可行的，那么，它们下面的第二组相应是：
    （1，2）、（1，3）、（1，4）、（1，5）
    （*，*）、（2，*）、（2，3）、（2，3）
    显然，后二组已经不符合要求了。
    因此，前二数只可能是：
    （1，2）              （1，3）
    （*，*）              （2，*）
    加入第三个数：
    （1，2）化为（1，2，3）、（1，2，4）、（1，2，5）
    （1，3）化为             （1，3，4）、（1，3，5）
        
    4、 把1、2、3、4、5、6、7、8八个数分成两组，每组四个数；
    要求：Xn ? Yn （n = 1, 2，3，4）
    有多少种分法？
    答：14种。
    继续“分化”：
    （1，2，3）化为（1，2，3，4）（1，2，3，5）（1，2，3，6）（1，2，3，7）
    （1，2，4）化为              （1，2，4，5）（1，2，4，6）（1，2，4，7）
    （1，2，5）化为                            （1，2，5，6）（1，2，5，7）
    （1，3，4）化为              （1，3，4，5）（1，3，4，6）（1，3，4，7）
    （1，3，5）化为                            （1，3，5，6）（1，3，5，7）

    5、 把1、2、3、4、5、6、7、8、9、10 十个数分成两组，每组五个数；
    要求：Xn ? Yn （n = 1, 2，3，4）
    有多少种分法？
    答：42种。
    （1，2，3，4）：（1，2，3，4，5）（1，2，3，4，6）（1，2，3，4，7）（1，2，3，4，8）（1，2，3，4，9）
    （1，2，3，5）：                 （1，2，3，5，6）（1，2，3，5，7）（1，2，3，5，8）（1，2，3，5，9）
    （1，2，3，6）：                                  （1，2，3，6，7）（1，2，3，6，8）（1，2，3，6，9）
    （1，2，3，7）：                                                   （1，2，3，7，8）（1，2，3，7，9）
    （1，2，4，5）：                 （1，2，4，5，6）（1，2，4，5，7）（1，2，4，5，8）（1，2，4，6，9）
    （1，2，4，6）：                                  （1，2，4，6，7）（1，2，4，6，8）（1，2，4，6，9）
    （1，2，4，7）：                                                   （1，2，4，7，8）（1，2，4，7，9）
    （1，2，5，6）：                                  （1，2，5，6，7）（1，2，5，6，8）（1，2，5，6，9）         
    （1，2，5，7）：                                                   （1，2，5，7，8）（1，2，5，7，9）
    （1，3，4，5）：                 （1，3，4，5，6）（1，3，4，5，7）（1，3，4，5，8）（1，3，4，5，9）                                    
    （1，3，4，6）：                                  （1，3，4，6，7）（1，3，4，6，8）（1，3，4，6，9）
    （1，3，4，7）：                                                   （1，3，4，7，8）（1，3，4，7，9）
    （1，3，5，6）：                                  （1，3，5，6，7）（1，3，5，6，8）（1，3，5，6，9）                                 
    （1，3，5，7）：                                                   （1，3，5，7，8）（1，3，5，7，9）
    6、 把1、2、3、4、5、6、7、8、9、10、11、12 十二个数分成两组，每组六个数；
    要求：Xn ? Yn （n = 1, 2，3，4）
    有多少种分法？
    答：48 + 42 + 42 = 132 种。
    （1，2，3，4，5）：第六数是（下同）6~11
    （1，2，3，4，6）：7~11
    （1，2，3，4，7）：8~11
    （1，2，3，4，8）：9~11
    （1，2，3，4，9）：10~11
    （1，2，3，5，6）：7~11
    （1，2，3，5，7）：8~11
    （1，2，3，5，8）；9~11
    （1，2，3，5，9）：10~11
    （1，2，3，6，7）：8~11
    （1，2，3，6，8）：9~11
    （1，2，3，6，9）：10~11
    （1，2，3，7，8）：9~11
    （1，2，3，7，9）：10~11        （6 + 5 + 4 + 3 + 2）+（5 + 4 + 3 + 2）+ （4 + 3 + 2）+ （3 + 2）= 48                                               
    （1，2，4，5，6）：7~11
    （1，2，4，5，7）：8~11
    （1，2，4，5，8）：9~11
    （1，2，4，6，9）：10~11
    （1，2，4，6，7）：8~11
    （1，2，4，6，8）：9~11
    （1，2，4，6，9）：10~11
    （1，2，4，7，8）：9~11
    （1，2，4，7，9）：10~11        （5 + 4 + 3 + 2）+ （4 + 3 + 2）+ （3 + 2）= 28
    （1，2，5，6，7）：8~11
    （1，2，5，6，8）：9~11
    （1，2，5，6，9）：10~11         
    （1，2，5，7，8）：9~11
    （1，2，5，7，9）：10~11        （4 + 3 + 2）+ （3 + 2）= 14
    （1，3，4，5，6）；7~11
    （1，3，4，5，7）：8~11
    （1，3，4，5，8）：9~11
    （1，3，4，5，9）：10~11                                    
    （1，3，4，6，7）：8~11
    （1，3，4，6，8）：9~11
    （1，3，4，6，9）：10~11
    （1，3，4，7，8）：9~11
    （1，3，4，7，9）：10~11        （5 + 4 + 3 + 2）+ （4 + 3 + 2）+ （3 + 2）= 28
    （1，3，5，6，7）：8~11
    （1，3，5，6，8）：9~11
    （1，3，5，6，9）：10~11                                 
    （1，3，5，7，8）：9~11
    （1，3，5，7，9）：10~11        （4 + 3 + 2）+ （3 + 2）= 14

    这样归纳，可以看到一些规律性的东西，也可以据此猜测把1~14分成两组，每组七数，并且符合要求…………的组数是多少。

showcraft

我在53楼的转帖已经很好的揭示了此问题的本质，答案为c(2n, n)/(n+1) = c(2n, n) - c(2n, n-1)。不知道晓梦兄有没有看到，或者对其中什么地方有不明白？当然我也只是看了答案思路后才恍然大悟，从白纸开始推导，没这个能力，呵呵。
我去翻阅了Knuth该书中所载，不允许的序列的个数是c(2n, n-1)，这个推导过程正是运用了D.Andre的反射原理，当然我没有搜到这个原理的具体内容。ys老的枚举，包括晓梦兄的思考，应该费了不少力气，枚举，或者说暴力法，当然有助于思考和发现规律，不过更重要的是探寻本质。比如本题的本质，便是卡特兰数以一种排列的形式的应用，明乎此，当可迎刃而解。
这个帖子当然是以Ross的《概率论基础教程》为主，但不会仅限于该书，事实上牵涉到该书内容的，我都会提到在书中何处找到，如果不提就代表其他出处，实际上我同时也在参阅布鲁迪的《组合数学》，Knuth的《具体数学》等。另外，我觉得关注本质内容即可，出处何方，其实殊途同归，意义不大，呵呵。

showcraft

http://zh.wikipedia.org/wiki/%E5%8D%A1%E5%A1%94%E5%85%B0%E6%95%B0
卡塔兰数维基百科，自由的百科全书


卡塔兰数是组合数学中一个常在各种计数问题中出现的数列。以比利时的数学家欧仁·查理·卡塔兰 (1814–1894)命名。
卡塔兰数的一般项公式为
前几项为 （OEIS中的数列A000108）: 1, 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, ...
[编辑]性质Cn的另一个表达形式为 所以，Cn是一个自然数；这一点在先前的通项公式中并不显而易见。这个表达形式也是André对前一公式证明的基础。(见下文的第二个证明。)
递推关系
它也满足
这提供了一个更快速的方法来计算卡塔兰数。
卡塔兰数的渐近增长为
它的含义是左式除以右式的商趋向于1当n → ∞。（这可以用n!的斯特灵公式来证明。）
所有的奇卡塔兰数Cn都满足。所有其他的卡塔兰数都是偶数。
[编辑]应用组合数学中有非常多.的组合结构可以用卡塔兰数来计数。在Richard P. Stanley的Enumerative Combinatorics: Volume 2一书的习题中包括了66个相异的可由卡塔兰数表达的组合结构。以下用Cn=3和Cn=4举若干例：

• Cn表示长度2n的dyck word的个数。Dyck word是一个有n个X和n个Y组成的字串，且所有的前缀字串皆满足X的个数大于等于Y的个数。以下为长度为6的dyck words:

XXXYYY XYXXYY XYXYXY XXYYXY XXYXYY

• 将上例的X换成左括号，Y换成右括号，Cn表示所有包含n组括号的合法运算式的个数:

((())) ()(()) ()()() (())() (()())

• Cn表示有n个节点组成不同构二叉树的方案数。下图中，n等于3。

证明：
令1表示进栈，0表示出栈，则可转化为求一个2n位、含n个1、n个0的二进制数，满足从左往右扫描到任意一位时，经过的0数不多于1数。显然含n个1、n个0的2n位二进制数共有个，下面考虑不满足要求的数目。
考虑一个含n个1、n个0的2n位二进制数，扫描到第2m+1位上时有m+1个0和m个1（容易证明一定存在这样的情况），则后面的0-1排列中必有n-m个1和n-m-1个0。将2m+2及其以后的部分0变成1、1变成0，则对应一个n+1个0和n-1个1的二进制数。反之亦然（相似的思路证明两者一一对应）。
从而。证毕。

• Cn表示所有在n × n格点中不越过对角线的单调路径的个数。一个单调路径从格点左下角出发，在格点右上角结束，每一步均为向上或向右。计算这种路径的个数等价于计算Dyck word的个数： X代表“向右”，Y代表“向上”。下图为n = 4的情况：

• Cn表示通过连结顶点而将n + 2边的凸多边形分成三角形的方法个数。下图中为n = 4的情况：

• Cn表示对{1, ..., n}依序进出栈的置换个数。一个置换w是依序进出栈的当S(w) = (1, ..., n), 其中S(w)递归定义如下：令w = unv，其中n为w的最大元素，u和v为更短的数列；再令S(w) = S(u)S(v)n，其中S为所有含一个元素的数列的单位元。

• Cn表示集合{1, ..., n}的不交叉划分的个数. 那么, Cn 永远不大于第n项贝尔数. Cn也表示集合{1, ..., 2n}的不交叉划分的个数，其中每个段落的长度为2。综合这两个结论，可以用数学归纳法证明 that all of the free cumulants of degree more than 2 of the Wigner semicircle law are zero. This law is important in free probability theory and the theory of random matrices.

• Cn表示用n个长方形填充一个高度为n的阶梯状图形的方法个数。下图为 n = 4的情况:

showcraft

不用客气。晓梦兄应该没受到飓风的影响吧？
不过你说不太概率，我觉得不妥。该题显然还是在组合数学的范畴内，当然用到了精妙的trick，而组合数学是概率的基础，我觉得还是挺概率的。
这段时间同时又在看Strang的linear algebra，所以ross的概率，我暂时搁浅在了第二章，等发现啥精彩的再说，呵呵。

showcraft

出道趣味题：
问题1.一个桶里各有黑白球100个，按照如下规则取球：
每次从桶中取出两个球，若这两个球同色，则再放入一个黑球，若异色，再放入一个白球。若干次后，最终桶里只剩下一个球，请问这个球是黑球的概率是多少？
问题2.如果是99个黑球，101个白球呢？

psyzjs

60# showcraft

1） 100% 黑
2） 100% 白
晓梦 发表于 2012-11-3 21:29

在这两种情况下，先验概率都发生了变化，后验概率怎么会不变呢？

林夕依寒

占个位置~

psyzjs

没那么复杂。无关先验后验。

只考虑白球： 1） 如果拿两个黑球，退回一个黑球，与白球无关。 2） 如果拿一黑一白，把白的退回，白球总数也不变。 3） 唯一影响白球数的情况是，拿两个白的，退回一个黑的，于是 ...
晓梦 发表于 2012-11-4 03:26

恐怕不对吧。

如晓梦所言，我们考虑终极状态，即，当桶里面只剩2个球时，若这2球全黑或全白，则最终球必是黑球，但若是一黑一白，最终球是白球；怎么算都不是100%的概率。

showcraft人呢？冒个泡啊。

psyzjs

补充一句，我之前所指的先验概率或先验信息是指，当桶内的黑白球的初始数量发生变化时，最终2球的颜色情况也会发生变化；意即，最终异色球的概率并非是频率论认为的1/3，而最终同色球概率也非频率论所认为的2/3.

老于，估计你读书时贝叶斯统计还被批判吧？指望你不上了。我得回去再看看书，再往深里讲。

showcraft

晓梦兄的分析完全正确，送上一朵小红花！
我再补充几句吧。正如晓梦兄所言，每次拿两球退一球操作后，白球数目或者不变或者减2，也就是说每次操作后白球数目的奇偶性与初始状态保持一致，那么最后一轮过后只剩下一个球，该种状况下白球数目的奇偶性与初始状态相等。所以在第一种情况下，留下0个白球（与初始100个白球的奇偶性一致），第二种情况下留下1个白球（与初始101个白球的奇偶性一致）
既然是趣味题，大树兄就不用想的太复杂了，呵呵。