New Recursion Formulas for the Partition Function

Teerapat Srichan, Watcharapon Pimsert^{1}, and Vichian Laohakosol Department of Mathematics Faculty of Science Kasetsart University Bangkok 10900 Thailand

                             fscitrp@ku.ac.th
                             fsciwcrp@ku.ac.th
                             fscivil@ku.ac.th

Abstract We derive several new recursion formulas for the unrestricted partition function as

applications of a general recursion formula for a novel restricted partition function.

1 Introduction and results

A partition of a positive integer n, [1, Chapter 14], is a finite sequence of positive integers λ_{1}, λ_{2}, …, λ_{m} such that

λ_{1} + λ_{2} + ⋯ + λ_{m} = n.

The λ_{i}’s are called the parts of the partition. The number of parts is unrestricted, repetition is allowed and the order of the parts is not taken into account. The corresponding partition function p(n) is defined as the number of unordered partitions of n. Some well-known values of p(n) are ([6, \underline{A000041}])

p(−n) = 0 (n ∈ ℕ), p(0) = 1 (by convention),
p(1) = 1, p(2) = 2, p(3) = 3, p(4) = 5, p(5) = 7, p(6) = 11,
p(7) = 15, p(8) = 22, p(9) = 30, p(10) = 42, p(11) = 56.  (1)

Finding explicit formulas for p(n) is one of the most fundamental problems in additive number theory, and there have appeared a good deal of formulas used to compute p(n).

1Corresponding author.

More recent ones in the spirit of our work here are e.g., the two works in [4, 5]. Added to this list, we present here a seemingly new recursion formula connecting the unrestricted partition function p(n) with a restricted partition function P (n, k); see also [6, \underline{A008284}]. Throughout, ℕ denotes the set of all positive integers and ℕ_{0} := ℕ ∪ {0}.

Definition 1. Let n ∈ ℕ, and k ∈ ℕ_{0}. Define

P (n, k) = \begin{cases}the number of partitions (λ_{1}, λ_{2}, …) of n with k < λ_{i} < n, & if 0 < k < n; \\ 0, & otherwise. \end{cases}

From this definition, note that P (n, k) = 0, when k > ⌊n/2⌋ − 1. Moreover, for a fixed n ∈ ℕ, the restricted partition P (n, k) is a decreasing function in k. Our main result reads as follows.

Theorem 2. Let p(0) = 1 and define p(n) to be 0 if n < 0. Then for n ≥ 4 and k ≥ 1 we have

∑_{i=0}^{∞} a_{k,i} p(n − i) = P (n, k) − P (n − 1, k),  (2)

where the coefficients a_{k,i} are obtained from the expansion

(x^{n} − 2x^{n−1} + x^{n−2}) ∏_{i=2}^{k} (1 − x^{−i}) = ∑_{i=0}^{∞} a_{k,i}x^{n−i},  (3)

where empty product is taken to be 1.

Comparing with existing schemes, Theorem 2 can be employed competitively to determine the values of p(n) efficiently subject to the ease of computing P (n, k) − P (n − 1, k) and a_{k,i}. When k is large, the expression P (n, k)−P (n−1, k) is easy to find while the coefficients a_{k,i} are not (because the product expansion in (3) is lengthy). In the last section, several applications of Theorem 2 for both large and small values of k are worked out. In addition, optimal values of k, in terms of n, which render easy and effective applications of Theorem 2 are derived.

2 Lemmas

The following lemma, whose simple straightforward computation check is omitted, provides information for some particular cases needed in the proof of Theorem 2.

Lemma 3. For k ∈ ℕ, we have

P (2k + 1, k) = 0, P (2k + 2, k) = 1, P (2k + 3, k) = 1.

The main ingredient in our proof of Theorem 2 is:

Lemma 4. For given k, n ∈ ℕ with n > k, we have

P (n, k) = P (n, k + 1) + P (n − k − 1, k) + 1.

