THE NUMBER OF ADMISSIBLE SEQUENCES FOR INDECOMPOSABLE SERIAL RINGS

Joshua O. Hanes and Darren D. Wick

Abstract. We give a formula for the number of admissible sequences for indecomposable serial rings with n indecomposable projective modules whose minimum composition length is less than or equal to m. In particular, if n = m is prime, we show that the number of such admissible sequences is

\binom{2n − 1}{n} + \frac{1}{n}[(n − 1)^{2} − \binom{2n − 2}{n}].

1. Introduction. To each indecomposable serial ring (with unity) R there is associated a set {e_{1}, ⋯, e_{n}} of basic primitive idempotents and a set {Re_{1}, Re_{2}, ⋯, Re_{n}} of pairwise non-isomorphic indecomposable projective left R-modules, each having a unique composition series. Denoting the composition lengths of Re_{i} by c_{i} = c(Re_{i}), then the sequence c_{1}, c_{2}, ⋯, c_{n} is called an admissible sequence for R, and satisfies the following inequalities [1]:

2 ≤ c_{l} ≤c_{l−1} + 1 for l = 2, ⋯, n.  (1.1)
c_{1} ≤ c_{n} + 1.  (1.2)

The admissible sequence for a serial ring is unique, except for cyclic permutation of the indices. We have shown that if R has a simple projective module, then the number of possible admissible sequences of length n is b_{n−1}, the (n − 1)^{st} Catalan number [2]. In this paper we count the number of admissible sequences for all serial rings. We adopt the convention that \binom{s}{t} = 0 for all integers s < t and for all s < 0 or t < 0. Furthermore, we will refer to various combinatorial identities and have collected them in the appendix.

2. Counting Admissible Sequences.

\underline{Definition 2.1}. Let i, j, k be positive integers and δ denote the Kronecker delta. Define a_{i,j}^{k} as follows: a) For all i, k ≥ 1, a_{i,1}^{k} = 0.

b) For all k ≥ 1 and j ≥ 2, a_{1,j}^{k} = δ_{j,k}.

c) For all k ≥ 1 and i, j ≥ 2, a_{i,j}^{k} = ∑_{l≥j−1} a_{i−1,l}^{k}. We note that each of the sums in part c) above is finite by the following lemma.

\underline{Lemma 2.2}. For all i, k ≥ 1 and for all j ≥ 0, a_{i,i+k+j}^{k} = 0.
\underline{Proof}. We induct on i. For i = 1, we have
a_{1,k+j+1}^{k} = δ_{k+j+1,k} = 0 for all j ≥ 0.

Let i > 1. Then

a_{i,i+k+j}^{k} = ∑_{l≥(i−1)+k+j} a_{i−1,l}^{k}

and by the induction hypothesis, each term in this summation is zero.

\underline{Lemma 2.3}. For all i ≥ 1 and j, k ≥ 2, a_{i,j}^{k} equals the number of sequences c_{1}, c_{2}, ⋯, c_{i} with c_{1} = k and c_{i} = j that satisfy (1.1).

\underline{Proof}. Fix c_{1} = k and induct on i. The case i = 1 is trivial, as c_{1} = k is the only such sequence and a_{1,j}^{k} = δ_{j,k}. Let i > 1. Suppose c_{1}, c_{2}, ⋯, c_{i} satisfies (1.1) with c_{i} = j. Then clearly c_{1}, c_{2}, ⋯, c_{i−1} also satisfies (1.1). Conversely, if c_{1}, c_{2}, ⋯, c_{i−1} satisfies (1.1), then so does c_{1}, c_{2}, ⋯, c_{i} = j if and only if 2 ≤ j ≤ c_{i−1}+1. Thus, every sequence of length i satisfying (1.1) is obtained from a sequence of length i − 1 satisfying (1.1). In particular, the number of sequences c_{1}, c_{2}, ⋯, c_{i} = j satisfying (1.1) is equal to the number of sequences c_{1}, c_{2}, ⋯, c_{i−1} satisfying (1.1) with c_{i−1} ≥ j − 1. By induction, the latter number is ∑_{l≥j−1} a_{i−1,l}^{k} which by definition is a_{i,j}^{k}.

