湖南衡阳县人 / 文件夹1 / 排列组合的一些公式及推导(非常详细易懂)

分享

   

排列组合的一些公式及推导(非常详细易懂)

2020-06-05  湖南衡阳...

绪论:加法原理、乘法原理

分类计数原理:做一件事,有n类办法,在第1类办法中有m1种不同的方法,在第2类办法中有m2种不同的方法,…,在第n类办法中有mn种不同的方法,那么完成这件事共有N=m1+m2+…+mn种不同的方法。

分步计数原理:完成一件事,需要分成n个步骤,做第1步有m1种不同的方法,做第2步有m2种不同的方法,…,做第n步有mn种不同的方法,那么完成这件事共有N=m1×m2×⋯×mn种不同的方法。

区别:分类计数原理是加法原理,不同的类加起来就是我要得到的总数;分步计数原理是乘法原理,是同一事件分成若干步骤,每个步骤的方法数相乘才是总数。

排列问题

排列数

从n个不同元素种取出m(m≤n)个元素的所有不同排列的个数,叫做从n个不同元素种取出m个元素的排列数,用符号Amn表示。

排列数公式

Amn=n(n−1)(n−2)⋯(n−m+1)=n!(n−m)!,n,m∈N∗,并且m≤n
(规定0!=1)

推导:把n个不同的元素任选m个排序,按计数原理分步进行

取第一个:有n种取法;
取第二个:有(n−1)种取法;
取第三个:有(n−2)种取法;
……
取第m个:有(n−m+1)种取法;

根据分步乘法原理,得出上述公式。

排列数性质

Amn=nAm−1n−1 可理解为“某特定位置”先安排,再安排其余位置。

Amn=mAm−1n−1+Amn−1 可理解为:含特定元素的排列有mAm−1n−1,不含特定元素的排列为Amn−1。

组合问题

组合数

从n个不同元素种取出m(m≤n)个元素的所有不同组合的个数,叫做从n个不同元素种取出m个元素的组合数,用符号Cmn表示。

组合数公式

Cmn=AmnAmm=n(n−1)(n−2)⋯(n−m+1)m!=n!m!(n−m)!,n,m∈N∗,并且m≤n

C0n=Cnn=1

证明:利用排列和组合之间的关系以及排列的公式来推导证明。

将部分排列问题Amn分解为两个步骤: 

第一步,就是从n个球中抽m个出来,先不排序,此即组合数问题Cmn;

第二步,则是把这m个被抽出来的球排序,即全排列Amm。

根据乘法原理,Amn=CmnAmm,那么
Cmn=AmnAmm=n(n−1)(n−2)⋯(n−m+1)m!=n!m!(n−m)!

组合数的性质

Cmn=Cn−mn 可以理解为:将原本的每个组合都反转,把原来没选的选上,原来选了的去掉,这样就变成从n个元素种取出n−m个元素,显然方案数是相等的。

递推公式Cmn=Cmn−1+Cm−1n−1 可理解为:含特定元素的组合有Cm−1n−1,不含特定元素的排列为Cmn−1。还不懂?看下面。

Example

从1,2,3,4,5(n=5)中取出2(m=2)个元素的组合(Cmn):

12 13 14 15 23 24 25 34 35 45

显然,这些组合中要么含有元素“1”,要么不含。

  • 其中含有“1”的是:12 13 14 15

    把里面的“1”都挖掉:2 3 4 5

    而上面这个等价于从2,3,4,5(n−1)中取出1(m−1)个元素的组合。

  • 其中不含“1”的是:23 24 25 34 35 45
    上面等价于从2,3,4,5(n−1)中取出2(m)个元素的组合。

而总方案数等于上面两种情况方案数之和,即Cmn=Cmn−1+Cm−1n−1。

组合数求和公式

C0n+C1n+C2n+⋯+Cnn=2n

我们感性认知一下,上面这个式子的左边表示什么呢?

把从n个球中抽出0个球的组合数(值为1)、抽出1个球的组合数、抽出2个球的组合数、……、抽出n个球的组合数相加。

换句话说,就是从n个球中随便抽出一些不定个数球,问一共有多少种组合。

对于第1个球,可以选,也可以不选,有2种情况。
对于第2个球,可以选,也可以不选,有2种情况。
对于任意一个球,可以选,也可以不选,有2种情况。

