On Number Of Partitions Of An Integer
Into A Fixed Number of Positive Integers
A. Yavuz Oruc¸
Department of Electrical Engineering
University of Maryland, College Park, MD 20742
Abstract
This paper focuses on the number of partitions of a positive integer n into
k positive summands, where k is an integer between 1 and n. Recently
some upper bounds were reported for this number in [Merca14]. Here, it is
shown that these bounds are not as tight as an earlier upper bound proved
in [Andrews76-1] for k ≤ 0.42n. A new upper bound for the number of
partitions of n into k summands is given, and shown to be tighter than the
upper bound in [Merca14] when k is between O(
√
n
lnn) and n − O(
√
n
lnn). It
is further shown that the new upper bound is also tighter than two other
upper bounds previously reported in [Andrews76-1] and [Colman82]. A
generalization of this upper bound to number of partitions of n into at most
k summands is also presented.
1 Introduction
Partitions of an integer play an important role in the solutions of combi-
natorial problems and this article is motivated in part by such a problem
that arises in counting multicast calls between n callers and n receivers
in a switching network [Oruc15]. In particular, three types of partitions
will be of interest in this paper as stated below and we refer the reader
to [Andrews76-1] for basic concepts in partition theory.
1. A partition of n is an unordered sum of n that comprises up to n positive
integers. The number of such sums is often denoted by p(n). For example,
p(3) = 3 as 3 = 3, 3 = 1 + 2, and 3 = 1 + 1 + 1.
2. A partition of n into exactly k parts is an unordered sum of n that uses
exactly k positive integers. The number of such partitions will henceforth
be denoted by p(n, k). For example, p(5, 3) = 2 as 5 = 1 + 2 + 2 and
5 = 1 + 1 + 3 are the only two sums of 5 that can be formed using three
positive integers.
1
3. A partition of n into at most k parts is an unordered sum of n that uses
at most k positive integers. Following the asterisk notation in [Colman82],
the number of such partitions will henceforth be denoted by p∗(n, k). For
example, p∗(5, 3) = 5 as 5 = 2 + 2 + 1, 5 = 3 + 1 + 1, 5 = 2 + 3, 5 = 4 + 1,
and 5 = 5 are the only sums of 5 that can be formed using one, two, or three
integers.
No exact closed-form expressions are known to compute the values of p(n),
p(n, k), and p∗(n, k). For p(n), Hardy-Ramanujan-Rademacher formula pro-
vides an asymptotic approximation to p(n) [Andrews76-2]:
p(n) ≈
1
4
√
3n
epi
√
2n
3 . (1)
Using Remark 1 in [Kane06], it can be shown that
0.02556 ≤ lim
n→∞
p(n)
1
4
√
3n
epi
√
2n
3
≤ 37.6393, (2)
while
lim
n→∞
∣
∣
∣
∣
1
4
√
3n
epi
√
2n
3 − p(n)
∣
∣
∣
∣ =∞. (3)
In the sequel, we will also need Kane’s inequality:
C−1,1
n
epi
√
2n
3 ≤ p(n) ≤
C+1,1
n
epi
√
2n
3 . (4)
where C−1,1 is any number less than
5e−2−
3γ
2
8
√
3pi3/2
, C+1,1 is any number greater
than 274
(
e
pi
)3/2
, and γ = 0.57721..., is the Euler constant. We will let C−1,1 =
0.0036 and C+1,1 = 5.44.
In the remainder of the paper, we analyze the previously reported upper
bounds for p(n, k) and present a sharper upper bound for the same. This new
bound is used to obtain an upper bound on p∗(n, k) as well. It is assumed
that i, j, k,m, n, s are all positive integers unless otherwise stated.
2 Partitions With A Fixed Number Of Parts
The following lower and upper bounds for p(n, k), 1 ≤ k ≤ n − 1 are well-
known [Andrews76-1]:
1
k!
(
n− 1
k
)
≤ p(n, k) ≤ Ua(n, k) =
1
k!
(
n+ k(k−1)2 − 1
k − 1
)
. (5)
2
Another upper bound, attributed to Rieger and stated below, was shown to
be effective in [Colman82] in estimating p(n, k) when
√
72n > k5/2,
p(n, k) ≤ Ur(n, k) =
1
k! (k − 1)!
(
n+
k(k − 3)
4
)k−1
, 4 ≤ k ≤ n. (6)
Expanding the binomial term in Ua(n, k), we find
Ua(n, k) =
1
k!(k − 1)!
k−1∏
j=1
(n+
k(k − 1)
2
− j)! (7)
≥
1
k!(k − 1)!
(
n+
k(k − 1)
2
− k + 1
)k−1
(8)
≥
1
k!(k − 1)!
(
n+
(k − 1)(k − 2)
2
)k−1
. (9)
Comparing Ur(n, k) in (6) with the last inequality shows that Ur(n, k) ≤
Ua(n, k) for all k, 1 ≤ k ≤ n.
More recently, a series of upper bounds was established in [Merca14] with
increasing numbers of terms in the formulas, using a relation between multi-
nomial and binomial coefficients. The simplest two of these upper bounds
are1
p(n, k) ≤
1
2
(
n− 1
k − 1
)
+
1
2
δ0,nmod k, (10)
p(n, k) ≤
1
3
(
n− 1
k − 1
)
+
2
3
δ0,nmod k +
1
3
δ2,k
⌊
n− 1
2
⌋
, (11)
where δu,v is the Kronecker delta function and so the following the upper
bounds obviously apply:
p(n, k) ≤ UM1(n, k) =
1
2
(
n− 1
k − 1
)
+
1
2
, (12)
p(n, k) ≤ UM2(n, k) =
1
3
(
n− 1
k − 1
)
+
2
3
+
1
3
⌊
n− 1
2
⌋
. (13)
1A number of other upper bounds have been provided in [Merca14], all having a dom-
inating term of
(n−1
k−1
)
that is multiplied by a constant 1/t, 2 ≤ t ≤ 10. Even though 1/t
decreases as t increases, it does not alter the order of complexity of the upper bound given
that t is a constant. An upper bound was also given in Theorem 2 in the same paper for
any positive integer t > 1, and it was shown that this upper bound converges to p(n, k)
as t tends to k!. However, this bound has a sum term whose value was not settled in the
paper.
3
What is not so obvious is whether UM1(n, k) ≤ Ua(n, k) or UM2(n, k) ≤
Ua(n, k) except when k = 1 and k = 2. For k = 1 and k = 2, UM1(n, k)
coincides with Ua(n, k). For k = 1 and k = 2, and n > 2, Ua(n, k) ≤
UM2(n, k). To settle this question for k, 3 ≤ k ≤ n − 1, we note that
Ua(n, k) can be expressed as
Ua(n, k) =
(n−1
k−1
)
k!
s−1∏
j=0
n− 1 + s− j
n− 1 + s− j − (k − 1)
, (14)
where s = k(k−1)2 . Let
f(s, k, n) =
1
k!
s−1∏
j=0
1
1− (k−1)n−1+s−j
. (15)
Then Ua(n, k) =
(n−1
k−1
)
f(s, k, n) and
Remark 1. if f(s, k, n) ≤ 12 , then Ua(n, k) ≤ UM1(n, k).
Similarly2,
Remark 2. if f(s, k, n) ≤ 13 , then Ua(n, k) ≤ UM2(n, k).
To proceed further, we will invoke the Geometric-Harmonic mean inequality:


