Information Technology Reference
In-Depth Information
Lemma 7.4.
Fo r n
>
1
,
n
/
3
i
=
1
P
(
n
)=
P
min
(
i
)
(
n
)+
n
/
2
−
n
/
3
+
1
.
(7.2)
n
i
=
1
P
min
(
i
)
(
Proof.
Of course,
P
(
n
)=
∑
n
)
, therefore the equation above follows from
the previous lemma.
Let us denote by
P
k
(
)
the number of partitions of
n
with at most
k
summands,
which is computable by means of the following well-known inductive equation:
n
P
k
(
n
)=
P
k
−
1
(
n
)+
P
k
(
n
−
k
)
with
P
1
(
1.
The following lemma expands the integer partitions enumeration formula (7.2)
of Lemma 7.4.
n
)=
P
n
(
n
)=
P
k
(
0
)=
Lemma 7.5.
P
min
(
1
)
(
n
)=
P
(
n
−
1
)
.Fork
>
1
and n
>
k,
n
i
=
2
/
k
P
min
(
k
)
(
n
)=
P
i
−
1
(
n
−
ik
)
.
Proof.
In general,
P
is the number of partitions of
n
where the summand
m
occurs. Therefore,
P
min
(
1
)
(
(
n
−
m
)
n
)=
P
(
n
−
1
)
. Given an arbitrary partition, say it
π
,
of
n
−
ik
with at most
i
−
1 summands, we can transform it (in a 1-to-1 way) in
π
,having
k
as its minimum summand.
Namely, consider the
ik
units of
n
which are exceeding
n
a partition of
n
with
i
summands, say it
−
ik
, then add
k
of them to
each of the
i
−
1 (possibly null) terms of
π
, and use the remaining
k
units for the
i
-th
π
the presence of a minimum summand
k
is guaranteed).
In this manner, if
i
varies from 2 to
π
(so that in
summand of
n
/
k
(
n
>
k
), then we get
P
min
(
k
)
(
n
)
by means
of the formula given above.
However, the previous enumeration, based on minimum summands, can be substan-
tially improved by using the following lemma.
Lemma 7.6.
Fo r k
<
n
/
3
and
1
≤
n
,
k
i
=
1
P
min
(
i
)
(
n
−
k
−
1
)
P
min
(
k
+
1
)
(
n
)=
P
(
n
−
k
−
1
)
−
Proof.
Let us consider the partitions of
n
having
k
+
1 as a part, which equals
P
(
n
−
k
. Now remove from these the partitions that have 1 as a minimum part, those
having 2 as a minimum part, and so on, up those having
k
as a minimum part. In this
way, we obtain the partitions of
n
having
k
−
1
)
+
1 as minimum summand.
