组合计数

发表于

组合数

排列数

从n个不同的元素中依次取出k个排成一排，考虑顺序P_{k}^{n}={\frac {n!}{(n-k)!}}

n!表示n的阶乘

组合数

从n个元素中依次取出k个元素组成一个集合，即不考虑顺序

C_{k}^{n}={n \choose k}={\frac {P_{k}^{n}}{k!}}={\frac {n!}{k!(n-k)!}}

注意组合数与排列数从n中取k’’都不放回去’’

以下将用P(n,k) C(n,k)代表上述简写

性质

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

由组合数的定义可得，对于从n个不同的元素中取出m个组成的每个集合，剩余未取出的元素也构成一个集合，两者一一对应

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

从n个不同的元素中取m个有两种方法 取n号元素和不取n号元素

若取，则应在剩余n-1个元素中选m-1个，有C(n-1,m-1)种取法

若不取，同理，有C(n-1,m)种取法

根据加法原理，上式成立

这个其实也是杨辉三角的原理

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

从n个不同的元素中取出若干个元素组成一个集合，有n+1类方法，分别为取出0,1,2,…n个 共C(n,0)+C(n,1)+……+C(n,n)种方法

从另一方面，它们可取可不取，总方法数为2^n

二项式定理

(a+b)^n=∑k=0→n C(n,k)a^k*b^(n-k)

多重集

还记得上述的从n中取k’’都不放回去’’吗？现在讨论放回去的情况

多重集指包含重复元素的广义集合

排列

设S={n1·a1,n2·a2,……,nk·ak}

n1个a1,…….nk个ak

S的全排列数为n!/(n1!n2!……nk!)

组合

{\displaystyle H_{k}^{n}={\frac {(n+k-1)!}{k!\cdot (n-1)!}}}

即C(n+k-1,n-1)=C(n+k-1,k)

Lucas定理

若p是质数，对于任意1<=m<=n

C(n,m)≡C(n mod p,m mod p)*C(n/p,m/p)(mod p)

Catalan数列

给定n个0和n个1，他们按照某种顺序排成长度为2n的序列，满足任意前缀中的0的个数都不小于1的个数的序列数量

换言之

  1. n个左括号和n个右括号组成的合法括号序列数Cat(n)
  2. n个节点构成的不同的二叉树的数量Cat(n)
  3. 平面直角坐标系内，只能向上和向右走，从(0,0)到(n,m)并且除两个端点外不接触直线y=x的路线数为2Cat(n-1)
  4. 1,2,…n经过一个栈，形成的合法出栈序列数 Cat(n)

Cat(n)=C(2n,n)-C(2n,n-1)=C(2n,n)/(n+1)