Proof. Let A be the set of unrestricted partitions of n having parts > k + 1 but < n, and B the set of unrestricted partitions of n having parts > k with at least one part being k + 1. By definition, we have

P (n, k) = |A| + |B|.  (4)

By definition, we have

|A| = P (n, k + 1),

while |B| is equal to the number of unrestricted partitions of n − k − 1 having parts > k and < n plus the partition n = (n − k − 1) + (k + 1). Putting these values into (4), Lemma 4 follows.

The next lemma relates the partition function p(n) with the initial value of the function P (n, k).

Lemma 5. For n ≥ 2, we have

p(n) = P (n, 1) + p(n − 1) + 1.  (5)

Proof. The case n = 2 follows immediately from the numerical values p(2) = 2, p(1) = 1 and P (2, 1) = 0.

For n ≥ 3, the proof follows from the observation that the set of all unrestricted partitions of n comprises 3 disjoint classes. The first class consists of all partitions having parts belonging to {2, 3, …, n − 1}, while the second class contains all partitions having at least one part being 1, and the last class is simply the set {n}.

Our next lemma relates P (n, k) with the partition function p_{s}(n) which counts the number of partitions of n into s parts ([2, 3]).

Lemma 6. Let m, k ∈ ℕ. We have

P (mk + r, k) = ∑_{i=2}^{m−1} p_{i}((m − i)k + r),  (6)

where 0 ≤ r < k.

Proof. For m ∈ {1, 2}, the relation (6) holds trivially because P (k, k) = P (2k, k) = P (2k + 1, k) = 0, and the right-hand sum is empty. Consider now m ≥ 3. By definition, we can write

P (mk + r, k) = ∑_{i=2}^{m−1} P_{i}(mk + r, k),  (7)

where

P_{i}(n, k) = \begin{cases}the number of partitions (λ_{1}, λ_{2}, …, λ_{i}) of n with k < λ_{•} < n, & if 0 < k < n; \\ 0, & otherwise. \end{cases}

For a fixed number of parts i ∈ {2, 3, …, m − 1}, to count P_{i}(mk + r, k), we first delete k from each of the i parts. This gives rise to an equivalent counting of an unordered partition of mk + r − ik = (m − i)k + r, yielding P_{i}(mk + r, k) = p_{i}((m − i)k + r).

The following lemma details precise values and certain relations of p_{s}(n) for small s. Trivial proofs of the first two assertions are omitted while the remaining two assertions are quoted from [2].

Lemma 7. For n ≥ 0, we have

1) p_{2}(n) = ⌊n/2⌋.

2) p_{3}(n) = ⟨n^{2}/12⟩, where ⟨z⟩ denotes the nearest integer of z ∈ ℝ.

3) ([2, Proposition 5]) For n ≥ 3, we have

p_{3}(n) − p_{3}(n − 1) = ⌊\frac{n + 1}{2}⌋ − ⌊\frac{n + 2}{3}⌋ .

4) ([2, Proposition 9]) For n ≥ 5, we have

p_{4}(n) − p_{4}(n − 1) = p_{3}(χ(n)), where χ(n) = \begin{cases}\frac{n}{2} + 1, & if 2 | n; \\ \frac{n−1}{2}, & otherwise. \end{cases}

3 Proof of Theorem 2

From Lemma 4, we have

P (n, k + 1) = P (n, k) − P (n − k − 1, k) − 1,  (8)

which shows that the second argument can be successively reduced to the case k = 1, i.e., each P (n, k) can be uniquely written as a ℤ-linear combination of finitely many elements taken from P (n, 1), P (n − 1, 1), P (n − 2, 1), . . .. Applying the result of Lemma 5, the values P (n, 1), P (n − 1, 1), P (n − 2, 1), … can be furthered uniquely reduced to the values of the unrestricted partition function p(n), p(n − 1), p(n − 2), …, which implies that each P (n, k) can be uniquely written as a ℤ-linear combination of finitely many elements taken from p(n), p(n − 1), p(n − 2), . . .. To determine this explicitly, it is more convenient to write

