---
tags:
- 组合数学
- 斯特林数
上一篇: '[[数学系/离散数学/容斥原理与口味序列计数/02 六种口味排成十位序列]]'
前置知识: '[[数学系/离散数学/容斥原理与口味序列计数/02 六种口味排成十位序列]]'
返回目录: '[[数学系/离散数学/容斥原理与口味序列计数/学习指南]]'
abstract: '用出现次数、非空分组、递推和生成函数理解同一计数，并区分二项式系数和两类斯特林数。'
creation: 2026-10-13
---

# 其他计数方法与斯特林数

本篇是原文衍生讨论的选学整理。问题仍是：6 种指定口味排成长度为 10 的序列，每种至少出现一次。

## 1. 按每种口味的出现次数分类

设第 $i$ 种指定口味出现 $x_i$ 次，则

$$
x_1+\cdots+x_6=10,\qquad x_i\ge1.
$$

令 $y_i=x_i-1$，得到 $y_1+\cdots+y_6=4$，其中 $y_i\ge0$。由隔板法，有

$$
\binom{4+6-1}{6-1}=\binom95=126
$$

种**有序的次数分配**。

> [!proof] 补充证明：为什么是隔板法
> 将 4 个相同标记与 5 块隔板排成一行。隔板分出的 6 段中，标记数依次为 $y_1,\ldots,y_6$；允许空段，恰好对应非负整数解。在 9 个位置中选择 5 个放隔板，得到 $\binom95$。

次数确定后，还要决定每种口味占据哪些位置。对应排列数是

$$
\binom{10}{x_1}\binom{10-x_1}{x_2}\cdots
=\frac{10!}{x_1!x_2!\cdots x_6!}.
$$

因此

$$
N=\sum_{\substack{x_1+\cdots+x_6=10\\x_i\ge1}}
\frac{10!}{x_1!x_2!\cdots x_6!}.
$$

每个序列有唯一的次数向量，不同次数向量对应的序列互不重叠，所以可以直接求和。

> [!warning] 原文分组表述与重复计数修正
> 原文将“把 10 个位置分成 6 个非空组”说成等价于求正整数解个数。正整数解只记录各组大小，没有确定具体位置的归属，两者不能直接等同。
>
> 原文还曾在上述求和式后额外乘 $6!$，随后自行指出重复计数。这里 $x_i$ 已对应第 $i$ 种指定口味，再乘 $6!$ 会多计 $6!$ 倍。保留的正确公式不含这个因子。

## 2. 先分成无标号组：第二类斯特林数

第二类斯特林数记作

$$
S(n,k)=\left\{\begin{matrix}n\\k\end{matrix}\right\},
$$

表示把 $n$ 个不同元素分成 $k$ 个非空、互不相交、合起来覆盖全部元素的子集的方法数，组与组之间不区分顺序。

例如 $S(4,2)=7$：大小为 $1+3$ 的分组有 4 种，大小为 $2+2$ 的分组有 $\binom42/2=3$ 种。

对于口味问题，先把 10 个不同位置分为 6 个无标号非空组，再为各组分配一种不同口味：

$$
N=6!S(10,6).
$$

> [!proof] 补充证明：为什么这里能乘 $6!$
> 任意合格序列都能唯一分成“同一种口味占据的位置组”。去掉口味名称，得到一个无标号的非空分组；反过来，给这 6 个组分别贴上 6 种不同口味的标签，就唯一确定一个序列。标签分配有 $6!$ 种，因此建立了所需的一一对应。

与上一节的区别在于：这里的组原先没有口味标签，所以需要乘 $6!$；上一节中的 $x_i$ 已绑定指定口味。

### 定义独立于容斥，显式公式可由容斥推出

对于 $n\ge1$、$1\le k\le n$，将“6 种、10 位”换为“$k$ 种、$n$ 位”，得到

$$
k!S(n,k)=\sum_{j=0}^{k}(-1)^j\binom kj(k-j)^n,
$$

所以

$$
S(n,k)=\frac1{k!}\sum_{j=0}^{k}(-1)^j\binom kj(k-j)^n.
$$

其推导是：先对 $k$ 个带标签的组用容斥排除空组，再除以标签的 $k!$ 种排列。这说明容斥是计算第二类斯特林数的一种工具，并不意味着其定义依赖容斥。

