06第二章：正整数的分拆2014

23
本讲内容
1 、正整数分拆的概念 2 、有序分拆
3 、分拆数 4 、分拆的 Ferrers 图
24
12
四、分拆的 Ferrers 图
我们将借助于Ferrers图来研究正整数分拆， 这是一种直观有效的组合思想. 设 n是一个正整数，n的一个k部分拆 =(n1, n2, …, nk )≥ 的 Ferrers 图是由 n个点组成的一个(形如倒置 阶梯的)平面格点阵列, 它有 k行, n1列 ,其第i行 点数为ni (1≤i≤k).
…
第 2个盒子
…
…
第 k个盒子
有 n1个
有 n2个
有 nk个
7
本讲内容
1 、正整数分拆的概念 2 、有序分拆
3 、分拆数 4 、分拆的 Ferrers 图
8
4
二、 有序分拆
有序分拆:若表达式 n=n1+n2+…+nk (2-1) 各分部不同的次序认为是不同的表示法.
有序分拆可用一个有序k元组 n1,n2,…,nk 来 表示 .这时称ni为这个有序分拆的第i个分部.
1 1+2 2+…+nn=n
17
三、分拆数
1. 分拆的指数型表示法
n的一种分拆为 1122 … n n-型的，则有
1 1+2 2+…+n n=n 即 1, 2,…, n为下面不定方程 1x1+2x2+…+nxn=n (2-3) 的一个非负整数解. 反之不定方程 (2-3)的一个非负整数解对应n的一 种无序分拆 . p(n)恰是不定方程 (2-3)的非负整数解个数 .
定理 2.13 n的各分部都是奇数的分拆的个数 等于 n的各分部两两不同的分拆的个数.
例如 =543315对应 因为 4=22，3=20+21， 5=20+22.
22 21 21,22,3· 20,20) =(20,6,4,3,1)
所以 =543315对应的 ’ =(20,6,4,3,1) 如右图 .
18
9
三、分拆数
2. 分拆数的递推关系
由正整数n的k部分拆的定义可知， 若 n>1，则 p(n,1)=p(n,n1)=1， p(n,2) = n/2，
迄今为止 , p(n, k)和 p(n)都没有比较简单的计 数公式 .
19
三、分拆数
n2 , 12 n2 1 - , 12 12 p( n, 3) 2 n - 1 , 12 3 2 n 1, 12 4 n 0 (mod 6) n 1, 5 (mod 6) n 2, 4 (mod 6) n 3 (mod 6) n2 12
证明 设 n+k的 k部分拆的集合是E, n的至多有 k个分布的 分拆的集合为 F，定义映射 : E —— F =(n1,n2 ,…,nk ) | ( )=(n1–1,n2 –1,…,nj –1) , 其中 j是使 nj >1的最大下标 . 因为 n+k>k, 所以 n1>1,故这样的 j存在. 是双射.
22
11
三、分拆数
定理 2.9 设 n,k，则p(n, k)有如下递推关系： (1) p(n,k)= p(n–1,k–1)+ p(n–k,k); (2) p(n+k,k)= p(n, 1)+ p(n,2)+…+p(n,k).
利用定理 2.9，理论上讲可以对n从小到大逐步求得 所有 p(n, k)的值。于是可以求出p(n).
有序分拆的计数问题常常能归结为求不定方程的整
数解问题 .
9
二、 有序分拆
定理 2.8 正整数n的一个k部有序分拆n1,n2,…, nk 就是 k元不定方程 x1+ x2+ …+ xk=n (2-2) 的一个正整数解，从而可知其总数是
n - 1 C ( n - 1, n - k ) k - 1
当实数a 整数 +1/2时，记号a表示与a最接近 的整数.
20
10
三、分拆数
定理 2.9 设 n,k，则p(n, k)有如下递推关系： (1) p(n,k)= p(n–1,k–1)+ p(n–k,k); 证明 n的所有k部分拆(n1,n2,…,nk)可分成两类：
一类满足nk=1，共有p(n–1,k–1)个；
15
三、分拆数
p(n, n) =p(n, 1) =1.
若 k >n 1, 则 p(n, k)=0， p(n,0)=p(0,n)=0. 规定 p(0, 0)=1, 则函数p(n,k)的定义域是0.
无序分拆的计数问题能否也可归结为带有一定限制
条件的不定方程的整数解问题呢？
16
8
三、分拆数
1. 分拆的指数型表示法 例如 4的所有分拆有如下表示： 4＝ 4→41,4＝3+1→31 11,4＝2+2→22, 4＝ 2+1+1→2112，4＝1+1+1+1→14. 一般地,如果 n的一种分拆中有1个1, 2个 2,…, n个n，称为1122 … n n-型的，且有
12
6
二、 有序分拆
例 2 设 p1,p2,…,pk是k个正整数, 则正整数n的k 部有序分拆中第i个分部大于等于pi (1 ik)的 分拆个数是
k n k 1 p i i 1 k -1
它也是把 n个全相同的球放进k个全不同的盒子里, 第 i个盒子里至少有pi个球的分配方法数.
=(5,5,3,2)≥

