排列组合

计数问题分类

计数对象	有序	无序
都不重复	排列	组合	集合
允许重复			重集

集合的排列

圆排列

集合中互不相同的元素按顺时针排成圆圈，称为的k元圆排列，其数目为.

线性排列

又称为元排列。集合X的有序k元组()称为x的k元排列，元组中元素互不相同。含n个元素的集合中的k元排列数目记为.
- 时，；
- 时，（称为全排列）
排列可以表示为元组的形式，例如：.

全排列

全排列是线性排列在时的特殊情况。

置换

置换（双射）：这个元素的双射，如置换.
置换是排列的另一种视角：
全排列可以视为置换（双射），例如：排列对应置换.

循环分解

长为的循环.
置换的循环分解式，若中长为的循环有个，则称是型的。

Cauchy公式

中型的置换个数为

无符号第一类Stirling数

$恰有个循环的元置换$
规定：.
满足递推关系

推论：
Pf .

集合的组合

组合定义：集合的（元素互不相同的）无序k元组()称为的元组合，记为

二项式系数有如下性质：

Pf. 从m+n个人(男生m名，女生n名)中选择r人。
Specially, when , denoted as 中心二项数.
二项式定理

重集的排列

集合的可重复排列
集合X的有序k元组称为X的k元可重复排列，其中可取相同值，记为.
e.g. 的2元字：
def. let ,if appears times in a word (),则称该字是型的。
th. let , given , then X 上的型字个数为
多项式系数
e.g. 的8元字

重集的组合

集合的可重复组合
def. 集合X的无序k元组称为X上的k元可重复组合，其中可取重复值。
重数：出现的次数，
$元集的元重集$
th.

p.s.

cor. 方程的非负整数解个数为.不等式加松弛变量。变量带下界则构造新的变量使其非负。
def. 称的k元子集为间隔的，如果其中任意两数之差.
th. $的间隔的元子集$
e.g. 的2间隔的3元子集：

二项式系数

esp:

三角形数：
四面体数：

性质

对称
递推（与杨辉三角有关）
行和
行交错和
行平方和
格路
二项式系数的一种表示，可以为二项式系数提供一种组合解释。
从(0,0)到(k,n-k)，只走(1,0)或(0,1)方向的所有可能路径数目为。因为到每一个点的前序点有2个
二项式定理

代数证明：数学归纳
cor.
可由此推出前面的部分性质:,.
二项式系数的正交性
单峰性
def. ，使得，则称数列具有单峰性。
二项式系数的单峰性
峰值在取得
分奇偶项讨论，证明奇偶项各自的单峰性。为奇数时，相邻两项相等且均为峰值。
cor. 对固定的，数列的峰值为
对数凹性
def. 实数数列，若，则称数列是凹的，若，则称数列是对数凹的。
th. 对于正数列，凹对数凹单峰

组合数学