CONGRUENCES MODULO POWERS OF 2 FOR THE NUMBER OF UNIQUE PATH PARTITIONS

C. KRATTENTHALER

Fakultät für Mathematik der Universität Wien, Oskar-Morgenstern-Platz 1, A-1090 Vienna, Austria.

                     WWW: http://www.mat.univie.ac.at/~kratt

Dedicated to Krishnaswami Alladi on the occasion of his 60th birthday

Abstract. We compute the congruence class modulo 16 of the number of unique path partitions of n (as defined by Olsson), thus generalising previous results by Bessenrodt, Olsson and Sellers [Ann. Combin. 13 (2013), 591–602].

1. Introduction

Unique path partitions were introduced by Olsson in [3]. Their study is motivated from the Murnaghan–Nakayama rule for the calculation of the value of characters of the symmetric group. They were completely characterised by Bessenrodt, Olsson and Sellers in [1]. They used this characterisation to derive a formula for the generating function for the number u(n) of all unique path partitions of n. This formula reads (cf. [1, Remark 3.6])

∑_{n≥1} u(n)q^{n} = 2 ∑_{i≥1} q^{2^{i}−1}(1 + q^{2^{i−1}}) ∏_{j=0}^{i−2} \frac{1}{1 − q^{2^{j}}}

= 2 (q(1 + q) + ∑_{i≥2} \frac{q^{−1} + 1}{1 − q^{2}} · \frac{q^{2^{i}}(1 + q^{2^{i−1}})}{∏_{j=1}^{i−2}(1 − q^{2^{j}})}) .  (1.1)

The final part in [1] concerns congruences modulo 8 for u(n). The corresponding main result [1, Theorem 4.6] provides a complete description of the behaviour of u(n) modulo 8 (in terms of the related sequence of numbers w(n); see the next section for the definition of w(n)). The arguments to arrive at this result are mainly of a recursive nature.

The purpose of this note is to show that a more convenient and more powerful method to derive congruences (modulo powers of 2) is by an analysis of the generating function (1.1). Not only are we able to recover the result from [1], but in addition we succeed in determining the congruence class of u(n) modulo 16, see (2.1) and Theorem 7, thus solving the problem left open in the last paragraph of [1]. We point out that the approach presented here is very much inspired by calculations in [2, Appendix], where expressions similar to the one on the right-hand side of (1.1) appear, with the role of the prime number 2 replaced by 3, though.

2010 Mathematics Subject Classification. Primary 05A15; Secondary 05A17 11A07 11P83.

Key words and phrases. Unique path partitions, congruences, q-series.

†Research partially supported by the Austrian Science Foundation FWF, grants Z130-N13 and S50-N15, the latter in the framework of the Special Research Program “Algorithmic and Enumerative Combinatorics”.

2. An equivalent expression for the generating function

We start with the observation (already made in [1]) that, first, all numbers u(n) are divisible by 2, and, second, we have u(2n) = u(2n − 1) for all n. This is easy to see from the right-hand side of (1.1) since it has the form 2(1 + q)f(q^{2}), where f(t) is a formal power series in t. We therefore divide the right-hand side of (1.1) by 2(1 + q^{−1}), subsequently replace q by q^{1/2}, and consider the “reduced” generating function

∑_{n≥2} w(n)q^{n} = ∑_{i≥2} q^{2^{i−1}}(1 + q^{2^{i−2}})\frac{1}{(1 − q) ∏_{j=0}^{i−3}(1 − q^{2^{j}})}.

In other words, we have

2w(n) = u(2n) = u(2n − 1)  (2.1)

for all n.

Using the convention

∑_{k=M}^{N−1} Expr(k) = \begin{cases}∑_{k=M}^{N−1} Expr(k), & N > M, \\ 0, & N = M, \\ − ∑_{k=N}^{M−1} Expr(k), & N < M. \end{cases}  (2.2)

for sums, we rewrite the above equation in the following way:

∑_{n≥2} w(n)q^{n} = ∑_{i≥2} q^{2^{i−1}} \frac{1 + q^{2^{i−2}}}{(1 − 2q + q^{2}) ∏_{j=1}^{i−3}(1 − q^{2^{j}})}

= ∑_{i≥2} q^{2^{i−1}} \frac{1 + q^{2^{i−2}}}{(1 − \frac{2q}{1+q^{2}} )(1 + q^{2}) ∏_{j=1}^{i−3}(1 − q^{2^{j}})}