## 3. 用递推独立计算

### 指定的 $k$ 种口味全部出现

记 $g(n,k)$ 为用指定的 $k$ 种口味组成长度为 $n$ 的序列、且每种都出现的数量。

按最后一位所用口味是否在前面出现，分成两个互斥情况：

1. 前面已经出现全部 $k$ 种口味：前 $n-1$ 位有 $g(n-1,k)$ 种，最后一位有 $k$ 种选择。
2. 最后一位的口味首次出现：先选出这一个新口味，有 $k$ 种选择；前 $n-1$ 位恰好使用其余指定的 $k-1$ 种，有 $g(n-1,k-1)$ 种。

因此原文的递推为

$$
g(n,k)=k\,g(n-1,k)+k\,g(n-1,k-1),\qquad n,k\ge1.
$$

初始条件应完整写为

$$
g(0,0)=1,\qquad g(n,0)=0\ (n>0),\qquad g(0,k)=0\ (k>0).
$$

当 $k>n$ 时也为零。这里 $g(0,0)=1$ 对应唯一的空序列。

### 第二类斯特林数的递推（补充证明）

由非空分组定义可得

$$
S(n,k)=kS(n-1,k)+S(n-1,k-1).
$$

> [!proof] 补充证明
> 考虑第 $n$ 个元素所在的组。若它不单独成组，先将其余元素分成 $k$ 个非空组，再选一个组放入它，共 $kS(n-1,k)$ 种；若它单独成组，其余元素分成 $k-1$ 个非空组，共 $S(n-1,k-1)$ 种。两类互斥且穷尽。

边界同样为 $S(0,0)=1$，$S(n,0)=0$（$n>0$），$S(0,k)=0$（$k>0$），$k>n$ 时为零。结合 $g(n,k)=k!S(n,k)$，也能得到上一递推。

整理时用递推补充核验：

$$
S(10,6)=22\,827,\qquad
g(10,6)=720\times22\,827=16\,435\,440.
$$

### 原文提到的另一种状态

若改为“从固定的 6 种口味里，恰有 $k$ 种出现”，记为 $h(n,k)$，则（整理补充）

$$
h(n,k)=\binom6k g(n,k),\qquad 0\le k\le6,
$$

其递推为

$$
h(n,k)=k h(n-1,k)+(7-k)h(n-1,k-1).
$$

第一个系数来自已出现的 $k$ 种；第二个系数来自此前未出现的 $6-(k-1)$ 种。边界为 $h(0,0)=1$，其余空序列状态为零，非法下标状态也为零。原文对第二项系数的犹豫，源于混用了“指定 $k$ 种”和“6 种中任意 $k$ 种”两个状态。

## 4. 指数型生成函数（进阶选学）

一种指定口味至少出现一次，对应

$$
e^x-1=\sum_{r=1}^{\infty}\frac{x^r}{r!}.
$$

因此答案可写作

$$
N=10![x^{10}](e^x-1)^6,
$$

其中 $[x^{10}]$ 表示取 $x^{10}$ 的系数。

> [!proof] 补充证明：为什么提取系数后乘 $10!$
> 展开六个级数的乘积时，每一个满足 $x_1+\cdots+x_6=10$、$x_i\ge1$ 的次数向量贡献 $1/(x_1!\cdots x_6!)$。乘以 $10!$ 后，正好成为第一节的多项式系数计数。因此这里的乘积由次数分配的组合结构决定，不需要概率意义上的“独立性”假设。

用二项式定理展开：

$$
(e^x-1)^6=\sum_{j=0}^{6}(-1)^j\binom6j e^{(6-j)x}.
$$

又因为

$$
e^{(6-j)x}=\sum_{n=0}^{\infty}\frac{(6-j)^n}{n!}x^n,
$$

所以

$$
N=10!\sum_{j=0}^{6}(-1)^j\binom6j\frac{(6-j)^{10}}{10!}
=\sum_{j=0}^{6}(-1)^j\binom6j(6-j)^{10}.
$$

> [!warning] 原文方法关系的修正
> 原文说“分组最后仍然绕回容斥”“不用容斥只能用生成函数或递推”，这些说法过强。按次数直接求和、按分组递推，都能独立得到结果；生成函数展开后出现同一个求和式，说明这些表达式相等，不意味着每一种计算过程都必须先使用容斥。容斥对本题很直接，哪种方法更易懂取决于已掌握的知识。

