Séminaire Lotharingien de Combinatoire 51 (2005), Article B51h

THE NUMBER OF INDECOMPOSABLE SCHUR RINGS OVER A CYCLIC 2-GROUP

I. KOVÁCS*

Abstract. Indecomposable Schur rings over a cyclic group Z_{n} of order n are considered. In the case n = p^{m}, p an odd prime, the total number of such rings was described in terms of Catalan numbers by Liskovets and Pöschel [Discr. Math. 214 (2000), 173–191]. Here, a closed formula is shown for the total number of indecomposable Schur rings over Z_{2^{m}} using Catalan and Schröder numbers. The result is obtained after the initial problem is turned into a lattice path problem.

1. Introduction

Let H be a finite group with identity element e. Denote by ℤ[H] the group ring of all formal sums ∑_{h∈H} a_{h}h, a_{h} ∈ ℤ, h ∈ H. For T ⊆ H, the group ring element ∑_{h∈T} h will be denoted by \underline{T}. Such an element is also called a simple quantity. The transpose of α = ∑_{h∈H} a_{h}h is defined as α^{⊤} = ∑_{h∈H} a_{h}(h^{−1}). A subring 𝔖 of ℤ[H] is called a Schur ring over H (for short S-ring) if it is generated as a module over ℤ by the simple quantities \underline{T}_{1}, …, \underline{T}_{r} such that they satisfy the axioms:

• T_{1} = {e}, T_{i} ∩ T_{j} = ∅ for all i ≠ j,

• ∑_{i=1}^{r} \underline{T_{i}} = \underline{H},

• for each i ∈ \{1, …, r\} there exists some j ∈ \{1, …, r\} such that \underline{T_{i}}^{⊤} = \underline{T_{j}}. The sets T_{i} are called the basic sets of 𝔖. We will denote by B(𝔖) the set of all basic sets of 𝔖.

Trivial examples for S-rings are provided by the full group ring ℤ[H], and the module generated by the basic sets {e} and H \ {e}. The latter one is also called the trivial S-ring over H.

The notion of an S-ring was created by I. Schur to use them in his investigation of permutation groups, see [10]. Later it was developed to a powerful tool in group theory, see [11, 13].

It was observed later that S-rings can also be applied in algebraic combinatorics. For a given subset S ⊆ H, the Cayley digraph of H with respect to S is defined as the digraph (V, E), where V = H and E = {(h, hs) : h ∈ H, s ∈ S}. Cayley digraphs of cyclic groups are also called circulant digraphs. From now on Z_{n} will denote a cyclic group of order n. M. Klin and R. Pöschel started an approach based on S-rings to study circulant digraphs, see [3]. For a recent survey on this approach, see [9].

Let 𝔖 be an S-ring over Z_{n}. 𝔖 is called wreath-decomposable (or shortly decomposable), if there is a nontrivial, proper subgroup H < Z_{n} such that for every basic

*This research was partially supported by grant OTKA T-043758, and by a grant provided by the University of Pécs.

2 I. KOVÁCS*

set T, T ⊂ H or T = ⋃_{h∈T} Hh. Otherwise, 𝔖 is called indecomposable. If an Sring is decomposable, then it can be obtained as the wreath product of two smaller S-rings, see [9]. Indecomposable S-rings play a crucial role in the description of the automorphism group of circulant graphs with p^{m} vertices, p a prime, see [4, 6].

In this paper we consider the problem of counting the number of indecomposable rings. For m ∈ ℕ and a prime p, we set the notation:

I(m, p) = #{ indecomposable S-rings over Z_{p^{m}}}.

It was shown in [8] that if p > 2, then

I(m, p) = δ(p − 1)c_{m−1},

where δ(p − 1) is equal to the number of positive divisors of (p − 1), and for k ∈ ℕ_{0}, c_{k} is the k-th Catalan number: c_{k} = \frac{1}{k+1} \binom{2k}{k}, cf. [12, page 172]. In this paper, a closed formula is derived for the numbers I(m, 2). For this purpose, besides the Catalan numbers, we will also need the so called Schröder numbers. For k ∈ ℕ_{0}, the k-th Schröder number is: s_{k} = ∑_{k=0}^{n} \frac{1}{k+1} \binom{2k}{k}\binom{n+k}{2k}, cf. [12]. In Section 4, the interpretation of both type of numbers will be recalled in terms of certain lattice paths. Our main result is the following theorem.

Theorem 1.1. If m ≥ 3 then

I(m, 2) = 1 + \frac{1}{3\sqrt{17}} ∑_{k=0}^{m−1} a_{m−1−k}[ (\frac{11 + 3\sqrt{17}}{4})^{k+1} − (\frac{11 − 3\sqrt{17}}{4})^{k+1} ],

where a_{0} = 2, a_{1} = −9 and

a_{i} = (2c_{i} − 4c_{i−1}) + (s_{i} − 2s_{i−1}) − 3 ∑_{j=0}^{i−1} c_{i}s_{i−1−j}, i ≥ 2.

Here, c_{i} and s_{i} are the i-th Catalan and Schröder number, respectively.

It is easy to derive that I(1, 2) = 1 and I(2, 2) = 2. The values of I(m, 2) for m ≤ 10 are shown in the following table.

\begin{matrix}m & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ I(m, 2) & 1 & 2 & 5 & 16 & 63 & 271 & 1225 & 5726 & 27461 & 134461 \end{matrix}

We refer to the characterization of S-rings over Z_{2^{m}} given in [2]. This paper contains a table which lists all S-rings over Z_{2^{m}}, m ≤ 5. One can select the indecomposable ones to find that their total numbers completely agree with the numerical data presented above.

We conclude the introduction with a brief outline of our paper. The starting point of our examinations is the classification of S-rings over Z_{2^{m}} proved in [1, 2]. This will be shortly recalled in Section 2. In Section 3, this classification will be used to establish a bijection between the set of all nontrivial, indecomposable S-rings over Z_{2^{m}} and the collection of so-called indecomposable parameter vectors of length m (see also [5]). In Section 4, the initial counting problem will be turned into a lattice path counting problem. It will be shown that the set indecomposable parameter vectors

THE NUMBER OF INDECOMPOSABLE SCHUR RINGS OVER A CYCLIC 2-GROUP 3

of length m is in one-to-one correspondence with a nicely described set of paths in the (m − 1) × (m − 1) plane integer lattice consisting of steps (1, 0), (0, 1), and (1, 1). Theorem 1.1 will be settled in Section 5 based on this correspondence.

2. S-rings over cyclic 2-groups

Throughout the section n = 2^{m} and m ≥ 2 are assumed. Let Z_{n} = ⟨g⟩. Denote by H_{i} the subgroup of Z_{n} of order 2^{i}, i = 0, …, m, i.e., H_{i} = ⟨g^{2^{m−i}}⟩. We set the notation L_{i} = H_{m−i} \ H_{m−1−i}, i = 0, …, m − 1, and L_{m} = {e}.

