《组合数学-第七节：整数的分拆》由会员分享，可在线阅读，更多相关《组合数学-第七节：整数的分拆（7页珍藏版）》请在金锄头文库上搜索。
1、2.6 正整数的分拆粗略地说，正整数的分拆就是将一个正整数分成几个正整数的和。在本章的前几节中已经看到，某些重要和式的求和范围都与正整数的分拆有联系，在2.7节中我们将说明有一类分配问题就是“分拆问题”。分拆问题也是组合论的重要内容之一，本节我们将介绍正整数的分拆的概念及其一些最基本的性质，在2.7节中再将本节的一些结果应用到一类分配问题。定义2.6.1正整数n的一个k分拆是把n表示成k个正整数的和（2.6.1）的一种表示法，其中叫做该分拆的分部量。如果表达式（2.6.1）是无序的，也就是说，对诸任意换位后的表示法都只视为一种表示法，这样的分拆叫做无序分拆，或简称为分拆。反之，若表达式（2.6
2、.1）是有序的，即表达式（2.6.1）右边的和不仅与各项的数值有关，而且与各项的次序有关，不同的次序认为是不同的表示法，这样的分拆叫做有序分拆。这时，叫做该有序分拆的第i个分部量。n的k分拆的个数称为n的k分拆数，n的所有分拆（k取遍所有可能的值）的个数称为n的分拆数。例如：是4的所有3个有序3分拆。在4的第一个有序3分拆中，第1个分部量为2，第2个和第3个分部量均匀为1。而：是4的唯一一个3分拆。2.6.1 有序分拆在这一小节中，我们介绍n的有序分拆的计数公式，以及在几类限定条件下n的有序分拆的计数公式。定理2.6.1 正整数n的有序k分拆的个数为。证明 正整数n分成k个分部量的一个有序分拆
3、：，等价于方程：。的正整数解，由2.3节定理2.3.4的证明知，正整数n的有序k分拆的个数为。由定理2.3.4和定理2.6.1，正整数n的有序k分拆数等于多重集合的至少出现一次的n组合数，均为。定理2.6.2 （1）正整数n的有序k分拆，要求第i个分部量大于等于，其个数为：（2）正整数2n分拆成k个分部，各分部量都是正偶数的有序分拆个数为。（3）正整数n分成k个分部，若n与k同为奇数或同为偶数，则n的各分部量都是奇数的有序分拆数为：证明 （1）设：（2.6.2）是n满足条件：（2.6.3）的一个有序k分拆。令：且满足方程：（2.6.4）即是方程（2.6.4）的一组非负整数解。反之，若给定方程（
4、2.6.4）的一组非负整数解，令，则构成n的一个有序k分拆（2.6.2），且满足条件（2.6.3）。所以，n的满足条件（2.6.3）的有序k分拆与方程（2.6.4）的非负整数解之间构成一一对应。由定理2.3.3的证明知，其个数为：（2）设2n的一个有序k分拆：满足条件：为偶数（2.6.5），令，则有：即是n的一个有序k分拆。反之，设是n的一个有序k分拆，令，则是2n的一个满足条件（2.6.5）的有序k分拆。所以，2n满足条件（2.6.5）的有序k分拆数等于n的有序k分拆数，为。（3）n的各分部量为奇数的分拆：与的各分部量为偶数的分拆：显然构成一一对应。由（2）知，n的各分部量为奇数的分拆数为：
5、定理2.6.2给出了几种不同限定条件下的有序分拆数。2.6.2无序分拆我们用来表示n的k分拆的个数，用表示n的所有分拆的个数，则显然有（1）；（2）n的k分拆中，各分部量的次序无关紧要，一般按递降顺序排列。若：则：如果在n的k分拆中有个分部量为，那么可以把该分拆记为：有时也记为：例如，的所有5分拆为：表2.6.1列出了当时n的所有k分拆。定理2.6.3 n的k分拆数满足递推关系：（2.6.6）（2.6.7）证明 由的定义易知等式（2.6.7）成立，下面证明递推关系（2.6.6）为此，我们考虑n分成至多k个分部的分拆，这样的分拆总数为n的每个分成至多k个分部的分拆可表示为：这个和式中包含k项，并
6、且：我们将n的这个m分拆映射到的k分拆如下：该和式中包含k项，并且：设上面确定的映射为，因为不同的n分为至多k个分部的分拆对应着不同的k分拆，所以是单射。又因为每个的k分拆：在作用下的原像是每个减去1，再保留不为零的那些项而得到的n的一个分部数至多为k的分拆，所以是满射。因此，是一一映射，于是有：定理2.6.3提供了对逐行递推的计算方法，见表2.6.2，例如：例1 正整数n的2分折数为：其中，表示小于等于的最大整数。证明 设n的2分拆为：因，所以恰能取1，2，中的任一个，故：2.6.3 分拆的Ferrers图研究分拆数性质的一种简单有效的组合手段就是Ferrers图，设n的一个k分拆为（2.6
7、.8）我们在一条水平直线上画个点，在其下面一条直线上画个点，且使这两条直线上的第一个点在同一条竖线上，其他点依次与上一行的点对齐；依此类推，最后在第k条直线上画个点，第一个点与前面各行的第一个点均在同一条竖线上，其他点依次与上面各行的点对齐，这样得到的点阵图叫做n的k分拆（2.6.8）的Ferrers图例如，15的4分拆：（2.6.9）的Ferrers图如图2.6.1所示。图2.6.1反过来，对于n的一个Ferrers图，又可按上述规则对应于n的唯一的一个分拆。所以，n的分拆同它的Ferrers图之间是一一对应的。把一个Ferrers图的各行改成列，但其相对位置不变，这样又得到一个Ferrer
8、s图，叫做原Ferrers图的共轭图。例如，图2.6.1对应的共轭图是图2.6.2。图2.6.2共轭Ferrers图所对应的分拆叫做原分拆的共轭分拆。例如，图2.6.2对应的分拆（2.6.10）是分拆（2.6.9）的共轭分拆。若n的一个分拆与其共轭分拆相同，则该分拆称为n的自共轭分拆。从分拆的Ferrers图可以证明以下一些定理：定理2.6.4 n的k分拆的个数等于n的最大分部量为k的分拆数。证明 上面定义的分拆的共轭运算是一个映射，它将n的最大分部量为k的分拆映射到n的k分拆。例如，分拆（2.6.9）是15的最大分部量为5的分拆，其共轭分拆（2.6.10）是15的一个5分拆。并且这个映射显然
9、是一一的，所以两者相等。定理2.6.5 n的自共轭分拆的个数等于n的各分部量都是奇数且两两不等的分拆的个数。证明 为了证明这个性质，我们将借助于Ferrers图建立一个n的各分部量为奇数且两两不等的分拆到n的自共轭分拆之间的一一对应。设n的一个分部量为奇数且两两不等的分拆为：（2.6.11）其中：由n的分拆（2.6.11），我们构造n的一个自共轭分拆的Ferrers图。在第1行与第1列都画个点，共有个点；画完第1行和第1行后，在第2行与第2列再各画个点，共个点，此时，第2行与第2列中加上第1行与第1列已画的点，都已有个点；在第k行与第k行再画个点，共个点。因为，所以如此画的n个点的点阵图的每一
10、行都不比下一行的点数少，因而是n的一个分拆的Ferrers图。且由上面的构造法知，该Ferrers图是对称的，所以其对应的分拆是自共轭的。例如，用上述方法由分拆：构造的Ferrers图如图2.6.3所示，对应的自共轭分拆为显然，上面建立的n个分部量为奇数且两两不等的分拆与n的自共轭分拆之间的对应关系是一一的，所以定理的结论成立。图2.6.3定理2.6.6 n的分部量两两不等的分拆的个数等于n的各分部量都是奇数的分拆的个数。证明 证明的方法还是建立定理中提及的两类不同的分拆之间的一一对应。在一个n的各分部量为奇数的分拆中，假设数出现p次，我们将p写成2的幂次和的形式：则这种表示法是唯一的。我们将
11、n的这个分拆的Ferrers图中这个小点按下列方法重排：各行的小点数分别为，如此将原来那个分拆的Ferrers图中所有的点重排了一次。然后再将各行按小点数递减的顺序排列，就得到n的另一个分拆的Ferrers图。例如，分拆的Ferrers图如图2.6.4所示。我们将重复数2，3，5分别写成2的幂次和的形式：则由上述方法构造出的新Fereers图如图2.6.5所示，它所对应的24的分拆为在新的Ferrers图中，各行的点数为的形式。在各行点数的表达式中，参数k和i中必有一个不同，所以各行的点数互不相同，因而它所对应的分拆的各分部量不同。图2.6.4 图2.6.5如上建立了两类分拆之间的一一对应。事实上，任一自然数表示成2的幂次和的形式是唯一的，从而上面建立的映射是单射。另外，上面构造成新的Ferrers图的方法显然是可逆的，所以上面的映射是满射。综合以上分析，n的分部量两两不等的分拆的个数等于n的分部量都是奇数的分拆的个数。例2 n的最小分部量为1的k分拆数等于的分拆数。证明 设n的一个最小分部量为1的k分拆为：（2.6.12）则显然：（2.6.13）是的一个分拆。上面显然构造了一个从n的最小分部量为1的k分拆到的分拆之间的一一对应，所以此两类分拆数相等。