P (n, k) − P (n − 1, k) = ∑_{i=0}^{∞} a_{k,i}p(n − i),  (9)

where a_{k,i} ∈ ℤ; this sum is finite because p(m) = 0 for integers m < 0. To compute the coefficients a_{k,i}, we resort to the use of generating series

f_{k}^{n}(x) = ∑_{i=0}^{∞} a_{k,i}x^{n−i}.  (10)

We claim that

f_{1}^{n}(x) = x^{n} − 2x^{n−1} + x^{n−2}, f_{k}^{n}(x) = (x^{n} − 2x^{n−1} + x^{n−2}) ∏_{i=2}^{k}(1 − x^{−i}) (2 ≤ k < n). (11)

For the case k = 1, Lemma 5 gives

P (n, 1) − P (n − 1, 1) = (p(n) − p(n − 1) − 1) − (p(n − 1) − p(n − 2) − 1)
= p(n) − 2p(n − 1) + p(n − 2),

yielding a_{1,0} = 1, a_{1,1} = −2, a_{1,2} = 1 and a_{1,n} = 0 for all n ≥ 3, and so (11) holds when k = 1. For 2 ≤ k < n, using Lemma 4, we get

P (n, k − 1) − P (n − 1, k − 1)
= (P (n, k) + P (n − k, k − 1) + 1) − (P (n − 1, k) + P (n − 1 − k, k − 1) + 1)
= (P (n, k) − P (n − 1, k)) + (P (n − k, k − 1) − P (n − k − 1, k − 1)) .

Using (9) to replace the differences of two restricted partitions, we get

∑_{i=0}^{∞} a_{k−1,i} p(n − i) = ∑_{i=0}^{∞} a_{k,i} p(n − i) + ∑_{i=0}^{∞} a_{k−1,i} p(n − k − i).  (12)

We claim now that

f_{k−1}^{n}(x) = f_{k}^{n}(x) + f_{k−1}^{n−k}(x).  (13)

Using (10), the relation (13) holds if and only if the following system of equations holds

a_{k−1,i} = a_{k,i}  (i = 0, 1, …, k − 1)
a_{k−1,i} = a_{k,i} + a_{k−1,i−k} (i = k, k + 1, k + 2, …).

This system is identical with the one obtained from (12) by equating the coefficients of p(n − i). As the coefficients a_{j,i} are uniquely determined, the system of equation does indeed hold which in turn affirms the relation (13). Since

f_{k−1}^{n−k}(x) = a_{k−1,0}x^{n−k} + a_{k−1,1}x^{n−k−1} + ⋯ = \frac{1}{x^{k}} f_{k−1}^{n}(x),

substituting this into (13), we get f_{k}^{n}(x) = (1 − \frac{1}{x^{k}} ) f_{k−1}^{n}(x). Hence,

f_{2}^{n}(x) = (1 − \frac{1}{x^{2}} ) f_{1}^{n}(x), …,

f_{k}^{n}(x) = (1 − \frac{1}{x^{k}} ) (1 − \frac{1}{x^{k−1}} ) ⋯ (1 − \frac{1}{x^{2}} ) f_{1}^{n}(x) = (x^{n} − 2x^{n−1} + x^{n−2}) ∏_{i=2}^{k} (1 − x^{−i}) ,

which proves the second assertion in (11).

4 Applications

To apply Theorem 2 to compute values of p(n) subject to the knowledge of preceding values, we subdivide our treatment into two separate subcases corresponding to large and small values of k relative to n.

4.1 The case of large k

Here, we obtain several applications for k = ⌊n/3⌋ , ⌊n/4⌋ and ⌊n/5⌋. In these cases, explicit formulas for the right-hand expression of (2) can be easily determined using Lemmas 6 and 7.

Theorem 8. For n ≥ 4, we have

∑_{i=0}^{∞} a_{⌊n/3⌋,i} p(n − i) = \begin{cases}1, & if n is even; \\ 0, & if n is odd. \end{cases}  (14)