Let 𝔖 be an S-ring over Z_{n}. Next we describe its basic sets following [1, 2]. Let T ∈ B(𝔖), T ≠ {e}. It was proved in [1, 2] (cf. also [7]) that there are two main possibilities for T: either T = H_{j} \ H_{k} for some 0 ≤ k < j ≤ m, or T is contained in some set L_{i}. The basic relation θ of 𝔖 is an equivalence relation which is defined on the set {0, 1, …, m − 1} in such a manner that it has equivalence classes of the form {i, …, i + j}, i ∈ {0, …, m − 1}, j ∈ {0, …, m − 1 − i}. The set {i, …, i + j} with j > 0 is an equivalence class of θ if and only if H_{m−i} \ H_{m−i−j−1} is a basic set of 𝔖. The set {i} is an equivalence class if and only if L_{i} cannot be obtained as a proper subset of a basic set of 𝔖.

Assume that T ⊆ L_{i}. According to the classical theory of S-rings, see [13], the basic sets of 𝔖 contained in L_{i} are the orbits of some subgroup K ≤ Aut(Z_{n}). Consequently, T can be obtained as one of the orbits of K. For every i ∈ {0, …, m − 1}, denote by K_{i} the maximal subgroup of Aut(Z_{n}) such that the sets L_{i} ∩ T, T ∈ B(𝔖) are orbits of K_{i}. We refer to the groups K_{0}, …, K_{m−1} as the basic groups of 𝔖.

It follows from the above observations that 𝔖 is uniquely determined by its basic relation and basic groups. In [1, 2] the basic relation together with the basic groups were called the S-system of 𝔖. To recall the characterization of S-rings in terms of their basic relation and basic groups we need to give explicitly the subgroups of Aut(Z_{n}). It is clear that Aut(Z_{n}) = {g^{i} ↦ g^{i·k} : 1 ≤ k < n, gcd(k, n) = 1}. In what follows, we identify Aut(Z_{n}) with the multiplicative group modulo n of elements 1 ≤ k ≤ n, gcd(k, n) = 1. It is well-known that Aut(Z_{2^{m}}) = ⟨−1, 5⟩. (Operations are taken modulo n = 2^{m}.) The subgroups of Aut(Z_{n}) are

G_{3i+1} = {±1 + 2^{i+2}k | 0 ≤ k < 2^{m−i−2}} (i = 0, …, m − 2),
G_{3i+2} = {1 + 2^{i+2}k | 0 ≤ k < 2^{m−i−2}} (i = 0, …, m − 2),  (1)
G_{3i} = {(−1)^{k} + 2^{i+1}k | 0 ≤ k < 2^{m−i−1}} (i = 1, …, m − 2).

In fact, it is not hard to see that G_{3i+1} = ⟨−1, 5^{2^{i}}⟩, G_{3i+2} = ⟨5^{2^{i}}⟩, and G_{3i} = ⟨−5^{2^{i−1}}⟩. The S-rings over Z_{2^{m}} (m ≥ 2) are characterized in the following theorem.

Theorem 2.1. [1, 2] Let θ be a relation on {0, …, m−1}, and let K_{i} ≤ Aut(Z_{n}), i = 0, …, m−1 (m ≥ 2). Then they form the basic relation and basic groups, respectively, of some S-ring over Z_{2^{m}} if and only if the following properties hold:

(i) Every equivalence class of θ is of the form {i, …, i + j},

4 I. KOVÁCS

(ii) If {i, …, i + j} is an equivalence class of θ with j > 0, then K_{i} = K_{i+1} = ⋯ = K_{i+j} = G_{1}, and K_{i−1} = G_{1}, K_{i−2} ∈ {G_{1}, G_{2}} (if i = 0 or i = 1, then delete the conditions where negative indices appear),

(iii) K_{m−1} = G_{1}, K_{m−2} ∈ {G_{1}, G_{2}}, (iv) Let 1 ≤ j ≤ m − 2. If K_{j} = G_{3i+1} or K_{j} = G_{3i+3} for some 0 ≤ i ≤ m − 2,

then

K_{j−1} ∈ {G_{2}} ∪ {G_{3s+1} | 0 ≤ s ≤ i + 1} ∪ {G_{3r+3} | 0 ≤ r ≤ i},

If K_{j} = G_{3i+2} for some 0 ≤ i ≤ m − 2, then

K_{j−1} ∈ {G_{1}} ∪ {G_{3s+2} | 0 ≤ s ≤ i + 1}.

Denote by S(m) the set of all S-rings over Z_{2^{m}}. It follows immediately that the trivial S-ring is indecomposable. In what follows, we will ignore this possibility. Actually, the first summand 1 in the main formula (Theorem 1.1) will be responsible for the trivial S-ring. In the rest of this section it will be shown: if 𝔖 is a nontrivial, indecomposable S-ring over Z_{2^{m}}, m ≥ 2, then its basic relation is equal to the identity relation ω_{m} on {0, …, m − 1}, i.e., ω_{m} consists of singleton classes. We introduce the notation S^{∗}(m) for the collection of S-rings over Z_{2^{m}} that have basic relation ω_{m}. We remark that not all members of S^{∗}(m) are indecomposable. The description of the indecomposable rings will be completed in the next section.

We introduce the functions f_{i} : S(m) → ℤ, i = 0, …, m − 1, which act on an 𝔖 ∈ S(m) by

f_{i}(𝔖) = max{k : H_{k}g^{2^{i}} ⊆ T ∩ L_{i}, T ∈ B(𝔖)}.

In particular, if T′ is a basic set of 𝔖 which is contained in L_{i}, then f_{i}(𝔖) is the maximal number k such that T′ is the union of H_{k}-cosets. The value f_{i}(𝔖) can be calculated from the basic group K_{i} of 𝔖 by using (1). We have