We next give a closed form of a_{i,j}^{k}.

\underline{Lemma 2.4}. For all i, j, k ≥ 2, we have

a_{i,j}^{k} = \binom{2i − j + k − 3}{i − j + k − 1} − \binom{2i − j + k − 3}{i + k − 2}.

\underline{Proof}. We induct on i. Let i = 2. Then

a_{2,j}^{k} = ∑_{l≥j−1} a_{1,l}^{k} = ∑_{l≥j−1} δ_{l,k} = \{ \begin{matrix}1 & if j ≤ k + 1 \\ 0 & else. \end{matrix}

On the other hand,

\binom{2i − j + k − 3}{i − j + k − 1} − \binom{2i − j + k − 3}{i + k − 2} = \binom{k − j + 1}{k − j + 1} − \binom{k − j + 1}{k}.

But since j ≥ 2, we have that k − j + 1 ≤ k − 1 < l so that \binom{k−j+1}{k} = 0. Furthermore, \binom{k−j+1}{k−j+1} = 1 if and only if j ≤ k + 1, and is zero otherwise. Let i > 2. Then by the induction hypothesis,

\begin{aligned}a_{i,j}^{k} = ∑_{l≥j−1} a_{i−1,l}^{k} & = ∑_{l≥j−1} \binom{2(i − 1) − l + k − 3}{i − 1 − l + k − 1} − \binom{2(i − 1) − l + k − 3}{i − 1 + k − 2} \\ & = ∑_{l≥j−1} \binom{2i + k − l − 5}{i + k − l − 2} − ∑_{l≥j−1} \binom{2i + k − l − 5}{i + k − 3}. \end{aligned}

Let A denote the first sum immediately above, and B denote the second sum. Since i ≥ 3 we have that 2i + k − l − 5 ≥ i + k − l − 2. Furthermore, the last non-zero term in the summation A is when i + k − l − 2 = 0 or l = k + i − 2. We then apply identity (A.1) with s = 2i + k − (j − 1) − 5, t = i + k − (j − 1) − 2 and p = l − (j − 1) to get that

\begin{matrix}A = & ∑_{l=j−1}^{i+k−2} \binom{2i + k − l − 5}{i + k − l − 2} \\ = & ∑_{p=0}^{i+k−(j−1)−2} \binom{2i + k − 5 − (j − 1) − p}{i + k − 2 − (j − 1) − p} \\ = & \binom{2i + k − (j − 1) − 5 + 1}{i + k − (j − 1) − 2} = \binom{2i − j + k − 3}{i − j + k − 1}. \end{matrix}

Next, we note that the only non-zero terms in the summation B occur when 2i + k − l − 5 ≥ i + k − 3 or k ≤ i − 2, so that

B = ∑_{l=j−1}^{i−2} \binom{2i + k − l − 5}{i + k − 3}.

We first consider when i ≤ j, in which case the summation above is empty. But if i ≤ j, we also have that 2i − j + k − 3 < i + k − 2 and thus, \binom{2i−j+k−3}{i+k−2} = 0. Next, consider the case when i > j. We then apply identity (A.2) to B with s = 2i + k − (j − 1) − 5, t = i + k − 3 and p = l − (j − 1). Thus, we have

\begin{matrix}B = & ∑_{l=j−1}^{i−2} \binom{2i + k − l − 5}{i + k − 3} \\ = & ∑_{p=0}^{i−j−1} \binom{2i + k − 5 − (j − 1) − p}{i + k − 3} \\ = & \binom{2i + k − (j − 1) − 5 + 1}{i + k − 3 + 1} = \binom{2i − j + k − 3}{i + k − 2}. \end{matrix}

Thus, we see that A − B gives the desired result.

The next lemma will be used in section 3.

\underline{Lemma 2.5}. Let i ≥ 2. Then for all r, 1 ≤ r ≤ i − 1,

∑_{l=2}^{i} a_{i−r,i}^{l} = \binom{2i − 2r − 2}{i − r − 1}.

\underline{Proof}. First consider the case when r = i − 1. Then

∑_{l=2}^{i} a_{i−r,i}^{l} = ∑_{l=2}^{i} a_{1,i}^{l} = a_{1,i}^{i} = 1.

Conversely,

\binom{2i − 2r − 2}{i − r − 1} = \binom{2i − 2(i − 1) − 2}{i − (i − 1) − 1} = \binom{0}{0} = 1.

Let 1 ≤ r ≤ i − 2. By Lemma 2.4 we have that

\begin{matrix}∑_{l=2}^{i} a_{i−r,i}^{l} = & ∑_{l=2}^{i} [\binom{2i − 2r − i + l − 3}{i − r − i + l − 1} − \binom{2i − 2r − i + l − 3}{i − r + l − 2}] \\ = & ∑_{l=2}^{i} [\binom{i − 2r + l − 3}{l − r − 1} − \binom{i − 2r + l − 3}{i − r + l − 2}]. \end{matrix}

But since r ≥ 1, we have i − 2r + l − 3 ≤ i − r + l − 4 ≤ i − r + l − 2 so that all of the terms above of the form \binom{i−2r+l−3}{i−r+l−2} are zero. Furthermore, if l < r + 1, then l − r − 1 < 0 in which case all terms above of the form \binom{i−2r+l−3}{l−r−1} are zero. Therefore, letting p = l − r − 1,

∑_{l=2}^{i} a_{i−r,i}^{l} = ∑_{l=r+1}^{i} \binom{i − 2r + l − 3}{l − r − 1} = ∑_{p=0}^{i−r−1} \binom{i − r − 2 + p}{p}.

Finally, we apply identity (A.1) with s = 2i − 2r − 3 and t = i − r − 1 to get the desired result

∑_{l=2}^{i} a_{i−r,i}^{l} = ∑_{p=0}^{i−r−1} \binom{i − r − 2 + p}{p} = \binom{2i − 2r − 2}{i − r − 1}.

For each k ≥ 2 and n ≥ 1, let the set of all admissible sequences c_{1}, c_{2}, ⋯, c_{n} with c_{1} = k be denoted by σ_{n}^{k}. In order to satisfy (1.2) we must have that c_{n} ≥ c_{1} − 1 = k − 1. Thus,

|σ_{n}^{k}| = ∑_{j≥k−1} a_{n,j}^{k} = a_{n+1,k}^{k}.

For each m ≥ 2 and n ≥ 1, let T_{n,m} denote the set of all admissible sequences c_{1}, c_{2}, ⋯, c_{n} with 2 ≤ c_{1} ≤ m. Then

T_{n,m} = ⋃_{l=2}^{m} σ_{n}^{l}

and

|T_{n,m}| = | ⋃_{l=2}^{m} σ_{n}^{l}| = ∑_{l=2}^{m} a_{n+1,l}^{l}.

\underline{Corollary 2.6}. Let m ≥ 2 and n ≥ 1. Then

|T_{n,m}| = (m − 1)\binom{2n − 1}{n} − ∑_{l=2}^{m} \binom{2n − 1}{n + l − 1}.

\underline{Proof}. Applying Lemma 2.4 we get that

|T_{n,m}| = ∑_{l=2}^{m} a_{n+1,l}^{l}

= ∑_{l=2}^{m} [\binom{2(n + 1) − l + (l − 3)}{n + 1 − l + l − 1} − \binom{2(n + 1) − l + (l − 3)}{n + 1 + (l − 2)}]

= ∑_{l=2}^{m} [\binom{2n − 1}{n} − \binom{2n − 1}{n + l − 1}]

= (m − 1)\binom{2n − 1}{n} − ∑_{l=2}^{m} \binom{2n − 1}{n + l − 1}.

\underline{Corollary 2.7}. Let m ≥ 2 and n ≥ 1. Then for m ≥ n

|T_{n,m}| = m\binom{2n − 1}{n} − 2^{2n−2}.

\underline{Proof}. Whenever l > n we have that n + l − 1 > 2n − 1 so that \binom{2n−1}{n+l−1} = 0. We then apply identity (A.3) to Corollary 2.6 to obtain

|T_{n,m}|

= (m − 1)\binom{2n − 1}{n} − ∑_{l=2}^{m} \binom{2n − 1}{n + l − 1}

= (m − 1)\binom{2n − 1}{n} − ∑_{l=2}^{n} \binom{2n − 1}{n + l − 1}

= (m − 1)\binom{2n − 1}{n} − [2^{2n−2} − \binom{2n − 1}{n}] = m\binom{2n − 1}{n} − 2^{2n−2}.

3. Cyclic Permutations. Since the admissible sequence for a serial ring is unique only up to cyclic permutation, we next consider the equivalence classes of the elements of T_{n,m} under cyclic permutation. Notice that T_{n,m} does not contain all cyclic permutations of its own elements (e.g. a = m, m+1, ⋯, m+n−1 ∈ T_{n,m} but every non-trivial cyclic permutation of a is not in T_{n,m}). Thus, we enlarge T_{n,m} to include these elements as follows:

For m ≥ 2 and n ≥ 1, let C_{n} = {α_{0}, α_{1}, ⋯, α_{n−1}} denote the cyclic group of order n acting on the set T_{n,m} as follows: Let a = c_{1}, c_{2}, ⋯ c_{n} ∈ T_{n,m}, then α_{0}(a) = a and for 1 ≤ i ≤ n − 1, α_{i}(a) = c_{i+1}, ⋯ c_{n}, c_{1}, ⋯ c_{i}. Let S_{n,m} = {α_{i}(a) : a ∈ T_{n,m}, 0 ≤ i ≤ n − 1}. Thus, S_{n,m} is the set of all cyclic permutations of the elements of T_{n,m} and T_{n,m} ⊂ S_{n,m}.

Regarding two admissible sequences as equivalent if one is a cyclic permutation of the other, we see that the number of equivalence classes of admissible sequences is just the number of orbits of C_{n} on S_{n,m}. We denote this number of equivalence classes by O_{n,m}. We first consider the size of the set S_{n,m}. Also, note that if a = c_{1}, ⋯ c_{n} ∈ S_{n,m}, then min{c_{1}, ⋯ c_{n}} ≤ m.

\underline{Lemma 3.1}. Let m ≥ 2 and n ≥ 1. Then

|S_{n,m} \ T_{n,m}| = ∑_{k=1}^{n−1} [k|T_{k,2}|( ∑_{i=2}^{m} a_{n−k,m}^{i})].

\underline{Proof}. Let a = c_{1}, ⋯, c_{n} ∈ T_{n,m}. Then all cyclic permutations of a are in T_{n,m} if and only if c_{i} ≤ m for all i, 1 ≤ i ≤ n. Thus, there exists a cyclic permutation of a that is not in T_{n,m} if and only if there exists j with 1 ≤ j ≤ n − 1 such that

i) c_{j} = m. ii) c_{j+1} = m + 1. iii) There exists k with 1 ≤ k ≤ n − j so that c_{i} > m for all i with

