组合数学初步公式推导
作为一名数论小白，今天不得不正面刚一下组合数学了。
先来推导一波公式 (太弱了)
这篇博客写给自己，如果有人看，
也和你分享下我自己的理解
排列数公式
先来说一下什么是排列
初赛书上的定义
排列：从n个不同元素中，任取m个元素（m<=n），
按照一定顺序排成一列，
叫做从n个元素中，取出m个元素的一个排列。排列数：从n个不同元素中取出m(m<=n)个元素的所有排列的个数
排列数公式：
A^{m}_{n} = \frac{n!}{(n-m)!}
下面进行推导
思考：我们有n个数，要选m个数，组成各种排列。
现在在你心中想象有m个位置，，，
对于第一个位置，我们有n个数可以放
对于第二个位置，我们就只剩n-1个数可以放了
对于第三个位置，我们只剩n-2个数可以放
. . . . . . . . . . . . . . . . .
对于第m个位置，我们就只剩n-m+1个数可以放
所以有
A^{m}_{n} = n (n-1) (n-2) (n-3) .......* (n-m+1)
A^{m}_{n} =\frac{n* (n-1)* (n-2)* (n-3)* .......* (n-m+1)*(n-m)*(n-m-1)*.....*4*3*2*1}{(n-m)*(n-m-1)*.....*4*3*2*1}
即有
A^{m}_{n} = \frac{n!}{(n-m)!}
组合数公式
为什么我先讲排列再讲组合呢，，当然是有道理的
也来说下什么是组合
又来一波一本通初赛篇的定义
组合：从n个不同元素中，任取m(m<=n)个元素并成一组
叫做从n个不同元素中取出m个元素的一个组合现在想一下
组合数和排列数的区别在哪
区别就在于
两个排列相同，当且仅当元素必须相同！且！排列的顺序必须完全相同!
而从组合数定义可知，如果两个组合中的元素完全相同，不管元素顺序如何，都是相同的！
组合数公式
C^{m}_{n} = \frac{n!}{(n-m)!m!}
观察组合数公式和排列数的公式
显然，他们的区别在于
组合数公式的分母多了个m!
想一下为什么会这样?
先讨论一个子问题
对于m个数，他们的全排列方案数
显然为m!
这和组合数又扯上了什么联系呢？
设n个数中选m个数的组合数为X
排列数为Y
把定义记清楚！
令X=3；
令这三个组合为a1,a2,a3
Y相对于X而言
显然Y>=X
对于每个子组合a
Y之所以>=X
是因为Y可以对每个子组合进行排列！
例如 子组合 1 2 3
而这三个数对X的贡献为1（他们只是一种组合）
而我们对这三个数搞个全排列
1 2 3
1 3 2
2 1 3
3 1 2
3 2 1
2 3 1
发现他们对Y的贡献为6(不同的顺序可以增大贡献)
及增大为 3！(3的阶层)
所以有
X = 1+1+1（前面说了令组合数为3）
*Y = 1 m! + 1 m! + 1 m!（其中每一个1代表一个组合）**
即x = y / m!
用人话说，
就是组合数X中的每一个子组合，做个全排列的方案数相加，就是排列数
dalao看到这里心想（这么显然的问题你讲那么久）
所以有
C^{m}_{n} =\frac{A^{m}_{n}}{m!}
即