where the coefficients a_{⌊n/3⌋,i} are obtained from the expansion

(x^{n} − 2x^{n−1} + x^{n−2}) ∏_{i=2}^{⌊n/3⌋} (1 − x^{−i}) = ∑_{i=0}^{∞} a_{⌊n/3⌋,i}x^{n−i},  (15)

with empty product being taken as 1.

Proof. Write n = 3k + r for some k ∈ ℕ ∪ {0} and 0 ≤ r < 3. From Lemma 6 and Lemma 7 part 1), we get

P (n, k) − P (n − 1, k) = P (3k + r, k) − P (3k + r − 1, k)
= p_{2}(k + r) − p_{2}(k + r − 1) = ⌊\frac{k + r}{2}⌋ − ⌊\frac{k + r − 1}{2}⌋ = \begin{cases}1, & if k + r is even; \\ 0, & if k + r is odd. \end{cases} (16)

Applying Theorem 2 with k = ⌊n/3⌋ and using (16), the result follows.

Example 9. As an illustration, we use Theorem 8 to compute p(9). Here, n = 9, k = ⌊n/3⌋ = 3. The left-hand expression of (15) is

(x^{9} − 2x^{8} + x^{7}) ∏_{i=2}^{3}(1 − x^{−i}) = x^{9} − 2x^{8} + x^{6} + x^{5} − 2x^{3} + x^{2},

so that

a_{3,0} = 1, a_{3,1} = −2, a_{3,2} = 0, a_{3,3} = 1, a_{3,4} = 1, a_{3,5} = 0, a_{3,6} = −2, a_{3,7} = 1.

From (14), we have

0 = p(9) − 2p(8) + p(6) + p(5) − 2p(3) + p(2),

and using known values from (1), we get

p(9) = 2p(8) − p(6) − p(5) + 2p(3) − p(2) = 2(22) − 11 − 7 + 2(3) − 2 = 30.

Similarly, to find p(10) and p(11), we take n = 10 and n = 11 yielding in both cases k = ⌊n/3⌋ = 3. Using (14), the left-hand expressions of (15) are, respectively,

x^{10} − 2x^{9} + x^{7} + x^{6} − 2x^{4} + x^{3} and x^{11} − 2x^{10} + x^{8} + x^{7} − 2x^{5} + x^{4}.

In view of (14) and using known preceding values from (1), we get

p(10) = 2p(9) − p(7) − p(6) + 2p(4) − p(3) + 1 = 2(30) − 15 − 11 + 2(5) − 3 + 1 = 42
p(11) = 2p(10) − p(8) − p(7) + 2p(5) − p(4) = 2(42) − 22 − 15 + 2(7) − 5 = 56.

For the remaining two cases, it is more convenient to work with k and r instead of n.

Theorem 10. For k ≥ 1 and 0 ≤ r < 4, we have

∑_{i=0}^{∞} a_{k,i} p(4k + r − i) = ⌊\frac{r}{2}⌋ − ⌊\frac{r − 1}{2}⌋ + ⌊\frac{k + r + 1}{2}⌋ − ⌊\frac{k + r + 2}{3}⌋  (17)

where the coefficients a_{k,i} are obtained from the expansion

(x^{4k+r} − 2x^{4k+r−1} + x^{4k+r−2}) ∏_{i=2}^{k} (1 − x^{−i}) = ∑_{i=0}^{∞} a_{k,i}x^{4k+r−i},  (18)

with empty product being taken as 1.

Proof. Writing n = 4k + r, 0 ≤ r < 4, using Lemma 6 and Lemma 7 parts 1) and 3), we have

P (4k + r, k) − P (4k + r − 1, k) = p_{2}(2k + r) − p_{2}(2k + r − 1) + p_{3}(k + r) − p_{3}(k + r − 1)

= ⌊\frac{2k + r}{2}⌋ − ⌊\frac{2k + r − 1}{2}⌋ + ⌊\frac{k + r + 1}{2}⌋ − ⌊\frac{k + r + 2}{3}⌋

