计数与概率方法 · 方法讲解

整数分拆:不计顺序的分组

把每种分组排成非降序,再按最小数分类,避免重复与遗漏。

下载视频 ↗
01

8个相同小球,分成3个无标签的非空组

只关心每组有几个。小球彼此相同,组也没有名字;交换两组不产生新分法。组内顺序不计,每组至少1个,恰好分成3组。共有多少种分法?

第1步 / 共7步:先把每种分组按从小到大记录。

125

5、1、2和2、5、1,都只记成(1,2,5)。

对应左侧8个球、3个非空组

排序去重

同一分组只保留一个代表

写成a≤b≤c,而不是给三组贴上甲、乙、丙的标签。

每个圆点代表一个相同小球,横线区分组,横线位置不产生额外分法。

02

为什么排序能保证不重不漏?

学习目标与前置

需要会有序枚举、整数大小关系,了解隔板法中“盒子可区分”的条件。目标是区分整数分拆与有标签分配,给出分类边界,并掌握互异条件下的一一对应。

对象与适用条件

整数分拆把正整数写成若干正整数之和,通常不计加数顺序。本页主要固定为3项,只数数量结构。若物品彼此不同、组有标签,或存在额外容量限制,需重新建模。

一、选规范代表

任何一个分组都能排序,所以不会漏。一个多重集合只有唯一的非降序数量表;即使数量重复,排序后的数值表也相同,所以不会重。我们不是数“排序操作有几种”,而是数排序后的不同结果。

二、从边界生成合法分支

固定三个非空组,设数量为a、b、c,总数为n。只枚举满足下列约束的整数:

1 ≤ a ≤ ⌊n/3⌋; a ≤ b ≤ ⌊(n−a)/2⌋; c=n−a−b。

因为三项都至少为a,所以3a≤n;又因为c≥b,所以2b≤n−a。每选定a、b,c就被总和唯一确定。反过来,任一合法非降序三元组都落在唯一的a分支和b位置。这里⌊x⌋表示不超过x的最大整数。

S班是本项目的深度编排,不代表已核实的地方官方课纲。这里只用小规模枚举与对应,不引入一般分拆公式或生成函数。

03

完整例题:分类枚举与结构变换

例一|8拆成恰好3个正整数,顺序不计

题目即上方8球问题。先规定1≤a≤b≤c,a+b+c=8。a≤⌊8/3⌋=2。

  1. a=1时,1≤b≤⌊7/2⌋=3,得到(1,1,6)、(1,2,5)、(1,3,4),共3种。
  2. a=2时,2≤b≤⌊6/2⌋=3,得到(2,2,4)、(2,3,3),共2种。
  3. a≥3时总数至少9,排除。共3+2=5种。

与隔板法对照:21为何不能除以6?

如果改成甲、乙、丙三个不同盒子,每盒非空,有C(7,2)=21种。无标签分组(1,2,5)对应6个有序排列,(1,1,6)只有3个,(2,3,3)也只有3个。五种代表的排列数依次是3、6、6、3、3,总和21。因为重复倍数不同,21÷6=7/2不能作为分拆数。

例二|12拆成3个互不相同的正整数

条件:三项都为正、总和12、两两不相同、顺序不计。按a<b<c记录。直接枚举可行,但先建立对应能把“互异”变为已熟悉的“可相等”。

  1. 令x=a,y=b−1,z=c−2。整数严格递增意味着x≤y≤z,而且x≥1;总和x+y+z=12−3=9。
  2. 反向给任意1≤x≤y≤z、总和9的三元组,加回0、1、2,得到x<y+1<z+2且总和12。正反过程互逆,分法数相等。
  3. 对9分类:最小数1有(1,1,7)、(1,2,6)、(1,3,5)、(1,4,4);最小数2有(2,2,5)、(2,3,4);最小数3有(3,3,3)。共4+2+1=7种。
  4. 加回阶梯后得到(1,2,9)、(1,3,8)、(1,4,7)、(1,5,6)、(2,3,7)、(2,4,6)、(3,4,5)。答案:7种。

不能直接把总数减3后仍要求三项互异;变换后的条件已经变成允许相等。变换要同时修改总数与约束。

04

迁移练习

练习一|每组至少2个

9个相同小球分成恰好3个无标签的组,每组至少2个,组内顺序不计。共有多少种?

查看完整解析

设2≤a≤b≤c,a+b+c=9。每项减1,得到三个非降序正整数,总和6。最小数1时是(1,1,4)、(1,2,3),最小数2时只有(2,2,2),共3种。加回1,原题为(2,2,5)、(2,3,4)、(3,3,3)。答案3种。也可每项减2,把问题转为总和3的三个非负整数;必须允许零。

练习二|至多3个非空组

6个相同小球分成至多3个非空无标签组,组内顺序不计。不把空组视作额外的组。共有多少种?

查看完整解析

在数量表左侧补零至3项,唯一对应0≤a≤b≤c、总和6。a=0时有(0,0,6)、(0,1,5)、(0,2,4)、(0,3,3),共4种;a=1时有(1,1,4)、(1,2,3),共2种;a=2时有(2,2,2),共1种。总计7种。去掉零后分别是1组、2组或3组的分拆;补零与去零互逆,不重复计算“空组的位置”。

05

反例、边界与回顾

回顾:定对象和标签 → 固定组数与零的规则 → 排序选唯一代表 → 按最小数分类并写边界 → 还原检查总和及限制。

06

逐章回看

点击章节标题,定位到对应的视频讲解。

八个相同小球,分成三个非空的组。组没有标签,交换位置不算新分法。

例如五、一、二与二、五、一,排序后都是一、二、五。每种分组只保留一个非降序代表。

设三组数量为a、b、c,满足一不大于a,a不大于b,b不大于c,而且总和为八。

最小数是一时,有一一六、一二五、一三四。最小数是二时,有二二四、二三三。一共五种。

为什么不能把有序分法二十一除以六?一二五有六个排列,一一六只有三个排列,重复次数并不一致。

再看十二分成三个互不相等的正整数。从小到大,依次减去零、一、二,就变成总和为九的非降序正整数。

反过来依次加回零、一、二,必然严格递增。这是一一对应,枚举得到七种。

先确认组有没有标签、能否为空、组数是否固定。用排序去重,按最小数分类,再检查每个分支的边界。