= ∑_{i≥2} q^{2^{i−1}} \frac{1 + q^{2^{i−2}}}{(1 − \frac{2q}{1+q^{2}} )(1 − q^{4}) ∏_{j=2}^{i−3}(1 − q^{2^{j}})}

= ∑_{i≥2} q^{2^{i−1}} \frac{1 + q^{2^{i−2}}}{(1 − \frac{2q}{1+q^{2}} )(1 − q^{4})^{2} ∏_{j=3}^{i−3}(1 − q^{2^{j}})}

. . . . . . . . . . . . . . . . . . .

= ∑_{i≥1} q^{2^{2i−1}} \frac{1 + q^{2^{2i−2}}}{(1 − \frac{2q}{1+q^{2}} )(1 − \frac{2q^{4}}{1+q^{8}} ) ⋯ (1 − \frac{2q^{2^{2i−4}}}{1+q^{2^{2i−3}}} )(1 − q^{2^{2i−2}})}

+ ∑_{i≥1} q^{2^{2i}} \frac{1}{(1 − \frac{2q}{1+q^{2}} )(1 − \frac{2q^{4}}{1+q^{8}} ) ⋯ (1 − \frac{2q^{2^{2i−2}}}{1+q^{2^{2i−1}}} )}

= ∑_{i≥1} q^{2^{2i−1}} \frac{1 + \frac{2q^{2^{2i−2}}}{1−q^{2^{2i−2}}}}{∏_{j=0}^{i−2}(1 − \frac{2q^{2^{2j}}}{1+q^{2^{2j+1}}} )} + ∑_{i≥1} q^{2^{2i}} \frac{1}{∏_{j=0}^{i−1}(1 − \frac{2q^{2^{2j}}}{1+q^{2^{2j+1}}} )}.  (2.3)

From the last expression it is immediately obvious that w(n) is odd if and only if n is a power of 2, thus recovering the first assertion of [1, Cor. 4.3]. The above mentioned mod-4 result [1, Theorem 4.6] for w(n) — which, by (2.1), translates into a mod-8 result for u(n) — can also be derived within a few lines from the above expression.

In the next section, we show how to obtain congruences modulo 8 for w(n), which, by (2.1), translate into congruences modulo 16 for the unique path partition numbers u(n).

3. Congruences modulo powers of 2

In what follows, we write

f(q) = g(q) modulo 2^{γ}

to mean that the coefficients of q^{i} in f(q) and g(q) agree modulo 2^{γ} for all i. We apply geometric series expansion in (2.3), and at the same time we neglect terms which are divisible by 8. For example, we expand

\frac{1}{1 − \frac{2q}{1+q^{2}}} = 1 + \frac{2q}{1 + q^{2}} + \frac{4q^{2}}{(1 + q^{2})^{2}} modulo 8.

In this manner, we obtain the congruence

∑_{n≥2} w(n)q^{n} = ∑_{i≥1} q^{2^{2i−1}}(1 + \frac{2q^{2^{2i−2}}}{1 − q^{2^{2i−2}}} + 2 ∑_{j=0}^{i−2} \frac{q^{2^{2j}}}{1 + q^{2^{2j+1}}}

+ 4\frac{q^{2^{2i−2}}}{1 − q^{2^{2i−2}}} ∑_{j=0}^{i−2} \frac{q^{2^{2j}}}{1 + q^{2^{2j+1}}} + 4 ∑_{0≤s≤t≤i−2} \frac{q^{2^{2s}+2^{2t}}}{(1 + q^{2^{2s+1}})(1 + q^{2^{2t+1}})})

+ ∑_{i≥1} q^{2^{2i}}(1 + 2 ∑_{j=0}^{i−1} \frac{q^{2^{2j}}}{1 + q^{2^{2j+1}}} + 4 ∑_{0≤s≤t≤i−1} \frac{q^{2^{2s}+2^{2t}}}{(1 + q^{2^{2s+1}})(1 + q^{2^{2t+1}})})

modulo 8.

After rearrangement, this becomes

∑_{n≥2} w(n)q^{n} = ∑_{i≥1} q^{2^{i}} + \frac{2q^{3}}{1 − q} + 2 ∑_{j≥1} \frac{1}{1 − q^{2^{2j}}} (q^{2^{2j}+2^{2j+1}} + q^{2^{2j−2}}(1 − q^{2^{2j−1}}) ∑_{ℓ≥2j} q^{2^{ℓ}})

