New Identities for the Polarized Partitions and Partitions with d-Distant Parts

Ivica Martinjak and Dragutin Svrtan Faculty of Science University of Zagreb Bijenička cesta 30 HR-10000 Zagreb Croatia

                       imartinjak@phy.hr
                        dsvrtan@math.hr

Abstract In this paper we present a new class of integer partition identities. The number of partitions with d-distant parts can be written as a sum of the numbers of partitions of various lengths with 1-distant parts whose even parts, if there are any, are greater than twice the number of odd parts. We also provide a direct bijection between these classes of partitions.

1 Preliminaries and introduction

A partition is the sequence λ=(λ_{1}, λ_{2}, …, λ_{l}), where λ_{i} is a natural number ∀i, assuming λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{l}. When ∑_{i=1}^{l} λ_{i}=|λ|=n we say that λ is a partition of n, and denote it by λ ⊢ n. The numbers λ_{i} are parts of a partition, and the number of parts l(λ)=l is the length of a partition. We let P_{n} denote the set of all partitions of n, with p(n) := |P_{n}|. The number of partitions λ ⊢ n with exactly k summands is denoted by p_{k}(n). We let p(n, r) denote the number of partitions λ ⊢ n with the smallest part ≥ r.

Now we define certain families of partitions. The set D_{n} consists of partitions λ ⊢ n with distant parts. We say that such a partition has 1-distant parts and we let p^{(1)}(n)(= |D_{n}|) denote the number of such partitions λ ⊢ n. Similarly we set

D_{n}^{d} := {(λ_{1}, λ_{2}, …, λ_{l}) : λ_{i} − λ_{i+1} ≥ d}, and
p^{(d)}(n) := |D_{d}|.

We say that elements of D_{n}^{2} have 2-distant parts while elements of D_{n}^{3} have 3-distant parts.

Let l_{i,q}(λ) denote the number of parts of a partition λ congruent to i (mod q). In particular, l_{o}(λ) = l_{1,2}(λ) is the number of odd parts of a partition.

Definition 1. Let e(λ) be the smallest even part of a partition λ ⊢ n or, in case of a partition with all parts odd, we set e(λ) := l_{o}(λ) + 2. Partitions with distant parts and obeying the property e(λ) > 2l_{o}(λ) we call polarized partitions.

We let p̂^{(1)}(n) denote the number of polarized partitions λ ⊢ n,

p̂^{(1)}(n) := |{λ ∈ D_{n} : e(λ) > 2l_{o}(λ)}|.

It is known that the number of partitions of λ ⊢ n with d-distant parts equals the number of partitions μ ⊢ n with 1-distant parts fulfilling the following constraint: the smallest part that is congruent to i (mod d) is greater than

d ∑_{j=1}^{i−1} l_{j,d}(μ),

1 ≤ i ≤ d [5]. Namely, given a partition with d-distant parts, subtract q from the second smallest part, than 2q, 3q, … from the subsequent smallest parts. During this operation, the parts of resulting partition keep the same congruence condition with respect to q whereas the weight of the partition is decreased and the d-difference is lost. The opposite can be done in a unique way. On the other hand, the similar procedure leads to the same resulting partition starting with a partition with 1-distant parts satisfying the condition above. These two facts prove the identity above.

Note that for d=2 the previous sum is reduced to only one term, resulting with 2l_{o}(μ). In this case the number of partitions with 2-distant parts equals the number of partitions with 1-distant parts and with every even part, if there are any, greater than twice the number of odd parts. This polarization, expressed by the next theorem, is of additional interest since it interprets the left hand side of the first Rogers-Ramanujan identity [3, 4, 6].

Figure 1: The map (12,10,7,4,1) ↦ (12,10,6,5,1). Resulting partition consists of 1-distant parts, having 3 even and two odd parts.

The proof is illustrated by the Young diagrams in Figure 1. Arrange the diagram in a way the left margin has two dots extra indentation per row. Draw the line of justification (of the original diagram) in such a way that in the last row one point remains on the left side of the line. Now rearrange the rows on the right side of the normal line: firstly put odd parts in descending order and then even parts in decreasing order too. As a result we have a new partition starting with even parts. Every row has size at least 2k–1, where k is counted from the bottom of the diagram. This means, if diagram possessed k odd parts then the smallest even part is at least (2k-1)+2+1.

In order to prove that this correspondence is invertible, we start with adjusted left margin as in the previous consideration. Now we have to explain that all rows intersect the normal line. The condition e(μ) > 2l_{o}(μ) ensures that the smallest even part intersects the line. Having in mind that even parts are mutually different by 2 or more, all other even parts intersect the justification line. In the following theorem we show this proof more explicitly.