## 5. 二项式系数与两类斯特林数的区别

### 二项式定理给出二项式系数

$$
(x+y)^n=\sum_{k=0}^{n}\binom nk x^{n-k}y^k,
\qquad \binom nk=\frac{n!}{k!(n-k)!}.
$$

例如 $(x+y)^3=x^3+3x^2y+3xy^2+y^3$，系数为 $1,3,3,1$。

> [!proof] 补充证明
> 从 $n$ 个因子 $(x+y)$ 中选出 $k$ 个贡献 $y$，其余贡献 $x$，得到 $x^{n-k}y^k$。选择这 $k$ 个因子有 $\binom nk$ 种，因此得到二项式定理。组合数的阶乘式来自先排列 $k$ 个不同对象，再除以所选对象内部的 $k!$ 种顺序。

### 第一类斯特林数记录循环

本篇采用**无符号第一类斯特林数**

$$
c(n,k)=\left[\begin{matrix}n\\k\end{matrix}\right],
$$

表示 $n$ 个不同元素的排列中，恰有 $k$ 个不相交循环的排列数。每个循环内部按循环顺序区分，循环之间不排序，循环旋转视为相同。

例如 $c(4,2)=11$：循环长度为 $1+3$ 时有 $4\times2=8$ 种，长度为 $2+2$ 时有 3 种，共 11 种。

它对应上升阶乘的展开：

$$
x^{\overline n}=x(x+1)\cdots(x+n-1)
=\sum_{k=0}^{n}c(n,k)x^k.
$$

例如

$$
x(x+1)(x+2)=x^3+3x^2+2x,
$$

所以 $c(3,3)=1$、$c(3,2)=3$、$c(3,1)=2$。

> [!proof] 补充证明：循环计数与上升阶乘
> 加入第 $n$ 个元素时，它或者单独成一个循环，贡献 $c(n-1,k-1)$；或者插入原排列中某个元素之后，共有 $n-1$ 个插入位置，贡献 $(n-1)c(n-1,k)$。因此 $c(n,k)=c(n-1,k-1)+(n-1)c(n-1,k)$。
>
> 令 $P_n(x)=\sum_k c(n,k)x^k$，则 $P_n(x)=(x+n-1)P_{n-1}(x)$，且 $P_0(x)=1$。递推得到 $P_n(x)=x(x+1)\cdots(x+n-1)$。

### 第二类斯特林数把普通幂展开为下降阶乘

定义下降阶乘

$$
x^{\underline k}=x(x-1)\cdots(x-k+1),\qquad x^{\underline0}=1.
$$

则

$$
x^n=\sum_{k=0}^{n}S(n,k)x^{\underline k}.
$$

> [!proof] 补充证明
> 先令 $x$ 为非负整数。将 $n$ 个不同元素分别映射到 $x$ 个标签，有 $x^n$ 种。按实际使用的标签数 $k$ 分类：先分出 $k$ 个非空原像组，有 $S(n,k)$ 种，再向这些组分配互不相同的标签，有 $x^{\underline k}$ 种。相加得到等式。两边都是关于 $x$ 的多项式，且在无穷多个非负整数处相等，故为多项式恒等式。

| 对象 | 组合意义 | 对应展开 |
| --- | --- | --- |
| 二项式系数 $\binom nk$ | 从 $n$ 个不同对象中选 $k$ 个 | $(1+x)^n=\sum_k\binom nk x^k$ |
| 无符号第一类斯特林数 $c(n,k)$ | 排列中有 $k$ 个不相交循环 | $x^{\overline n}=\sum_k c(n,k)x^k$ |
| 第二类斯特林数 $S(n,k)$ | 分成 $k$ 个无标号非空子集 | $x^n=\sum_k S(n,k)x^{\underline k}$ |

二项式定理与第一类斯特林数不是同一个概念；第二类斯特林数也有独立的分组定义。本题直接使用第二类斯特林数，是因为相同口味所在的位置构成非空子集。

返回 [[数学系/离散数学/容斥原理与口味序列计数/学习指南|学习指南]]；主线例题见 [[数学系/离散数学/容斥原理与口味序列计数/02 六种口味排成十位序列|六种口味排成十位序列]]。