根据乘法原理,一共2×2×⋯×2⏟n个2相乘=2n种组合。

想要严谨的证明?数学归纳法

  1. 当m=1时,C01+C11=2=21成立。

  2. 假设n=k(k∈N∗)时等式成立,即
    k∑i=0Cik=2n
    成立,当n=k+1时,
    C0k+1+C1k+1+C2k+1+⋯+Ckk+1+Ck+1k+1=C0k+1+(C0k+C1k)+(C1k+C2k)+⋯+(Ck−1k+Ckk)+Ck+1k+1=(C0k+C1k+C2k+⋯+Ckk)+(C0k+C1k+C2k+⋯+Ckk)=2×2k=2k+1
    等式也成立。

  3. 由1、2得,等式对n∈N∗都成立。

也可偷懒地用二项式定理证明(其实二项式定理也是用数学归纳法证明的):

(a+b)n=n∑k=0Cknan−kbk
令a=b=1,就得到了
n∑i=0Cin=2n

类似的公式(由Cmn=Cn−mn推导):

C0n+C2n+C4n+⋯=C1n+C3n+C5n+⋯=2n−1

杨辉三角

这个神奇的图形和组合数、二项式定理密切相关。


杨辉三角可以帮助你更好地理解和记忆组合数的性质:

  1. 第n行的m个数可表示为 Cm−1n−1,即为从n−1个不同元素中取m−1个元素的组合数。

  2. 第n行的数字有n项。

  3. 每行数字左右对称(第n行的第m个数和第n−m+1个数相等,Cmn=Cn−mn),由1开始逐渐变大。

  4. 每个数等于它上方两数之和(第n+1行的第i个数等于第n行的第i−1个数和第i个数之和,即Cin+1=Cin+Ci−1n)。

  5. (a+b)n的展开式中的各项系数依次对应杨辉三角的第n+1行中的每一项(二项式定理)。


以下来自维基百科(我只是随便贴这)

二项式系数

二项式系数可排列成帕斯卡三角形。
在数学上,二项式系数是二项式定理中各项的系数。一般而言,二项式系数由两个非负整数n和k为参数决定,写作,定义为的多项式展开式中,项的系数,因此一定是非负整数。如果将二项式系数写成一行,再依照顺序由上往下排列,则构成帕斯卡三角形。 \tbinom nk {\displaystyle (1+x)^{n}}x^{k}{\displaystyle {\binom {n}{0}},{\binom {n}{1}},\dots ,{\binom {n}{n}}}{\displaystyle n=0,1,2,\dots }

二项式系数常见于各数学领域中,尤其是组合数学。事实上,可以被理解为从n个相异元素中取出k个元素的方法数,所以大多读作「n取k」。二项式系数的定义可以推广至n是复数的情况,而且仍然被称为二项式系数。

二项式系数亦有不同的符号表达方式,包括:C(n,k)、_nC_k、^nC_k、、[注3],其中的C代表组合(combinations)或选择(choices)。很多计算机使用含有C的变种记号,使得算式只占一行的空间,相同理由也发生在置换数,例如写作P( n , k )。 {\displaystyle C_{n}^{k}}{\displaystyle C_{k}^{n}}{\displaystyle P_{k}^{n}}

定义及概念
对于非负整数n和k,二项式系数定义为的多项式展开式中,项的系数,即 \tbinom nk{\displaystyle (1+x)^{n}}x^{k}

{\displaystyle (1+x)^{n}=\sum _{k=0}^{n}{\binom {n}{k}}x^{k}={\binom {n}{0} }+{\binom {n}{1}}x+\cdots +{\binom {n}{n}}x^{n}}
事实上,若x、y为交换环上的元素,则

(x+y)^n=\sum_{k=0}^n\binom nk x^{nk}y^k

此数的另一出处在组合数学,表达了从n物中,不计较次序取k物有多少方式,亦即从一n元素集合中所能组成k元素子集的数量。

计算二项式系数

除展开二项式或点算组合数量之外,尚有多种方式计算的值。 \tbinom nk

递归公式
以下递归公式可计算二项式系数:

\binom nk = \binom{n-1}{k-1} + \binom{n-1}k \quad \forall n,k\in\N

其中特别指定:

\binom n0 = 1 \quad \forall n\in\N\cup\{0\}, \binom 0k = 0 \quad \forall k\in\N.

