我们都学习过排列与组合，今天我们来探讨一下排列组合的基本运算性质。

从n个不同的元素中选取m个元素排成一列的方法数称为排列数，用符号A(n,m)表示。

A(n,m)=n×(n-1)×…×(n-m+1)

从n个不同的元素中选取n个元素排成一列，也就是直接对这n个元素进行排序，称为n个数的全排列，简称全排。全排数用符号A(n,n)表示。

A(n,n)=n×(n-1)×…×2×1

=1×2×…×(n-1)×n

A(n,n)的计算结果又称为n的阶乘，用符号n!表示。

A(n,n)=n!=1×2×…×(n-1)×n

对于阶乘，很显然有如下性质：

n!=1×2×…×(n-1)×n

=[1×2×…×(n-1)]×n

=(n-1)!×n

n!=(n-1)!×n

有了阶乘的概念，我们很容易发现如下关系：

A(n,m)=n×(n-1)×…×(n-m+1)

={[n×(n-1)×…×(n-m+1)]×[(n-m)×(n-m-1)×…×2×1]}/[(n-m)×(n-m-1)×…×2×1]

=n!/(n-m)!

我们得出了排列数与阶乘的关系：

A(n,m)=n!/(n-m)!

接下来我们继续来讨论组合数。

从n个不同的元素中选取m个元素组成一组的方法数称为组合数，用符号C(n,m)表示。

组合数与排列数的区别在于，排列数选出的m个元素是有序的，而组合数选出的m个元素是无序的。所以我们在计算组合数时，首先计算排列数，再把选出的这m个元素的顺序除掉，也就是用排列数除以m个数的全排数，那么这m个元素就没有顺序了，从而求出组合数。

C(n,m)=A(n,m)/A(m,m)

=[n×(n-1)×…×(n-m+1)]/m!

A(n,m)=C(n,m)×A(m,m)

C(n,m)=A(n,m)/A(m,m)

=[n!/(n-m)!]/m!=n!/[m!(n-m)!]

C(n,m)=n!/[m!(n-m)!]

到这里，我们就得出了排列数、组合数与阶乘的关系式：

A(n,m)=n!/(n-m)!

C(n,m)=n!/[m!(n-m)!]

进一步，我们还可以得出组合数的一个很重要的公式。

从n个不同的元素中选取m个元素，则会剩下(n-m)个元素。很显然，选出m个元素的方法数与选出(n-m)个元素的方法数是一一对应关系。也就是说，从n个不同的元素中选出m个元素的组合数与选出(n-m)个元素的组合数是相等的。

C(n,m)=C(n,n-m)

我们再用阶乘的关系式证明一下这个结论：

C(n,m)=n!/[m!(n-m)!]

C(n,n-m)=n!/{(n-m)![n-(n-m)]!}

=n!/[(n-m)!m!]=C(n,m)

C(n,m)=C(n,n-m)

很明显，从n个不同的元素中选取n个元素的方法数只有一种，那就是把这n个元素全部选出。所以：

C(n,n)=1

为了保证之前的公式对0同样适用，我们规定：

C(n,0)=C(n,n-0)=C(n,n)=1

C(n,0)=1

这里特别强调，C(n,0)并没有实际意义，仅仅是为了满足运算人为定义的结果。

类似地，我们还可以定义0!

C(n,m)=n!/[m!(n-m)!]

C(n,n)=n!/[n!(n-n)!]

=n!/(n!0!)=1/0!=1

0!=1

接下来，我们来证明组合数中一个非常重要的结论：

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

证明：C(n,m)+C(n,m-1)

=n!/[m!(n-m)!]+n!/{(m-1)![n-(m-1)]!}

=[n!(n-m+1)]/[m!(n-m+1)!]+(n!m)/[m!(n-m+1)!]

=[n!(n-m+1)+(n!m)]/[m!(n-m+1)!]

=[n!(n+1)]/[m!(n-m+1)!]

