Partitions with Fixed Number of Sizes

David Christopher Department of Mathematics The American College Madurai Tamil Nadu India

                     davchrame@yahoo.co.in

Abstract

Let t(n, s) and t(n, k, s), respectively, be the number of partitions of n with s different sizes, and the number of partitions of n with exactly k parts and s different sizes. In this article, an asymptotic estimate for t(n, k, s) is presented for the following two cases: (i) s = k − 1 and (ii) when k is a prime number with s = 2. Further, the enumeration of uniform partitions with exactly 2 sizes is considered and the estimate for its partial sum is derived. Finally, a parity result for t(n, 2) is obtained.

1 Introduction and statement of results

Let n be a positive integer. By a partition of n we mean a finite non-increasing sequence of positive integers λ = (λ_{1}, λ_{2}, …, λ_{m}) such that λ_{1} + λ_{2} + ⋯ + λ_{m} = n. The λ_{i} are called the parts of the partition and each element in the set of parts is called a size of λ.

Let t(n, s) and t(n, k, s), respectively, be the number of partitions of n with s different sizes, and the number of partitions of n with exactly k parts and s different sizes.

These two classes of functions are subjects of investigation in the recent past. MacMahon [7] was the first who considered this kind of partitions. In 2005, Deutsch included the number of partitions of n with exactly two odd sizes (see \underline{A117955}) and the number of partitions of n with exactly two sizes, one odd and one even (see \underline{A117956}) in the On-Line Encyclopedia of Integer Sequences (OEIS). Sloane [9] included the function t(n, 2) in the OEIS (see \underline{A002133}).

Deutsch presented the following generating function of t(n, 2) (see \underline{A002133}):

∑_{n=1}^{∞} t(n, 2)x^{n} = ∑_{j=1}^{i−1} ∑_{i=1}^{∞} \frac{x^{i+j}}{(1 − x^{i})(1 − x^{j})}.

Andrews [1] gave the following formula for t(n, 2) by means of q series manipulations:

t(n, 2) = \frac{∑_{k=1}^{n−1} τ(k)τ(n − k) + τ(n) − σ(n)}{2},

where τ(n) denote the number of positive divisors of n and σ(n) denote the sum of the positive divisors of n.

In 2011, Tani and Bouroubi [8] found an elegant exact formula for the function t(n, k, 2). The purpose of this article is twofold. First, we give an asymptotic estimate for t(n, k, s)

for certain cases.

Theorem 1. We have

t(n, k + 1, k) ∼ \frac{C_{k−1}}{(k + 1)!^{k−1}} n^{k−1},  (1)

where C_{k−1} is given by the recurrence relation:

C_{k−1} = (k − 2)!kC_{k−2}(k + 1)^{k−2} + k \frac{(k + 1)!^{k−2}}{(k − 1)!}  (2)

with C_{1} = 3.

Theorem 2. For prime p ≥ 3, we have

t(n, p, 2) ∼ \frac{∑{p−1 \atop j=1} \frac{(p−1)!}{j}}{p!} n.

The method adopted to arrive at the above estimates is similar to the one used in a recent paper by David Christopher et al. [5]. In addition to the estimates above, we consider the uniform partitions with 2 sizes and we derive the estimate for the partial sums of its enumeration function.

Definition 3. A partition λ is said to be an uniform partition (see [3]) if, the number of occurrences of a size in λ is identical with that of all the other sizes in λ. The enumeration function U(n, 2) is defined to be the number of uniform partitions of n with exactly 2 sizes.

Theorem 4. We have

∑_{m=1}^{n} U(m, 2) ∼ \frac{π^{2}}{24}n^{2}.

The next result in this article is a parity expression for t(n, 2).

Theorem 5. Let n be a positive integer.

1. If n ≡ 1 (mod 2), then we have

t(n, 2) ≡ \begin{cases}\frac{τ(n)−1}{2} (mod 2), & if n is a square; \\ \frac{τ(n)}{2} (mod 2), & if n is not a square. \end{cases}

2. If n ≡ 0 (mod 2) and β is the highest power of 2 that divides n, then we have

t(n, 2) ≡ \begin{cases}\frac{(β−1)τ( \frac{n}{2^{β}} )−1}{2} (mod 2), & if n is a square; \\ \frac{(β−1)τ( \frac{n}{2^{β}} )}{2} (mod 2), & if n is not a square. \end{cases}

In the final section, we provide two different proofs for this theorem.

2 Proof of the Estimates

