Information Technology Reference
In-Depth Information
Let us define by induction the following
partition difference
operator
D
k
,ofdegree
k
,for
n
>
1and
k
n
(see Example 7.9 for a computation of
D
):
D
1
≤
(
n
)=
P
(
n
−
1
)
(7.3)
D
k
+
1
k
i
=
1
D
i
(
n
)=
P
(
n
−
k
−
1
)
−
∑
(
n
−
k
−
1
)
Lemma 7.7.
Fo r k
<
n
/
3
,
D
k
P
min
(
k
)
(
n
)=
(
n
)
.
Proof.
This lemma follows easily by induction on
k
, from the definition of
D
k
and
D
1
the previous lemma. In fact,
P
min
(
1
)
(
n
)=
P
(
n
−
1
)=
(
n
)
. Moreover, from the
previous lemma,
P
min
(
k
+
1
)
(
. Therefore,
by induction hypothesis, we can replace the terms of the right side by obtaining
P
min
(
k
+
1
)
(
n
)=
P
(
n
−
k
−
1
)
−
∑
i
=
1
,
k
P
min
(
k
)
(
n
−
k
−
1
)
)
−
∑
i
=
1
,
k
D
k
n
)=
P
(
n
−
k
−
1
(
n
−
k
−
1
)
, from which, according to the
definition of
D
k
+
1
,weget
P
min
(
k
+
1
)
(
D
k
+
1
n
)=
(
n
)
.
Finally, from lemmas 7.4, 7.6, and 7.7 a theorem follows which provides a simple
recurrent formula enumerating integer partitions.
Theorem 7.8.
P
(
1
)=
1
and P
(
2
)=
2
.Forn
>
2
,
n
/
3
i
=
1
D
i
P
(
n
)=
(
n
)+
n
/
2
−
n
/
3
+
1
.
(7.4)
Example 7.9.
The computation of
P
(
27
)=
3010, according to formula (7.4).
D
1
D
2
D
3
D
4
D
5
D
6
D
7
P
(
27
)=
(
27
)+
(
27
)+
(
27
)+
(
27
)+
(
27
)+
(
27
)+
(
27
)
D
8
D
9
+
(
27
)+
(
27
)+
27
/
2
−
27
/
3
+
1
D
1
(
27
)=
P
(
26
)=
2436
D
2
(
27
)=
383
D
3
(
27
)=
110
D
4
(
27
)=
39
D
5
(
27
)=
18
D
6
(
27
)=
9
D
7
(
)=
27
5
D
8
(
)=
27
3
D
9
(
)=
27
2
P
(
27
)=
2436
+
383
+
110
+
39
+
18
+
9
+
5
+
3
+
2
+
13
−
9
+
1
=
3010.
The detailed computation of
D
4
(
27
)=
39
D
4
D
1
D
2
D
3
(
27
)=
P
(
23
)
−
(
23
)
−
(
23
)
−
(
23
)
P
(
23
)=
1255
D
1
(
23
)=
P
(
22
)=
1002