= ⌊\frac{r}{2}⌋ − ⌊\frac{r − 1}{2}⌋ + ⌊\frac{k + r + 1}{2}⌋ − ⌊\frac{k + r + 2}{3}⌋ .

Example 11. We illustrate the use of Theorem 10 to compute p(8). Here n = 8, k = 2 and r = 0. The left-hand expression of (18) is

(x^{8} − 2x^{7} + x^{6}) ∏_{i=2}^{2}(1 − x^{−i}) = x^{8} − 2x^{7} + 2x^{5} − x^{4},

so that

a_{2,0} = 1, a_{2,1} = −2, a_{2,2} = 0, a_{2,3} = 2, a_{2,4} = −1.

In view of (17), we have

1 = ⌊\frac{0}{2}⌋ − ⌊\frac{0 − 1}{2}⌋ + ⌊\frac{2 + 0 + 1}{2}⌋ − ⌊\frac{2 + 0 + 2}{3}⌋ = p(8) − 2p(7) + 2p(5) − p(4),

and using known values from (1), we get

p(8) = 2p(7) − 2p(5) + p(4) + 1 = 2(15) − 2(7) + 5 + 1 = 22.

Similarly, to find p(9), p(10) and p(11), we take n = 9, 10 and n = 11. In the three cases we have r = 1, 2, 3, and the left-hand expressions of (18) are, respectively,

x^{9} − 2x^{8} + 2x^{6} − x^{5}, x^{10} − 2x^{9} + 2x^{7} − x^{6} and x^{11} − 2x^{10} + 2x^{8} − x^{7}.

In view of (17), we have

1 = ⌊\frac{1}{2}⌋ − ⌊\frac{1 − 1}{2}⌋ + ⌊\frac{2 + 1 + 1}{2}⌋ − ⌊\frac{2 + 1 + 2}{3}⌋ = p(9) − 2p(8) + 2p(6) − p(5),

1 = ⌊\frac{2}{2}⌋ − ⌊\frac{2 − 1}{2}⌋ + ⌊\frac{2 + 2 + 1}{2}⌋ − ⌊\frac{2 + 2 + 2}{3}⌋ = p(10) − 2p(9) + 2p(7) − p(6),

1 = ⌊\frac{3}{2}⌋ − ⌊\frac{3 − 1}{2}⌋ + ⌊\frac{2 + 3 + 1}{2}⌋ − ⌊\frac{2 + 3 + 2}{3}⌋ = p(11) − 2p(10) + 2p(8) − p(7),

and using known values from (1), we get

p(9) = 2p(8) − 2p(6) + p(5) + 1 = 2(22) − 2(11) + 7 + 1 = 30
p(10) = 2p(9) − 2p(7) + p(6) + 1 = 2(30) − 2(15) + 11 + 1 = 42
p(11) = 2p(10) − 2p(8) + p(7) + 1 = 2(42) − 2(22) + 15 + 1 = 56.

In passing, observe that to compute p(11), using Theorem 8 we need 5 preceding partitions terms, while using Theorem 10 we need only 3 terms, which indicates that Theorem 10 seems more effective than Theorem 8.

Theorem 12. For k ≥ 1 and 0 ≤ r < 5, we have

∑_{i=0}^{∞} a_{k,i} p(5k + r − i) = (k + ⌊\frac{k + r}{2}⌋ + ⌊\frac{r + 1}{2}⌋ + ⟨\frac{(χ(k + r))^{2}}{12} ⟩ )

− ( ⌊\frac{k + r − 1}{2}⌋ + ⌊\frac{2k + r + 2}{3}⌋ )  (19)

where the coefficients a_{k,i} are obtained from the expansion

(x^{5k+r} − 2x^{5k+r−1} + x^{5k+r−2}) ∏_{i=2}^{k} (1 − x^{−i}) = ∑_{i=0}^{∞} a_{k,i}x^{5k+r−i}  (20)