2.1 Prerequisites

To begin with, we need the following recurrence relation satisfied by t(n, k, s), which has k − s + 2 preceding terms. Note that, the following recurrence relation is identical to the one given by Tani and Bouroubi [8], but it is presented here in a linear form. The method of proof below is bijective whereas the former proof is based upon a simple variation in the system of equations that admits partitions with fixed number of sizes as its solution. Lemma 6 (Tani and Bouroubi [8]). We have

t(n, k, s) = t(n − k, k, s) + ∑_{r=1}^{k−s+1} t(n − k, k − r, s − 1).

Proof. Let (λ_{1}, λ_{2}, …, λ_{k}) be a partition of n with exactly k parts and s different sizes. Case (i): Assume that λ_{k} > 1. Consider the mapping

(λ_{1}, λ_{2}, …, λ_{k}) → (λ_{1} − 1, λ_{2} − 1, …, λ_{k} − 1);

this mapping establishes an one-to-one correspondence between the following sets: • The set of all partitions of n with exactly k parts, s different sizes and least part a_{k} > 1.

• The set of all partitions of n − k with exactly k parts and s different sizes.

We observe that the cardinality of the latter set is t(n − k, k, s). Case (ii): Assume that λ_{k} = λ_{k−1} = ⋯ = λ_{k−(r−1)} = 1 and λ_{k−r} > 1 for some positive integer r ≥ 1.

We see that the mapping

(λ_{1}, λ_{2}, …, λ_{k}) → (λ_{1} − 1, λ_{2} − 1, …, λ_{k−r} − 1)

establishes an one-to-one correspondence between the following sets:

• The set of all partitions of n with exactly k parts, s different sizes and λ_{k} = λ_{k−1} = ⋯ = λ_{k−(r−1)} = 1 and λ_{k−r} > 1.

• The set of all partitions of n − k with exactly k − r parts and s − 1 different sizes. Notice that the cardinality of the latter set is t(n − k, k − r, s − 1). Since r varies from 1 to k − s + 1, the result follows. Definition 7. Let n and k be two positive integers with n ≥ \frac{k(k+1)}{2} . The enumeration function q(n, k) is defined to be the number of partitions of n with k distinct parts.

The following result is required in the proof of Theorem 1. Lemma 8 (David Christopher and Davamani Christober [4]). Let k ≥ 2 be a positive integer. For each r ∈ {0, 1, …, k! − 1}, the function q(k!l + r, k) is a polynomial in l of degree k − 1 with the leading coefficient \frac{k!^{k−2}}{(k−1)!}.

2.2 Proof of Theorem 1

Wielding Lemma 6 and Lemma 8 we will prove the following statements:

1. The function t((k + 1)!l + r, k + 1, k) is a polynomial in l of degree k − 1 for each r ∈ {0, 1, …, (k + 1)! − 1}.

2. The leading coefficient of t((k +1)!l +r, k +1, k), denoted C_{k−1}, satisfies the recurrence

relation (2). From these statements one can get the following limit:

lim_{l→∞} \frac{t((k + 1)!l + r, k + 1, k)}{((k + 1)!l + r)^{k−1}} = \frac{C_{k−1}}{(k + 1)!^{k−1}}

for each r ∈ {0, 1, …, (k + 1)! − 1}; which is equivalent to the estimate (1).

Now we prove the statements above simultaneously by induction over k. We observe that: t(n, k, k) = q(n, k). Put k = 3 and s = 2 in Lemma 6 to get

t(n, 3, 2) − t(n − 3, 3, 2) = t(n − 3, 2, 1) + q(n − 3, 1)
= \begin{cases}2, & if n ≡ 3 (mod 2); \\ 1, & otherwise. \end{cases}

Put n = 3!l + r with 0 ≤ r ≤ 3! − 1, where l is a non-negative integer. Then we have

t(3!l + r, 3, 2) − t(3!l + r − 3, 3, 2) = \begin{cases}2, & if r ≡ 1 (mod 2); \\ 1, & if r ≡ 0 (mod 2), \end{cases}

and

t(3!l + r − 3, 3, 2) − t(3!l + r − 6, 3, 2) = \begin{cases}2, & if r ≡ 0 (mod 2); \\ 1, & if r ≡ 1 (mod 2). \end{cases}