s−1∏
j=0
uj


1
s
≥
s
∑s−1
j=0
1
uj
, (16)
where we let uj = 1−
(k−1)
k−1+s−j . Thus,
s−1∏
j=0
uj ≥
(
s
∑s−1
j=0
1
uj
)s
. (17)
Now, let w(s, k, n) =
∏s−1
j=0 uj and z(s, k, n) =
∑s−1
j=0
1
uj
. Then
f(s, k, n) =
1
k!w(s, k, n)
, (18)
2As it will be shown later, it suffices to focus on the first inequality.
4
w(s, k, n) ≥
(
s
z(s, k, n)
)s
, (19)
and
z(s, k, n) =
s−1∑
j=0
1
uj
(20)
=
s−1∑
j=0
1
1− k−1n−1+s−j
(21)
=
s−1∑
j=0
n+ s− j − 1
n+ s− j − k
. (22)
Replacing the sum by the integral
∫ s
x=0
n+s−x−1
n+s−x−kdx in the last expression
results in the inequality
z(s, k, n) ≤ s+ 2(k − 1) arctanh
(
s
s− 2k + 2n
)
(23)
≤ s+(k−1)
[
ln
(
1+
s
s−2k + 2n
)
−ln
(
1−
s
s−2k + 2n
)]
(24)
≤ s+ (k − 1) ln
(
2s− 2k + 2n
2n− 2k
)
(25)
≤ s+ (k − 1) ln
(
1 +
s
n− k
)
. (26)
Combining the last inequality with (19), we find
w(s, k, n) ≥


