组合数学

排列组合

计数问题分类

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

集合的排列

圆排列

集合中互不相同的元素按顺时针排成圆圈，称为的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. 对于正数列，凹对数凹单峰