The sum of the above two expressions can be put as t(3!l + r, 3, 2) − t(3!(l − 1) + r, 3, 2) = 3 for each r ∈ {0, 1, …, 3! − 1}. Then substituting 2, 3, …, l in place of l gives t(3!l +r, 3, 2) = 3(l − 1) + t(r, 3, 2) for each r ∈ {0, 1, …, 3! − 1}. Thus, the statements above hold for k = 2.

Assume that the assertion is true up to some k ≥ 2. Set k + 1 as the number of parts, k as the number of sizes and n = (k + 1)!l + r, where l is a non-negative integer and r ∈ {0, 1, …, (k + 1)! − 1}. Then applying Lemma 6 k! times, we get

t((k + 1)!l + r, k + 1, k) − t((k + 1)!(l − 1) + r, k + 1, k)

= ∑_{i=1}^{k!} t((k + 1)!l + r − i(k + 1), k, k − 1)

+ ∑_{i=1}^{k!} q((k + 1)!l + r − i(k + 1), k − 1).

In view of the division algorithm one can obtain unique pair of integers say (r_{i}, q_{i}) for each i ∈ {1, 2, …, k!} satisfying the equality k!q_{i} + r_{i} = r − i(k + 1) with 0 ≤ r_{i} ≤ k! − 1. Similarly one can get unique pair of integers say (r′_{i}, q′_{i}) for each i ∈ {1, 2, …, k!} satisfying the equality (k − 1)!q′_{i} + r′_{i} = r − i(k + 1) with 0 ≤ r′_{i} ≤ (k − 1)! − 1. Consequently, the right side of the above equality can be written as

∑_{i=1}^{k!} t(k!((k + 1)l + q_{i}) + r_{i}, k, k − 1) + ∑_{i=‘1}^{k!} q ((k − 1)! (\frac{(k + 1)!}{(k − 1)!}l + q′_{i}) + r′_{i}, k − 1) . (3)

Put l_{i} = (k+1)l+q_{i}. By induction assumption, the function t(k!l_{i}+r_{i}, k, k−1) is a polynomial in l_{i} of degree k − 2 with the leading coefficient C_{k−2} as given in the recurrence relation (2) for each r_{i} ∈ {0, 1, …, k! − 1} and i ∈ {1, 2, …, k!}. Just assuming this polynomial representation, we see that the first summation in (3) is a sum of k! polynomials in l, each of which is of degree k − 2 with the leading coefficient C_{k−2}(k + 1)^{k−2}. (At this juncture, we note that (k + 1)l + q_{i} may be negative for some initial values of l. In such instances, we assume the extrapolation of the function t(k!l_{i} + r_{i}, k, k − 1) as a polynomial in l_{i} and not as an enumeration function.) Thus, the first summation in (3) is itself a polynomial in l of degree k − 2 with the leading coefficient k!C_{k−2}(k + 1)^{k−2}. Put l′_{i} = \frac{(k+1)!}{(k−1)!}l + q′_{i}. From Lemma 8 it follows that q((k − 1)!l′_{i} + r′_{i}, k − 1) is a polynomial in l′_{i} of degree k − 2 for each r′_{i} ∈ {0, 1, …, (k − 1)! − 1} and i ∈ {1, 2, …, k!}. Consequently, the second summation in (3) is itself a polynomial in l of degree k − 2 with the leading coefficient k!\frac{(k−1)!^{k−3}}{(k−2)!} \frac{(k+1)!^{k−2}}{(k−1)!^{k−2}} . Thus, the summation term in (3) is a polynomial in l of degree k − 2 with the leading coefficient k!C_{k−2}(k + 1)^{k−2} + k!\frac{(k−1)!^{k−3}}{(k−2)!} \frac{(k+1)!^{k−2}}{(k−1)!^{k−2}} . Accordingly, t((k + 1)!l + r, k + 1, k) − t((k + 1)!(l − 1) + r, k + 1, k) is a polynomial in l of degree k − 2. Put f(l) = t((k + 1)!l + r, k + 1, k) − t((k + 1)!(l − 1) + r, k + 1, k). Substituting the values 1, 2, …, l in place of l and adding we get t((k + 1)!l + r, k + 1, k) = ∑_{i=1}^{l} f(i) − t(r, k + 1, k). This equality implies that t((k + 1)!l + r, k + 1, k) is a polynomial in l of degree k − 1.

If one denotes the leading coefficient of t((k + 1)!l + r, k + 1, k) by C_{k−1}, then from the conclusions above we get

(k − 1)C_{k−1} = k!C_{k−2}(k + 1)^{k−2} + k!\frac{(k − 1)!^{k−3}}{(k − 2)!} \frac{(k + 1)!^{k−2}}{(k − 1)!^{k−2}} .

