Counting
| Type | Repetition Allowed? | Formula |
|---|---|---|
| r-permutations | No | $P_n^k =r! { n \choose k } $ |
| r-combinations | No | \(C_n^k = {n \choose r}\) |
| r-permutations | Yes | \(n^k\) |
| r-combinations | Yes | $C_{n+k-1}^k = {n+k-1 \choose k} $ |
r-combinations with repetition allowed
\[\begin{aligned}
& k:=0 \\
& \quad \text { for } i_1:=1 \text { to } n \\
& \quad \quad \text { for } i_2:=1 \text { to } i_1 \\
& \quad \quad \quad ... \\
& \quad \quad \quad \text { for } i_m:=1 \text { to } i_{m-1} \\
& \quad \quad \quad \quad \quad k:=k+1 \\
&
\end{aligned}
\]
\(k\) 的值相当于从 \(n\) 个数中可以重复地抽 \(m\) 个出来. 也就是有 \(n\) 个间隙（也就是有 \(n - 1\) 个挡板），把 \(m\) 个物品放到这些间隙中.
\(k ={n+m-1 \choose m}\).
distinguishable objects and distinguishable boxes
以下描述等价：
-
indistinguishable objects and indistinguishable boxes
-
\(n\) 个不相同的物品，分到不相同的 \(k\) 盒子里，分进每个盒子之后没有顺序；
-
也可以理解为 \((x_1 +x_2 + ... +x_k)^n\) 中 \(\prod_i^k x_i\) 的系数；
\[\frac{n !}{n_{1} ! n_{2} ! \cdots n_{k} !}
\]
distinguishable objects and indistinguishable boxes
\(n\) 个不相同的物品，分到 \(k\) 个一模一样的盒子里，(分进每个盒子之后没有顺序)；
No closed form.
Stirling numbers of the second kind
\(S(n, j)\) ：\(n\) 个不相同的物品，分到 \(k\) 个一模一样的盒子里，每个盒子里至少分到 1 个物品（包括 1 个）；
\[S(n, j)=\frac{1}{j !} \sum_{i=0}^{j-1}(-1)^i\left(\begin{array}{l}
j \\
i
\end{array}\right)(j-i)^n
\]
如果允许有空盒，就考虑分成各种子情况再相加，也就是 \(\sum_{j=1}^k S(n, j)\).
\[\sum_{j=1}^k S(n, j)=\sum_{j=1}^k \frac{1}{j !} \sum_{i=0}^{j-1}(-1)^i\left(\begin{array}{l}
j \\
i
\end{array}\right)(j-i)^n
\]
递推关系：
\[S(n\,+\,1,\,r)=S(n,\,r\,-\,1)\,+\,r S(n,\,r).
\]
一些别的：
\[n\geq 1,\,S(n,\,1)\,=\,S(n,\,n)\,=\,1,
\]
分成两类就是
\[S(n,\,2)\,=\,2^{n-1}\,-\,1
\]
\[S(n,\,n\,-\,1)\,=\,\textstyle{\frac{1}{2}}n(n\,-\,1).
\]
这样写会更直观：
\[\begin{array}{ c c c c c c c}
& & & & & & 1 \\
& & & & & 1 & & 1 \\
& & & & 1 & & 3 & & 1 \\
& & & 1 & & 7 & & 6 & & 1 \\
& & 1 & & 15 & & 25 & & 10 & & 1 \\
\end{array}
\]
indistinguishable objects and indistinguishable boxes
No closed form.
indistinguishable objects and distinguishable boxes
和 r-combinations with repetition allowed 等价.
尽管等价但是注意 \(n\) 和 \(k\) 的位置发生了变化.
- \(k\) 个一模一样的物品放到 \(n\) 个不一样的盒子里
- \(n\) 个间隙，也就是 \(n-1\) 个挡板，和 \(k\) 个物品
- \({n+k-1 \choose k}\)
- 从 \(n\) 个不相同的物品里面可以重复地取出 \(k\) 个物品，取出后没有顺序
- 在 \(n\) 个物品前面放一个计数用的盒子，有 \(k\) 根竹签，要娶一下第 \(k\) 个就放一根竹签在盒子里.
- \(n\) 个盒子可以看成 \(n - 1\) 个挡板.
- \({n+k-1 \choose k}\)
Catalan numbers
- \(n\) 组括号的合法运算数；
- ...
\[\begin{aligned}
C_{n}&=C_{0}C_{n-1}+C_{1}C_{n-2}+\cdot\cdot\cdot\cdot+C_{n-2}C_{1}+C_{n-1}C_{0} \\
&=\sum_{k=0}^{n-1}C_{k}C_{n-k-1}
\end{aligned}
\]
\[C_n=\frac{1}{n+1}\left(\begin{array}{c}
2 n \\
n
\end{array}\right)=\frac{(2 n) !}{(n+1) ! n !}
\]