正整数的分拆就是将一个正整数分成几个正整数的和。为了以后叙述的严谨性，下面给出如下定义：
正整数 n 的一个 k 分拆是把 n 表示成 k 个正整数的和
http://s14/bmiddle/7b7cad23t7a363b7ba87d&690的一种表示法，其中 http://s14/bmiddle/7b7cad23tc61e572bc5fd&690 ni 叫做该分拆的分部量。如果等式右端的 k 项是无序的，也就是说，对诸 ni 任意换位后的表示法都只视为一种表示法，这样的分拆叫做无序分拆。反之，如果等式右端的 k 项是有序的，即等式右端的和不仅与各项的数值有关，而且与各项的次序有关，不同的次序认为是不同的表示法，这样的分拆叫做有序分拆。这时，ni 叫做该分拆的第 i 个分部量。n 的 k 分拆的个数称为 n 的 k 分拆数，n 的所有分拆（k 取遍所有可能的值）的个数称为 n 的分拆数。而这也是我们在谈及正整数分拆时所关心的主要问题。
下面，我将用两节来分别介绍无序分拆和有序分拆的计数问题。
这一篇主要来介绍有关无序分拆的计数问题。
比如，4 可以表示成如下形式：
4=4 4=3+1
4=2+2
4=2+1+1
4=1+1+1+1
因此，4 的无序分拆数就是 5。那么，对于一个任意给定的正整数 n，其无序分拆数是多少呢？
下面我将用三个算法来分别解决这个问题。
算法一：
仔细观察上面 4 的分拆，可以发现，对于一个分拆，由于是无序的，因此对这个分拆起决定作用的就是这个分拆中的最大数。那么这个最大数与正整数 n 的无序分拆数之间有什么关系呢？
设一个分拆中的最大数是 m，那么对于 n 的无序分拆，当最大数是 m 时，分拆数就等于”n-m 的分拆数“。之所以要加一个引号，是因为并不是真正的 n-m 的分拆数。因为对于 n 来说，分拆的最大数是 m，因此，n-m 的分拆中的最大数就不能超过 m。
记 F(n,m) 表示 n 的分拆中最大数为 m 的分拆个数，根据上面的分析，可以得到如下公式：
http://s14/bmiddle/7b7cad23tc61e59d6b58d&690
那么，n 的分拆总数 F(n) 可以用如下公式计算：
http://s3/bmiddle/7b7cad23t7a363c73d752&690
初始条件：F(n,1)=F(n,n)=1。
算法二：
在算法一中，F(n,m) 表示 n 的分拆中最大的数就是 m，那么，我们能不能放宽一下限制呢？记 F(n,m) 表示 n 的分拆中最大的数不超过 m。
(1) m=n：也就是 n 的分拆中，最大数不超过 n 的个数。当然，最大数为 n 的分拆只有一个，也就是它自己。除了这一个之外，最大数就不可能为 n 了，最多是 n-1 而已。因此，求出 n 的分拆中最大数是 n-1 的分拆个数，再加上 n=n 这一个分拆，就是 F(n,n)。即 F(n,n)=1+F(n,n-1)。
(2) n<m：要把 n 分拆，但最大数 m 却超过 n，这是不可能的。
(3) n>m：在 n 的分拆中，如果最大数最大可以为 m，那么这不外乎分拆中有一个或若干个 m，或者是根本就没有 m。比如，在 4 的分拆中，说最大数最大可以到 2，那么因为 4=2+2=2+1+1=1+1+1+1，于是有 m=2 的就是 2+2 与 2+1+1，完全没有 2 的则是 1+1+1+1。如果 n 的反拆中根本就没有 m，那么它的个数不就与 n 的分拆中最大数最大可以到 m-1 的个数(即 F(n,m-1) )相同吗？如果 n 的分拆中至少有一个 m，亦即 n=m+”......“，于是 n-m=”......“，所以”......“的部分正好是 n-m 的一个分拆，它的最大数最多可以到 m。因为 n-m 的分拆中最大数最多可以到 m 的有 F(n-m,m) 个，再加上 F(n,m-1)，这就是所有的情况。即 F(n,m)=F(n,m-1)+F(n-m,m)。
这样，n 的分拆数仍可用算法一中的第二个公式进行计算。
初始条件：F(n,1)=F(1,m)=1。
算法三：
在前面的两个算法中都是把注意力放在一个分拆中的最大数上，那么能不能换一个角度，看看一个分拆中的最小数与分拆个数之间是什么关系呢？
记 F(n,m) 表示将 n 分拆成 m 部分的分拆个数。考虑分拆中的最小数，如果它等于 1，那么剩下的数就被分拆成 m-1 部分，其个数为 F(n-1,m-1)；如果它不等于 1，那么分拆成的 m 部分中的每一个数一定都大于等于 2，将这 m 部分中的每个数都减去 1，则得到一个新的分拆，即 n-m 的分拆，也是被分成 m 部分，其个数为 F(n-m,m)。根据加法原理，有 F(n,m)=F(n-1,m-1)+F(n-m,m)。
这样，n 的分拆数依然可以采用算法一中的第二个公式进行计算。
初始条件：F(n,1)=F(n,n)=1。
从上面的三个算法可以看出，通常对一个问题，如果从不同的角度进行分析，可能会得到不同的解决问题的方法，而且难易程度也会因算法的不同而大相径庭。就上面的三个算法来说，算法三可能是最简单、最易于实现的。