* = (4,4,3,2,2)≥
*的 Ferrers图是通过的 Ferrers图的转置得到的.
28
14
四、分拆的 Ferrers 图
记 n的所有分拆的集合为F (n),则映射 |* 定义了F (n)到自身的一个双射. 映射 |*把F (n)中的最大分部是k的分 拆映射成一个k部分拆.
25
四、分拆的 Ferrers 图
下面分别是15的一个分拆=(5,5,3,2)≥的 Ferrers图
26
13
四、分拆的 Ferrers 图
若记 n的一个k部分拆=(n1, n2, …, nk )≥ 的 Ferrers 图第 j列点数为sj (1≤j≤n1), 则
s1 s2 ... sn1 n
13
本讲内容
1 、正整数分拆的概念 2 、有序分拆
3 、分拆数 4 、分拆的 Ferrers 图
14
7
三、分拆数
现在来研究无序分拆，即对诸ni任意换位后不 变的分拆,无序分拆记为=(n1,n2,…,nk)
无序分拆简称为分拆. p(n,k)--正整数n的所有k部分拆的个数; n的 k部分拆数. p(n)-- n的所有分拆的个数称为n的分拆数． p(n)= p(n,1)+ p(n,2)+…+ p(n,n)
4
2
本讲内容
1 、正整数分拆的概念 2 、有序分拆 3 、分拆数
4 、分拆的 Ferrers 图
5
一、 基本概念
给定 n, k, n的一个k部分拆:把n表示成k个正整数之和 n=n1+n2+…+nk (2-1) 的一种表示法，其中ni 1(1ik). 分部： ni 容量： ni的大小 分拆分为有序分拆和无序分拆 无序分拆简称为分拆
20
33
思考题
P65 2.14 2.18
34
17
小 结：
1 、正整数分拆的概念 2 、有序分拆 3 、分拆数
4 、分拆的 Ferrers 图
35
课后练习
P65 2.12 2.13 2.15 2.17 2.19 2.20 2.21
36
18
29
四、分拆的 Ferrers 图
定理 2.10 n的 k部分拆的个数p(n, k)等于n的最 大分部是k的分拆个数; n的至多有k个分部的分 拆的个数(p(n+k, k))等于 n的最大分部至多是k 的分拆的个数.
30
15
四、分拆的 Ferrers 图
满足 *=的分拆称为自共轭分拆.
定理 2.11 一个分拆是自共轭的当且仅当的 Ferrers图的第i行和第i列的点数相同.
组
合
论
第二章 特 殊 计 数
1
组
合
论
第二章 特 殊 计 数
§ 2.3 正整数的分拆
2
1
本讲内容
1 、正整数分拆的概念 2 、有序分拆 3 、分拆数
4 、分拆的 Ferrers 图
3
知识点：
正整数分拆的概念 分拆数及递推关系 分拆的 Ferrers 图
内容及其掌握程度：
理解正整数分拆的有关概念 能熟练掌握计算分拆数的一些方法 学会利用 Ferrers 图来研究正整数分拆
=(4,4,3,2)≥
31
四、分拆的 Ferrers 图
定理 2.12 正整数 n的自共轭分拆的个数等于 n的各分部两两不同且都是奇数的分拆的个数.
例如分拆 =(11,7,5)，各分部两两不同且都是奇数 :
得到自共轭分拆’=(6,5,5,3,3,1).
32
16
四、分拆的 Ferrers 图
则得到 的共轭分拆,记为* =(s1, s2, …, sn1 )≥.
其 Ferrers 图是 的Ferrers 图的转置,也是n 个点的格点阵列. 其第 i行点数为si(1≤i≤n1)， 第 j列点数为 nj (1≤j≤k). 于是 ( *)*=.
27
四、分拆的 Ferrers 图
例如下面分别是15的一个分拆 =(5,5,3,2)≥ 及它的共轭分拆 *的Ferrers图