=(n+1)!/[m!(n-m+1)!]

C(n+1,m)

=(n+1)!/[m!(n+1-m)!]

=(n+1)!/[m!(n-m+1)!]

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

证毕！

对于这个公式，我们还可以这样来理解。

从(n+1)个不同的元素中选取m个元素

共有C(n+1,m)种情况

对于这(n+1)个的元素中的某一个元素P，是否选取P分成两种情况：

①不选P：除了元素P以外还有n个元素，需要从这n个元素中选取m个元素；

共有C(n,m)种情况

②选P：除了元素P以外还有n个元素，还需要从这n个元素中选取(m-1)个元素；

共有C(n,m-1)种情况

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

这个公式和著名的杨辉三角还有着非常奇妙的联系，具体联系我们下次再讲。

利用这个公式我们还可以得到一个有趣的结论。

首先从n个不同的元素中选取1个元素的方法数有n种，也就是说：

C(n,1)=n

1+2+3+…+n

=C(1,1)+C(2,1)+C(3,1)+…+C(n,1)

=C(2,2)+C(2,1)+C(3,1)+…+C(n,1)

=C(3,2)+C(3,1)+…+C(n,1)

=C(4,2)+…+C(n,1)

=C(n,2)+C(n,1)

=C(n+1,2)

=[n(n+1)]/2

1+2+3+…+n=[n(n+1)]/2

这不正是正整数前n项和的求和公式吗？你有没有被惊艳到，原来组合数还可以对等差数列求和进行如此风骚的操作。

最后我们来讨论一下非常著名的二项式定理：

对于(a+b)^n

(a+b)^n=(a+b)×(a+b)×…×(a+b)

这里一共有n个(a+b)相乘

展开式的第(r+1)项T(r+1)，就是从这n个(a+b)中选出r个(a+b)

这r个(a+b)分别取因数b，剩下(n-r)个(a+b)分别取因数a

T(r+1)=C(n,r)×a^(n-r)×b^r

(a+b)^n=Σ[C(n,r)×a^(n-r)×b^r]

r=0，1，2，…，n

接下来我们来讨论这样一个问题：

对于n道判断对错的判断题，这n道题的答案共有多少种情况？

我们可以从两个不同的角度来思考这个问题

角度一：这n道题的答案中有0道是对的，共有C(n,0)种情况；有1道是对的，共有C(n,1)种情况；有2道是对的，共有C(n,2)种情况；……；有n道是对的，共有C(n,n)种情况。

这n道题的答案共有

C(n,0)+C(n,1)+C(n,2)+…+C(n,n)

种情况

角度二：这n道题每道题的答案都有对和错两种不同的情况

这n道题的答案共有2^n种情况

结合这两种不同的角度可得

C(n,0)+C(n,1)+…+C(n,n)=2^n

我们再用二项式定理推导一下这个结论：

2^n=(1+1)^n

=Σ[C(n,r)×1^(n-r)×1^r]

=Σ[C(n,r)]，r=0,1,2,…,n

=C(n,0)+C(n,1)+C(n,2)+…+C(n,n)

C(n,0)+C(n,1)+…+C(n,n)=2^n

类似地，我们还可以得到另一个有趣的结论：

0=0^n=(1-1)^n=[1+(-1)]^n

=Σ[C(n,r)×1^(n-r)×(-1)^r]

=Σ[C(n,r)×(-1)^r]，r=0,1,2,…,n

=C(n,0)-C(n,1)+C(n,2)-C(n,3)+…

C(n,0)+C(n,2)+..=C(n,1)+C(n,3)+..

好了，今天关于排列组合的知识点就讲到这里。在今天的内容中我们探讨了排列、组合、阶乘、二项式定理、等差数列求和、杨辉三角相互之间的联系。

我们今天推导出了很多关于排列组合的有趣结论，整体看来并不是很复杂，大家可以再自行推导一遍，加深对这些公式的理解。