+ 4 ∑_{1≤s<t} \frac{q^{2^{2s−2}+2^{2t−2}}}{(1 − q^{2^{2s−1}})(1 − q^{2^{2t−1}})}(q^{2^{2t−1}}(1 + q^{2^{2t−2}}) + ∑_{ℓ≥2t} q^{2^{ℓ}})

+ 4 ∑_{s≥1} \frac{q^{2^{2s−1}}}{(1 − q^{2^{2s}})} ∑_{ℓ≥2s} q^{2^{ℓ}}  modulo 8.  (3.1)

We must now analyse the individual sums in (3.1).

Lemma 1. Let n ≥ 2, and write n = ∑_{i=a}^{e} n_{i} · 2^{i}, with 0 ≤ n_{i} ≤ 1 for all i and n_{a} ≠ 0 ≠ n_{e}. Then the coefficient of q^{n} in

∑_{j≥1} \frac{q^{2^{2j}+2^{2j+1}}}{1 − q^{2^{2j}}}  (3.2)

is equal to ⌊a/2⌋ if n is not a power of 2, and it is equal to max{⌊a/2⌋−1, 0} otherwise.

Proof. By geometric series expansion, we see that the coefficient of q^{n} in (3.2) is equal to the number of possibilities to write n = (k + 3)2^{2j} for some j ≥ 1 and k ≥ 0. For fixed j, we can find a suitable k if and only if n ≥ 3 · 2^{2j}. If n is not a power of 2, this is equivalent to the condition that 2j ≤ a. The claim follows immediately. □

Lemma 2. Let n ≥ 2, and write n = ∑_{i=a}^{e} n_{i} · 2^{i} as in Lemma 1. Then the coefficient of q^{n} in

∑_{j≥1} \frac{q^{2^{2j−2}}}{1 − q^{2^{2j}}} ∑_{ℓ≥2j} q^{2^{ℓ}}  (3.3)

is equal to e − 2j + 1 if a = 2j − 2, n_{a+1} = n_{2j−1} = 0, and n is not a power of 2, and it is equal to 0 otherwise.

Proof. By geometric series expansion, we see that the coefficient of q^{n} in (3.3) is equal to the number of possibilities to write n = 2^{2j−2} + k · 2^{2j} + 2^{ℓ} for some j ≥ 1, ℓ ≥ 2j, and k ≥ 0. The claim follows immediately. □

Lemma 3. Let n ≥ 2, and write n = ∑_{i=a}^{e} n_{i} · 2^{i} as in Lemma 1. Then the coefficient of q^{n} in

∑_{j≥1} \frac{q^{2^{2j−2}+2^{2j−1}}}{1 − q^{2^{2j}}} ∑_{ℓ≥2j} q^{2^{ℓ}}  (3.4)

is equal to e − 2j + 1 if a = 2j − 2, n_{a+1} = n_{2j−1} = 1, and it is equal to 0 otherwise.

Proof. By geometric series expansion, we see that the coefficient of q^{n} in (3.4) is equal to the number of possibilities to write n = 2^{2j−2} + 2^{2j−1} + k · 2^{2j} + 2^{ℓ} for some j ≥ 1, ℓ ≥ 2j, and k ≥ 0. The claim follows immediately. □

Lemma 4. Let n ≥ 2, and write n = ∑_{i=a}^{e} n_{i} · 2^{i} as in Lemma 1. Then the coefficient of q^{n} in

∑_{s≥1} \frac{q^{2^{2s−1}}}{1 − q^{2^{2s}}} ∑_{ℓ≥2s} q^{2^{ℓ}}  (3.5)

is equal to e − 2s + 1 if a = 2s − 1 and n is not a power of 2, and it is equal to 0 otherwise.

Proof. By geometric series expansion, we see that the coefficient of q^{n} in (3.5) is equal to the number of possibilities to write n = 2^{2s−1} + k · 2^{2s} + 2^{ℓ} for some s ≥ 1, ℓ ≥ 2s, and k ≥ 0. The claim follows immediately. □

Lemma 5. Let n ≥ 2, and write n = ∑_{i=a}^{e} n_{i} · 2^{i} as in Lemma 1. Then the coefficient of q^{n} in

