信奥赛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) 1S(n, 0) 0对 n 0S(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) 1S ( 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)12×13则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)12×37。组合意义验证将 4 个不同球放入 2 个相同盒子方案确实有 7 种一个盒子 1 个球另一个 3 个球选哪个球单独放有 4 种。两个盒子各 2 个球固定一个盒子包含 1 号球另一个球有( 3 1 ) 3 \binom{3}{1} 3(13)3种选择。但注意盒子相同无顺序所以就是 3 种。总 (437) 种。例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)33×16则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)73×625。三、编程案例盒子与球题目描述现有r rr个互不相同的盒子和n nn个互不相同的球要将这n nn个球放入r rr个盒子中且不允许有空盒子。请求出有多少种不同的放法。两种放法不同当且仅当存在一个球使得该球在两种放法中放入了不同的盒子。输入格式输入只有一行两个整数分别代表n nn和r rr。输出格式输出一行一个整数代表答案。输入输出样例 1输入 13 2输出 16说明/提示样例输入输出 1 解释有两个盒子编号为1 , 2 1, 21,2和三个球编号为1 , 2 , 3 1, 2, 31,2,3共有六种方案分别如下盒子编号方案 1方案 2方案 3方案 4方案 5方案 6盒子1 11小球1 11小球2 22小球3 33小球2 , 3 2, 32,3小球1 , 3 1, 31,3小球1 , 2 1, 21,2盒子2 22小球2 , 3 2, 32,3小球1 , 3 1, 31,3小球1 , 2 1, 21,2小球1 11小球2 22小球3 33数据规模与约定对于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!代码实现#includebits/stdc.husingnamespacestd;constintN15;// 范围很小开大一点防止越界intn,m;ints[N][N];// s[i][j] 表示 S(i, j)inta[N];// a[j] 表示 j!intmain(){cinnm;// 特判如果盒子数大于球数不可能非空if(mn){cout0endl;return0;}// 1. 初始化边界s[0][0]1;for(inti1;in;i)s[i][0]0;// S(n,0)0 (n0)// 2. 递推计算第二类斯特林数for(inti1;in;i){for(intj1;jmin(i,m);j){s[i][j]s[i-1][j-1]j*s[i-1][j];}}// 3. 计算阶乘a[0]1;for(inti1;im;i){a[i]a[i-1]*i;}// 4. 输出结果couts[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各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、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.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}
信奥赛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) 1S(n, 0) 0对 n 0S(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) 1S ( 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)12×13则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)12×37。组合意义验证将 4 个不同球放入 2 个相同盒子方案确实有 7 种一个盒子 1 个球另一个 3 个球选哪个球单独放有 4 种。两个盒子各 2 个球固定一个盒子包含 1 号球另一个球有( 3 1 ) 3 \binom{3}{1} 3(13)3种选择。但注意盒子相同无顺序所以就是 3 种。总 (437) 种。例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)33×16则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)73×625。三、编程案例盒子与球题目描述现有r rr个互不相同的盒子和n nn个互不相同的球要将这n nn个球放入r rr个盒子中且不允许有空盒子。请求出有多少种不同的放法。两种放法不同当且仅当存在一个球使得该球在两种放法中放入了不同的盒子。输入格式输入只有一行两个整数分别代表n nn和r rr。输出格式输出一行一个整数代表答案。输入输出样例 1输入 13 2输出 16说明/提示样例输入输出 1 解释有两个盒子编号为1 , 2 1, 21,2和三个球编号为1 , 2 , 3 1, 2, 31,2,3共有六种方案分别如下盒子编号方案 1方案 2方案 3方案 4方案 5方案 6盒子1 11小球1 11小球2 22小球3 33小球2 , 3 2, 32,3小球1 , 3 1, 31,3小球1 , 2 1, 21,2盒子2 22小球2 , 3 2, 32,3小球1 , 3 1, 31,3小球1 , 2 1, 21,2小球1 11小球2 22小球3 33数据规模与约定对于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!代码实现#includebits/stdc.husingnamespacestd;constintN15;// 范围很小开大一点防止越界intn,m;ints[N][N];// s[i][j] 表示 S(i, j)inta[N];// a[j] 表示 j!intmain(){cinnm;// 特判如果盒子数大于球数不可能非空if(mn){cout0endl;return0;}// 1. 初始化边界s[0][0]1;for(inti1;in;i)s[i][0]0;// S(n,0)0 (n0)// 2. 递推计算第二类斯特林数for(inti1;in;i){for(intj1;jmin(i,m);j){s[i][j]s[i-1][j-1]j*s[i-1][j];}}// 3. 计算阶乘a[0]1;for(inti1;im;i){a[i]a[i-1]*i;}// 4. 输出结果couts[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各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}1、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html2、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html3、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.html4、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}