j + 1 ≤ i ≤ j + k. iv) c_{[j+k+1]} ≤ m (where [p] denotes the least positive residue of p modulo

n). Without loss of generality, we permute a and consider a′ = α_{j}(a), where

i) a′ = a_{1}, a_{2} with a_{1} a subsequence of length k and a_{2} a subsequence of length n − k.

ii) a_{1} = d_{1}, ⋯, d_{k} with all d_{i} > m and d_{1} = m + 1. iii) a_{2} = d_{k+1}, ⋯ d_{n} ∈ T_{n−k,m} and d_{n} = m. iv) 1 ≤ k ≤ n − 1. Clearly, there exist k permutations of a′ (and hence of a) that are not in T_{n,m}, namely α_{i}(a′) for 0 ≤ i ≤ k − 1. Moreover, every element of S_{n,m} \ T_{n,m} is of the form α_{i}(a′) for some i, 0 ≤ i ≤ k − 1, and for some a′ as above. Thus, the number of sequences in S_{n,m} \ T_{n,m} is found by multiplying the number of sequences of the form a′ by k. The number of sequences of the form a_{2} above is ∑_{i=2}^{m} a_{n−k,m}^{i}. Let U_{k} be the set of sequences of the form a_{1} above. Then there is a bijection f: T_{k,2} → U_{k}, where f(d_{1}, ⋯ d_{k}) = d_{1} + m − 1, ⋯, d_{k} + m − 1. Thus, |U_{k}| = |T_{k,2}|. Multiplying by the k cyclic permutations of a′ that are not in T_{n,m} and summing over all k, 1 ≤ k ≤ n − 1, gives the desired result.