∑_{1≤s<t} \frac{q^{2^{2s−2}+2^{2t−2}}}{(1 − q^{2^{2s−1}})(1 − q^{2^{2t−1}})} ∑_{ℓ≥2t−1} q^{2^{ℓ}}  (3.6)

is congruent to

e ∑_{i=a+2}^{e−χ(e even)} n_{i} − a · n_{a+2} + ⌊\frac{1}{2}(e − a − 1)⌋  (mod 2),  (3.7)

where χ(S) = 1 if S is true and χ(S) = 0 otherwise.

Proof. By geometric series expansion, we see that the coefficient of q^{n} in (3.6) is equal to the number of possibilities to write

n = (2k_{1} + 1)2^{2s−2} + (2k_{2} + 1)2^{2t−2} + 2^{2t−1+k_{3}}  (3.8)

for some s and t with 1 ≤ s < t and k_{1}, k_{2}, k_{3} ≥ 0. Clearly, we need a to be even in order that the number of these possibilities be non-zero. Given that a = 2s − 2, we just have to count the number of possible triples (t, k_{2}, k_{3}) in (3.8), since the appropriate k_{1} can certainly be found. If we fix t and k_{3}, the number of possible k_{2}’s is

⌊\frac{1}{2} · \frac{n − 2^{2t−1+k_{3}}}{2^{2t−2}} + \frac{1}{2}⌋ = ⌊\frac{n}{2^{2t−1}} + \frac{1}{2}⌋ − 2^{k_{3}}.

This needs to be summed over all t and k_{3} with \frac{1}{2}(a + 2) = s < t ≤ \frac{1}{2}(e + 1) and 0 ≤ k_{3} ≤ e − 2t + 1. We obtain

∑_{t=s+1}^{⌊\frac{1}{2} (e+1)⌋} ∑_{k_{3}=0}^{e−2t+1} (⌊\frac{n}{2^{2t−1}} + \frac{1}{2}⌋ − 2^{k_{3}})

≡ ∑_{t= \frac{1}{2} (a+4)}^{⌊\frac{1}{2} (e+1)⌋} ∑_{k_{3}=0}^{e−2t+1} ⌊n_{a} · 2^{a−2t+1} + ⋯ + (n_{2t−2} + 1) · 2^{−1}

+ n_{2t−1} + n_{2t} · 2 + ⋯ + n_{e} · 2^{e−2t+1}⌋ − ⌊\frac{1}{2}(e − a − 1)⌋

≡ ∑_{t= \frac{1}{2} (a+4)}^{⌊\frac{1}{2} (e+1)⌋}(e − 2t + 2)(n_{2t−2} + n_{2t−1}) + ⌊\frac{1}{2}(e − a − 1)⌋

≡ e ∑_{t= \frac{1}{2} (a+4)}^{⌊\frac{1}{2} (e+1)⌋} n_{2t−1} + e ∑_{t= \frac{1}{2} (a+4)}^{⌊\frac{1}{2} (e−1)⌋} n_{2t} + (e − a)n_{a+2} + ⌊\frac{1}{2}(e − a − 1)⌋ (mod 2).

□

Lemma 6. Let n ≥ 2, and write n = ∑_{i=a}^{e} n_{i} · 2^{i} as in Lemma 1. Then the coefficient of q^{n} in

∑_{1≤s<t} \frac{q^{2^{2s−2}+2^{2t}}}{(1 − q^{2^{2s−1}})(1 − q^{2^{2t−1}})}  (3.9)

is congruent to

∑_{t= \frac{1}{2} (a+4)}^{⌊\frac{1}{2} (e+1)⌋} n_{2t−1} + ⌊\frac{1}{2}(e − a − 1)⌋ .  (mod 2).  (3.10)

Proof. By geometric series expansion, we see that the coefficient of q^{n} in (3.9) is equal to the number of possibilities to write

n = (2k_{1} + 1)2^{2s−2} + (k_{2} + 2)2^{2t−1}  (3.11)

for some s and t with 1 ≤ s < t and k_{1}, k_{2} ≥ 0. Clearly again, we need a to be even in order that the number of these possibilities be non-zero. Given that a = 2s − 2, we just have to count the number of possible pairs (t, k_{2}) in (3.11), since the appropriate k_{1} can certainly be found. If we fix t, the number of possible k_{2}’s is

