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\) 的系数；
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\) 组括号的合法运算数；
- ...