昨天看到一道某公司三面的概率题，本质是排列组合，于是乎打算回顾下排列组合：

用C(n,m)表示从n个不同的物品选择m个的选法，n>=m combination

用P(n,m)表示从n个不同的物品选择m个进行排列的选法，n>=m permutation

昨天看到一道面试题，说是概率，其实本质就是求样本空间数的排列组合，和事件数排列组合，然后比一下，本质还是排列组合，当然如果你比较敏锐，直接用概率来算，也是可以的，而且更快

54张扑克牌均分成3堆，则大小王在一堆的概率？

样本空间数 C(54,18)*C(36,18)*C(18,18)/P(3,3)

上面显而易见，为何要除以P(3,3) 我总是习惯A(3,3)= =还是受以前的习惯？

因为三堆大小相同，你第一次选择的时候，不知道是哪一堆，或者更通俗的例子，1-6 均分3堆，12,34,56和34,12,56其实是一种，但在分子的数种算了两次，由于三个可以排列，即P(3,3)，所以除以它。

如果不一样呢？ 1-7分3,2,2三堆，C(7,3)C(4,2)C(2,2)/P(2,2)，因为三个数和其他不同的，后面要除以P(2,2),例如123,45,67 123,67,45是一个，但是在里面算了两次，

因此我们来看大小王在一堆事件数。

C(2,2)C(52,16)C(36,18)C(18,18)/P(2,2), 类比前面，从52个选16个陪在大小王边上，之间是没有重复的，不管三堆怎么换(而之前的6个分三堆不一样，第一次选12,后面34,56和第一次34，后面12,56是一种，然而在公式里算重了) 而后面

是两堆一样的，可能重，故除以P(2,2)

算概率了~~~

P(X=大小王在一堆)= C(2,2)C(52,16)C(36,18)C(18,18)/P(2,2) / C(54,18)*C(36,18)*C(18,18)/P(3,3) =17/53

我看到某博客上答案好像不对啊~~~~

经过和sumnous_t大神的交涉，博客上答案改正过来啦~~~答案不重要，最重要的是思维，思路开阔，我喜欢这种探讨~~~~

顺带提几个重要的组合公式，有了新的对应事件的解释：

C(n,m)=C(n-1,m-1)+C(n-1,m-1) 我每次要完全回忆都会稍借助比较小的数据， C(4,2)=C(3,2)+C(3,1)

将组合数朝着小的方向分解，类似分治，且后一项都为m-1

看到百度百科有一个新的解释，从n个选m个，对于其中一个，可以选或不选，根据这个feature(我理解成ML的特征)只有两种，且之间不重复，并起来等于原问题，

选的话C(n-1,m-1) 不选的话C(n-1,m)

因此C(n,m)=C(1,1)C(n-1,m-1)+C(1,0)C(n-1,m)

从这里我又得到启发，推新的公式，对于其中两个，可以选0,1,2个，

C(n,m)=C(2,0)C(n-2,m)+C(2,1)C(n-2,m-1)+C(2,2)C(n-2,m-2) //用小的case检验正确

还有一个更逆天的公式。。

notation:

Sum(K=1,N)f(K)表示求和

也是从N个选M个，不排列，那么对N-M个数从1编号,另外M个数

选1，剩下选m-1 C(n-1,m-1)，选1只有一种

不选1，选2，剩下选m-1 C(n-2,m-1)，不选1 选2 在1,2的四种组合中是一种

...

不选1...N-M-1, 选N-M, 剩下选m-1，C(m,m-1)

不选1,...N-M, 剩下选M C(m,m)=C(m-1,m-1)

这N-M+1个情况，之间没有交集，因为给定编号的N-M个数完全不同(case1与case2...n-m+1不同，关于选不选1，不同是互相的，所以case2只要与case3...n-m+1比较就可以了，case2与case3...casen-m+1不同，一直下去，所有的互不相同，没交集)，并且并起来，包含了全部N个选M个的情况(有点难理解，选了1或者不选1，不选1又包含了选2 和不选2 ，然后一直下去)

因此得

Sum(k=m，n)C(k-1，m-1)=C(n，m) (n>=m)

因此两个组合重要公式：

1. C(n,m)=C(1,1)C(n-1,m-1)+C(1,0)C(n-1,m)

鄙人又扩充了一个C(n,m)=C(2,0)C(n-2,m)+C(2,1)C(n-2,m-1)+C(2,2)C(n-2,m-2)

2.Sum(k=m，n)C(k-1，m-1)=C(n，m) (n>=m)

另外关于是否要除于排列数对于简单的情况有了一个总结