此公式可由计算(1 + X ) n −1 (1 + X )中的X k项,或点算集合{1, 2, ..., n }的k个元素组合中包含n与不包含n的数量得出。

显然,如果k > n,则。而且对所有n,,故此上述递归公式可于此等情况下中断。递归公式可用作建构帕斯卡三角形。 \tbinom nk=0\tbinom nn=1

帕斯卡三角形(杨辉三角)

有关二项式系数的恒等式

关系式

阶乘公式能联系相邻的二项式系数,例如在k是正整数时,对任意n有:

{\binom {n+1}{k}}={\binom {n}{k}}+{\binom {n}{k-1}} \binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1} \binom {n-1}{k} - \binom{n-1}{k-1} = \frac{n-2k}{n} \binom{n}{k}.

两个组合数相乘可作变换:

\binom ni \binom im=\binom nm \binom {nm}{im} \sum_{r=0}^n \binom nr = 2^{n}

{\displaystyle \sum _{r=0}^{k}{\binom {n+r-1}{r}}={\binom {n+k}{k}}}

{\displaystyle \sum _{r=0}^{nk}{\frac {(-1)^{r}(n+1)}{k+r+1}}{\binom {nk}{r} }={\binom {n}{k}}^{-1}}

\sum_{r=0}^n \binom {dn}{dr}=\frac{1}{d}\sum_{r=1}^d (1+e^{\frac{2 \pi ri}{ d}})^{dn}

\sum_{i=m}^n \binom {a+i}{i} = \binom {a+n+1}{n} - \binom {a+m}{m-1}

\binom {a+m}{m-1} + \binom {a+m}{m} + \binom {a+m+1}{m+1} + ... + \binom {a+n} {n} = \binom {a+n+1}{n}

F_n=\sum_{i=0}^{\infty} \binom {ni}{i}

F_{n-1}+F_n=\sum_{i=0}^{\infty} \binom {n-1-i}{i}+\sum_{i=0}^{\infty} \binom {ni }{i}=1+\sum_{i=1}^{\infty} \binom {ni}{i-1}+\sum_{i=1}^{\infty} \binom {ni}{i} =1+\sum_{i=1}^{\infty} \binom {n+1-i}{i}=\sum_{i=0}^{\infty} \binom {n+1-i}{ i}=F_{n+1}
主条目:朱世杰恒等式
\sum_{i=m}^n \binom ia = \binom {n+1}{a+1} - \binom {m}{a+1} \binom {m}{a+1} + \binom ma + \binom {m+1}a ... + \binom na = \binom {n+1}{a+1}
二阶求和公式
{\displaystyle \sum _{r=0}^{n}{\binom {n}{r}}^{2}={\binom {2n}{n}}}
\sum_{i=0}^n \binom {r_1+n-1-i}{r_1-1} \binom {r_2+i-1}{r_2-1}=\binom {r_1+r_2+n-1 }{r_1+r_2-1}
(1-x)^{-r_1} (1-x)^{-r_2}=(1-x)^{-r_1-r_2}
(1-x)^{-r_1} (1-x)^{-r_2}=(\sum_{n=0}^{\infty} \binom {r_1+n-1}{r_1-1} x^ n)(\sum_{n=0}^{\infty} \binom {r_2+n-1}{r_2-1} x^n)=\sum_{n=0}^{\infty} (\sum_{ i=0}^n \binom {r_1+n-1-i}{r_1-1} \binom {r_2+i-1}{r_2-1}) x^n
(1-x)^{-r_1-r_2}=\sum_{n=0}^{\infty} \binom {r_1+r_2+n-1}{r_1+r_2-1} x^n
主条目:范德蒙恒等式
\sum_{i=0}^k \binom ni \binom m{ki}=\binom {n+m}k
三阶求和公式
主条目:李善兰恒等式
{\binom {n+k}k}^2=\sum_{j=0}^k {\binom kj}^2 \binom {n+2k-j}{2k}

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。如发现有害或侵权内容,请点击这里 或 拨打24小时举报电话:4000070609 与我们联系。

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多
    喜欢该文的人也喜欢 更多

    ×
    ×

    ¥.00

    微信或支付宝扫码支付:

    开通即同意《个图VIP服务协议》

    全部>>