This simplifies to the recurrence relation (2). The proof is now completed.

Corollary 9. From the recurrence relation of C_{n} given in the Theorem 1 we get

C_{1} = 3, C_{2} = 72, C_{3} = 24000, C_{4} = 233280000, …

From these values of C_{i}, we have the following estimates:

t(n, 3, 2) ∼ \frac{1}{2}n;

t(n, 4, 3) ∼ \frac{1}{8}n^{2};

t(n, 5, 4) ∼ \frac{1}{72}n^{3};

t(n, 6, 5) ∼ \frac{1}{1152}n^{4}.

2.3 Proof of Theorem 2

Let p be a prime number. Then from Lemma 6 it follows that

t(n, p, 2) − t(n − p, p, 2) = ∑_{j=1}^{p−1} t(n − p, j, 1).

Put n = p!l + r (where l is a positive integer and 0 ≤ r ≤ p! − 1) and apply Lemma 6 (p − 1)! times in the above relation to get

t(p!l + r, p, 2) − t(p!(l − 1) + r, p, 2) = ∑_{j=1}^{p−1} ∑_{i=1}^{(p−1)!} t(p!l + r − pi, j, 1).  (4)

Notice that

t(p!l + r − pi, j, 1) = \begin{cases}1, & if pi ≡ r (mod j); \\ 0, & otherwise, \end{cases}

and the congruence equation

px ≡ r (mod j)

has unique solution modulo j for each j ∈ {1, 2, …, p − 1}. Consequently, we get the right side of (4) as ∑_{j=1}^{p−1} \frac{(p−1)!}{j}. Then replacing l by 1, 2, …, l in (4) and adding gives

t(p!l + r, p, 2) = t(r, p, 2) + (∑_{j=1}^{p−1} \frac{(p − 1)!}{j}) l

for each r ∈ {0, 1, …, p! − 1}. This implies that

lim_{l→∞} \frac{t(p!l + r, p, 2)}{p!l + r} = \frac{∑{p−1 \atop j=1} \frac{(p−1)!}{j}}{p!}

for each r ∈ {0, 1, …, p! − 1}. Equivalently,

t(n, p, 2) ∼ \frac{∑{p−1 \atop j=1} \frac{(p−1)!}{j}}{p!} n;

this is the contention of the Theorem 2.

Remark 10. At this juncture, we remark that, the method adopted so far to derive asymptotic estimates may turn futile for some other cases. For instance, from the exact expression for the function t(n, 4, 2) given in [8] one can get the following values:

1. t(12l + 4, 4, 2) = 7l for every non-negative integer l.

2. t(12l + 5, 4, 2) = 4l + 1 for every non-negative integer l.

This leads to the conclusion that

t(n, 4, 2) ≁ Kn

for every real number K.

2.4 Proof of Theorem 4

Recall that the function U(n, 2) is the number of uniform partitions of n with exactly 2 sizes. We have

U(n, 2) = ∑_{d|n} q (d, 2)

= ∑_{d|n} ⌊\frac{d − 1}{2}⌋

≤ ∑_{d|n} \frac{d − 1}{2}

= \frac{1}{2} (σ(n) − τ(n)) .

On the other hand, we have

U(n, 2) = ∑_{d|n} q (d, 2)

= ∑_{d|n} ⌊\frac{d − 1}{2}⌋

≥ ∑_{d|n} \frac{d − 2}{2}

= \frac{1}{2} (σ(n) − 2τ(n)) .

Consequently, we have

\frac{1}{2} (∑_{m=1}^{n} σ(m) − 2 ∑_{m=1}^{n} τ(m)) ≤ ∑_{m=1}^{n} U(m, 2) ≤ \frac{1}{2} (∑_{m=1}^{n} σ(m) − ∑_{m=1}^{n} τ(m)) .  (5)

Since

lim_{n→∞} \frac{∑_{m=1}^{n} σ(m)}{\frac{π^{2}}{12} n^{2}} = 1  (6)

and

lim_{n→∞} \frac{∑_{m=1}^{n} τ(m)}{n log n} = 1,  (7)

dividing the inequality (5) by \frac{π^{2}}{12} n^{2} and letting n → ∞ gives

lim_{n→∞} \frac{∑_{m=1}^{n} U(m, 2)}{\frac{π^{2}}{12} n^{2}} = \frac{1}{2},