with empty product being taken as 1; the symbols ⟨z⟩ and χ(n) are defined as in Lemma 7 parts 2) and 4).

Proof. Writing n = 5k + r, 0 ≤ r < 5, using Lemma 6 and Lemma 7 parts 1), 2), 3) and 4), we have

P (5k + r, k) − P (5k + r − 1, k)

= p_{2}(3k + r) − p_{2}(3k + r − 1) + p_{3}(2k + r) − p_{3}(2k + r − 1) + p_{4}(k + r) − p_{4}(k + r − 1)

= ⌊\frac{3k + r}{2}⌋ − ⌊\frac{3k + r − 1}{2}⌋ + ⌊\frac{2k + r + 1}{2}⌋ − ⌊\frac{2k + r + 2}{3}⌋ + p_{3}(χ(k + r))

= ⌊\frac{k + r}{2}⌋ − ⌊\frac{k + r − 1}{2}⌋ + k + ⌊\frac{r + 1}{2}⌋ − ⌊\frac{2k + r + 2}{3}⌋ + ⟨\frac{(χ(k + r))^{2}}{12} ⟩ .

Example 13. We illustrate the use of Theorem 12 to compute p(10), p(11), p(12), p(13) and p(14) with the following respective values:

n = 10, k = 2, r = 0;  n = 11, k = 2, r = 1;  n = 12, k = 2, r = 2;
n = 13, k = 2, r = 3; n = 14, k = 2, r = 4.

The left-hand expression of (20) is

(x^{n} − 2x^{n−1} + x^{n−2}) ∏_{i=2}^{2}(1 − x^{−i}) = x^{n} − 2x^{n−1} + 2x^{n−3} − x^{n−4},

so that a_{2,0} = 1, a_{2,1} = −2, a_{2,2} = 0, a_{2,3} = 2, a_{2,4} = −1. From (19), we have

∑_{i=0}^{∞} a_{2,i} p(10 + r − i) = (2 + ⌊\frac{2 + r}{2}⌋ + ⌊\frac{r + 1}{2}⌋ + ⟨\frac{(χ(2 + r))^{2}}{12} ⟩ )

− ( ⌊\frac{2 + r − 1}{2}⌋ + ⌊\frac{4 + r + 2}{3}⌋ ) =: S_{r}.

By simple computation, we get

S_{0} = 1, S_{1} = 1, S_{2} = 3, S_{3} = 1, S_{4} = 3.

Using known values from (1), we get

p(10) = 2p(9) − 2p(7) + p(6) + 1 = 2(30) − 2(15) + 11 + 1 = 42
p(11) = 2p(10) − 2p(8) + p(7) + 1 = 2(42) − 2(22) + 15 + 1 = 56
p(12) = 2p(11) − 2p(9) + p(8) + 3 = 2(56) − 2(30) + 22 + 3 = 77
p(13) = 2p(12) − 2p(10) + p(9) + 1 = 2(77) − 2(42) + 30 + 1 = 101
p(14) = 2p(13) − 2p(11) + p(10) + 3 = 2(101) − 2(56) + 42 + 3 = 135.

4.2 The case of small k

In this case, using a trick, the right-hand side of (2) can be slightly improved. Theorem 14. For n ≥ 4 and k ≥ 1, we have

∑_{i=0}^{∞} a_{k,i} p(n − i) = ∑_{i=2}^{⌊n/(k+1)⌋} (p_{i}(n − ki) − p_{i}(n − ki − 1)) ,  (21)

where the coefficients a_{k,i} are obtained from the expansions (3). Proof. Write n = mk + r, 0 ≤ r < k. From Lemma 6, we have

P (n, k) = P (mk + r, k) = ∑_{i=2}^{m−1} p_{i}((m − i)k + r) = ∑_{i=2}^{⌊n/(k+1)⌋} p_{i}(n − ki);  (22)