Theorem 2. The number of partitions λ ⊢ n with 2-distant parts is equal to the number of polarized partitions μ ⊢ n,

p^{(2)}(n) = p̂^{(1)}(n).  (1)

Proof. Suppose that λ has j odd parts, at indexes b_{1} < b_{2} < ⋯ < b_{j}, where λ_{b_{1}} ≤ ⋯ ≤ λ_{b_{j}}, and thus k − j even parts, at indexes c_{1} < c_{2} ⋯ < c_{k−j}, where λ_{c_{1}} ≤ ⋯ ≤ λ_{c_{k−j}}.

Then the decreasing rearrangement of

λ_{b_{1}} − 2b_{1} + 2, λ_{b_{2}} − 2b_{2} + 4, …, λ_{b_{j}} − 2b_{j} + 2j, λ_{c_{1}} − 2c_{1} + 2j + 2, …, λ_{c_{k−j}} − 2c_{k−j} + 2k

is a partition with distant parts, again with j odd and k − j even parts. The new partition has distant parts. Namely,

(λ_{b_{i+1}} − 2b_{i+1} + 2(i + 1)) − (λ_{b_{i}} − 2b_{i} + 2i) = (λ_{b_{i+1}} − λ_{b_{i}}) − 2(b_{i+1} − b_{i}) + 2
≥ 2,

as λ_{b_{i+1}} ≥ λ_{b_{i}} + 2(b_{i+1} − b_{i}) since the original partition had 2-distant parts, 1 ≤ i < j. The same reasoning holds true for even parts.

The smallest even part of the original partition λ_{c_{1}} is greater than or equal to 2c_{1}, twice its index. Therefore the smallest even part of the new partition, λ_{c_{1}} − 2c_{1} + 2j + 2, is strictly greater than 2j, twice the number of odd parts in the new partition.

For the purpose to take an insight into the nature of partitions λ ⊢ n with d-distant parts, note that they are in one to one correspondence with the partitions μ such that

(i) μ ∈ S_{n}^{d}, S_{n}^{d} := {μ : μ ∈ P_{n}, μ_{min} ≥ 1 + (l(μ) − 1)q/2} when d is even,

(ii) μ ∈ S_{n}^{d} ∩ D_{n} when d is odd; q = d − [d = odd].

Namely, for d even we have

1 + (1 + d) + ⋯ + (1 + (l − 1)d) = l + d\binom{l}{2}
= l (1 + \frac{(l − 1)d}{2}) ,

and analogously when d is odd. Let p^{sd}(n) := |S_{n}^{d}|.

In particular, we have

p^{(2)}(n) = p^{s2}(n)  (2)
p^{(3)}(n) = p^{(1)s2}(n)  (3)

meaning that partitions with 2-distant parts are equinumerous to the partitions having exactly one Durfee square. On the other hand, partitions with 3-distant parts are equinumerous to the partitions having exactly one Durfee square but with distant parts. These facts allow to represent p^{(d)}(n) as the sum either of regular partitions (when d is even) or partitions with 1-distant parts (d odd). For d = 2 and 3 it follows immediately:

p^{(2)}(n) = ∑_{i^{2}≤n} ∑_{j≤i} p_{j}(n − i^{2})  (4)
p^{(3)}(n) = ∑_{i^{2}<n} ∑_{j=i−1,i} p_{j}^{(1)}(n − i^{2}).  (5)

2 The maximal length of a d-distant partition

We let l(n, d) denote the length l(λ) of the longest partition λ ∈ D_{n}^{d}. Obviously, for the partitions having 2-distant parts the minimal number n = |λ|, λ ∈ D_{n}^{2}, l(n, 2)=2 is 4 since 1 + 3 = 4. The minimal n with length 3 is 9 since 1 + 3 + 5 = 9 etc. Thus, for every square number m, the maximal length increases by 1 in respect to the previous square number,

l(m, 2) = l((\sqrt{m} − 1)^{2}, 2) + 1.

Consequently, the next relation follows:

l(n, 2) = ⌊\sqrt{n}⌋.  (6)

This rule is generalized in the next lemma.

Lemma 3. Let λ ∈ D_{n}^{d}. Then the maximal length l(n, d) of λ ⊢ n is as follows:

l(n, d) = ⌊\frac{d − 2 + \sqrt{(d − 2)^{2} + 8dn}}{2d}⌋.  (7)