f_{i}(𝔖) = \{ \begin{matrix}m − 2 − a − i, & if K_{i} = G_{3a+b} ≠ G_{1}, \\ m − 1 − i, & if K_{i} = G_{1}. \end{matrix}  (2)

Proposition 2.2. Let 𝔖 be an S-ring over Z_{2^{m}} having basic groups K_{0}, …, K_{m−1}. If K_{1} ≠ G_{1}, then f_{0}(𝔖) ≥ f_{1}(𝔖).

Proof. Let K_{1} = G_{k}, k = 3a + b. Since we assumed k > 1, by (2) we have

f_{1}(𝔖) = m − 3 − a.

Let K_{0} = G_{k′}, k′ = 3a′ + b′. Because of Theorem 2.1(iv), we have a′ ≤ a + 1. If k′ = 1, then f_{0}(𝔖) = m − 1, which is clearly larger than f_{1}(𝔖). If k′ > 1, then (2) and a′ ≤ a + 1 imply

f_{0}(𝔖) = m − 2 − a′ ≥ m − 3 − a = f_{1}(𝔖).
□

Proposition 2.3. If 𝔖 is a nontrivial, indecomposable S-ring over Z_{2^{m}}, then its basic relation is ω_{m}.

THE NUMBER OF INDECOMPOSABLE SCHUR RINGS OVER A CYCLIC 2-GROUP 5

Proof. Let 𝔖 have basic relation θ and let it have basic groups K_{0}, …, K_{m−1}. We are going to show that if θ ≠ ω_{m}, then 𝔖 is decomposable. We proceed by induction on m. The cases m ≤ 3 can be checked directly, hence we assume that m ≥ 4.

If K_{0} = G_{1}, then there is a subgroup H_{k} such that Z_{n} \ H_{k} is a basic set of 𝔖. If k = 0, then 𝔖 is the trivial S-ring. This possibility is excluded, hence k > 0, and by definition it follows that 𝔖 is decomposable.

Assume that K_{0} ≠ G_{1}. Then \underline{H_{m−1}} ∈ 𝔖, hence we can consider the S-ring over H_{m−1} generated by the basic sets of 𝔖 contained in H_{m−1}. Denote this S-ring by 𝔖^{∗}. It follows that the basic relation of 𝔖^{∗} is equal to θ^{∗} = {(i, j) : (i + 1, j + 1) ∈ θ}. Thus θ^{∗} ≠ ω_{m−1}, and, because of the induction hypothesis, 𝔖^{∗} is decomposable. This means by definition that there is some 1 ≤ r ≤ m − 2 such that every basic set of 𝔖^{∗} (which are the basic sets of 𝔖 contained in H_{m−1}) not contained in H_{r} is the union of some H_{r}-cosets. This implies that f_{1}(𝔖) ≥ r. A basic set in L_{0} = H_{m} \ H_{m−1} is the union of H_{d}-cosets, where d = f_{0}(𝔖). Thus if d ≥ r, then 𝔖 is decomposable. In case K_{1} ≠ G_{1} this follows from Proposition 2.2, for d = f_{0}(𝔖) ≥ f_{1}(𝔖) ≥ r.

Therefore, it remains to consider the case K_{1} = G_{1}. The assertion that L_{1} = H_{m−1} \ H_{m−2} is not a basic set is equivalent to saying that θ has equivalence class {1, …, i} with i > 1. According to Theorem 2.1(ii), we have K_{0} = G_{1}, i.e., d = m−1, which clearly exceeds r and, consequently, 𝔖 is decomposable. Assume finally that L_{1} is a basic set, i.e., \underline{H_{m−2}} ∈ 𝔖^{∗}. This gives K_{0} = G_{k} with k ≤ 4, see Theorem 2.1(iv). Thus, by (2),

d = f_{0}(𝔖) ≥ m − 3.  (3)

As before, the S-ring over H_{m−2} which is generated by the basic sets of 𝔖 contained in H_{m−2} is decomposable because of the induction hypothesis. This implies that every basic set of 𝔖 which is contained in H_{m−2} \ H_{s} is the union of H_{s}-cosets for some 1 ≤ s ≤ m − 3. Since d ≥ m − 3 ≥ s, see (3), and since L_{1} is a basic set, we obtain finally that 𝔖 is decomposable as required. The proof now is completed. □

For our purpose, only the S-rings in S^{∗}(m) need to be considered. An S-ring 𝔖 ∈ S^{∗}(m) is uniquely determined by its basic groups K_{0}, …, K_{m−1} since, by definition, its basic relation is θ = ω_{m}. Now, K_{m−1} = G_{1}, K_{m−2} ∈ {G_{1}, G_{2}} (Theorem 2.1(iii)), and for i < m − 2 the basic group K_{i} is determined recursively from K_{i+1} (see Theorem 2.1(iv)). This can be interpreted via a rooted tree, which will be denoted by T (m). Each vertex of T (m) is labeled by one of the groups G_{i}. Label the root, which is also considered as the 0-th level of the tree, by G_{1}. Put two points on the 1-th level, label them by G_{1} and G_{2}, respectively, and join the root with both using a directed edge. The i-th level, 1 < i ≤ m−1, is built based on the recursion in Theorem 2.1(iv). As an illustration, T (4) is shown in Figure 1. Then the rings in S^{∗}(m) can be naturally identified with the directed paths in T (m) of length m − 1. The S-ring 𝔖 ∈ S^{∗}(m) having basic groups (K_{0}, …, K_{m−1}) corresponds to the directed path of T (m) that passes the i-th level at the vertex labeled with K_{m−1−i}; and conversely, any such directed path induces an ring in S^{∗}(m) by considering the labels of its vertices.

[figure: G_{1}; G_{1}; G_{2}; G_{1}; G_{2}; G_{3}; G_{4}; G_{5}; G_{1}; G_{2}; G_{3}; G_{4}; G_{5}; G_{6}; G_{7}; G_{8}]

Figure 1. The directed rooted tree T (4)

3. Parameter vectors

In this section we will identify the S-rings in S^{∗}(m), m ≥ 2, with a collection of parameters. The main purpose is to give a formal description of the parameters that correspond to indecomposable rings in S^{∗}(m). (Hence, they will also describe all nontrivial, indecomposable S-rings over Z_{2^{m}}.)

Introduce the set M = {0, …, m − 1} × {0, +, −}. For the element (s, ±) ∈ M and (s, 0) ∈ M, respectively, we agree to use the notations s^{±} and s, respectively.

Definition 3.1. Let 𝔖 ∈ S^{∗}(m), and let it have basic groups K_{0}, …, K_{m−1} (m ≥ 2). The parameter vector u⃗ = (u_{0}^{ε_{0}}, …, u_{m−1}^{ε_{m−1}}) ∈ M^{m} of 𝔖 is defined as

u_{i} = f_{i}(𝔖) = \{ \begin{matrix}m − 2 − a − i, & if K_{i} = G_{3a+b} ≠ G_{1}, \\ m − 1 − i, & if K_{i} = G_{1}, \end{matrix}  (4)

and

ε_{i} = \{ \begin{matrix}−, & if K_{i} = G_{3a}, \\ +, & if K_{i} = G_{3a+1} and a > 0, \\ 0, & if K_{i} = G_{1} or K_{i} = G_{3a+2}. \end{matrix}  (5)

The parameter vector u⃗ is called indecomposable if and only if 𝔖 is indecomposable.

As a direct consequence of Definition 3.1 we have the following proposition.

Proposition 3.2. If (u_{i}^{ε_{i}}) is a parameter vector of length m, then

u_{i} ≤ \{ \begin{matrix}m − 3 − i, & if ε_{i} ≠ 0, \\ m − 1 − i, & if ε_{i} = 0, \end{matrix}

for all i ∈ {0, …, m − 1}.

The parameter vectors of length m can be easily obtained using T (m). First, replace the labels of T (m) by elements of M in the following manner: if a vertex on the i-th level is labeled by G_{3a+b}, then assign to it the “new” label u^{ε} ∈ M, where

u = \{ \begin{matrix}i − 1 − a, & if 3a + b > 1, \\ i, & if 3a + b = 1, \end{matrix}

and

ε = \{ \begin{matrix}+, & if b = 1 and a > 0, \\ −, & if b = 0, \\ 0, & if b = 2 or 3a + b = 1. \end{matrix}

See Figure 2 below, where the tree T (4) is shown with its “new” labels.

[figure: 0; 1; 0; 2; 1; 0^{−}; 0^{+}; 0; 3; 2; 1^{−}; 1^{+}; 1; 0^{−}; 0^{+}; 0]

Figure 2. T (4) with “new” labels

Now the parameter vector (u_{i}^{ε_{i}}) of a given S-ring 𝔖 ∈ S^{∗}(m) can be easily obtained. Consider the directed path of T (m) corresponding to 𝔖, and then write down the “new” labels of T (m) that are passed by the path. (Note: the label of the root provides u_{m−1}^{ε_{m−1}}, and so on.) Based on Figure 2, we list all parameter vectors of length at most 4 in Table 1.

m parameter vectors
2 (1, 0)  (0, 0)^{∗}
3 (2, 1, 0) (2, 0, 0) (1, 1, 0) (1, 0, 0)^{∗} (0^{−}, 1, 0)^{∗}
(0^{+}, 1, 0)^{∗}  (0, 0, 0)^{∗}
4 (3, 2, 1, 0)  (3, 2, 0, 0)  (3, 1, 1, 0)  (3, 1, 0, 0) (3, 0^{−}, 1, 0)
(3, 0^{+}, 1, 0) (3, 0, 0, 0)  (2, 2, 1, 0)  (2, 2, 0, 0) (2, 1, 1, 0)
(2, 1, 0, 0)^{∗}  (2, 0^{−}, 1, 0)^{∗} (2, 0^{+}, 1, 0)^{∗} (2, 0, 0, 0)^{∗} (1^{−}, 2, 1, 0)
(1^{−}, 2, 0, 0)^{∗} (1^{−}, 0^{−}, 1, 0)^{∗} (1^{−}, 0^{+}, 1, 0)^{∗} (1^{+}, 2, 1, 0) (1^{+}, 2, 0, 0)^{∗}
(1^{+}, 0^{−}, 1, 0)^{∗} (1^{+}, 0^{+}, 1, 0)^{∗} (1, 1, 1, 0)  (1, 1, 0, 0)^{∗} (1, 0, 0, 0)^{∗}
(0^{−}, 0^{+}, 1, 0)^{∗} (0^{+}, 0^{+}, 1, 0)^{∗} (0, 0, 0, 0)^{∗}

Table 1. The parameter vectors of S-rings in S^{∗}(m), m = 2, 3, 4.

The decomposability of an S-ring in S^{∗}(m) can easily be checked in terms of its parameter vector as stated in the following proposition.

Proposition 3.3. If u⃗ = (u_{i}^{ε_{i}}) is the parameter vector of an S-ring 𝔖 ∈ S^{∗}(m), then 𝔖 is decomposable if and only if there exits some r ∈ {1, …, m − 1}, such that u_{i} ≥ r for all i = 0, …, m − 1 − r.

Proof. Recall that u_{i} = f_{i}(𝔖), see (4). By the definition of f_{i} (cf. Section 2), the value u_{i} can also be regarded as the maximal number k that every basic set in L_{i} is the union of H_{k}-cosets. Our claim is an immediate consequence of this interpretation. 𝔖 is decomposable by definition if there exists some r ∈ {1, …, m − 1} such that every basic set is either contained in H_{r} or is the union of H_{r}-cosets (cf. Section 1). For our 𝔖 ∈ S^{∗}(m), this is equivalent to saying that every basic set in L_{i}, i = 0, …, m−1−r, is the union of some H_{r}-cosets for some r ∈ {1, …, m − 1}. This is equivalent to saying that u_{i} ≥ r for all i = 0, …, m − 1 − r. □

Using Proposition 3.3, it is easy to check that the indecomposable parameter vectors in Table 1 are exactly those that are marked with the sign ^{∗}.

At the end of this section, we establish a formal description of indecomposable parameter vectors (Theorem 3.8). To prepare for this description, we give next further properties of the parameter vectors. Let 𝔖 ∈ S^{∗}(m), and let 𝔖 have basic groups

K_{0} = G_{3a_{0}+b_{0}}, …, K_{m−2} = G_{3a_{m−2}+b_{m−2}}, K_{m−1} = G_{1}.

Let u⃗ = (u_{i}^{ε_{i}}) denote the parameter vector of 𝔖. For the next three propositions assume that i ∈ {1, …, m − 1}.

Proposition 3.4. If ε_{i−1} ≠ 0 and ε_{i} = 0, then u_{i−1} = u_{i} − 1 = m − 2 − i. Otherwise, u_{i−1} ≥ u_{i}.

Proof. Because of (5), the conditions ε_{i−1} ≠ 0 and ε_{i} = 0 are equivalent with

( b_{i−1} = 0 ∨ (b_{i−1} = 1 ∧ a_{i−1} > 0) ) ∧ ( 3a_{i} + b_{i} = 1 ∨ b_{i} = 2 ).  (6)

Theorem 2.1(iv) shows that (6) holds exactly when 3a_{i} + b_{i} = 1 and 3a_{i−1} + b_{i−1} ∈ {3, 4}. By (4), these equalities imply u_{i−1} = m − 2 − 1 − (i − 1) = m − 2 − i and u_{i} = m − 1 − i.

Assume that (6) does not hold. By Theorem 2.1(iv) we know that a_{i−1} ≤ a_{i} + 1. If 3a_{i} + b_{i} ≠ 1, then, according to (4), we have u_{i} = m − 2 − a_{i} − i. Therefore,

u_{i} ≤ m − 2 − (a_{i−1} − 1) − i = m − 2 − a_{i−1} − (i − 1) ≤ u_{i−1}.

Let 3a_{i} + b_{i} = 1. Since (6) does not hold, we have 3a_{i−1} + b_{i−1} ∈ {1, 2}. This implies u_{i} = m − 1 − i and u_{i−1} ∈ {m − i, m − 1 − i}, hence u_{i−1} ≥ u_{i} as required. The proof is completed. □

Corollary 3.5. If 𝔖 is indecomposable, then u_{i} = m − 1 − i if and only if i = m − 1 or (i ≥ 1 ∧ ε_{i−1} ≠ 0 ∧ ε_{i} = 0).

THE NUMBER OF INDECOMPOSABLE SCHUR RINGS OVER A CYCLIC 2-GROUP 9

Proof. If i = m − 1, then K_{m−1} = G_{1}, see Theorem 2.1(iii). This gives u_{m−1} = m − 1 − (m − 1) = 0. If i ≥ 1 and ε_{i−1} ≠ 0 and ε_{i} = 0, then u_{i} = m − 1 − i by Proposition 3.4.

Conversely, assume that u_{i} = m − 1 − i holds and i ∈ {0, …, m − 2}. Then 3a_{i} + b_{i} = 1, see (4). If i = 0, then L_{0} is a basic set, hence 𝔖 is decomposable, a contradiction. Thus i ≥ 1 and we can consider u_{i−1}. According to Proposition 3.4, we have u_{i−1} ≥ u_{i} or u_{i−1} = u_{i} − 1.

Assume that u_{i−1} ≥ u_{i}. We show next

u_{j} ≥ m − 1 − i, for all j = 0, …, i.  (7)

We use induction on j. The relation in (7) is clear for j ∈ {i, i − 1}. Assume that i > 1 and that (7) holds for j ∈ {1, …, i − 1}. By Proposition 3.4, either u_{j−1} ≥ u_{j} or u_{j−1} = m − 2 − j. Note that in both cases u_{j−1} ≥ m − 1 − i, as required.

By choosing r = m − i − 1 in Proposition 3.3, one obtains via (7) that 𝔖 is decomposable, a contradiction. Therefore, we have u_{i−1} = u_{i} − 1. By Proposition 3.4, this implies that ε_{i−1} ≠ 0 and ε_{i} = 0, and this completes the proof. □

Proposition 3.6. If ε_{i−1} = 0 and ε_{i} ≠ 0, then u_{i−1} ∈ {m − i, m − 1 − i}.

Proof. Because of (5), the conditions ε_{i−1} = 0 and ε_{i} ≠ 0 are equivalent with

( 3a_{i−1} + b_{i−1} = 1 ∨ b_{i−1} = 2 ) ∧ ( b_{i} = 0 ∨ (b_{i} = 1 ∧ a_{i} > 0) ).

Theorem 2.1(iv) shows that the only possibility that this may occur is that 3a_{i−1} + b_{i−1} = 1 or 3a_{i−1} + b_{i−1} = 2. By (4), we have u_{i−1} = m − 1 − (i − 1) or u_{i−1} = m − 2 − (i − 1), i.e., u_{i−1} ∈ {m − i, m − 1 − i}. □

Proposition 3.7. If ε_{i−1} ≠ 0, ε_{i} ≠ 0 and u_{i−1} = u_{i}, then ε_{i} = +.

Proof. By (4) and (5), the conditions ε_{i−1} ≠ 0, ε_{i} ≠ 0 and u_{i−1} = u_{i} give

u_{i−1} = m − 2 − a_{i−1} − (i − 1) = m − 2 − a_{i} − i = u_{i}.

Thus a_{i−1} = a_{i} + 1. Theorem 2.1(iv) shows that this may occur only when b_{i} = 1, which, by (5), gives ε_{i} = +. □

In fact, the above properties completely describe the indecomposable parameter vectors among the elements of M^{m}.

Theorem 3.8. The parameter vector u⃗ = (u_{i}^{ε_{i}}) ∈ M^{m} (m ≥ 2) is indecomposable if and only if it satisfies the properties:

(i) for all i ∈ \{0, …, m − 1\}, u_{i} ≤ \{ \begin{matrix}m − 3 − i, & if ε_{i} ≠ 0, \\ m − 1 − i, & if ε_{i} = 0, \end{matrix}

(ii) u_{i} = m − 1 − i if and only if i = m − 1 or i ≥ 1 and ε_{i−1} ≠ 0 and ε_{i} = 0, (iii) if ε_{i−1} ≠ 0 and ε_{i} = 0, then u_{i−1} = u_{i} − 1; otherwise, u_{i−1} ≥ u_{i}, (iv) if ε_{i−1} = 0 and ε_{i} ≠ 0, then u_{i−1} ∈ {m − i, m − 1 − i},

(v) if ε_{i−1} ≠ 0, ε_{i} ≠ 0 and u_{i−1} = u_{i}, then ε_{i} = +.

Proof. If u⃗ is an indecomposable parameter vector, then the properties (i)-(v) are just a reformulation of Proposition 3.2, Propositions 3.4, 3.6, 3.7, and Corollary 3.5.

10 I. KOVÁCS

Conversely, assume that u⃗ = (u_{i}^{ε_{i}}) ∈ M^{m} satisfies (i)-(v). We are going to prove by induction on m that u⃗ is an indecomposable parameter vector, i.e., that it is the parameter vector of a nontrivial, indecomposable S-ring over Z_{2^{m}}. If m = 2, then it can be directly checked that (0, 0) is the only element of M × M satisfying all properties (i)-(v).

Assume that m ≥ 3. For a given u_{i}^{ε_{i}}, i ∈ {0, …, m − 1}, substitute u_{i} into the equation (4). This will determine a unique number a_{i}. Then consider the equation in (5) which corresponds to our given ε_{i}. It will hold for a unique b_{i} ∈ {0, 1, 2} as a_{i} is already fixed. Then put K_{i} = G_{3a_{i}+b_{i}}.

In fact, it suffices to show that the groups K_{0}, …, K_{m−1} are the basic groups of an indecomposable S-ring 𝔖 ∈ 𝔖^{∗}(m), for then u⃗ is clearly the parameter vector of 𝔖. We prove first that they are the basic groups of an S-ring in 𝔖^{∗}(m) by showing that K_{0}, …, K_{m−1} satisfy Theorem 2.1(iii)-(iv). We distinguish two cases.

Case 1: u_{1} < m − 2.

We set u′ = (u_{1}^{ε_{1}}, …, u_{m−1}^{ε_{m−1}}) ∈ M^{m−1}. It can be checked that in this case u′ satisfies all properties (i)-(v). Therefore, the induction hypothesis yields that u′ is the parameter vector of an indecomposable S-ring 𝔖′ over ℤ_{2^{m−1}}. It follows from this that the groups K_{1}, …, K_{m−1} satisfy the conditions Theorem 2.1(iii)-(iv). Therefore, we only have to check K_{0}.

Assume that ε_{1} = 0. Since u_{1} < m−2, it follows that K_{1} = G_{3a_{1}+2}. If ε_{0} ≠ 0, then, by (ii), we have u_{1} = m − 2, a contradiction. Also, ε_{0} = 0. If K_{0} ≠ G_{1}, then b_{0} = 2, and, by (2) and (i),

0 ≤ a_{0} = m − 2 − u_{0} ≤ m − 3 − (u_{1}) + 1 = a_{1} + 1.

Therefore, we obtain

K_{0} ∈ {G_{1}} ∪ {G_{3i+2} | 0 ≤ i ≤ a_{1} + 1},

as stated in Theorem 2.1(iv).

Assume next that ε_{1} ≠ 0. This is the same as K_{1} = 3a_{1} + 1 or K_{1} = 3a_{1} for a_{1} > 0. If now ε_{0} = 0, then, by (iv), we have u_{0} ∈ {m − 1, m − 2}. By (2), this implies that K_{0} ∈ {G_{1}, G_{2}}. If ε_{0} ≠ 0, then K_{1} = 3a_{0} + 1 or K_{1} = 3a_{0} for a_{0} > 0. By (2) and (i), we have 0 ≤ a_{0} ≤ a_{1} + 1, and a_{0} = a_{1} + 1 is the same as u_{0} = u_{1}. In this case, by (iii) it follows that ε_{1} = +. Furthermore, we have b_{1} = 1. Altogether we obtain that in case K_{1} = G_{3a_{1}+1} or K_{1} = G_{3a_{1}+3},

K_{0} ∈ {G_{2}} ∪ {G_{3i+1} | 0 ≤ i ≤ a_{1} + 1} ∪ {G_{3i+3} | 0 ≤ i ≤ a_{1}}.

Thus, K_{0} satisfies Theorem 2.1(iv).

Case 2: u_{1} = m − 2.

Then, according to (4) and (5), we have K_{1} = G_{1} and ε_{1} = 0. We set u′ = (u_{2}^{ε_{1}}, …, u_{m−1}^{ε_{m−1}}) ∈ M^{m−2}. In this case, u_{2} < m − 3, since otherwise ε_{1} ≠ 0 would follow because of (iii). It follows from this that the groups K_{2}, …, K_{m−1} satisfy the conditions Theorem 2.1(iii)-(iv). Therefore, we only have to check K_{1} and K_{0}.

Since K_{1} = G_{1}, it satisfies Theorem 2.1(iii)-(iv) independently of K_{2}. According to (ii), we have ε_{0} ≠ 0 and ε_{1} = 0. Thus, u_{0} = m − 3 because of (i), hence, from (4), we get that K_{0} ∈ {G_{3}, G_{4}}. This shows that K_{0} satisfies Theorem 2.1(iv), as required.

THE NUMBER OF INDECOMPOSABLE SCHUR RINGS OVER A CYCLIC 2-GROUP 11

We proved that u⃗ is the parameter vector of an S-ring 𝔖 ∈ 𝔖^{∗}(m). It remains to show that 𝔖 is indecomposable. By way of contradiction, assume that 𝔖 is decomposable. Because of Proposition 3.3, there is some r ∈ {1, …, m − 1} such that

u_{i} ≥ r for all i = 0, …, m − 1 − r.  (8)

In particular, u_{m−1−r} ≥ r = m − 1 − (m − 1 − r). Because of (i) and (ii), we have u_{m−1−r} = r, m − 1 − r > 0, ε_{m−1−r} = 0, and ε_{u_{m−2−r}} ≠ 0. Now (iii) implies u_{m−2−r} = u_{m−1−r} − 1 = r − 1, which contradicts (8). The proof of the theorem is now completed. □

4. Lattice paths

In this section, we consider lattice paths (for short paths) in the integer plane lattice, which consist of steps →= (1, 0), ↑= (0, 1) and ↗= (1, 1). A path π is uniquely determined by its starting point and the sequence of its steps. We express this as π = (s_{1}, …., s_{k}), s_{i} ∈ {→, ↑, ↗}. The path induced by π′ = (s_{i}, s_{i+1}, …, s_{j}), 1 ≤ i ≤ j ≤ k, will be called a subpath of π.

In this section we are going to associate a path with any indecomposable parameter vector. Let u⃗ = (u_{0}^{ε_{0}}, …, u_{m−1}^{ε_{m−1}}) be an indecomposable parameter vector. The associated path will have starting point (0, 0), and its steps will be constructed recursively in m − 1 steps. In each step, a subpath will be determined, which will be denoted by π_{i}, whose end point will be denoted by (x_{i}, y_{i}). As initial value, let π_{0} be the empty path with starting point (0, 0), so that (x_{0}, y_{0}) = (0, 0).

Assume that π_{i} is already defined, connecting (0, 0) with (x_{i}, y_{i}), 0 ≤ i < m − 2. Then define π_{i+1} as the concatenation of π_{i} with π′, where π′ has starting point (x_{i}, y_{i}), and where its steps are determined by the following rules:

If ε_{i} = 0 then

π′ := \{ \begin{matrix}(→, ↑), & if i ≥ 1, ε_{i−1} ≠ 0, \\ (\underbrace{→, …, →}_{r}, ↑) & if i = 0 or (i ≥ 1, ε_{i−1} = 0), \end{matrix}  (9)

where r = max(m − 1 − x_{i} − u_{i}, 0).

If ε_{i} ≠ 0 then

π′ := \{ \begin{matrix}(\overbrace{↑, …, ↑, ↑}^{s}, →) & if ε_{i} = +, \\ (\underbrace{↑, …, ↑}_{s−1}, ↗) & if ε_{i} = −, \end{matrix}  (10)

where s = max(m − 2 − y_{i} − u_{i}, 0).

It is easy to see that for the end point of π_{i+1} we have

(x_{i+1}, y_{i+1}) = \{ \begin{matrix}(x_{i} + 1, y_{i} + 1), & if i ≥ 1, ε_{i} = 0, ε_{i−1} ≠ 0, \\ (x_{i} + r, y_{i} + 1), & if ε_{i} = 0, (i = 0 or i ≥ 1, ε_{i−1} = 0), \\ (x_{i} + 1, y_{i} + s), & if ε_{i} ≠ 0. \end{matrix}

Given this construction, we associate u⃗ with the path π_{m−1}. We set the notation π(u⃗) = π_{m−1}.

Example 4.1. π(u⃗), u⃗ = (2^{−}, 2^{+}, 3, 0^{+}, 1, 0).

By definition π_{0} is the empty path, (x_{0}, y_{0}) = (0, 0). As for π_{1}, since u_{0}^{ε_{0}} = 2^{−}, apply (10) with s = 2 to find π_{1} = π′ = (↑, ↗), (x_{1}, y_{1}) = (1, 2). π_{2} is the concatenation of π_{1} with π′, where π′ starts at (1, 2) and, according to (10), π′ = (→). Continuing in this way, we obtain:

[figure: π_{1}; π_{2}; π_{3}; π_{4}; π(u⃗) = π_{5}]

Next, we provide more paths associated with indecomposable parameter vectors. For sake of simplicity, we put π(u⃗) = π(u_{0}^{ε_{0}}, …, u_{m}^{ε_{m}}) if u⃗ = (u_{0}^{ε_{0}}, …, u_{m}^{ε_{m}}).

Example 4.2. The paths associated with indecomposable parameter vectors of length m, 2 ≤ m ≤ 4.

\underline{m = 2:} There is only one path: π(0, 0) = (→, ↑).

\underline{m = 3:}

[figure: π(0, 0, 0); π(1, 0, 0); π(0^{+}, 1, 0); π(0^{−}, 1, 0)]

\underline{m = 4:}

[figure: π(0, 0, 0, 0); π(1, 1, 0, 0); π(1, 0, 0, 0); π(1, 0^{+}, 1, 0); π(1, 0^{−}, 1, 0); π(2, 1, 0, 0); π(2, 0, 0, 0)]

[figure: π(0^{+}, 0^{+}, 1, 0); π(0^{−}, 0^{+}, 1, 0); π(1^{+}, 0^{+}, 1, 0); π(1^{+}, 0^{−}, 1, 0); π(1^{−}, 0^{+}, 1, 0); π(1^{−}, 0^{−}, 1, 0); π(1^{+}, 2, 0, 0); π(1^{−}, 2, 0, 0)]

It will turn out that the class of paths which can be obtained from indecomposable parameter vectors can be nicely described by using classical paths such as Catalan and Schröder paths.

Catalan paths are defined as paths connecting two points lying on the line y = x such that they consist of steps → and ↑, and reach no point above the line y = x. The total number of Catalan paths from (0, 0) to (n, n) is the n-th Catalan number c_{n}, [12, Exercise 6.20/c]. Schröder paths connect two points lying on the diagonal line, consist of steps →, ↑ and ↗, and reach no point below the line y = x. The total number of Schröder paths from (0, 0) to (n, n) is equal to n-th Schröder number s_{n}, [12, Exercise 6.39/j]. For our purpose we will need a slight modification of the Schröder paths. Namely, we call a path a long Schröder path if it is the extension of a Schröder path with two additional steps → and ↑.

By examining the paths in the examples, one might observe that they can be described as concatenation of Catalan and long Schröder paths. We are going to show that this is true in general.

THE NUMBER OF INDECOMPOSABLE SCHUR RINGS OVER A CYCLIC 2-GROUP 13

Theorem 4.3. If m ≥ 2, then the mapping u⃗ ↦ π(u⃗) is a bijection from the set of all indecomposable parameter vectors of length m to the class of paths described by

concatenations of Catalan and long Schröder paths from (0, 0) to (m − 1, m − 1). (11)

The proof of Theorem 4.3 will be based on induction on m. This requires a few preparatory propositions. As these are straightforward consequences of the definitions, we leave the proofs to the reader.

Let u⃗ = (u_{i}^{ε_{i}}) ∈ M^{m} be an indecomposable parameter vector, and let m ≥ 3. We introduce the vector u′ = (w_{0}^{ξ_{0}}, …, w_{m−2}^{ξ_{m−2}}) by

w_{0}^{ξ_{0}} = \{ \begin{matrix}u_{1}^{ε_{1}}, & if u_{1} < m − 2, \\ m − 3, & otherwise, \end{matrix}

and for i ∈ {1, …, m − 2} let w_{i}^{ξ_{i}} = u_{i+1}^{ε_{i+1}}. The vector u′ will be called the derivation of u⃗.

Proposition 4.4. If u⃗ is an indecomposable parameter vector of length m ≥ 3, then so is its derivation u′.

Let π = (s_{1}, …, s_{k}) be a path starting at (0, 0). For the numbers 1 ≤ i_{1} < ⋯ < i_{t} ≤ k, we denote by π^{− i_{1},...,i_{t}} the path starting at (0, 0), and whose steps are obtained from those of π by deleting the steps s_{i_{1}}, …, s_{i_{t}}. For a path π = (s_{1}, …, s_{k}) connecting (0, 0) with (m, m), we define its derivation as the path π′ connecting (0, 0) with (m − 1, m − 1) such that:

π′ = \{ \begin{matrix}π^{− 1}, & if s_{1} =↗, \\ π^{− 1,l+1}, & if s_{1} = ⋯ = s_{l} =→ (↑), s_{l+1} =↑ (→), \\ π^{− (l+1)}, & if s_{1} = ⋯ s_{l} =↑, s_{l+1} =↗ . \end{matrix}  (12)

Example 4.5. The derivation of π = π(3^{−}, 4, 0^{+}, 0^{+}, 1, 0) and ρ = π(3, 2, 2, 0^{+}, 1, 0). (The derivations are shown after translating them by the vector (1, 1).)

[figure: π; ↦; π′; ρ; ↦; ρ′]

The vectors (3^{−}, 4, 0^{+}, 0^{+}, 1, 0) and (3, 2, 2, 0^{+}, 1, 0) are indecomposable parameter vectors, see Theorem 3.8. It can be seen that the derivation paths are also concatenations of Catalan and long Schröder paths. Moreover, π′ = π(3, 0^{+}, 0^{+}, 1, 0), ρ′ = π(2, 2, 0^{+}, 1, 0), and (3, 0^{+}, 0^{+}, 1, 0) and (2, 2, 0^{+}, 1, 0) are the derivations of (3^{−}, 4, 0^{+}, 0^{+}, 1, 0) and (3, 2, 2, 0^{+}, 1, 0), respectively. In general, we have the following relation between the derivation of vectors and paths.

Proposition 4.6.

(i) If π is a path as described in (11) with m ≥ 3, then π′ is also a concatenation of Catalan and long Schröder paths, connecting (0, 0) with (m − 2, m − 2).

(ii) If u⃗ is an indecomposable parameter vector of length m, m ≥ 3, then (π(u⃗)) ′ = π(u′).

14 I. KOVÁCS

Now everything is prepared to prove Theorem 4.3.

The proof of Theorem 4.3. We proceed by induction on m. The assertion is true for m = 2, see Table 1 and Example 4.2.

Assume that m ≥ 3. It follows from (9) and (10) that u⃗ ↦ π(u⃗) is an injection. We show next that if u⃗ is an indecomposable parameter vector of length m, then π(u⃗) is a path as described in (11). Let π = π(u⃗). We have π′ = π(u′), see Proposition 4.6(ii). Since u′ is an indecomposable parameter vector, see Proposition 4.4, π′ is a concatenation of Catalan and long Schröder paths connecting (0, 0) with (m−2, m−2). Now one can use (9), (10), and (12) to conclude that π must be a path as described in (11).

The proof will be completed by showing that if ρ is a path which connects (0, 0) with (m − 1, m − 1) such that it is a concatenation of Catalan and long Schröder paths, then ρ = π(u⃗) for some indecomposable parameter vector u⃗ of length m. Let ρ = (s_{1}, …, s_{k}). Use Proposition 4.6(i) and the induction hypothesis to deduce ρ′ = π(v⃗) for some indecomposable vector v⃗ of length m − 1. Furthermore, let v⃗ = (v_{0}^{ξ_{0}}, …, v_{m−2}^{ξ_{m−2}}).

We distinguish two cases depending on whether ρ starts with a Catalan or with a long Schröder subpath. We consider only the first case as the second one can be settled along the same line of reasoning.

Let the starting Catalan subpath of ρ have first steps s_{1} = ⋯ = s_{l} =→, s_{l+1} =↑, 1 ≤ l ≤ m − 2. Now define u⃗ = (u_{i}^{ε_{i}}) by

u_{i}^{ε_{i}} = \{ \begin{matrix}(m − 1 − l)^{0}, & if i = 0, \\ v_{i−1}^{ξ_{i−1}}, & if 1 < i ≤ m − 1. \end{matrix}

We are going to complete the proof by showing that u⃗ is an indecomposable parameter vector of length m, and ρ = π(u⃗). Now, u⃗ being an indecomposable parameter vector is equivalent to the conditions

u_{0} ≤ m − 2,
ε_{1} ≠ 0 ⇒ u_{0} = m − 2,
u_{0} ≥ u_{1},

see Theorem 3.8. It immediately follows that u_{0} ≤ m−2. Let ε_{1} ≠ 0. We have ξ_{0} ≠ 0. Moreover, ρ′ starts with a long Schröder path, see (10). As ρ starts with a Catalan subpath, this can only occur if l = 1, see (12). Hence u_{0} = m − 2. It remains to show that u_{0} ≥ u_{1}. We have u_{1} = v_{0} ≤ m − 3 since v⃗ is an indecomposable parameter vector of length m − 1. Hence we may assume that u_{1} < m − 2, so that l > 1. Thus, by (12), the path ρ′ starts with the Catalan subpath (s_{2}, …, s_{l}, s_{l+1}, …). Now use (9) to obtain l − 1 ≤ m − 2 − v_{0}. It follows that u_{1} = v_{0} ≤ m − 1 − l = u_{0}.

It is clear that u′ = v⃗. Therefore, we have (π(u⃗))′ = ρ′, see Proposition 4.6(ii). Moreover, for π(u⃗) = ρ it is enough to show that the two paths share the same first l + 1 steps. This is however clear since it follows that the first iteration of π(u⃗) is (s_{1}, …, s_{l+1}), see (9). □

THE NUMBER OF INDECOMPOSABLE SCHUR RINGS OVER A CYCLIC 2-GROUP 15

5. The proof of Theorem 1.1

Recall that I(m, p) denotes the number of indecomposable S-rings over Z_{p^{m}}. If m ≥ 2, then the nontrivial, indecomposable S-rings over Z_{2^{m}} were parameterized by the indecomposable parameter vectors of length m in Section 3. In Section 4 these vectors were shown to be in a one-to-one correspondence with paths as described in (11). Since the trivial S-ring is always indecomposable, for m ≥ 2 we have

I(m, 2) = 1 + #{paths as described in (11)}.  (13)

Our derivation of the expression for I(m, 2) given in Theorem 1.1 will be based on this interpretation. If n ≥ 1, let p_{n} denote the number of paths from (0, 0) to (n, n) as described in (11), and for convenience put p_{0} = 1. Thus, I(m, 2) = 1 + p_{m−1} if m ≥ 2. We set P (x) = ∑_{n≥0} p_{n}x^{n}.

Recall that the total numbers of Catalan and Schröder paths, respectively, connecting (0, 0) with (n, n) are given by

c_{n} = \frac{1}{n + 1}\binom{2n}{n} and s_{n} = ∑_{k=0}^{n} \frac{1}{k + 1}\binom{2k}{k}\binom{n + k}{2k}.  (14)

The corresponding generating functions are, see [12, page 178],

C(x) = ∑_{n≥0} c_{n}x^{n} = \frac{1 − \sqrt{1 − 4x}}{2x}, S(x) = ∑_{n≥0} s_{n}x^{n} = \frac{1 − x − \sqrt{1 − 6x + x^{2}}}{2x} . (15)

If s̃_{n} denotes the number of long Schröder paths, n ∈ ℕ, then the corresponding generating function is S̃(x) = (S(x) − 1)x, as is immediate to see.

The proof of Theorem 1.1. I(1, 2) = 1 is clear, hence assume m ≥ 2. As our paths are concatenations of Catalan and long Schröder paths, we have the following recursion:

p_{n} = ∑_{i=0}^{n} s̃_{i}p_{n−i} + ∑_{i=0}^{n−1} c_{i}p_{n−1−i}, n ≥ 1.

In terms of generating functions, P (x) = P (x)S̃(x) + P (x)C(x)x + 1. Substitute S̃(x) = (S(x) − 1)x and use (15) to deduce

P (x) = \frac{2}{3x + \sqrt{1 − 4x} + \sqrt{1 − 6x + x^{2}}} .

By getting rid of the square roots in the denominator and using (15) again, one can obtain

P (x) = \frac{1 + 4x + (4x − 2)C(x) + (2x − 1)S(x) + 3xC(x)S(x)}{4x^{2} + 11x − 2}.

From this, for the numerator we have:

−2 + 9x + ∑_{n≥2}( 4c_{n−1} − 2c_{n} + 2s_{n−1} − s_{n} + 3 ∑_{i=0}^{n−1} c_{i}s_{n−1−i})x^{n}.

Using partial fraction decomposition, the denominator can be expanded to

\frac{1}{4x^{2} + 11x − 2} = ∑_{n≥0} \frac{1}{3\sqrt{17}}[ (\frac{11 − 3\sqrt{17}}{4})^{n+1} − (\frac{11 + 3\sqrt{17}}{4})^{n+1} ]x^{n}.

Eventually, these facts are combined to derive the desired expression for p_{m−1}. The proof now is completed. □

Acknowledgements

The author thanks Mikhail Klin for helpful remarks and suggestions. A threeweek visit of the author at the University of Delaware was useful in producing the final version of the paper. This visit was partially supported by the University of Delaware. The author also thanks Christian Krattenthaler for his remarks regarding paths and their enumeration.

References

[1] Ja. Ju. Gol’fand, N. L. Najmark, R. Pöschel. The structure of S-rings over Z_{2^{m}}. Akad. der Wiss. der DDR Inst. für Math., Preprint P-MATH-01/85 (1985), 1–30.

[2] M. Ch. Klin, N. L. Najmark, R. Pöschel. Schur rings over Z_{2^{m}}. Akad. der Wiss. der DDR Inst. für Math., Preprint P-MATH-14/81 (1981), 1–30.

[3] M. H. Klin and R. Pöschel. The König problem, the isomorphism problem for cyclic graphs and the method of Schur rings. Algebraic methods in graph theory, Vol. I,II (Szeged 1978), Colloq. Math. Soc. János Bolyai 25 (1981), 405–434.

[4] M. Ch. Klin, R. Pöschel. Circulant graphs via Schur ring theory. Automorphism groups of circulant graphs on p^{m} vertices, p an odd prime. Manuscript.

[5] I. Kovács, M. Klin. Automorphism groups of circulant graphs on 2^{m} vertices. (In preparation.)

[6] I. Kovács. On automorphisms of circulant digraphs on p^{m} vertices, p an odd prime. Linear Alg. and its Appl. 356 (2002), 231–252.

[7] K. H. Leung, S. L. Ma. The structure of Schur rings over cyclic groups. J. Pure Appl. Algebra 66 (1990), 287–302.

[8] V. Liskovets, R. Pöschel. Counting circulant graphs of prime-power order by decomposing into orbit enumeration problems. Discr. Math. 214 (2000), 173–191.

[9] M. Muzychuk, M. Klin and R. Pöschel. The isomorphism problem for circulant graphs via Schur ring theory. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. Vol. 56 (2001), 241–264.

[10] I. Schur. Zur Theorie der einfach transitiven Permutationsgruppen. Sitzungsber. Preuss. Akad. Wiss. Phys.-Math. Kl. (1933), 598–623.

[11] W. R. Scott. Group Theory. Prentice-Hall, 1964.

[12] R. P. Stanley. Enumerative Combinatorics vol II. Cambridge University Press, Cambridge, 1999.

[13] H. Wielandt. Finite Permutation Groups. Academic Press, Berlin, 1964.

István Kovács University of Primorska, Department of Mathematics and Computer Science Cankarjeva 5, Koper 6000, Slovenia kovacs@pef.upr.si