since p_{s}(n) counts the number of partitions of n into s parts, we must have s ≤ n. This enables us to replace the upper limit of summation m − 1 = ⌊n/k⌋ − 1 by ⌊n/(k + 1)⌋ which is better when k is small compared to n. Using Theorem 2 and (22), we have

∑_{i=0}^{∞} a_{k,i} p(n − i) = ∑_{i=2}^{⌊n/(k+1)⌋} p_{i}(n − ki) − ∑_{i=2}^{⌊(n−1)/(k+1)⌋} p_{i}(n − 1 − ki),

and the result follows from the observation that lengthening the last upper limit of summation yielding only zero value.

Example 15. We illustrate the use of Theorem 14 to compute p(14). If we take k = 2, then ⌊n/(k + 1)⌋ = ⌊14/3⌋ = 4. Thus, (21) and Lemma 7 give

∑_{i=0}^{∞} a_{2,i} p(14 − i) = ∑_{i=2}^{4} (p_{i}(14 − 2i) − p_{i}(13 − 2i))
= p_{2}(10) − p_{2}(9) + p_{3}(8) − p_{3}(7) + p_{4}(6) − p_{4}(5)
= ⌊10/3⌋ − ⌊9/2⌋ + ⌊9/2⌋ − ⌊10/2⌋ + p_{3}(χ(6)) = 3.

In view of (3), we have

(x^{14} − 2x^{13} + x^{12}) ∏_{i=2}^{2} (1 − x^{−i}) = x^{14} − 2x^{13} + 2x^{11} − x^{10} = ∑_{i=0}^{∞} a_{2,i} x^{14−i}.

Theorem 14 yields

p(14) = 2p(13) − 2p(11) + p(10) + 3 = 2(101) − 2(56) + 42 + 3 = 135.

If we take k = 3, then ⌊14/(3 + 1)⌋ = 3. From (21), we have

∑_{i=0}^{∞} a_{3,i} p(14 − i) = ∑_{i=2}^{3} (p_{i}(14 − 3i) − p_{i}(13 − 3i)) = p_{2}(8) − p_{2}(7) + p_{3}(5) − p_{3}(4) = 2.

In view of (3), we have

(x^{14} − 2x^{13} + x^{12}) ∏_{i=2}^{3} (1 − x^{−i}) = x^{14} − 2x^{13} + x^{11} + x^{10} − 2x^{8} + x^{7} = ∑_{i=0}^{∞} a_{3,i} x^{14−i}.

Theorem 14 and preceding values give

p(14) = 2p(13) − p(11) − p(10) + 2p(8) − p(7) + 2
= 2(101) − (56) − 42 + 2(22) − 15 + 2 = 135.

5 Acknowledgments

The authors gratefully acknowledge a financial support under the Basic Research Fund (BRF) provided by the Faculty of Science, Kasetsart University.

References

[1] T. M. Apostol, Introduction to Analytic Number Theory, Springer, 1976.

[2] M. Barnabei, F. Bonetti, and M. Silimbani, Bijections and recurrences for integer partitions into a bounded number of parts. Appl. Math. Lett. 22 (2009), 297–303.

[3] J. L. De Carufel, A few identities involving partitions with a fixed number of parts, Ars Comb. 68 (2003), 125–130.

[4] M. Merca, A generalization of Euler’s pentagonal number recurrence for the partition function, Ramanujan J. 37 (2015), 589–595.

[5] M. Merca and M. D. Schmidt, The partition function p(n) in terms of the classical Möbius function, Ramanujan J. 49 (2019), 87–96.

[6] N. J. A. Sloane et al., The On-line Encyclopedia of Integer Sequences, 2020. Available

   at https://oeis.org/.

2020 Mathematics Subject Classification: Primary 05A17; Secondary 11P81. Keywords: recursion formula, restricted partition function.

(Concerned with sequences \underline{A000041} and \underline{A008284}.)

Received March 23 2021; revised version received May 20 2021. Published in Journal of Integer Sequences, May 20 2021.

Return to Journal of Integer Sequences home page.