组合计数

计数原理


加法原理:做一件事情有$n$个办法,第$i$个办法有$p_i$种方案,则一共有$p_1+p_2+…+p_n$种方案

乘法原理:做一件事情有$n$个步骤,第$i$个步骤有$p_i$种方案,则一共有$p_1 \times p_2 \times … \times p_n$种方案

容斥原理

先不考虑重叠的情况,计算出所有对象的数目,再把计数时重复计算的数目排斥出去

鸽巢原理

把$n+1$个小球放进$n$个盒子,至少有一个盒子包含至少两个小球

一般形式:把$m$个小球放进$n$个盒子,至少有一个盒子包含至少$⌈m/n⌉$个小球

最差原则:考虑所有可能情况中,最不利于某件事情发生的情况

Ramsey定理

将$6$个顶点的完全图的边用红、蓝两色任意着色,至少存在一个红色边三角形或蓝色边三角形


排列组合


排列数

$n$个不同的数,选$k$个排成一排,每个数最多选一次

由乘法原理,$P(n,k)=\frac{n!}{(n-k)!}$

特别地,定义$0!=1$,$n$个数的全排列数$P(n,n)=n!$

组合数

$n$个不同的数,选$k$个(顺序无关),每个数最多选一次

把$n$选$k$的排列问题分成两个步骤:

首先选出$k$个数的组合,然后把这$k$个数进行全排列

$C(n,k)=\frac{P(n,k)}{P(k,k)}=\frac{n!}{(n-k)!k!}$

性质

  1. $C(n,0)=C(n,n)=1$
  2. $C(n,k)=C(n,n-k)$,$n$选$k$和$n$不选$k$的方案一一对应
  3. $C(n,k)=C(n-1,k)+C(n-1,k-1)$,组合数递推公式,由加法原理推导出
  4. 二项式定理:$(a+b)^n=\sum\limits_{k=0}^{n} _{}^{}$

note danger, note danger, note danger
note danger, note danger, note danger

一些计数问题

// copy from youdao note

等价类计数

群论基础知识

置换群

http://blog.csdn.net/xym_CSDN/article/details/53456447

分享到: