Information Technology Reference
In-Depth Information
exp
3
π
2
n
/
P
(
n
)
∼
4
n
√
3
as
n
→
∞
.
Many other recurrent enumerative formulae are also known. Let us mention only
one of them, due to Euler:
P
(
n
)=
P
(
n
−
1
)+
P
(
n
−
2
)
−
P
(
n
−
5
)
−
P
(
n
−
7
)+
P
(
n
−
12
)+
P
(
n
−
15
)
−...
3
k
2
where
P
(
n
)
is recurrently computed by using the values
P
(
n
−
q
)
with
q
∈{
(
+
k
)
/
2
|
k
∈
Z
}
, according to the following formula (
P
(
1
)=
1
,
P
(
i
)=
0for
i
≤
0):
)=
k
∈
Z
(
−
1
)
k
+
1
P
3
k
2
P
(
n
(
n
−
(
+
k
)
/
2
)
.
Numbers
q
above are called
pentagonal numbers
because in the case of
k
nega-
tive they correspond to figurate numbers already known by Greek mathematicians,
which can be arranged in pentagonal shapes (differences of two suitable triangu-
lar numbers). This formula is one of Euler's jewels, known as
Euler's Pentagonal
Number Theorem
.
The following tables show the first 30 values of
P
(
n
)
.
n 123456789101112131415
P(n)1235711152230425677101135176
n 16171819202122 23 24 25 26 27 28 29 30
P(n) 231 297 385 490 627 792 1002 1255 1575 1958 2436 3010 3718 4565 5604
Now we present a new perspective were partitions are classified according to
their minimum summand. In this way, we discover a recurrent formula comput-
ing
P
by using elementary combinatorial arguments (see Eq. (7.4)). However,
computational experiments show that the recurrent pentagonal formula of Eulero is
computationally better than our formula. Nevertheless, we briefly present this el-
ementary method for computing integer partitions, as an example of derivation of
recurrent relations in a classical combinatorial context.
Let us denote by
P
min
(
k
)
(
(
n
)
n
)
the number of partitions of
n
having
k
as minimum
summand.
Lemma 7.3
P
min
(
n
)
(
n
)=
1
P
min
(
k
)
(
n
)=
0
for
n
/
2
<
k
<
n
P
min
(
k
)
(
n
)=
1
for
n
/
3
<
k
≤
n
/
2
.
Proof.
If
k
n
there is obviously only one partition of
n
with
k
as minimum sum-
mand. If
k
is smaller than
n
, but greater than
=
, no partition of
n
can exist with
minimum part
k
.If
k
is comprised between the two extreme values
n
/
2
n
/
2
and
n
/
3
,
then there is exactly one partition of
n
=
k
+(
n
−
k
)
having
k
as minimum part.