Proof. Let n be the smallest number with property l(n, d) = l(n − 1, d) + 1. Then, the value of the d-distant partition λ, n ≤ |λ| < n+q, q being non-negative integer, corresponds to the largest integer smaller than or equal to the sum of m numbers 1, (1 + d), (1 + 2d), …, (dm − (d − 1)). This sum equals \frac{m(dm−d+2)}{2}, which leads to the quadratic equation

dm^{2} − (d − 2)m − 2n = 0.

Since l(n, d) = ⌊m⌋ the statement of lemma follows immediately.

3 The main result

The result of Bressoud, mentioned above, of which Theorem 2 is a special case, gives identities between partitions with d-distant parts and partitions with 1-distant parts having parts separated by certain congruence condition. In particular, when d=2 this condition is reduced to ≡ 0, 1 (mod 2), separating a partition into even and odd parts. Here we extend these ideas of the polarization of partition. More precisely, we show that there is one to one correspondence between partitions with d-distant parts, where d > 2, and partitions with 1-distant parts having even parts, if there are any, greater than twice the number of odd parts.

Theorem 4. The number of partitions λ ⊢ n with 3-distant parts is equal to the sum of numbers of polarized partitions of various lengths μ_{i} ⊢ n − \binom{i}{2}, l(μ_{i}) = i, i = 1, …, l(n, 3),

p^{(3)}(n) = ∑_{i≥1} p̂_{i}^{(1)} (n − \binom{i}{2}) .  (8)

Proof. We arrange the starting partition λ ⊢ n in the same manner as in the proof of Theorem 2, thus obtaining rows on the left side of the line of justification are shifted by two. Since the partition λ consists of 3-distant parts this means that rows on the right side of vertical line are spaced at least by 1, as Figure 2 presents. In case the last row possesses two or more spaces, we have Sylvester triangle with side l(λ) on the right side (see Corollary 5 and Figure 3). However, this is not the general case but the triangle with side l(λ)–1.

Extracting the triangular partition

ν_{i} ⊢ \frac{i(i − 1)}{2}, i = l(λ)

form λ, we obtain partition μ_{i} ∈ D_{|λ|−\binom{i}{2}}. Furthermore, the proof is completed by the same reasoning as in Theorem 2.

Figure 2: The partition λ = (13, 9, 5, 2) after extracting the Sylvester’s triangle and rearranging rows is mapped to μ = (10, 6, 4, 3), |μ| = 29 − 6 = 23.

Thus, the number of partitions λ ⊢ n with 3-distant parts equals the sum of partitions μ_{i} ⊢ m_{i} with 1-distant parts and with the smallest even part greater than 2l_{o}(μ_{i}) (if partition has any even part); m_{i} = |μ_{i}| = n − i(i − 1)/2, l(μ_{i}) = i for every i = 1, 2, …, l(n, 3), i.e., terms in the sum represent the partition μ_{i} that arises by subtracting the Sylvester’s triangle \frac{i(i−1)}{2} from the λ.

As an example, we calculate the number of partitions with 3-distant parts for n=15. First, note that the partition λ = (n) gets mapped into itself, which means that the first term in the sum in Theorem 4 is always 1. So, according to Theorem 4, for this particular case we have

p^{(3)}(15) = 1 + p̂_{2}^{(1)}(14) + p̂_{3}^{(1)}(12)
= 1 + 6 + 3
= 10.

Figure 3: When the smallest part of a partition with 3-distant parts is equal to or greater than 2 the side of a Sylvester triangle equals the length of the starting partition.

The all 6 partitions of 14 of length 2 has even parts greater than the number of odd parts, whereas 3 out of 7 partitions of 12 having length 3 are in line with the condition.

Corollary 5. The number of partitions λ ⊢ n with 3-distant parts and with the smallest part at least 2 is equal to the sum of numbers of polarized partitions of various lengths μ_{i} ⊢ n − \frac{i(i+1)}{2}, l(μ_{i}) = i, i = 1, 2, …

p^{(3)}(n, 2) = ∑_{i≥1} p̂_{i}^{(1)} (n − \frac{i(i + 1)}{2}) .  (9)

An argument analogous to the proof of Theorem 4 proves identities for partitions with d-distant parts. Therefore, when d = 4 we have

p^{(4)}(n) = ∑_{i≥1} p̂_{i}^{(1)}(n + i − i^{2})  (10)

with the corollary

p^{(4)}(n, 2) = ∑_{i≥1} p̂_{i}^{(1)}(n − i^{2}).  (11)