which is equivalent to the estimate given in Theorem 4. (The validity of the limits (6) and (7) can be seen in [2, p. 57–60].)

3 Two proofs of Theorem 5

In this section, we adopt the following notation: if λ = (λ_{1}, λ_{2}, …, λ_{k}) is a partition of n and {a_{1}, a_{2}, …} is the set of all sizes of λ with a_{1} > a_{2} > ⋯, then we denote λ = (a_{1}^{f_{1}}a_{2}^{f_{2}} ⋯) when the size a_{i} occurs exactly f_{i} number of times in λ. Let P_{2}^{n} denote the set of all partitions of n with exactly two sizes.

3.1 A proof using Jacobi’s formula

Proof. Let λ = (a_{1}^{f_{1}}a_{2}^{f_{2}}) ∈ P_{2}^{n}. Then we have a_{1}f_{1} + a_{2}f_{2} = n with a_{1} > a_{2}.

Case (i): f_{1} = f_{2}. In this case we have n = f_{1}a_{1} + f_{2}a_{2} = f(a_{1} + a_{2}), where f_{1} = f_{2} = f (say). Clearly, f|n and the enumeration of the ordered pairs (a_{1}, a_{2}) satisfying the equality is q (\frac{n}{f}, 2). Thus, the number of partitions belonging to this case is ∑_{f|n} q (\frac{n}{f}, 2).

Case (ii): f_{1} = a_{1} and f_{2} = a_{2}. We see that the number of partitions belonging to this case equals the number of ways that n can be written as the sum of two distinct nonzero squares; we denote this enumeration by R_{2}(n).

Case (iii): Assume that f_{1} ≠ f_{2} with either a_{1} ≠ f_{1} or a_{2} ≠ f_{2}, and either f_{1} ≠ a_{2} or f_{2} ≠ a_{1}. In this case, consider the mapping

T ((a_{1}^{f_{1}}a_{2}^{f_{2}})) = \begin{cases}(f_{1}^{a_{1}}f_{2}^{a_{2}}), & if f_{2} < f_{1}; \\ (f_{2}^{a_{2}}f_{1}^{a_{1}}), & if f_{1} < f_{2}. \end{cases}

Clearly, T is an involutory mapping with no fixed point. Moreover, we see that if λ belongs to this case, then T (λ) also belongs to this case and vice versa. Thus, the set of partitions belonging to this case can be got as the disjoint union of set of pairs of elements of the form {λ, T (λ)}, where λ runs over the partitions belonging to this case. Consequently, the number of partitions belonging to this case is even; thus, this enumeration contributes zero to the modulo 2.

Case (iv): f_{1} ≠ f_{2} with a_{1} = f_{2} and a_{2} = f_{1}. We note that this is a special case when n ≡ 0 (mod 2). In this case, we have n = 2a_{1}a_{2}. Consequently, the number of partitions belonging to this case is \frac{τ( \frac{n}{2} )−δ( \frac{n}{2} )}{2}, where δ(·) is the characteristic function of squares defined as follows:

δ(n) = \begin{cases}1, & if n is a square; \\ 0, & otherwise. \end{cases}

Since the above cases are exhaustive, we have the following parity identity for t(n, 2):

t(n, 2) ≡ \begin{cases}(∑_{d|n} q (\frac{n}{d}, 2) + R_{2}(n) + \frac{τ( \frac{n}{2} )−δ( \frac{n}{2} )}{2}) (mod 2), & if n ≡ 0 (mod 2); \\ (∑_{d|n} q (\frac{n}{d}, 2) + R_{2}(n)) (mod 2), & if n ≡ 1 (mod 2). \end{cases} (8)

The remaining part of the proof relies on a formula due to Jacobi. Jacobi [6] found a formula for the number of representations of a given positive integer n as the sum of two squares. This representation includes negative numbers and zero in the squaring process and also the order of the summands is taken into account. Jacobi’s formula [6] is

r_{2}(n) = 4 (d_{1}(n) − d_{3}(n)) ,

where r_{2}(n) denotes the number of ways that a given positive integer n can be written as the sum of two squares and d_{1}(n)(resp.d_{3}(n)) denotes the number of divisors of n that are 1(resp. 3) modulo 4. Using this formula, we can write

R_{2}(n) = \begin{cases}\frac{r_{2}(n)−4}{8}, & if δ(n) = 1 or δ(\frac{n}{2}) = 1; \\ \frac{r_{2}(n)}{8}, & otherwise. \end{cases}