在上部分中介绍了有关正整数无序分拆的问题，这部分主要来介绍有关正整数有序分拆的问题。
在给出对一个给定正整数的有序分拆数的计算方法前，先给出一些准备性知识：
多重集合：同一般集合一样，也是一组对象的整体，只不过不像一般集合那样必须要求集合中每个元素互不相同。例如：
http://s7/bmiddle/7b7cad23tc66894012b36&690
是一个 10 个元素的多重集合，其中有 3 个a，1 个b，2 个c，4 个d。通常，我们将 M 表示为http://s14/bmiddle/7b7cad23tc66895145ead&690
其中，3、1、2、4分别称为元素a、b、c、d的重数。
一般地，多重集合表示为http://s7/bmiddle/7b7cad23tc66896128846&690
其中，a1，a2，...，an为 M 中所有的互不相同的元素，M 中有 ki 个 ai（1<=i<=n），称 ki 为 ai 的重数。ki 是正整数，也可以是 ∞，表示 M 中有无限多个 ai。多重集合 M 的 r 排列：从 M 中选出 r 个元素的有序选择。
多重集合 M 的 r 组合：从 M 中选出 r 个元素的无序选择。
引理一：多重集合
http://s5/bmiddle/7b7cad23tc66897162ce4&690
的 r 组合数为http://s8/bmiddle/7b7cad23tc66898da30e7&690证明：设多重集合 M 的某个 r 组合为
http://hiphotos.baidu.com/xwf_like/abpic/item/e611192883cf5ae699250a06.jpg(1)则有
http://s12/bmiddle/7b7cad23tc6689ac6619b&690(2)
其中，x1，x2，...，xk为非负整数。反之，若给出方程(2)的一组非负整数解x1，x2，...，xk，则对应于 M 的一个 r 组合(1)。所以，M 的 r 组合与方程(2)的非负整数解构成一一对应，从而将求 M 的 r 组合的问题转化为求方程(2)的非负整数解的问题。
方程(2)的一个非负整数解可以表示成长为 k-1+r 的 0、1 序列
http://hiphotos.baidu.com/xwf_like/pic/item/4f8c91b657c7b6ec31add1e9.jpg其中，0 的个数为 k-1 个，该 0、1 序列是集合
http://hiphotos.baidu.com/xwf_like/abpic/item/c6182a255d772d33d40742f3.jpg(3)的一个全排列。方程(2)的解与集合(3)的全排列之间是一一对应的，从而多重集合 M 的 r 组合数为
http://hiphotos.baidu.com/xwf_like/abpic/item/e10db28ee69bb2e2513d92fb.jpg引理二：多重集合
http://hiphotos.baidu.com/xwf_like/abpic/item/c4152df5f7a81776ddc474c1.jpg要求 a1，a2，...，ak 至少出现一次的 r 组合数为
http://hiphotos.baidu.com/xwf_like/abpic/item/8104134feb902fd2d1c86ad3.jpg
证明：在 M 的 r 组合中 a1，a2，...，ak 至少出现一次，所以 r>=k。设
http://hiphotos.baidu.com/xwf_like/abpic/item/9b1e22e8ab0e9a27b80e2d53.jpg是 M 满足定理条件的任一 r 组合，则有
http://hiphotos.baidu.com/xwf_like/abpic/item/6dc52947a80605116b63e525.jpg(4)且
http://hiphotos.baidu.com/xwf_like/abpic/item/bd6a204e74ef4c2eafc3ab23.jpg(5)令
http://hiphotos.baidu.com/xwf_like/abpic/item/27a3e8eefc2ef02eacafd52b.jpg则
http://hiphotos.baidu.com/xwf_like/abpic/item/d815be1758d71449f3de3231.jpg(6)且
http://hiphotos.baidu.com/xwf_like/abpic/item/eed2f20160927609728b653f.jpg(7)显然，方程(4)满足条件(5)的解的个数等于方程(6)的非负整数解的个数。由引理一的证明知，满足引理条件的组合数为
http://hiphotos.baidu.com/xwf_like/abpic/item/07d18aedca53d83f62d09f0c.jpg 有了上面的准备知识以后，就可以给出如下定理：
定理：正整数 n 的有序 k 分拆的个数为
http://hiphotos.baidu.com/xwf_like/abpic/item/a0f371672340b23cab184c1a.jpg证明：正整数 n 分成 k 个分部量的一个有序分拆
http://hiphotos.baidu.com/xwf_like/abpic/item/a281af553e8e4b073a2935ec.jpg等价于方程
http://hiphotos.baidu.com/xwf_like/abpic/item/47d4a2cac9bd0de552664fea.jpg的正整数解(n1，n2，...，nk)，由引理二的证明知，正整数 n 的有序 k 分拆的个数为
http://hiphotos.baidu.com/xwf_like/abpic/item/f11fb3eed7401cf7ce1b3eca.jpg 记 F(n) 表示正整数 n 的有序分拆数，F(n,k) 表示正整数 n 的有序 k 分拆的个数，则有如下公式：
http://hiphotos.baidu.com/xwf_like/abpic/item/872db4dc23c4162c5982ddcc.jpg(8) 至此，便得到了计算正整数的有序分拆数的计算公式(8)。