As the Figure 4 illustrates, for the extracted partition we have

1 + 2 + 3 + ⋯ + (l − 1) = \binom{l}{2}
(d − 2) + (2d − 4) + (3d − 6) + ⋯ + (l − 1)(d − 2) = (d − 2)\binom{l}{2}

for d = 3 and for general case, respectively, where l is the length of a starting partition. So, for any d we keep 2-distant parts on the left side of the justification line, which means that these parts are odd. After applying

(i) subtracting partition ν_{i} ⊢ (d − 2)\binom{i}{2}, i = 1, …, l(n, d); and

(ii) sorting parts on the right side of the justification line,

we get a partition polarized into even and odd parts. This proves the next theorem.

Theorem 6. Partitions λ ⊢ n with d-distant parts are equinumerous to polarized partitions μ_{i} ⊢ n − (d − 2)\binom{i}{2}, l(μ_{i}) = i, i = 1, …, l(n, d),

p^{(d)}(n) = ∑_{i≥1} p̂_{i}^{(1)}(n − (d − 2)\binom{i}{2}).  (12)

Figure 4: Extracted partitions for d = 3, 4, 5, respectively.

Imagine a partition with 3-distant parts and a partition with 3-distant parts where the minimal part is at least 2. According to Theorem 4 and Corollary 5 there is one to one correspondence between these partitions and a certain polarized partitions. Note that if the starting partitions are of the same length l then the difference between extracted parts is exactly l. Obviously, the difference l between extracted parts is always the case when starting partitions have characteristics mentioned above. Thus, the generalization of the previous corollaries is as follows:

p^{(d)}(n, 2) = ∑_{i≥1} p̂_{i}^{(1)} (n − i − (d − 2)\binom{i}{2}) .  (13)

A similar identity holds for the general case, i.e., when there is any constraint on the minimal part of a partition. Let the starting partition λ, l(λ) = l in our bijection has minimal part equal to r. Then the parts on the right side of the justification line that we subtract from the starting partition are

r − 1, r − 1 + (d − 2), r − 1 + 2(d − 2), …, r − 1 + (l − 1)(d − 2).

In other words, we subtract r − 1 rows of the height l more than in the case we consider in the previous theorem, i.e., the subtracted part is

(r − 1)l + (d − 2)\binom{l}{2}.

This reasoning leads to the next corollary.

Corollary 7. Partitions λ ⊢ n with d-distant parts and with the smallest part at least r are equinumerous to polarized partitions μ_{i} ⊢ n − (r − 1)i − \frac{i(i+1)}{2}, i = 1, 2, …

p^{(d)}(n, r) = ∑_{i≥1} p̂_{i}^{(1)}(n − (r − 1)i − (d − 2)\binom{i}{2}).  (14)

Results demonstrated in this paper show that the number p^{(d)}(n, r), d ≥ 2, r ≥ 1, n ≥ 0 can be represented as the sum of numbers of polarized partitions of a certain natural number, with k 1-distant parts. In other words, there is one to one correspondence between polarized partitions and partitions with d-distant parts possibly having a constraint on the minimal part.

4 Acknowledgment

The authors thank the anonymous referee for valuable suggestions that improved the final version of the paper.

References

[1] M. Aigner, A Course in Enumeration, Springer, 2007.

[2] G. E. Andrews, The Theory of Partitions, Cambridge University Press, 1998.

[3] G. E. Andrews and K. Eriksson, Integer Partitions, Cambridge University Press, 2004.

[4] C. Boulet and I. Pak, Combinatorial proof of the Rogers-Ramanujan and Schur identities, J. Combin. Theory Ser. A 113 (2006), 1019–1030.

[5] D. M. Bressoud, A new family of partition identities, Pacific J. Math. 77 (1978), 71–74.

[6] P. A. MacMahon, Combinatory Analysis, Vol. 2, Cambridge University Press, 1916. Reprint, Chelsea, 1960.

[7] I. Pak, Partition bijections, a survey, Ramanujan J. 12 (2006), 5–75.

2010 Mathematics Subject Classification: Primary 11P84; Secondary 05A17. Keywords: integer partition, partition identity, direct bijection, Durfee square, Rogers-Ramanujan identity.

(Concerned with sequence \underline{A003106}, \underline{A003114}, and \underline{A025157}.)

Received March 14 2014; revised versions received September 1 2014; October 24 2014. Published in Journal of Integer Sequences, November 7 2014.

Return to Journal of Integer Sequences home page.