= \begin{cases}\frac{d_{1}(n)−d_{3}(n)−1}{2}, & if δ(n) = 1 or δ(\frac{n}{2}) = 1; \\ \frac{d_{1}(n)−d_{3}(n)}{2}, & otherwise. \end{cases}

We now simplify the parity formula of t(n, 2) mentioned in (8) by using the above expression for R_{2}(n).

To proceed further, we need a few calculations. If n ≡1 (mod 2), then for every divisor d of n, we have

⌊\frac{d − 1}{2}⌋ ≡ \begin{cases}0 (mod 2), & if d ≡ 1 (mod 4); \\ 1 (mod 2), & if d ≡ 3 (mod 4), \end{cases}

and hence it follows that

∑_{d|n} q(d, 2) = ∑_{d|n} ⌊\frac{d − 1}{2}⌋ ≡ d_{3}(n) (mod 2).

If n ≡0 (mod 2), then we have

∑_{d|n} q(d, 2) = ∑_{d|n, d≡1 (mod 2)} q(d, 2) + ∑_{d|n, d≡0 (mod 2)} q(d, 2).

By the previous calculation, we see that

∑_{d|n, d≡1 (mod 2)} q(d, 2) ≡ d_{3}(n) (mod 2).

Let β be the highest power of 2 that divides n. Since ⌊\frac{2n−1}{2}⌋ = n − 1, we have ⌊\frac{2^{k}n−1}{2}⌋ = 2^{k−1}n − 1 ≡ 1 (mod 2) for every k ≥ 2. And consequently we get

∑_{d|n, d≡0 (mod 2)} q(d, 2) ≡ (β − 1)τ (\frac{n}{2^{β}} ) (mod 2).

Accordingly, when n ≡ 0 (mod 2) and β is the highest power of 2 that divides n, we have

∑_{d|n} q(d, 2) ≡ d_{3}(n) + (β − 1)τ (\frac{n}{2^{β}} ) (mod 2).

When these calculations are incorporated in the parity identity (8) we get

t(n, 2) ≡ \begin{cases}d_{3}(n) + \frac{d_{1}(n)−d_{3}(n)−1}{2} (mod 2), & if n ≡ 1 (mod 2) \\ & and δ(n) = 1; \\ d_{3}(n) + \frac{d_{1}(n)−d_{3}(n)}{2} (mod 2), & if n ≡ 1 (mod 2) \\ & and δ(n) = 0; \\ d_{3}(n) + \frac{d_{1}(n)−d_{3}(n)−1}{2} + (β − 1)τ (\frac{n}{2^{β}} ) + \frac{τ( \frac{n}{2} )−δ( \frac{n}{2} )}{2} (mod 2), & if n ≡ 0 (mod 2) \\ & and δ(n) = 1 or \\ & δ(\frac{n}{2}) = 1; \\ d_{3}(n) + \frac{d_{1}(n)−d_{3}(n)}{2} + (β − 1)τ (\frac{n}{2^{β}} ) + \frac{τ( \frac{n}{2} )−δ( \frac{n}{2} )}{2} (mod 2), & if n ≡ 0 (mod 2) \\ & and δ(n) = 0. \end{cases}

Let n ≡ 0 (mod 2). If δ(\frac{n}{2^{β}}) = 1 then either δ(n) = 1 or δ(\frac{n}{2}) = 1. Conversely, if δ(\frac{n}{2^{β}}) = 0, then δ(n) = δ(\frac{n}{2}) = 0. This simple observation transforms the above congruence as follows:

t(n, 2) ≡ \begin{cases}\frac{τ(n)−1}{2} (mod 2), & if n ≡ 1 (mod 2) and \\ & δ(n) = 1; \\ \frac{τ(n)}{2} (mod 2), & if n ≡ 1 (mod 2) and \\ & δ(n) = 0; \\ (β − 1)τ(\frac{n}{2^{β}}) + \frac{τ( \frac{n}{2^{β}} )−1}{2} + \frac{τ( \frac{n}{2} )−δ( \frac{n}{2} )}{2} (mod 2) & if n ≡ 0 (mod 2) and \\ & δ(\frac{n}{2^{β}}) = 1; \\ (β − 1)τ(\frac{n}{2^{β}}) + \frac{τ( \frac{n}{2^{β}} )}{2} + \frac{τ( \frac{n}{2} )}{2} (mod 2) & if n ≡ 0 (mod 2) and \\ & δ(\frac{n}{2^{β}}) = 0. \end{cases}

