组合数学-第七节：整数的分拆
网上订火车票怎么订-谭晶简历
2.6正整数的分拆
粗略地说，正整数的分拆就是将一个正整数分成几个正整数的和。在本章的前几节中已经看到，某些
重要和式的求和范围都与正整数的分拆有联系，在
2.7节中我们将说明有一类分配问题就是“分拆问题” 。 分拆问
题也是组合论的重要内容之一，
本节我们将介绍正整数的分拆的概念及其一些最基本的性质， 在2.7
节中再将本节的
一些结果应用到一类分配问题。
定义261正整数n的一个k分拆是把n表示成k个正整数的和
n = n
i
一种表示法，其中 口
.0 1
叮乞
k
n
i
叫做该分拆的分部量。如果表达式（
n
2
• n
k
k _ 1
（2.6.1） 的
2.6.1
）是无序的，也就是说，对诸 m任意换位后的表示法都只视为
一种表示法，这样的分拆叫做无序分拆，
或简称为分拆。反之，若表达式（2.6.1）是有序的，即表达式（261）
右边的和不仅与各项的数值有关，而且与各项的次序有关，不同的次序认为是不同的表示法，这样的分拆
叫做有序分拆。这时，
n
i
叫做该有序分拆的第
i个分部量。n的k分拆的个数称为 n的k分拆数，n的所
有分拆（k取遍所有可能的值）的个数称为
例如：
4 =2 11 =1 2 1
=1 1 2
是4的所有3个有序3分拆。在4的第一个有序3分拆中，第1个分部量为2,第2个和第3个分部量均
匀为 1。而：
4 = 2 • 1 • 1
是4的唯 --- 个3分拆。
2.6.1有序分拆
在这一小节中，我们介绍
n的有序分拆的计数公式，以及在几类限定条件下
「
n-1
）
。
k1
」
n的有序分拆的计数公式。
n的分拆数。
定理2.6.1正整数n的有序k分拆的个数为
l -
证明
正整数n分成k个分部量的一个有序分拆：
n = n
1
'
| ■
n
k
，等价于方程：
X
|，
x
2
•
11「
x
k
= n
。
n的有序k分拆的个数为
的正整数解
厲川
2
丨||
n
k
，由2.3节定理2.3.4的证明知，正整数
卞一
1
.,
k
由定理2.3.4和定理2.6.1，正整数 n的有序k分拆数等于多重集合
M
-「：：
a
「；
a
2
,HI,
；
a
?
的
a
1
,ajl|a
k
至少出现一次的
1^-1
、
n组合数，均为
Ik-1
丿
定理2.6.2 （ 1）正整数n的有序k分拆，要求第i个分部量大于等于 口，其个数为:
k-1
（2）正整数2n分拆成k个分部，各分部量都是正偶数的有序分拆个数为
m-1]
1丿。
（3）正整数n分成k个分部，若n与k同为奇数或同为偶数，则
n的各分部量都是奇数的有序分拆数为:
山―
k
八
------ -1
2
I k 一
1
」
证明
（
1）设：
n = n
1
JH
n
k
（2.6.2）
（2.6.3） 是 n 满足条件：
n^Pi（1WiEk）
的一个有序
k
分拆。令：
％
=口 - 口
1 _ i _ k
且满足方
程：
Y
1
y
2
丨
1（ Y
k =
m - P
1
k
n
2
- P
2
川
n
k
-
P
k
（ 2.6.
4）
即
y
1
,y
2
」l（,y
k
是方程（2.6.4）的一组非负整数解。
反之，若给定方程（2.6.4）的一组非负整数解
有序k分拆（2.6.2），且满足条件（263）。
所以，n的满足条件（2.6.3）的有序k分拆与方程（2.6.4）的非负整数解之间构成
------- 对应。由定理 2.3.3
的证明知，其个数为：
k
y^,
y
2
^|, y
k
，令
n = % + Pi
（1
兰
i
兰
k ）
，则构成n的一个
n k p -1
i d
k-1
（2）设2n的一个有序k分拆：
2n =
x
1
■ x^ J
H ■ x
k
x
满足条件：
X
i
为偶数
（
1 w i Ek
）（2.6.5），令
y
i
=寸
（
1
兰
i Ek
），则有：
n = y1 + y
?
+川
+
Y
k
即
Y
1
* Y
2
Y
k
是n的一个有序k分拆。
反之，设
％
*
y
2
V
Y
k
是n的一个有序k分拆，令
X
j
= 2%
仁
i
岂
k
，则捲，
x
?
V
X
k
是2n的一
个满足条件（2.6.5）的有序k分拆。
所以，2n满足条件（2.6.5）的有序
k分拆数等于n的有序k分拆数，为
l
k
T
」
（3
）
n
的各分部量为奇数的分拆：
n =y
1
■
y
2
Jll y
k
与
n -
k
的各分部量为偶数的分拆：
n -
k =
（n
1
T）
■ （n
2
T） ' 1
1
「
（
n
k
T）
n -1 1 _i _k
偶
显然构成—对应。由（
2
）知，
n
的各分部量为奇数的分拆数为:
定理2.6.2给出了几种不同限定条件下的有序分拆数。
262无序分拆
我们用
B n,k
来表示n的k分拆的个数，用
Bn
表示n的所有分拆的个数，则显然有
n
(1)
B n,k
=0
k n
； (2)
B n
為
B n,k
k4
n的k分拆中，各分部量的次序无关紧要，一般按递降顺序排列。若：
n
二
n
1
• n
■ nk
则：
m _
n
2
1
1（ n
k
n -k
1
1 k
2
■ k
n
n
如果在n的k分拆中有
k
i
个分部量为
i 1
mi
乞
k
，那么可以把该分拆记为：
有时也记为：
n
=仆
2
吩
n
kn
9 =5 1
例如，
B 9,5 =5,9
的所有5分拆为：
1 1 ^1 5 4 1
^2 3 3 1
2 1
= 4211^141231
=3 3 1
1
= 3 2 2 1 1 =1 3 2 2
=22221=4211
表2.6.1列出了当
n -1,2,3,4,5
时n的所有k分拆
1
乞
i
乞
k
。
表2■召■ 1 分拆表
X
]
2
3
1
1
2 3
4
5
]
2
3
4
5
r
12
13. 2
2
11,
23
l
3
1-2
1 咯 12
a
V2
..
5
J
I
5
定理2.6.3 n的k分拆数
B n, k
满足递推关系：
Bn
k,^-B n,1 • B n ,2
•川•
B n,k
(2.6.6)
B n,1i
；
=1,B n,n ]=1
(2.6.7) 证明
由
B
n,k
的定义易知等式（2.6.7）成立，下面证明递推关系
（2.6.6）为此，我们考虑
n分成至多
k个分部的分拆，这样的分拆总数为
B
n,1 B n,2B n,k
n = m ■ n
2
■ n
m
• 0 • • 0 n
的每个分成至多
k
个分部的分拆可表示为：
这个和式中包含k项，并且：
ni_n
2
川
n
m
_11^m^k
f i n
2
• 1 • 1n
m
T
• 1 • 111 • 1
我们将
n
的这个
m
分拆映射到
n •
k
的
k
分拆如下：
n • k = n
1
该和式中包含k项，并且：
n
「
1_n
2
,1 n
m
，
1_2
设上面确定的映射为
f
，因为不同的n分为至多k个分部的分拆对应着
n
・
k
不同的k分拆，所以
f
是单
射。又因为
每个
n •
k
的
k
分拆：
n
亠
k = hT
2
71( ' l
k
n的一个分部数至多为 k
在
f
作用下的原像是每个
l
i
1 < Hl
k
减去1,再保留不为零的那些项而得到的
的分拆，所以
f
是满射。因此，
f
是一一映射，于是有：
定理2.6.3提供了对
B n,k
逐行递推的计算方法，见表
Bn
k,k
二
B n,1 B n,2
•川•
B n,k
2.6.2,例如：
B 9,5 i
；
= B 4,1 B 4,2 B
4,3 B 4,4 B 4,5 [=1 2 1 1 0 = 5
证明
设
n
的
2
分拆为：
n
二
n •
r
b
m _
珏
|中的任一个，故：
B(n
,2)=j
卫
「
2
」
2
因
n
1
-匕，所以
n
2
恰能取1, 2,……,
2.6.3
分拆的Ferrers图
正整数
n
的
2
分折数为：
B(n,2)=—
其中,
.2
一
表 2- 6- 2
表示小于等于
n
的最大整数。
2
1
二J
2
3
4
5
5 …
1
2
3
4
5 '
6
:
1
1
1
1
I
2
1
1
2
2
3
■
3
]
I
''1
1
1
2
,3
1-
石
1
2
<■
I
1
1
7
11
I- fl
研究分拆数性质的一种简单有效的组合手段就是
*
4
A
A
■ A
■ !l
Ferrers
*
图，设n的一个k分拆为
n
二厲
n
2
我们在一条水平直线上画
l||
n
k
n _ n
2
川
n
k
(268)
n
i
个点，在其下面一条直线上画
n
2
个点，且使这两条直线上的第一个点在同一条
k条直线上画
n
k
个点，第一个点与前面各行
n的k分拆（2.6.8）
竖线上，其他点依次与上一行的点对齐；依此类推，最后在第
的第一个点均在同一条竖线上， 其他点依次与上面各行的点对齐， 这样得到的点阵图叫做
的 Ferrers 图
例如，15 的 4 分拆：
1^5 5 3
的Ferrers图如图2.6.1所示。
2
（2.6.9）
□
0000
[]][[
L J J
C ]
图 2.6.1
反过来，对于n的一个Ferrers图，又可按上述规则对应于
n的唯一的一个分拆。所以，n的分拆同它的Ferrers
图之间是 --- 对应的。
把一个Ferrers图的各行改成列，但其相对位置不变，这样又得到一个
图。例如，图2.6.1对应的共轭图是图 2.6.2。
Ferrers图，叫做原Ferrers图的共轭
□ □ □ D
图
2.6.2
共轭Ferrers图所对应的分拆叫做原分拆的共轭分拆。例如，图
2.6.2对应的分拆
15=4 4 3 2 2
）
是分拆（2.6.9）的共轭分拆。若 n的一个分拆与其共轭分拆相同，则该分拆称为
n的自共轭分拆。
从分拆的Ferrers图可以证明以下一些定理：
定理2.6.4
n的k分拆的个数等于n的最大分部量为k的分拆数。
证明 上面定义的分拆的共轭运算是一个映射，
（ 2.6.10
它将n的最大分部量为k的分拆映射到n的k分拆。例如，
分拆（
2.6.9）是15的最大分部量为5的分拆，其共轭分拆（2.6.10）是15的一个5分拆。并且这个映射
显然是一一
的，所以两者相等。
定理2.6.5 n的自共轭分拆的个数等于
证明
为了证明这个性质，我们将借助于
的自共轭分拆之间的 -- 对应。
n的各分部量都是奇数且两两不等的分拆的个数。
Ferrers图建立一个n的各分部量为奇数且两两不等的分拆到 n
设n的一个分部量为奇数且两两不等的分拆为:
n = 2
口
1 i
亠
i2n
2
1
川
2n
k
1
(2.6.11)
则由上述方法构造出的新
图如图2.6.5所示，它所对应的24的分拆为
Fereers
其中：
n
i
.
n
2
111 n
k
_0
由n的分拆（2.6.11）,我们构造n的一个自共轭分拆的
Ferrers图。在第1行与第1列都画n^ +1个点，共
有
2n-
|
1
个点；画完第1行和第1行后，在第2行与第2列再各画
n
2
1
个点，共
2n
2
• 1
个点，此时，第
2行与第2列中加上第1行与第1列已画的点，都已有
n
2
1
个点；……
;
在第k行与第k行再画
n
k
1
个 点，共
2n
k
，
1
个点。因为
厲.啓
||（
n
k
，所以如此画的
n
个点的点阵图的每一行都不比下一行的点数
少，因而是n的一个分拆的
Ferrers图。且由上面的构造法知，该
Ferrers图是对称的，所以其对应的分拆
17=9+5+3
是自共轭的。例如，用上述方法由分拆：
241 221 211
构造的Ferrers图如图2.6.3所示，对应的自共轭分拆为
17=5 4 4 3
1
显然，上面建立的n个分部量为奇数且两两不等的分拆与
定理的结论成立。
n的自共轭分拆之间的对应关系是一一的，所以
L _L L
_L J
图 2.6.3
定理2.6.6 n的分部量两两不等的分拆的个数等于
n的各分部量都是奇数的分拆的个数。
证明
证明的方法还是建立定理中提及的两类不同的分拆之间的一一对应。
在一个n的各分部量为奇数的分拆中，假设数
2k
1
出现p次，我们将p写成2的幕次和的形式：
P=2
「
2
「川
i
1
i
2
-HI
则这种表示法是唯一的。我们将
n的这个分拆的Ferrers图中这
p 2k 1
个小点按下列方法重排：各行
的小点数分别
为
2k 1 ■2
i1
, 2k 1
2
i2
,l||
,如此将原来那个分拆的 Ferrers图中所有的点重排了一次。
然后再将各行按小点数递减的
顺序排列，就得到
例如，分拆
n的另一个分拆的Ferrers图。
24=2 5 3 3 5 1
的Ferrers图如图2.6.4所示。我们将重复数 2, 3, 5分别写成2的幕次和的形式：
2 =2[
3 =2
「
2
0
5 =
2
2
2
°
24
=10 6431
在新的Ferrers图中，各行的点数为
2k - 1
■2
i
的形式。在各行点数的表达式
2k - 1
■2
i
中，参数k和i
中必有一个不同，所以各行的点数互不相同，因而它所对应的分拆的各分部量不同。
:L
21
-
6
L - L2
0
3
=3
L
2
2
2
1=4
C C ] ]
C C
C
：：
]
L L L
L
|L
id
图 2.6.4
图 2.6.5
如上建立了两类分拆之间的一一对应。事实上，任一自然数表示成
建立的映射是单射。另外，上面构造成新的
2的幕次和的形式是唯一的，从而上面
Ferrers图的方法显然是可逆的，所以上面的映射是满射。
n的分部量都是奇数的分拆的个数。 综合以上分析，n的分部量两两不等的分拆的个数等于
例2 n的最小分部量为1的k分拆数等于
n -1
的
k
-1
分拆数。
证明 设n的一个最小分部量为 1的k分拆为：n = n-
i
n
2
，
|l（ • n
k
」• 1 （2.6.12）
则显然：
n
「
1 = n^i • n
2
J
1（
，
n
k
」 （2.6.13）
是
n -1
的一个
k -1
分拆。上面显然构造了一个从
n的最小分部量为1的k分拆到
n -1
的
k -1
分拆之间的
对应，所以此两类分拆数相等。
则由上述方法构造出的新
Fereers图如图2.6.5所示，它所对应的24的分拆为