计数规则
$\quad\\$
序列|收集|分配|组成|划分|排列
$\quad\\$
对于$n$元有限集$X$，即$|X|=n$，将$X$的元素与如下$I_n$中的元素建立一个双射，称为$X$的一个标签
$$\forall n\in \mathbb{N_+}\qquad I_n=\{1,2,\cdots,n\}\qquad I_0=\varnothing$$
将与$I_n$中$1$对应的元素称为$X$的第一个元素，与$2$对应的元素称为$X$的第二个元素，以此类推，按照约定，$I_n=\{!,?,*,\#,\cdots,\&\}$表示第一个元素为$!$，第二个元素为$?$，第$n$个元素为$\&$等
令$(\cdots)$表示有序元组，$[\cdots]$表示无序元组，$n,k\in \mathbb{N}$，现在来定义一些名词
序列(Sequence)
$$\small k元组(x_1,x_2,\cdots,x_k)称为I_n的一个k序列\\
\small 其中x_i为I_n中元素(可以重复)，即(x_1,x_2,\cdots,x_k)为笛卡尔积I_n^k的元素$$
分配(Sharing)
$$\small k元组(X_1,X_2,\cdots,X_k)称为I_n的一个k分配\\
\small 其中X_i为I_n的两两不相交的子集(可以为空)且并为I_n$$
组成(Composition)
$$\small k元组(x_1,x_2,\cdots,x_k)称为I_n的一个k组成\\
\small 其中x_i为自然数(含0)且x_1+x_2+\cdots+x_k=n$$
收集(Collection)
$$\small n元组[X_{1},X_{2},\cdots,X_{n}]称为I_n的一个k收集\\
\small 其中X_{i}为I_n中元素i的重集，且|X_1|+|X_2|+\cdots+|X_n|=k$$
划分(Partition)
$$\small k元组[X_{1},X_{2},\cdots,X_{k}]称为I_n的一个k划分\\
\small 其中X_i为I_n的两两不相交的非空子集且并为I_n$$
$$\small k元组[x_{1},x_{2},\cdots,x_{k}]称为n的一个k划分\\
\small 其中x_i为自然数(不含0)且x_1+x_2+\cdots+x_k=n$$
排列(Permutation)
$$\small 取I_n的一个k序列(x_1,x_2,\cdots,x_k)\\
\small 若有[y_1,y_2,\cdots,y_k]=[x_1,x_2,\cdots,x_k]\\
\small 则称(y_1,y_2,\cdots,y_k)为(x_1,x_2,\cdots,x_k)的一个排列$$
$\quad\\$
记号
$\quad\\$
记$S(n,k)$为$I_n$的没有重复元素的$k$序列个数，$n,k\in \mathbb{N}$，则有
$$S(n,k)=\left\lbrace\begin{array}{l}\frac{n!}{(n-k)!}&k\leq n\\
0&k>n\end{array}\right.$$
记$C(n,k)$为$I_n$的没有重复元素的$k$收集个数，$n,k\in \mathbb{N}$，则有
$$C(n,k)=\left\lbrace\begin{array}{l}\frac{S(n,k)}{k!}=\left(\begin{array}.n\\k\end{array}\right)&0\leq k\leq n\\
0&\text{otherwise}\end{array}\right.$$
记$S((n,k))$为$I_n$的$k$序列个数或$I_k$的$n$分配个数，$n,k\in \mathbb{N}$，则有
$$S((n,k))=n^k$$
记$C((n,k))$为$I_n$的$k$收集个数或$I_k$的$n$组成个数，$n,k\in \mathbb{N}$，则有
$$C((n,k))=\left\lbrace\begin{array}{l}\left(\begin{array}.n+k-1\\k\end{array}\right)&1\leq n+k\\
0&n=k=0\end{array}\right.$$
记$P(x_1,x_2,\cdots,x_k)$为$I_n$的$k$序列$(x_1,x_2,\cdots,x_k)$的排列个数，若序列$(x_1,x_2,\cdots,x_k)$具有占有列$(k_1,k_2,\cdots,k_n)$，即元素$i$恰好在序列中出现$k_i$次，$n,k\in \mathbb{N}$，则有
$$P(x_1,x_2,\cdots,x_k)=\left(\begin{array}.k\\k_1,k_2,\cdots,k_n\end{array}\right)$$
记$S(n,k;(k_1,k_2,\cdots,k_n))$为具有占有列$(k_1,k_2,\cdots,k_n)$的$I_n$的$k$序列个数或具有占有列$(k_1,k_2,\cdots,k_n)$即$|X_i|=k_i$的$I_k$的$n$分配个数，$n,k\in \mathbb{N}$，则有
$$S(n,k;(k_1,k_2,\cdots,k_n))=\left(\begin{array}.k\\k_1,k_2,\cdots,k_n\end{array}\right)$$
记$S(n,k;[k_1,k_2,\cdots,k_n])$为具有占有列$[k_1,k_2,\cdots,k_n]$即元素$i$恰好出现$k_j$次，其中$i$到$j$为任意双射的$I_n$的$k$序列个数或具有占有列$[k_1,k_2,\cdots,k_n]$即$|X_i|=k_j$，其中$i$到$j$为任意双射的$I_k$的$n$分配个数，$n,k\in \mathbb{N}$，则有
$$S(n,k;[k_1,k_2,\cdots,k_n])=\left(\begin{array}.k\\k_1,k_2,\cdots,k_n\end{array}\right)P(k_1,k_2,\cdots,k_n)$$
记$C(n,k;[k_1,k_2,\cdots,k_n])$为具有占有列$[k_1,k_2,\cdots,k_n]$即元素$i$恰好出现$k_j$次，其中$i$到$j$为任意双射的$I_n$的$k$收集个数或具有占有列$[k_1,k_2,\cdots,k_n]$即$|X_i|=k_j$，其中$i$到$j$为任意双射的$I_k$的$n$组成个数，$n,k\in \mathbb{N}$，则有
$$C(n,k;[k_1,k_2,\cdots,k_n])=P(k_1,k_2,\cdots,k_n)$$
$\quad\\$
Leibniz求导法则
$\quad\\$
令$f_1,f_2,\cdots,f_k$为$n$次可微函数，$n,k\in \mathbb{N}$，则有
$$(f_1f_2\cdots f_k)^{(n)}=\sum\limits_{\begin{array}&(n_1,n_2,\cdots,n_k)\in \mathbb{N}^k\\n_1+n_2+\cdots+n_k=n\end{array}}
\left(\begin{array}.n\\n_1,n_2,\cdots,n_k\end{array}\right)f_1^{(n_1)}f_2^{(n_2)}\cdots f_k^{(n_k)}$$
$\quad\\$
Gilbreath Principle
$\quad\\$
称一系列连续不断的自然数如$5,6,7,8,9$的集合为一个自然数区间，简称区间，对于$1$到$n$的自然数的一个排列$(x_1,x_2,\cdots,x_n)$，如果对于任意$0<i\leq n$，$集合{x_1,x_2,\cdots,x_i}$均是一个区间，则称此排列为Glibreath排列，Glibreath排列具有如下性质
$1$到$n$的自然数的排列$(x_1,x_2,\cdots,x_n)$是Glibreath排列当且仅当此排列可以按顺序拆解为区间序列$[i,n]$和$[i-1,1]$
$\nabla$证
$\textbf{充分性}$ $$对于排列(x_1,x_2,\cdots,x_n)\\\\ \quad\\\\ 易知若x_2属于增区间序列，则x_1=x_2-1，反之x_1=x_2+1\\\\ \quad\\\\ 因此\{x_1,x_2\}为一个区间\\\\ \quad\\\\ 假设X=\{x_1,x_2,\cdots,x_i\}为一个区间，则x_{i+1}=x_{max}+1或x_{min}-1\\\\ \quad\\\\ 因此\{x_1,x_2,\cdots,x_{i+1}\}也是区间\\\\ \quad\\\\ 由归纳法可知(x_1,x_2,\cdots,x_n)是Gilbreath排列 $$ $\textbf{必要性}$ $$对于Gilbreath排列(x_1,x_2,\cdots,x_n)\\\\ \quad\\\\ 令X_i={x_1,x_2,\cdots,x_i}\\\\ \quad\\\\ 因为x_{i+1}=x_{min}-1或x_{max}+1\\\\ \quad\\\\ 前一种情况将x_{i+1}归入减区间序列，反之归入增区间序列\\\\ \quad\\\\ 对于所有1\leq i\leq n-1均这样操作\\\\ \quad\\\\ 最后再将x_1归入任意区间即可完成拆解$$
$\quad\\$
Gilbreath Principle出现于许多魔术中。事先将牌分为增区间序列和减区间序列两叠牌，保证最小牌与最大牌同时在各自牌堆的顶部或底部，对两叠牌进行Gilbreath Shuffle，即不改变每叠牌中牌的相对位置的洗牌法，常见的鸽尾式洗牌Riffle Shuffle即是一种，这样洗好的牌就是一个Gilbreath排列
$\quad\\$
一些基本等式
$\quad\\$
$$1+\sum\limits_{i=1}^{n-1}i\;i!=n!\quad\forall n\geq 2\;\&\;n\in \mathbb{N}$$
$$\sum\limits_{i=0}^n\left(\begin{array}.n\\i\end{array}\right)=2^n\qquad\sum\limits_{i=0}^n(-1)^i\left(\begin{array}.n\\i\end{array}\right)=0\\
\quad\\
\sum\limits_{\begin{array}&0\leq i_1\leq n\\ \cdots \\0\leq i_k\leq n\end{array}}\left(\begin{array}.n_1\\i_1\end{array}\right)
\cdots\left(\begin{array}.n_k\\i_k\end{array}\right)=2^{n_1+\cdots+n_k}$$
$$\left(\begin{array}.n-1\\k-1\end{array}\right)+\left(\begin{array}.n-1\\k\end{array}\right)=\left(\begin{array}.n\\k\end{array}\right)\quad \text{Stifel formula}$$
$$C((n,k))=C((n-1,k+1))\\
\quad\\
C((n,k-1))+C((n-1,k))=C((n,k))\\
\quad\\
\sum\limits_{i=0}^kC((n-1,i))=C((n,k))$$
$\quad\\$
参考与引用来源
$\quad\\$