As we see, the proof for the case n ≡1 (mod 2) is finished. To finish the proof of the counterpart, we verify that the last two cases in the above congruence is equivalent to the congruence mentioned in the statement of the result. To that end, the following easily verifiable fact is required: using the multiplicative property of τ function, one can get that τ(\frac{n}{2^{β}}) + τ(\frac{n}{2}) = τ(\frac{n}{2^{β}}) + τ(\frac{n}{2^{β}})β = τ(\frac{n}{2^{β}})(β + 1) when n ≡ 0 (mod 2).

1. Let n ≡ 0 (mod 2). If δ(n) = 0 and δ(\frac{n}{2^{β}}) = 1, then we have τ(\frac{n}{2^{β}}) ≡ 1 (mod 2) and β − 1 ≡0 (mod 2). This gives

t(n, 2) ≡ \frac{τ(\frac{n}{2^{β}}) − 1}{2} + \frac{τ(\frac{n}{2}) − 1}{2}

≡ \frac{τ(\frac{n}{2^{β}})(β + 1)}{2} − 1

≡ \frac{β + 1}{2} − 1

≡ \frac{β − 1}{2}

≡ \frac{τ(\frac{n}{2^{β}})(β − 1)}{2} (mod 2).

2. Let n ≡ 0 (mod 2). If δ(n) = δ(\frac{n}{2^{β}}) = 0, then we have

t(n, 2) ≡ \frac{τ(\frac{n}{2^{β}})}{2} + \frac{τ(\frac{n}{2})}{2} ≡ \frac{(β + 1)τ(\frac{n}{2^{β}})}{2} ≡ \frac{(β − 1)τ(\frac{n}{2^{β}})}{2} (mod 2).

Equivalence of the last two congruences follows from the fact that the parity of β + 1 and β − 1 are identical.

3. Let n ≡ 0 (mod 2). If δ(n) = 1, then

t(n, 2) ≡ (β − 1)τ(\frac{n}{2^{β}}) + \frac{τ(\frac{n}{2^{β}}) − 1}{2} + \frac{τ(\frac{n}{2})}{2} ≡ 1 + \frac{τ(\frac{n}{2^{β}})(β + 1) − 1}{2} (mod 2). (9)

Since τ(\frac{n}{2^{β}}) ≡ 1 (mod 2), we have \frac{τ( \frac{n}{2^{β}} )(β+1)−1}{2} + 1 ≡ \frac{β+2}{2} (mod 2); on the other hand,

we have \frac{(β−1)τ( \frac{n}{2^{β}} )−1}{2} ≡ \frac{β−2}{2} ≡ \frac{β−2}{2} + 2 ≡ \frac{β+2}{2} (mod 2). Thus, the congruence (9) is

equivalent to the congruence: t(n, 2) ≡ \frac{(β−1)τ( \frac{n}{2^{β}} )−1}{2} (mod 2) as expected.

The proof is now completed.

3.2 A proof using conjugate mapping

Definition 11. Let λ = (a_{1}^{f_{1}}a_{2}^{f_{2}}) ∈ P_{2}^{n}. The conjugate of λ, denoted C(λ), is the partition ((f_{1} + f_{2})^{a_{2}}f_{1}^{a_{1}−a_{2}}).

Proof. Define the conjugate mapping C : P_{2}^{n} → P_{2}^{n}. Since C is an involutory self mapping, arguments similar to that of in the previous proof gives the congruence t(n, 2) ≡ SC_{2}(n) (mod 2) , where SC_{2}(n) denotes the number of self conjugate partitions in P_{2}^{n}.

Now we derive a formula for SC_{2}(n) in terms of the τ function. Define

D_{n} = \{d ∈ ℕ : d|n, d < \sqrt{n} and \frac{n}{d} − d ≡ 0 (mod 2)\} .

We contend that SC_{2}(n) = |D_{n}|. Let λ = (a_{1}^{f_{1}}a_{2}^{f_{2}}) ∈ P_{2}^{n} be a self conjugate partition. Then from the definition of self conjugate partition, we have a_{1} = f_{1} + f_{2} and a_{2} = f_{1}. Consequently, we can write n = f_{1}^{2} + 2f_{1}f_{2}. This leads to the equality \frac{n}{f_{1}} − f_{1} = 2f_{2}. Thus, f_{1} is a divisor of n which is less than \sqrt{n} and \frac{n}{f_{1}} − f_{1} ≡ 0 (mod 2). On the other hand, let d ∈ D_{n}. Since d < \sqrt{n} , we can write \frac{n}{d} − d = 2k for some k ≥ 1. From this we can construct the partition ((d + k)^{d}d^{k}) which is a self conjugate partition of n with two sizes. Accordingly, corresponding to each self conjugate partition in P_{2}^{n}, we can find an element in D_{n}; and to each element in D_{n} we can find a self conjugate partition in P_{2}^{n}. Thus, the claim follows. Now we find an expression for |D_{n}|.