s
s+ (k − 1) ln
(
1 + sn−k
)


s
(27)
≥
1
(
1 + k−1s ln
(
1 + sn−k
))s (28)
and combining the last inequality with (18)
f(s, k, n) ≤
(
1 + k−1s ln
(
1 + sn−k
))s
k!
. (29)
5
Hence, by Remark 1, Ua(n, k) ≤ UM1(n, k) if
(
1 + k−1s ln
(
1 + sn−k
))s
k!
≤
1
2
. (30)
Recalling that s = k(k − 1)/2, this inequality can be simplified as follows:
(
1 + 2k ln
(
1 + k(k−1)2n−2k
))k(k−1)/2
k!
≤
1
2
ln
(
1 +
k(k − 1)
2n− 2k
)
≤
k
2
((
k!
2
) 2
k(k−1)
− 1
)
k(k − 1)
2n− 2k
≤ exp
(
k
2
((
k!
2
) 2
k(k−1)
− 1
))
− 1
k +
k(k − 1)
2 exp
(
k
2
(
(
k!
2
) 2
k(k−1) − 1
))
− 2
≤ n.
It follows that if
n ≥ k +
k(k − 1)
2 exp
(
k
2
(
(
k!
2
) 2
k(k−1) − 1
))
− 2
(31)
then Ua(n, k) ≤ UM1(n, k). Let g(k) =
(k−1)
exp
(
k
2
(
( k!2 )
2
k(k−1)−1
))
−1
. Then
Ua(n, k) ≤ UM1(n, k) if
n ≥ k
(
1 +
g(k)
2
)
. (32)
It can be shown that g(k) has a minimum when k is near 2pi and 1 ≤ g(k) ≤ e
if k ≥ 3. Thus, the inequality in (32) is satisfied if n ≥ k(1+ e2), and therefore,
Ua(n, k) ≤ UM1(n, k), 3 ≤ k ≤ n1+ e2
= b0.42nc.
It can further be shown that the same limit holds when the k!/2 term is
replaced by k!/3 in g(k) and that the exact same upper bound on k, i.e.,
k ≤ b0.42nc also holds if UM2(n, k) is used in the comparison. It should
also be noted that Ur(n, k) ≤ UM1(n, k) and Ur(n, k) ≤ UM2(n, k) over the
same domain of values of k, given that it has already been established in
the preceding section that Ur(n, k) ≤ Ua(n, k), 1 ≤ k ≤ n.
6
� ������
k
Upper bounds on p(n,k) in natural log scale, 1 < k < n = 20,000
����������-�
5000 10000 15000 20000
5000
10000
15000
20000
25000
Figure 1: Comparison of the upper bounds in [Merca14] and [Andrews76-
1] in natural logarithmic scale, 1 ≤ k ≤ n = 20, 000. (The solid curve
represents the upper bound in (5). The dashed and dotted curves are the
upper bounds in (10) and (11) and they nearly coincide.)
Remark 3. The upper limit on k is not tight since we used an upper bound
for f(s, k, n) to determine it. The numerical comparison of Ua(n, k) with
UM1(n, k) reveals that Ua(20, 000, k) ≤ UM1(20, 000, k) for all k ≤ 10, 590.
This suggests that the upper limit tends to b0.53nc as n gets large, but
proving this requires a more precise estimation of f(s, k, n).
3 A Tighter Upper Bound
The value of p(n, k) can be predicted much more accurately for certain values
of k and n using the following theorem.
Theorem 1. p(n, k) = p(n− k), k ≤ n ≤ 2k.
Proof. The proof is based on an “n urns and k balls distribution” argument,
where each summand in a partition with exactly k summands represent the
number of balls in each of the k urns. Each urn must clearly have at least one
ball. With one ball in each urn, the remaining n− k balls can be placed in
p(n−k) ways, where each such placement corresponds to a partition of n−k,
as long as n − k ≤ k or n ≤ 2k. Given that the urns are indistinguishable,
the statement follows.
Combining this result with Hardy-Ramanujan-Rademacher asymptotic for-
mula yields the asymptotic formula
p(n, k) ≈
1
4
√
3(n− k)
epi
√
2(n−k)
3 , k ≤ n ≤ 2k. (33)
7
Furthermore, the following upper bound applies to p(n, k).
Corollary 1.
p(n, k) ≤
5.44
(n− k)
epi
√
2(n−k)
3 , 1 ≤ k ≤ n− 1. (34)
Proof. Using the same ”urns and balls” analogy in Theorem 1, in any
partition of n into exactly k parts, each urn must contain at least one ball.
The remaining n− k balls cannot be distributed to the k urns in more than
p(n−k) ways. Therefore, p(n, k) ≤ p(n−k) and the statement follows from
Kane’s upper bound in inequality (4).
Let
Unew(n, k) =
5.44
n− k
epi
√
2(n−k)
3 . (35)
The next three results compare the new upper bound with the previous
upper bounds.
Corollary 2. For n ≥ 171, and
⌈
2pi
√
2(n−1)/3
ln(n−1)
⌉
+1 ≤ k ≤ n−
⌈
2pi
√
2(n−1)/3
ln(n−1)
⌉
,
Unew(n, k) ≤ UM1(n, k). (36)
Proof. For the specified values of k and n, we need to show
5.44
n− k
epi
√
2(n−k)
3 ≤
1
2
(
n− 1
k − 1
)
(37)
or, given that k ≤ n−
⌈
2pi
√
2(n−1)/3
ln(n−1)
⌉
, we have n− k ≥
⌈
2pi
√
2(n−1)/3
ln(n−1)
⌉
≥ 13
for n ≥ 171.
Thus, it is sufficient to prove
10.88epi
√
2(n−1)
3
13
√
3
≤
(
n− 1
k − 1
)
. (38)
Now,
(n−1
m−1
)
=
( n−1
n−m
)
, 1 ≤ m ≤ n, and
(n−1
m−1
)
≤
(n−1
k−1
)
, m ≤ k ≤ n −m + 1.
In particular, if
⌈
2pi
√
2(n−1)/3
ln(n−1)
⌉
+ 1 ≤ k ≤ n−
⌈
2pi
√
2(n−1)/3
ln(n−1)
⌉
then
(
n− 1
d
2pi
√
2(n−1)/3
ln(n−1) e
)
≤
(
n− 1
k − 1
)
. (39)
Thus, (38) holds if
10.88epi
√
2(n−1)
3
13
≤
(
n− 1
d
2pi
√
2(n−1)/3
ln(n−1) e
)
(40)
8
holds, or using the inequality, (x/y)y ≤
(x
y
)
, it suffices to prove the inequality
10.88epi
√
2(n−1)
3
13
≤




