信奥赛C++提高组csp-s之组合数学专题课：第二类斯特林数

信奥赛C++提高组csp-s之组合数学专题课：第二类斯特林数

一、数学原理

1. 定义

第二类斯特林数通常记作 S(n, k) 或{ n k } \begin{Bmatrix} n \\ k \end{Bmatrix}{nk​}，其组合意义是：

将 n 个两两不同的元素，划分为 k 个互不区分的非空子集的方案数 。

这等价于经典的“球盒问题”：n 个不同的球放入 k 个相同的盒子，不允许有空盒。

2. 递推关系

第二类斯特林数满足以下递推式：
( n , k ) = S ( n − 1 , k − 1 ) + k ⋅ S ( n − 1 , k ) (n, k) = S(n-1, k-1) + k \cdot S(n-1, k)(n,k)=S(n−1,k−1)+k⋅S(n−1,k)
边界条件：

• S(0, 0) = 1
• S(n, 0) = 0（对 n > 0）
• S(n, k) = 0（对 k > n）

递推式的组合意义证明：
考虑第 n 个元素的放置方式 ：

• 单独成盒：前 n-1 个元素已经组成了 k-1个非空子集，第 n 个元素单独成为第 k 个子集。方案数为 S(n-1, k-1)。
• 放入已有盒子：前 n-1 个元素已经组成了 k 个非空子集，第 n 个元素可以放入这 k 个盒子中的任意一个。方案数为k × S ( n − 1 , k ) k \times S(n-1, k)k×S(n−1,k)。

根据加法原理，两式相加即得递推式。

3. 一些特殊值

• S(n, 1) = 1：所有元素只能放在同一个盒子里。
• S(n, 2) =2 n − 1 − 1 2^{n-1} - 12n−1−1。
• S(n, n-1) =( n 2 ) \binom{n}{2}(2n​)：相当于选两个元素放在同一个盒子，其余各成单元素集合。
• S(n, n) = 1：每个盒子恰好一个元素。

二、数学例子

例1：计算 (S(4, 2))

用递推式计算：

• S(3, 1) = 1
• S ( 3 , 2 ) = S ( 2 , 1 ) + 2 ⋅ S ( 2 , 2 ) = 1 + 2 × 1 = 3 S(3, 2) = S(2, 1) + 2 \cdot S(2, 2) = 1 + 2 \times 1 = 3S(3,2)=S(2,1)+2⋅S(2,2)=1+2×1=3
  则S ( 4 , 2 ) = S ( 3 , 1 ) + 2 ⋅ S ( 3 , 2 ) = 1 + 2 × 3 = 7 S(4, 2) = S(3, 1) + 2 \cdot S(3, 2) = 1 + 2 \times 3 = 7S(4,2)=S(3,1)+2⋅S(3,2)=1+2×3=7。

组合意义验证：将 4 个不同球放入 2 个相同盒子，方案确实有 7 种：

• 一个盒子 1 个球，另一个 3 个球：选哪个球单独放？有 4 种。
• 两个盒子各 2 个球：固定一个盒子包含 1 号球，另一个球有( 3 1 ) = 3 \binom{3}{1} = 3(13​)=3种选择。但注意盒子相同，无顺序，所以就是 3 种。
  总 (4+3=7) 种。

例2：计算 (S(5, 3))

递推：

• S(4, 2) = 7（已算）
• S ( 4 , 3 ) = S ( 3 , 2 ) + 3 ⋅ S ( 3 , 3 ) = 3 + 3 × 1 = 6 S(4, 3) = S(3, 2) + 3 \cdot S(3, 3) = 3 + 3 \times 1 = 6S(4,3)=S(3,2)+3⋅S(3,3)=3+3×1=6
  则S ( 5 , 3 ) = S ( 4 , 2 ) + 3 ⋅ S ( 4 , 3 ) = 7 + 3 × 6 = 25 S(5, 3) = S(4, 2) + 3 \cdot S(4, 3) = 7 + 3 \times 6 = 25S(5,3)=S(4,2)+3⋅S(4,3)=7+3×6=25。

三、编程案例：盒子与球

题目描述

现有r rr个互不相同的盒子和n nn个互不相同的球，要将这n nn个球放入r rr个盒子中，且不允许有空盒子。请求出有多少种不同的放法。

两种放法不同当且仅当存在一个球使得该球在两种放法中放入了不同的盒子。

输入格式

输入只有一行两个整数，分别代表n nn和r rr。

输出格式

输出一行一个整数代表答案。

输入输出样例 1

输入 1

3 2

输出 1

6

说明/提示

样例输入输出 1 解释

有两个盒子（编号为1 , 2 1, 21,2）和三个球（编号为1 , 2 , 3 1, 2, 31,2,3），共有六种方案，分别如下：

数据规模与约定

对于100 % 100\%100%的数据，保证0 ≤ r ≤ n ≤ 10 0 \leq r \leq n \leq 100≤r≤n≤10，且答案小于2 31 2^{31}231。

思路分析

题意简述：

现有 ( r ) 个互不相同的盒子和 ( n ) 个互不相同的球，要将这 ( n ) 个球放入 ( r ) 个盒子中，且不允许有空盒子。请求出有多少种不同的放法。

与第二类斯特林数的关系

第二类斯特林数 S(n, r) 的组合意义是：

将 ( n ) 个不同的球放入 ( r ) 个相同的盒子，不允许空盒的方案数。

而本题的盒子是互不相同的（即有标号的盒子）。因此，只需要在第二类斯特林数的基础上，乘以盒子的全排列 ( r! ) 即可：
答案 = S ( n , r ) × r ! \text{答案} = S(n, r) \times r!答案=S(n,r)×r!

代码实现

#include<bits/stdc++.h>usingnamespacestd;constintN=15;// 范围很小，开大一点防止越界intn,m;ints[N][N];// s[i][j] 表示 S(i, j)inta[N];// a[j] 表示 j!intmain(){cin>>n>>m;// 特判：如果盒子数大于球数，不可能非空if(m>n){cout<<0<<endl;return0;}// 1. 初始化边界s[0][0]=1;for(inti=1;i<=n;i++)s[i][0]=0;// S(n,0)=0 (n>0)// 2. 递推计算第二类斯特林数for(inti=1;i<=n;i++){for(intj=1;j<=min(i,m);j++){s[i][j]=s[i-1][j-1]+j*s[i-1][j];}}// 3. 计算阶乘a[0]=1;for(inti=1;i<=m;i++){a[i]=a[i-1]*i;}// 4. 输出结果cout<<s[n][m]*a[m]<<endl;return0;}

功能分析

1. 核心逻辑

• 递推填表：双重循环计算所有 S(i, j)，其中1 ≤ j ≤ min ⁡ ( i , m ) 1 \le j \le \min(i, m)1≤j≤min(i,m)。
• 阶乘计算：简单循环累乘。
• 最终答案：S ( n , m ) × m ! S(n, m) \times m!S(n,m)×m!。

2. 边界处理

• 当m > n时，直接输出 0（不可能非空）。
• 递推时内层循环上限取min(i, m)，避免计算无意义的状态。

3. 复杂度

• 时间：O ( n ⋅ m ) O(n \cdot m)O(n⋅m)，这里n , m ≤ 10 n, m \le 10n,m≤10。
• 空间：O ( n 2 ) O(n^2)O(n2)，极小。

更多系列知识，请查看专栏：《信奥赛C++提高组csp-s知识详解及案例实践》：
https://blog.csdn.net/weixin_66461496/category_13113932.html

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

1、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html

2、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）
https://blog.csdn.net/weixin_66461496/category_13125089.html

3、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html

4、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}