Case (i): Assume that n ≡ 1 (mod 2). Then apparently \frac{n}{d} − d ≡ 0 (mod 2) for every d|n. Thus, in this case, D_{n} is the set of divisors of n that are less than \sqrt{n}. Let D′_{n} be the set of divisors of n that are greater than \sqrt{n}. Define the mapping ϕ : D_{n} → D′_{n} by ϕ(d) = \frac{n}{d} for every d ∈ D_{n}. Clearly, ϕ is a non-fixed bijection and D_{n} ∩ D′_{n} = ∅. Thus,

|D_{n}| = \begin{cases}\frac{τ(n)}{2}, & if n is a non-square; \\ \frac{τ(n)−1}{2}, & if n is a square. \end{cases}

Case (ii): Assume that n ≡ 0 (mod 2). Let β be the highest power of 2 that divides n. For every odd divisor d of n, we have \frac{n}{d} − d ≡ 1 (mod 2) and for every even divisor d of n such that 2^{β}|d, we again have \frac{n}{d} − d ≡ 1 (mod 2). So, the divisors of these types does not contribute to the set D_{n}. Consider every even divisor d of n such that d < \sqrt{n} and 2^{β} does not divides d; then, for such d, we have \frac{n}{d} − d ≡ 0 (mod 2). Thus, D_{n} is the set of all even divisors of n that are less than \sqrt{n} and not a multiple of 2^{β}. Let D′′_{n} be the set of all even divisors of n that are greater than \sqrt{n} and not a multiple of 2^{β}. Now we define ψ : D_{n} → D′′_{n} by ψ(d) = \frac{n}{d} for every d ∈ D_{n}. Clearly, ψ is a bijective mapping and D_{n} ∩ D′′_{n} = ∅. Thus,

|D_{n}| = \begin{cases}\frac{(β−1)τ( \frac{n}{2^{β}} )−1}{2}, & if n is a square ; \\ \frac{(β−1)τ( \frac{n}{2^{β}} )}{2}, & if n is not a square. \end{cases}

The second proof is now completed.

References

[1] G. E. Andrews, Stacked lattice boxes, Ann. Comb. 3 (1999), 115–130.

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

[3] A. David Christopher and M. Davamani Christober, Relatively prime uniform partitions, Gen. Math. Notes. 13 (2012), 1–12.

[4] A. David Christopher and M. Davamani Christober, Estimates of five restricted partition functions that are quasi polynomials, Bull. Math. Sci. 5 (2015), 1–11.

[5] A. David Christopher and M. Davamani Christober, On asymptotic formula of the partition function p_{A}(n), INTEGERS 15 (2015), Article #A2.

[6] C. G. J. Jacobi, Fundamenta Nova Theoriae Functionum Ellipticarum, Königsberg, 1829. Also in Gesammelte Werke, Band I, pp. 49–239.

[7] P. A. MacMahon, Divisors of numbers and their continuations in the theory of partitions, Proc. London Math. Soc., 19 (1919), 75–113. Also in Collected Papers, Vol. 2, pp. 303– 341.

[8] Nesrine Benyahia Tani and Sadek Bouroubi, Enumeration of the partitions of an integer into parts of a specified number of different sizes and especially two sizes, J. Integer Seq. 14 (2011), Article 11.3.6.

[9] N. J. A. Sloane, Online Encyclopedia of Integer Sequences, http://oeis.org.

2010 Mathematics Subject Classification: Primary 05A17; Secondary 11P81. Keywords: partition, size of a partition, parity, asymptotic estimate.

(Concerned with sequences \underline{A000005}, \underline{A000203}, \underline{A002133}, \underline{A004526}, \underline{A010052}, \underline{A117955}, and \underline{A117956}.)

Received March 27 2015; revised versions received August 29 2015; October 5 2015; December 7 2015. Published in Journal of Integer Sequences, December 9 2015.

Return to Journal of Integer Sequences home page.