05 Divide and Conquer. Partitions
Compositions
将20个一模一样的小球分给四个小朋友，有多少种分发呢？顺序很重要，比如和是两种，因为前者第一个小朋友有1个球而后者第一个小朋友有6个！
Definition 5.1. 一个序列，对于所有的，，满足，称之为的弱composition(weak composition)。如果，则称之为的composition。
不确定composition对应的中文翻译，故用英文代替。
Theorem 5.2. 对于正整数和，分为部分的弱composition的数量是 Proof. 该问题其实就是将个球放到个盒子中，等价于用个隔板将个球分开。将个球和个隔板拍成一行，Theorem 3.5告诉我们共有 种不同的排列方式。
如果要求每个小孩至少一个呢？先每人分一个，然后问题就转化为了已知问题。
Corollary 5.3. 对于正整数和，分为部分的composition的数量是
将分成任意多的部分，那么所有的composition数是多少呢？明显地，每个部分不能是0个，也就是说不是弱composition，因为如果可以为0，那么个数就是无穷多，因为可以向每个composition 构成一个新的composition。
Corollary 5.4 对于正整数，其所有composition的个数是。
Proof. 任意部分从1开始一直到，所以
Proof 2. 使用递归法来证明。时，只有一种组合方式。假设时命题成立，我们考虑时即可。对于的每个composition，我们将多出来的一个1分两类处理。1）加到的第一个值上，那么有个，2）放到的第一个值的前面，和1）里面的肯定不同，因为1）里面第一个值至少为2，又有个，共计个不同的composition。
Set Partitions
我们现在考虑球不一样但是盒子是一样的，也就是将集合分配到个非空的盒子中。
Definition 5.5. 集合的分割(partition)是将每个元素唯一的分配到一个非空块(block)的集合。
我们将集合分配到个非空的块中表示为，其称之为第二类斯特朗数(Stirling numbers of the secondkind)。
如果，那么。我们约定，下一章会解释为什么。
Example 5.6. 时，。时，，任选两个组成一块，其余每个元素自成一块。
Example 5.7. 集合有七种分成两个非空块的分割： 所以。
第一类斯特林数呢？第六章会讲解。
有通项公式吗？第七章会给出一个包含求和记号的公式。
Theorem 5.8. 对于所有的正整数，有 Proof. 如果第个元素自成一块，那么剩下的问题就是将分成块，即右边的第一项；如果第个元素混杂在块中，那么先将分成块，即，任选一块，有种选法。
如果将个不同的球分到个不同的盒子里面，共有种分法。
Corollary 5.9. 所有上的满射函数的数量是
Proof. 略。
Corollary 5.10. 对于所有的实数和非负整数，有 Proof. 等式两边是的阶多项式，所以我们如果能够证明多于个的值都成立，那么上述等式成立。我们证明一个更强的命题，对于所有的正整数其都成立。
上面这段初看时我有两点不懂，这里是我的提问和大神的回答。
左边是所有的函数的个数，注意，不必是满射；右边是对于上函数个数求和，先选出个数，，根据Corollary 5.9.，函数个数是，其积是，
Definition 5.11. 集合的所有分割的个数（不限定块的大小）记作，称之为第贝尔数(
th Bell number)，习惯上。
所以，同时它也满足一个优雅的递归关系。
Theorem 5.12. 对于所有非负整数，有 Proof. 左边是集合所有分割的个数。假设第元素所在块的大小是，也就是有个元素不在这个块。有种方式取出这个数，然后有个分割数，对所有可能的求和。
Integer Partitions
现在我们分析球和盒子都一样的情况。
Definition 5.13. 都是整数且，序列是整数的分割(partition)。整数的所有分割的数目用表示，精确的分成个部分用表示。
和Definition 5.5. 一样使用了同一个词分割(partition)，通过上下文我们能够区分两者，一个是集合的分割，一个是整数的分割。
Example 5.14. 正整数5有7个分割，分别是。因此.
找到的公式是很困难的事情。即使我们知道所有的，也不能直接计算出。有一个近似值如下 比任何多项式增长都快，但是比任何指数函数都慢。
到第八章之前，我们不会讨论太多有用的结果，下面主要集中讨论分区的图形表示。
一个分割的Ferrers(Norman Macleod Ferrers) shape是一个边长为的正方形，第行有个盒子。下图是的分割。很明显，Ferrers shape和的分割一一对应。
将图形延对角线反转得到另外一个图形，表示的是分割的共轭(conjugate)。比如和共轭。原图形的第行是共轭图形的第列。
Definition 5.15. 如果的一个分割和其共轭相同，称之为自共轭(self-conjugate)。
Example 5.16. 分割，和都是自共轭的。
Example 5.14 告诉我们整数5的分割中，最多分成两部分的有三种，同时，每堆最多2个的分割也有三种。
Theorem 5.17. 将最多分成部分的分割数等于每堆数量不大于的分割数。
Proof. 前者对应的是Ferrers shape最多有行的图，而后者对应那些最多有列的图，根据共轭，我们可以将两者一一映射。
Theorem 5.18. 分成不同的奇数部分的分割数等于其共轭的分割数。
Proof. 在两者之间建立双射。
取任意一个共轭分割，我们移除图形的第一列和第一行，共计个，接着移除新的第一列和第一行，共计个，以此类推。我们得到了。每一块都是奇数，且因为，所以每一块的数量都不同。一个块下方和右侧的块被称为hook，使用这个术语来描述的话就是每次都移除了左上角的hook。
任意一个全都是奇数且均不相同的分割，第一行和第一列有个块，第二行和第二列个块，依次类推，组成了一个自共轭的分割。
Example 5.19. ，有。下图展示了两者的对应，其中的数字表示第步移除的块。
Theorem 5.20. 表示的每块至少为2的分割数，对于所有的正整数，有。
Proof. 我们需要构造的所有分割和有一个块为1的的分割的双射。其实很简单，对于的每个分割，后面增加一个块，其数量为1，构成了一个有一个块为1的的分割。
下面我们分析下集合的分割和正整数的分割的关系。是集合的一个分割，我们将其大小按非递增序排列得到，序列是正整数的一个分割。我们称是集合分割的类型。
Example 5.21. 集合分割是类型的一个分割。
Theorem 5.22. 是正整数的一个分割，是在中出现的次数，那么集合中属于类型的分割数是
Proof. 取个颜色为的小球，共个，排成一列，共中排法。和在同一块，当且仅当二者是相同的颜色。这些分割显然属于类型。
不过我们重复计算了很多。比如，有个颜色为1的球在子集对应的位置上，有同样多个颜色为2的球在子集对应的位置上，这是一种分割，相反，个颜色为2的球在子集对应的位置上和同样多个颜色为1的球在子集对应的位置上也是一种分割，但是这两种本质上是一种。一般地，在中出现了次，我们重复计算了次，所有结果要除以。
下面是本章的总结。
如果盒子不能是空的：
个一样的物体，个不同的盒子，对应的公式应该是
如果盒子能空，那么我们要说明盒子的数量，否则可以通过无限添加空盒子来增加分割数量。
Note
本章讨论的很多问题不仅吸引研究组合的人，也吸引很多研究数论的人。比如形如的五角形数(pentagonal numbe)，是任意整数。前几个数是。对于正整数，有
第项的符号是，绝对值是)。
欧拉也有一个关于五角形数的定理，是说如果不是五角形数，将其分成奇数个各不相同的块的分割数和将其分成偶数个各不相同的块的分割数相同；若是五角形数，则两者差一。比如6不是五角形数，其奇数个各不相同的块分割是6和3+2+1，其偶数个各不相同的块分割是5+1和4+2，两则相同。
Exercises
(1) 求
Solution. 函数有个，其中都映射到同一个值的函数有3个，现在求有多少个映射到其中两个值。
根据Corollary 5.9.，其个数是，现在我们需要求。
所以满射有个，进而
(9) 是正整数，是非负整数且，令，证明是的多项式函数。
Solution. 我们用归纳法证明一个更强的命题，是次多项式。，，显然成立。
将分成部分，如果每个部分减去1，等价于分成至多部分。因此
移项得
右边幂次最高是，所以右边是次多项式。
有个定理是说是次多项式当且仅当是次多项式。根据这个定理，可以得到是次多项式。
(32) 求证对所有正整数有。
参考了这个回答
Solution. 使用文中描述的Ferrers shape来帮助证明。先放个块，然后取两个的分割，一个放在其右边，一个放在其下边，那么得到了的分割。这样建立了和盒子数大于且前个盒子的球的数量大于等于的的分割的映射关系，显然比后者大。
(36) - (39)
想了半个多小时，基本思路就是利用Corollary 5.4 Proof 2的分割思想。