We note that by Corollary 2.6 we have

|T_{k,2}| = \binom{2k − 1}{k} − \binom{2k − 1}{k + 1} = \frac{1}{k + 1}\binom{2k}{k}

which is the k^{th} Catalan number. Applying this to Lemma 3.1 and Corollary 2.6 we have the following corollary.

\underline{Corollary 3.2}. Let m ≥ 2 and n ≥ 1. Then

\begin{matrix}|S_{n,m}| = & |T_{n,m}| + |S_{n,m} \ T_{n,m}| \\ = & (m − 1)\binom{2n − 1}{n} − ∑_{k=2}^{m} \binom{2n − 1}{n + k − 1} + ∑_{k=1}^{n−1} [\frac{k}{k + 1}\binom{2k}{k}( ∑_{i=2}^{m} a_{n−k,m}^{i})]. \end{matrix}

We consider the special case when n = m ≥ 2. Applying Corollary 3.2, Lemma 2.5, and Corollary 2.7, we have the following corollary.

\underline{Corollary 3.3}. Let n ≥ 2. Then

|S_{n,n}| = n\binom{2n − 1}{n} − 2^{2n−2} + ∑_{k=1}^{n−1} \frac{k}{k + 1}\binom{2k}{k}\binom{2n − 2k − 2}{n − k − 1}.