n− 1
⌈
2pi
√
2(n−1)/3
ln(n−1)
⌉




⌈
2pi
√
2(n−1)/3
ln(n−1)
⌉
. (41)
It is not difficult to see that this inequality is satisfied if the following in-
equality holds:
10.88epi
√
2(n−1)
3
13
≤



n− 1
2pi
√
2(n−1)/3
ln(n−1)



2pi
√
2(n−1)/3
ln(n−1)
. (42)
Hence, taking the logarithm of both sides of the inequality, we need to prove
pi
√
2(n− 1)
3
+ ln
10.88
13
≤
2pi
√
2(n−1)
3
ln(n− 1)
ln
(
(n− 1) ln(n− 1)
2pi
√
2(n− 1)/3
)
. (43)
Applying the logarithm to the terms inside the expression on the right gives
pi
√
2(n− 1)
3
− 0.179 ≤ pi
√
2(n− 1)
3
+
2pi
√
2(n−1)
3
ln(n− 1)
ln
(
ln(n− 1)
2pi
√
2/3
)
. (44)
The inequality clearly holds if ln(n−1) ≥ 2pi
√
2
3 or n ≥ 171 and the statement
follows.
We state the following analogous result without a proof.
Corollary 3. For n ≥ 171, and
⌈
2pi
√
2(n−1)/3
ln(n−1)
⌉
+1 ≤ k ≤ n−
⌈
2pi
√
2(n−1)/3
ln(n−1)
⌉
,
Unew(n, k) ≤ UM2(n, k).
These results establish that the new upper bound is tighter than the upper
bounds in [Merca14] if k is between O(
√
n/ lnn) and n−O(
√
n/ lnn). The
bounds on k can be sharpened using a tighter lower bound on
(n
k
)
for the
same lower bound on n given in Corollary 2. The lower bound for k in
Corollary 2 implies that k ≥ 14 when n = 171 for the new upper bound
to be less than UM1(n, k) and UM2(n, k). If we use the original inequality
in (37) then the new upper bound drops below UM1(n, k) and UM2(n, k) at
k = 8 when n ≥ 171.
9
Using Hardy-Ramanujan-Rademacher 
asymptotic formula
Exact values
k
100
Using Kane's upper bound coefficient
200 400 600 800 1000
10
20
30
40
50
60
70
New upper bound and exact values of p (n, k) in natural log scale, 1 < k < n = 1000
Figure 2: The new upper bound and exact values of p(n, k).
Remark 4.
The new upper bound (the dashed curve) is plotted in natural log scale
against the values of p(n, k) for n = 1000 and 1 ≤ k ≤ n − 1 in Fig-
ure 2. The Hardy-Ramanujan-Rademacher asymptotic formula for p(n, k)
in (33) is also plotted in the figure over the same interval (solid dark curve).
Both bounds closely track the values of p(n, k), with Hardy-Ramanujan-
Rademacher formula nearly coinciding with p(n, k) when k is between 100
and 999. This is expected as p(n, k) approaches p(n − k) as k approaches
n/2 in which case Hardy-Ramanujan-Rademacher formula provides a tight
approximation to p(n, k). However, it is only an asymptotic approximation,
not an upper bound. It should also be noted that the new upper bound
differs from the Hardy-Ramanujan-Rademacher formula in (33) only by a
constant factor of Kane’s upper bound coefficient 274
(
e
pi
)3/2
multiplied by
4
√
3, that is, 37.6393.
We now establish that Unew(n, k) is also tighter than Ua(n, k) when k is
between O(
√
n) and n− 1.
Corollary 4. If 1.77
(
6.28
√
0.56n−0.92 lnn+9.87+0.92 lnn−19.74
)
≤k ≤n
then Unew(n, k) ≤ Ua(n, k). (45)
10
Proof. We first note that the inequalities,
(r
q
)
>(r/q)q and r!<
√
2pir( re)
re
1
12r
imply
Ua(n, k) =
1
k!
(
n+ k(k−1)2 − 1
k − 1
)
≥
ek
√
2pike
1
12k kk
(
n+ k(k−1)2 − 1
k − 1
)k−1
. (46)
Rearranging the terms,
Ua(n, k) ≥
ek
√
2pike
1
12k k
(
n− 1
k(k−1)
+
1
2
)k−1
. (47)
Thus, it is sufficient to prove the following inequality in the specified interval
for k.
Unew(n, k) =
5.44
(n−k)
epi
√
2(n−k)
3 ≤
ek
√
2pike
1
12k k
(
n− 1
k(k−1)
+
1
2
)k−1
. (48)
Taking the logarithm of both sides and rearranging the terms, we find
pi
√
2(n−k)
3
≤k−
1
12k
+ln
n−k
k
−
1
2
ln 2pik+(k−1)ln
(
n−1
k(k−1)
+
1
2
)
−ln 5.44.(49)
Noting that 0 ≤ n−1k(k−1) and −
1
24 ≤ −
1
12k for k ≥ 2, to prove (48), it suffices
to prove the inequality:
pi
√
2(n−k)
3
≤ k −
1
24
+ ln
n−k
k
−
1
2
ln 2pik+(k−1)ln
1
2
− ln 5.44 (50)
in the specified interval for k. Now, suppose that k ≤ n2 . Then 0 ≤ ln
n−k
k
and −12 lnpin ≤ −
1
2 ln 2pik. Therefore, if k ≤
n
2 and if
pi
√
2(n−k)
3
≤ k −
1
24
−
1
2
lnpin+ (k − 1) ln
1
2
− ln 5.44 (51)
holds or equivalently
pi
√
2(n−k)
3
≤ k(1− ln 2)−
1
2
lnn− ln 2.77
√
pi −
1
24
(52)
≤ 0.3069k −
1
2
lnn− 1.6147 (53)
holds then (50) holds as well. Solving for k gives
(1.629 lnn− 29.667) + 3.909
√
4.572n−7.449 lnn+55.793 ≤ k ≤
n
2
(54)
11
Upper bounds on p(n,k), in natural log scale, 1 < k < n = 10,000 
Andrew76-1
Merca14 Rieger-Colman82
New upper bound k2000 4000 6000 8000 10000
2000
4000
6000
8000
10000
12000
Figure 3: The new upper bound (red dashed curve closest to the horizontal
axis) versus the previous upper bounds, where n = 10, 000 and 1 ≤ k ≤ n−1.
On the other hand, if n2 < k< n, then − lnn ≤ ln
n−k
k , −
1
2 ln 2pin ≤ −
1
2 ln 2pik,
and n− k ≤ n2 . Therefore if
n
2 < k< n and
pi
√
n
3
≤ k −
1
24
− lnn−
1
2
ln 2pin+ (k − 1) ln
1
2
− ln 5.44 (55)
then (50) also holds. Isolating k, we find
pi
√n
3 +
3
2 lnn+
1
24 − ln 2.77
√
2pi
1− ln 2
≤ k < n. (56)
This proves that (50) also holds if n/2 < k ≤ n− 1 and the statement
follows.
Remark 5. The new upper bound, Unew(n, k) (dashed curve) is plotted
against Ua(n, k) (dotted curve), UM1(n, k) (solid curve), and Ur(n, k) (dotted
and dashed curve), for n = 10, 000 and 1 ≤ k ≤ n − 1 in natural log scale
in Figure 3. It is seen that the new upper bound remains negligible as
compared to the previous upper bounds throughout the interval of interest.
It is also seen that Ur(n, k) is tighter than Ua(n, k) and this agrees with the
result that was established in Section 2.
Remark 6. That Unew(n, k) is also tighter than Ur(n, k) can be proved
using a similar approach. The upper bound, Ur(n, k) in inequality in (6)
can be put into the same form as the inequality in (47) using the factorial
12
inequality r!<
√
2pir( re)
re
1
12r as shown below
Ur(n, k) ≥
e2k−1
√
4pi2k(k − 1)e
1
12k+
1
12(k−1k
(
n
k(k − 1)
+
k − 3
4(k − 1)
)k−1
. (57)
It can then similarly be shown that the inequality
5.44epi
√
2(n−k)
3
n−k
≤
e2k−1
√
4pi2k(k − 1)e
1
12k+
1
12(k−1k
(
n
k(k − 1)
+
k − 3
4(k − 1)
)k−1
, (58)
where the term on the left is Unew(n, k), is satisfied if
21.7501
√
0.3208n−0.7705 lnn+7.8957 + 2.4015 lnn−62.5556≤ k < n. (59)
Thus, in this case, Unew(n,k)≤Ur(n,k) when k is between O(
√
n) and O(n).
4 Partitions With At Most k Parts
The Hardy-Ramanujan-Rademacher type bound for p(n, k) can be extended
to p∗(n, k) by combining Corollary 1 with the following obvious identity
[Szekeres51]3
p∗(n, k) =
k∑
j=1
p(n, j). (60)
Thus, the following inequality must hold:
p∗(n, k)≤5.44
k∑
j=1
epi
√
2(n−j)
3
n−j
. (61)
Replacing the sum by an integral and computing it gives
p∗(n,k) ≤ 5.44
∫ k
x=0
epi
√
2(n−x)
3
n−x
dx (62)
≤ 10.88
(
Ei
(
pi
√
2n
3
)
− Ei
(
pi
√
2(n− k)
3
))
. (63)
3In [Szekeres51] p∗(n, k) is denoted by P (n, k).
13
Using Hardy-Ramanujan-Rademacher asymptotic formula
Using Kane's upper bound coefficient
k
Exact values of p  (n,k)*
200 400 600 800 1000
20
40
60
80 New upper bound and exact values of p  (n,k) in natural log scale, 1 < k < n = 1000*
Figure 4: The new upper bound and exact values of p∗(n, k).
Now, using the following two-sided inequality4,
−ex ln
(
1−
1
x
)
≤ Ei(x) ≤ −
1
2
ex ln
(
1−
2
x
)
, x > 2, (64)
we obtain the following upper bound for p∗(n, k),
p∗(n,k)≤10.88

epi
√
2(n−k)
3 ln

1−
1
pi
√
2(n−k)
3

−
1
2
epi
√
2n
3 ln

1−
2
pi
√
2n
3



.(65)
Furthermore, replacing 10.88 by 1
2
√
3
gives an asymptotic formula for
p∗(n, k), 1 ≤ k ≤ n − 1. Both the upper bound and asymptotic formula
are plotted against p∗(n, k) for n = 1000 and 1 ≤ k ≤ n− 1 in Figure 4. It
is seen that the upper bound and asymptotic values for p∗(n, k) are not as
tight as those for p(n, k) even though they track the exact values as curves.
This is expected as p∗(n, k) is obtained by replacing the sum
∑k
j=1 p(n, j)
with the sum
∑k
j=1 p(n− j) and the error term p(n− j)− p(n, j) accumu-
lates as k tends to n−1. Thus, a tighter upper bound for p∗(n, k) will likely
involve a different method of computation.
4We combined identity 5.1.20 for the exponential integral E1(x) on p. 229 in
[Abromowitz-Stegun72] with the relation Ei(x) = −E1(−x) to derive this inequality.
14
REFERENCES CITED
[Abramowitz-Stegun-72] M. Abramowitz and I. Stegun. Ed. Hand-
book of Mathematical Functions with Formulas, Graphs, and Mathe-
matical Tables, New York: Dover Pub., 1972.
[Andrews76-1] G. E. Andrews. The Theory of Partitions. Chapter 4,
pp. 56-57. Addison-Wesley, 1976.
[Andrews76-2] G. E. Andrews. The Theory of Partitions. Chapter 5,
p. 72. Addison-Wesley, 1976.
[Colman82] W. J. A. Colman. The number of partitions of the integer
N into M nonzero positive integers. Math. of Computation. Vol. 39,
No. 159. pp. 213-24. July 1982.
[Kane06] D. M. Kane. An elementary derivation of the asymptotics of
partition functions. Ramanujan Journal. Vol. 11, No. 1. pp. 49-66.
[Merca14] M. Merca. New upper bounds for the number of partitions
into a given number of parts. J. of Number Theory. 142 (2014).
pp.298-304.
[Oruc15] A. Y. Oruc. Foundations of Interconnection Networks. To
be published. CRC Press.
[Szekeres50] G. Szekeres. An asymptotic formula in the theory of par-
titions. Quarterly Journal of Mathematics. Vol. 2, pp. 85-108. 1951.
15