路径数问题

$C(m+n, n)$，从$(0,0)$到$(m,n)$，那么每一个路径对应一个 xxyx… 这样的排列，选n个位置放y，即 $C(m+n, n)$

  • $C(n,r)=C(n-1,r)+C(n-1,r-1)$

可推出杨辉三角。

  • $(_r^{n+r+1})=(r^{n+r})+(^{n+r-1}{r-1})+…+(^n_0)$

  • $(^{m+n}_r)=(^m_0)(^n_r)+…+(^m_r)(^n_0)$

m+n个球，m个红球，n个蓝球，取出的r个球：0个红球，r个蓝球…..r个红球，0个蓝球

生成排列

由 n 个正整数组成的集合{1,2,..,n}有$n!$排列。

$n!=\sqrt{2\pi n}(\frac{n}{e})^n$

需求：从已知排列出发，生成新的排列

序数法

递增进位

以{(n-1)!,(n-2)!...2!,1!}为基数表示：
$$
n!=(n-1)(n-1)!+(n-1)!=…=\sum_{k=1}^{n-1}k\cdot k!+1
$$
那么对于任意一个整数 m（$0\le m\le n!-1$）：
$$
m=a_1(n-1)!+a_2(n-2)!+…+a_{n-1}1!\qquad(a_i\in[0,n-i])
$$
$(a_1,…,a_{n-1})$序列与$0\sim n!-1$之间的整数一一对应，故称为中介数

或相对应$(b_n,…,b_2)$，$b_n=a_1$，以此类推

转化：

$a_{n-1}=m/2的余数,a_{n-2}=(m/3)/2的余数…$

递减进位

$$
m=\sum_{i=1}^{n-1}a_i\cdot \frac{n!}{(n-i+1)!}\=a_1+a_2\cdot\frac{n!}{(n-1)!}+…+a_{n-1}\cdot\frac{n!}{2!}\qquad(a_i\in[0,n-i])
$$

$(a_{n-1},…,a_{1})$是中介数

转化：

$a_{1}=m/n的余数,a_{2}=(m/n)/(n-1)的余数…$

逆序

（1）排列$i_1i_2…i_n$与逆序列$(a_1,…,a_{n-1})$，$a_1$代表 1 左边比 1 大的整数的个数，以此类推。

转化：

先确定n个空位。确定 1 的位置：从左向右数$a_1$个空格，下一空格填1；确定 2 的位置：从左向右数$a_2$个空格，注意此时填了 1，空格就不包括这个位置。

（2）排列$i_1i_2…i_n$与逆序列$(b_n,…,b_2)$，$b_n$为 n 右边比 n 小的整数个数

转化：类似上边

字典序法

$i_1i_2…i_n$求下一个排列的算法：

从右向左找到第一个右邻比自己大的数$i_k$，在其右边的所有比自己大的数中选取最右边的数$i_j$，将两者交换。

例：839647521,4是从右向左第一个右邻比自己大的，然后右边比自己大的有7、5，选最右的5，交换，得下个排列为：839657421

中介数：$(a_1,a_2,…,a_{n-1})$ ，$a_1$代表$i_1$右边比$i_1$小的字符的个数

序数：
$$
m=a_1(n-1)!+a_2(n-2)!+…+a_{n-1}1!\qquad(a_i\in[0,n-i])
$$