\underline{Lemma 3.4}. Let n ≥ 2. Then

|S_{n,n}| = (n − 1)\binom{2n − 1}{n}.

\underline{Proof}. We first note that

\frac{k}{k + 1}\binom{2k}{k} = \binom{2k}{k − 1}

and that

\binom{2k}{k} − \binom{2k}{k − 1} = \frac{1}{k + 1}\binom{2k}{k}.

We then apply (A.4) and (A.5) to Corollary 3.3 to obtain

|S_{n,n}| = n\binom{2n − 1}{n} − 2^{2n−2} + ∑_{k=1}^{n−1} \frac{k}{k + 1}\binom{2k}{k}\binom{2n − 2k − 2}{n − k − 1}

= n\binom{2n − 1}{n} − ∑_{k=1}^{n−1} \binom{2k}{k}\binom{2(n − k − 1)}{n − k − 1} + ∑_{k=1}^{n−1} \binom{2k}{k − 1}\binom{2(n − k − 1)}{n − k − 1}

= n\binom{2n − 1}{n} − ∑_{k=0}^{n−1} [\binom{2k}{k} − \binom{2k}{k − 1}]\binom{2(n − k − 1)}{n − k − 1}

= n\binom{2n − 1}{n} − ∑_{k=0}^{n−1} \frac{1}{k + 1}\binom{2k}{k}\binom{2(n − k − 1)}{n − k − 1}

= n\binom{2n − 1}{n} − \binom{2(n − 1) + 1}{n − 1 + 1}

= (n − 1)\binom{2n − 1}{n}.