⌊\frac{n − 2^{2t}}{2^{2t−1}} + 1⌋ = ⌊\frac{n}{2^{2t−1}} ⌋ − 1.

This needs to be summed over all t with \frac{1}{2}(a + 2) = s < t ≤ \frac{1}{2}(e + 1). We obtain

∑_{t=s+1}^{⌊\frac{1}{2} (e+1)⌋} (⌊\frac{n}{2^{2t−1}} ⌋ − 1) ≡ ∑_{t= \frac{1}{2} (a+4)}^{⌊\frac{1}{2} (e+1)⌋} ⌊n_{a} · 2^{a−2t+1} + ⋯ + n_{2t−2} · 2^{−1}

+ (n_{2t−1} − 1) + n_{2t} · 2 + ⋯ + n_{e} · 2^{e−2t+1}⌋

≡ ∑_{t= \frac{1}{2} (a+4)}^{⌊\frac{1}{2} (e+1)⌋} n_{2t−1} − ⌊\frac{1}{2}(e − a − 1)⌋  (mod 2).  □

We are finally in the position to state and prove our main result. It expresses the congruence class of w(n) modulo 8 — and thus, by (2.1), the congruence class of the unique path partition number u(n) modulo 16 — in terms of the binary digits of n. We point out that the assertion (3.12) already appeared in [1, Prop. 4.5].

Theorem 7. Let n ≥ 2, and write n = ∑_{i=a}^{e} n_{i} · 2^{i} as in Lemma 1. Then, if a = e (i.e., if n is a power of 2), the number w(n) is congruent to

2 ⌊a/2⌋ + 1 (mod 8),  (3.12)

while it is congruent to

2 + 2 ⌊a/2⌋ + 2χ(a even)(1 − 2n_{a+1})(e − a − 1) + 4χ(a odd)(e − a)

+ 4χ(a even)(e ∑_{i=a+2}^{e−χ(e even)} n_{i} + a · n_{a+2} + ∑_{t= \frac{1}{2} (a+4)}^{⌊\frac{1}{2} (e+1)⌋} n_{2t−1}) (mod 8) (3.13)

otherwise.

Proof. Let first n = 2^{a}. We must then read the coefficient of q^{n} on the right-hand side of (3.1) and reduce the result modulo 8. Non-zero contributions come from the very first sum, from the series 2q^{3}/(1 − q^{2}), and from the series which is discussed in Lemma 1. Altogether, we obtain

1 + 2χ(a ≥ 2) + 2 max{⌊a/2⌋ − 1, 0},

which can be simplified to (3.12).

Now let n be different from a power of 2. The non-zero contributions when reading the coefficient of q^{n} on the right-hand side of (3.1) come again from the series 2q^{3}/(1 − q^{2}), and from the series discussed in Lemmas 1–6. These contributions add up to

2χ(n ≥ 3) + 2 ⌊a/2⌋ + 2χ(a even, n_{a+1} = 0)(e − a − 1) + 2χ(a even, n_{a+1} = 1)(e − a − 1) + 4χ(a odd)(e − a)

+4χ(a even)(e ∑_{i=a+2}^{e−χ(e even)} n_{i}−a·n_{a+2}+⌊\frac{1}{2}(e − a − 1)⌋+ ∑_{t= \frac{1}{2} (a+4)}^{⌊\frac{1}{2} (e+1)⌋} n_{2t−1}+⌊\frac{1}{2}(e − a − 1)⌋ ).

This expression can be simplified to result in (3.13). □

It is clear that, in the same way, one could also derive a result for w(n) modulo 16, 32, …, albeit at the cost of considerably more work.

References

[1] C. Bessenrodt, J. Olsson and J. A. Sellers, Unique path partitions: characterization and congruences, Ann. Combin. 13 (2013), 591–602.

[2] C. Krattenthaler and T. W. Müller, A method for determining the mod-3^{k} behaviour of recursive sequences, preprint, 83 pages; arχiv:1308.2856.

[3] J. Olsson, Sign conjugacy classes in symmetric groups, J. Algebra 322 (2009), 2793–2800.

Fakultät für Mathematik, Universität Wien, Oskar-Morgenstern-Platz 1, A-1090

Vienna, Austria. WWW: http://www.mat.univie.ac.at/~kratt.