4. Orbits of C_{n} on S_{n,m}. For each α ∈ C_{n}, let fix(α) = {a ∈ S_{n,m} : α(a) = a}. We note that for the identity α_{0}, fix(α_{0}) = S_{n,m}. For n ≥ 1 and m ≥ 2, we apply Burnsides Theorem to get

O_{n,m} = \frac{1}{|C_{n}|} ∑_{α∈C_{n}} fix(α) = \frac{1}{n}[|S_{n,m}| + ∑_{α∈C_{n}\\{α_{0}\}} |fix(α)|].  (4.1)

Note that for m = 1, we must include the number of admissible sequences of length n with c_{1} = 1. In this case, since the rings are indecomposable with a simple projective module, no cyclic permutations are needed, and the number of such sequences is the (n − 1)^{st} Catalan number, b_{n−1} = \frac{1}{n} \binom{2n−2}{n−1} [2]. Thus, for n ≥ 1 and m ≥ 2, the total number of equivalence classes of admissible sequences is

b_{n−1} + O_{n,m} = \frac{1}{n}[\binom{2n − 2}{n − 1} + |S_{n,m}| + ∑_{α∈C_{n}\\{α_{0}\}} |fix(α)|].  (4.2)

5. Special Case n = m is Prime. We consider the special case when n = m is prime. Then for each α ∈ C_{n} \ {α_{0}}, the only elements of fix(α) are the sequences k, k, ⋯ k where 2 ≤ k ≤ n, so that |fix(α)| = n − 1. Applying this together with the Lemma 3.4 and (4.2), we have that the number of equivalence classes of admissible sequences is

b_{n−1} + O_{n,m} = \frac{1}{n}[\binom{2n − 2}{n − 1} + (n − 1)\binom{2n − 1}{n} + (n − 1)^{2}]. (5.1)

Simplifying (5.1), we have the following theorem.

\underline{Theorem 5.2}. Let n be prime. Then the number of equivalence classes of admissible sequences for indecomposable serial rings with n indecomposable projective modules whose minimum composition length is less than or equal to n is

\binom{2n − 1}{n} + \frac{1}{n}[(n − 1)^{2} − \binom{2n − 2}{n}].

Appendix.

∑_{k=0}^{t} \binom{s − k}{t − k} = ∑_{k=0}^{t} \binom{s − t + k}{k} = \binom{s + 1}{t} for s ≥ t ≥ 0. ([3] pg. 7) (A.1)

∑_{k=0}^{s−t} \binom{s − k}{t} = \binom{s + 1}{t + 1} for s ≥ t ≥ 0.  ([3] pg. 7) (A.2)

∑_{k=1}^{s} \binom{2s − 1}{s + k − 1} = 2^{2s−2} for s ≥ 1.  ([3] pg. 34) (A.3)

∑_{k=0}^{s} \binom{2k}{k}\binom{2(s − k)}{s − k} = 2^{2s} for s ≥ 0.  ([3] pg. 130) (A.4)

∑_{k=0}^{s} \frac{1}{k + 1}\binom{2k}{k}\binom{2(s − k)}{s − k} = \binom{2s + 1}{s + 1} for s ≥ 0.  ([3] pg. 120) (A.5)

\underline{References}

1. F. W. Anderson and K. R. Fuller, Rings and Categories of Modules, Springer-Verlag, New York and Berlin, 2nd ed., 1992.

2. J. O. Hanes and D. D. Wick, “The Number of Admissible Sequences for Indecomposable Serial Rings with a Simple Projective Module,” Proceedings of the Louisiana-Mississippi Section of the Mathematical Association of America, Spring 2000.

3. J. Riordan, Combinatorial Identities, John Wiley and Sons, Inc., New York, London and Sydney, 1968.

Joshua O. Hanes Department of Mathematics University of Mississippi Oxford, MS 38677 email: jhanes@olemiss.edu

Darren D. Wick Department of Mathematics and Computer Science Ashland University Ashland, OH, 44805 email: dwick@ashland.edu