%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%     last update: 29/12/2003       % 
%     revisted:    16/06/2005       %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
\documentclass[12pt,reqno]{amsart}
\oddsidemargin=0in
\evensidemargin=0in
\textwidth=15.3truecm
\headheight=10truept
\headsep=10truept
\topmargin=0truein
\textheight=22.2truecm
%\baselineskip= 18pt
%\usepackage{amsmath}
\usepackage{amssymb,latexsym}
%\usepackage{amsthm}
\newcommand{\un}{\underline}
\newcommand{\ov}{\overline}
\newcommand{\cay}{\Gamma}
\newcommand{\aut}{\mbox{Aut}}
\newcommand{\Z}{{\mathbb Z}}
\newcommand{\N}{{\mathbb N}}
\newcommand{\Sr}{{\mathfrak S}}
\newcommand{\cS}{{\mathcal S}}
\newcommand{\laa}{\langle}
\newcommand{\raa}{\rangle}
\newcommand{\veps}{\varepsilon}
\newcommand{\uv}{\vec{u}} 
\renewcommand{\c}{\tilde{c}}
\newcommand{\ls}{\tilde{s}}
\newcommand{\lsg}{\tilde{S}}
\newcommand{\er}{\rightarrow}
\newcommand{\eu}{\uparrow}
\newcommand{\ed}{\nearrow}
\renewcommand{\proof}{\noindent {\bf Proof.}\ }
\newcommand{\eproof}{\hfill $\Box$ \smallskip }

\newtheorem{theo}{Theorem}[section] 
\newtheorem{ex}[theo]{Example} 
\newtheorem{prop}[theo]{Proposition} 
\newtheorem{de}[theo]{Definition} 
\newtheorem{cor}[theo]{Corollary} 
\begin{document}


\title{The number of indecomposable Schur rings over a cyclic 2-group} 
\author{I.~Kov\'acs*} 
\thanks{*This research was partially 
supported by grant OTKA T-043758, and by a grant 
provided by the University of  P\'ecs.}
\date{}

\begin{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\"oschel 
[{\it Discr.\ Math.} {\bf 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\"oder numbers. The result is 
obtained after the initial problem is turned into a lattice path problem.  
\end{abstract} 
\maketitle 

%First page headline in AmS-TeX for S\'eminaire Lotharingien de Combinatoire
\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8
\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 51 \rms (2005), Article~B51h\hfill}
\def\thepage{}

\section{Introduction}

Let $H$ be a finite group with identity element $e$. Denote by $\Z[H]$ the 
{\em group ring} of all formal sums $\sum_{h \in H}a_hh$, $a_h \in \Z$, $h \in H$. 
For $T \subseteq H$, the group ring element $\sum_{h \in T}h$ will be denoted 
by $\un{T}$. Such an element is also called a \emph{simple quantity}. 
The \emph{transpose} of $\alpha=\sum_{h \in H}a_hh$ is defined as  
$\alpha^\top=\sum_{h \in H}a_h(h^{-1})$. 
A subring $\Sr$ of $\Z[H]$ is called a \emph{Schur ring over $H$} 
(for short \emph{S-ring}) if it is generated as 
a module over $\Z$ by the simple quantities $\un{T}_1,\ldots,\un{T}_r$ 
such that they satisfy the axioms:   
\begin{itemize}
\item $T_1=\{e\}$, $T_i \cap T_j=\emptyset$ for all $i \neq j$,  
\item $\sum_{i=1}^{r}\un{T_i}=\un{H}$,  
\item for each $i \in \{1, \ldots, r\}$ there exists some 
$j \in \{1, \ldots, r\}$ such that $\un{T_i}^\top=\un{T_j}$.
\end{itemize} 
The sets $T_i$ are called the \emph{basic sets} of $\Sr$. 
We will denote by $B(\Sr)$ the set of all basic sets of $\Sr$. 

Trivial examples for S-rings are provided 
by the full group ring $\Z[H]$, and the module generated by the basic sets 
$\{e\}$ and $H\setminus\{e\}$. The latter one is also called the \emph{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 \cite{sch}. Later it was developed to 
a powerful tool in group theory, see \cite{sco,w}.  
\medskip 

It was observed later that S-rings can also be applied in algebraic combinatorics. 
For a given subset $S\subseteq H$, the \emph{Cayley digraph} of $H$ with respect to $S$ is 
defined as the digraph $(V,E)$, where $V=H$ and $E=\{(h,hs):\, h\in H,\, s\in S\}$. 
Cayley digraphs of cyclic groups are also called \emph{circulant digraphs}. 
From now on $Z_n$ will denote a cyclic group of order $n$. 
M.~Klin and R.~P\"oschel started an approach based on S-rings to study circulant digraphs, see \cite{kp1}. 
For a recent survey on this approach, see \cite{mkp}. 
\medskip


Let $\Sr$ be an S-ring over $Z_n$. 
$\Sr$ is called \emph{wreath-decomposable} (or shortly 
\emph{decomposable}), if there is a nontrivial, proper subgroup 
$H< Z_n$ such that for every basic set $T$, $T\subset H$ or  
$T=\bigcup_{h\in T}Hh$. Otherwise, $\Sr$ is called \emph{indecomposable}. 
If an S-ring is decomposable, then it can be obtained as 
the wreath product of two smaller S-rings, see \cite{mkp}. 
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 \cite{kp2,k}. 


%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL I. KOV\'ACS}{\SMALL THE NUMBER OF
INDECOMPOSABLE SCHUR RINGS OVER A CYCLIC 2-GROUP}
%
%

In this paper we consider the problem of counting the number of indecomposable rings. 
For $m\in \N$ and a prime $p$, we set the notation: 
$$I(m,p)=\#\{ \mbox{ indecomposable S-rings over }Z_{p^m}\}.$$ 

It was shown in \cite{lp} that if $p>2$, then 
$$ I(m,p)=\delta(p-1)c_{m-1},$$ 
where $\delta(p-1)$ is equal to the number of positive divisors of $(p-1)$, and for 
$k\in\N_0$, $c_k$ is the $k$-th {\it Catalan number}: 
$c_k=\frac{1}{k+1}{\binom {2k} k}$,   
cf.\ \cite[page 172]{st}. 
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 {\it Schr\"oder numbers}. 
For $k\in \N_0$, the $k$-th Schr\"oder number is: 
$s_k=\sum_{k=0}^{n}\frac{1}{k+1}{\binom {2k} k}
{\binom {n+k} {2k}}$, cf.~\cite{st}. 
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.

\begin{theo}\label{main} 
If $m\geq 3$ then  
$$I(m,2)=1+\frac{1}{3\sqrt{17}}\sum_{k=0}^{m-1}a_{m-1-k}
\Big[\, \Big(\frac{11+3\sqrt{17}}{4}\Big)^{k+1}-
\Big(\frac{11-3\sqrt{17}}{4}\Big)^{k+1}\, \Big],$$ 
where $a_0=2$, $a_1=-9$ and 
$$a_i=(2c_i-4c_{i-1})+(s_i-2s_{i-1})-3\sum_{j=0}^{i-1}c_{i}s_{i-1-j},\quad  
i \geq 2.$$ 
Here, $c_i$ and $s_i$ are the $i$-th Catalan and Schr\"oder number, respectively. 
\end{theo} 

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


\begin{center} \begin{tabular}{|l|l|l|l|l|l|l|l|l|l|l|}
\hline 
$m$      & $1$ & $2$ & $3$  & $4$  & $5$  & $6$   & $7$    & $8$     & $9$     & $10$  \\ 
\hline
$I(m,2)$ & $1$ & $2$ & $5$  & $16$ & $63$ & $271$ & $1225$ & $5726$  & $27461$ & $134461$ \\ \hline
\end{tabular} \end{center}\medskip  

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

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 \cite{gnp,knp}. 
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 \cite{kk}). 
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 of length $m$ is in one-to-one correspondence 
with a nicely described set of paths in the $(m-1)\times (m-1)$ plane integer lattice consisting of 
steps $(1,0)$, $(0,1)$, and $(1,1)$. Theorem~\ref{main} will be settled in Section~5 based on 
this correspondence. 

\section{S-rings over cyclic 2-groups} 

Throughout the section $n=2^m$ and $m\geq 2$ are assumed. 
Let $Z_n=\laa g\raa$. Denote by $H_i$ the subgroup of $Z_n$ of order $2^i$, $i=0,\dots,m$, 
i.e., $H_i=\laa g^{2^{m-i}}\raa$.   
We set the notation $L_i=H_{m-i}\setminus H_{m-1-i}$, $i=0,\dots,m-1$, and $L_m=\{e\}$.  
\medskip 

Let $\Sr$ be an S-ring over $Z_n$. Next we describe its basic sets following \cite{gnp,knp}.  
Let $T\in B(\Sr)$, $T\neq\{e\}$. It was proved in 
\cite{gnp,knp} (cf.\ also \cite{lm}) that there are two main possibilities for 
$T$: either $T=H_j\setminus H_k$ for some $0\leq k<j\leq m$, or 
$T$ is contained in some set $L_i$. 
The \emph{basic relation} $\theta$ of $\Sr$ is an equivalence relation which is defined 
on the set $\{0,1,\dots,m-1\}$ in such a manner that it has 
equivalence classes of the form 
$\{i,\dots,i+j\}$, $i\in \{0,\dots,m-1\}$, $j\in \{0,\dots,m-1-i\}$. 
The set $\{i,\dots,i+j\}$ with $j>0$ is an equivalence class of $\theta$ if and only if  
$H_{m-i}\setminus H_{m-i-j-1}$ is a basic set of $\Sr$. 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 $\Sr$. 

Assume that $T\subseteq L_i$. According to the classical theory of S-rings, see \cite{w}, 
the basic sets of $\Sr$ contained in $L_i$ are the orbits of 
some subgroup $K\leq \aut(Z_n)$. Consequently, $T$ can be obtained as one of the orbits 
of $K$. For every $i\in \{0,\dots,m-1\}$, denote by $K_i$ the maximal subgroup of 
$\aut(Z_n)$ such that the sets $L_i\cap T$, $T\in B(\Sr)$ are orbits of 
$K_i$. We refer to the groups $K_0,\dots,K_{m-1}$ as the \emph{basic groups} of $\Sr$.  
\medskip

It follows from the above observations that $\Sr$ is uniquely determined by 
its basic relation and basic groups. In \cite{gnp,knp} the basic relation together with 
the basic groups were called the \emph{S-system} of $\Sr$. 
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\mapsto g^{i\cdot k}:\, 1\leq k<n,\ \gcd(k,n)=1\}$. 
In what follows, we identify 
$\aut(Z_n)$ with the multiplicative group modulo $n$ of elements $1\leq k\leq n$, $\gcd(k,n)=1$. It is 
well-known that $\aut(Z_{2^m})=\laa -1,5\raa$. (Operations are taken modulo $n=2^m$.) 
The subgroups of $\aut(Z_n)$ are   
\begin{eqnarray} 
G_{3i+1}& = &\{\pm 1+2^{i+2}k\,\mid\, 0\leq k<2^{m-i-2}\}\quad  (i=0,\dots,m-2), \nonumber \\ 
G_{3i+2}& = &\{1+2^{i+2}k\,\mid\, 0\leq k<2^{m-i-2}\}\quad (i=0,\dots,m-2), \label{group} \\ 
G_{3i}& = &\{(-1)^k+2^{i+1}k\,\mid\, 0\leq k<2^{m-i-1}\}\quad (i=1,\dots,m-2). \nonumber
\end{eqnarray} 
In fact, it is not hard to see that $G_{3i+1}=\laa -1,5^{2^i}\raa$, $G_{3i+2}=\laa
5^{2^i}\raa$, and 
$G_{3i}=\laa -5^{2^{i-1}}\raa$. 
The S-rings over $Z_{2^m}$ ($m\geq 2$)  are characterized in the following theorem.

\begin{theo} {\rm \cite{gnp, knp}} \label{t1} \\ 
Let $\theta$ be a relation on $\{0,\dots,m-1\}$, and let  
$K_i\leq \aut(Z_n)$, $i=0,\dots,m-1$ $(m\geq 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: 
\begin{enumerate} 
\item[{(i)}] Every equivalence class of $\theta$ is of the form $\{i,\dots,i+j\}$, 
\item[{(ii)}] If $\{i,\dots,i+j\}$ is an equivalence class of 
$\theta$ with $j>0$, then $K_i=K_{i+1}=\dots=K_{i+j}=G_1$, and 
$K_{i-1}=G_1$, $K_{i-2}\in \{G_1,G_2\}$ {\em(}if $i=0$ or $i=1$, then delete the conditions where 
negative indices appear{\em)}, 
\item[{(iii)}] $K_{m-1}=G_1$, $K_{m-2}\in \{G_1,G_2\}$,
\item[{(iv)}] Let $1\leq j\leq m-2$. If $K_j=G_{3i+1}$ or $K_j=G_{3i+3}$ 
for some $0\leq i\leq m-2$, then 
\[ K_{j-1}\in \{G_2\}\,\cup\, \{G_{3s+1}\,\mid\, 0\leq s\leq i+1\}\, 
\cup\, \{G_{3r+3}\,\mid\, 0\leq r\leq i\}, \]
If $K_j=G_{3i+2}$ for some $0\leq i\leq m-2$, then 
\[ K_{j-1}\in \{G_1\}\,\cup\, \{G_{3s+2}\,\mid\, 0\leq s\leq i+1\}. \]
\end{enumerate} 
\end{theo} 

Denote by $\cS(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~\ref{main}) will be 
responsible for the trivial S-ring. 
In the rest of this section it will be shown: 
if $\Sr$ is a nontrivial, indecomposable S-ring over $Z_{2^m}$, $m\geq 2$, then 
its basic relation is equal to  the identity relation $\omega_m$ on 
$\{0,\dots,m-1\}$, i.e., $\omega_m$ consists of singleton classes. 
We introduce the notation $\cS^*(m)$ for the collection of 
S-rings over $Z_{2^m}$ that have basic relation $\omega_m$.   
We remark that not all members of $\cS^*(m)$ are indecomposable. 
The description of the indecomposable rings will be completed in 
the  next section. 
\medskip 

We introduce the functions $f_i:\cS(m)\rightarrow\Z$,
$i=0,\dots,m-1$, which act on an $\Sr\in\cS(m)$ by
$$f_i(\Sr)=\max\{ k:\,  H_kg^{2^i}\subseteq T\cap L_i,\, T\in B(\Sr)\}.$$ 
In particular, if $T'$ is a basic set of $\Sr$ which is contained in $L_i$, then  
$f_i(\Sr)$ is the maximal number $k$ such that $T'$ is the union of $H_k$-cosets. 
The value $f_i(\Sr)$ can be calculated from the basic group $K_i$ of $\Sr$ 
by using (\ref{group}). We have      
\begin{equation} \label{fi}
f_i(\Sr)=\left\{ \begin{array}{rr}m-2-a-i, & \mbox{if }K_i=G_{3a+b}\neq G_1,  \\
m-1-i, & \mbox{if }K_i=G_1. \end{array}\right. 
\end{equation} 

\begin{prop}\label{p21}
Let $\Sr$ be an S-ring over $Z_{2^m}$ having basic groups $K_0,\dots,K_{m-1}$.  
If $K_1\neq G_1$, then $f_0(\Sr) \geq f_1(\Sr)$. 
\end{prop}  
\proof Let $K_1=G_{k}$, $k=3a+b$. Since we assumed $k>1$, by (\ref{fi})  
we have
$$f_1(\Sr)=m-3-a.$$
Let $K_0=G_{k'}$, $k'=3a'+b'$. Because of Theorem~\ref{t1}(iv),
we have $a'\leq a+1$. 
If $k'=1$, then $f_0(\Sr)=m-1$, which is clearly larger than 
$f_1(\Sr)$. If $k'> 1$, then  (\ref{fi}) and $a'\leq a+1$ imply  
$$f_0(\Sr)=m-2-a'\geq m-3-a=f_1(\Sr).$$ 
\eproof


\begin{prop} \label{p22} 
If $\Sr$ is a nontrivial, indecomposable S-ring over $Z_{2^m}$, then its 
basic relation is $\omega_m$. 
\end{prop} 
\proof Let $\Sr$ have basic relation $\theta$ and let it have basic groups $K_0,\dots,K_{m-1}$. 
We are going to show that if $\theta\neq\omega_m$, then $\Sr$ is  decomposable. 
We proceed by induction on $m$. The cases $m\leq 3$ can be checked
directly, hence we assume that $m\geq 4$. 

If $K_0=G_1$, then there is a subgroup $H_k$ such that $Z_n\setminus H_k$ is a basic set 
of $\Sr$. If $k=0$, then $\Sr$ is the trivial S-ring. This possibility is excluded, hence $k>0$, 
and by definition it follows that $\Sr$ is decomposable. 
\medskip

Assume that $K_0\neq G_1$. Then $\un{H_{m-1}}\in \Sr$, hence  
we can consider the S-ring over $H_{m-1}$ generated by the basic sets of $\Sr$ contained in $H_{m-1}$. 
Denote this S-ring by $\Sr^*$. It follows that the basic relation of 
$\Sr^*$ is equal to $\theta^*=\{(i,j):\, (i+1,j+1)\in \theta\}$. 
Thus $\theta^*\neq \omega_{m-1}$, and, 
because of the induction hypothesis, $\Sr^*$ is decomposable. 
This means by definition that there is some $1\leq r\leq m-2$ such that every basic set of 
$\Sr^*$ (which are the basic sets of $\Sr$ contained in $H_{m-1}$) not contained in $H_r$ 
is the union of some $H_r$-cosets. This implies that $f_1(\Sr)\geq r$. 
A basic set in $L_0=H_m\setminus H_{m-1}$ is the union of $H_d$-cosets, where 
$d=f_0(\Sr)$. Thus if $d\geq r$, then $\Sr$ is decomposable.  
In case $K_1\neq G_1$ this follows from Proposition~\ref{p21}, for $d=f_0(\Sr)\geq f_1(\Sr)\geq r$. 
\medskip 

Therefore, it remains to consider the case $K_1=G_1$. 
The assertion that
$L_1=H_{m-1}\setminus H_{m-2}$ is not a basic set is equivalent to saying that $\theta$ has 
equivalence class $\{1,\dots,i\}$ with $i>1$. According to 
Theorem~\ref{t1}(ii), we have $K_0=G_1$, i.e., 
$d=m-1$, which clearly exceeds $r$ and, consequently, $\Sr$ is decomposable.  
Assume finally that $L_1$ is a basic set, i.e., $\un{H_{m-2}}\in \Sr^*$. 
This gives $K_0=G_k$ with $k\leq 4$, see Theorem~\ref{t1}(iv). 
Thus, by (\ref{fi}),
\begin{equation}\label{e21} d=f_0(\Sr) \geq m-3.\end{equation} 
As before, the S-ring over $H_{m-2}$ which is generated by the basic sets of $\Sr$ contained in $H_{m-2}$ 
is decomposable because of the induction hypothesis. This implies  
that every basic set of $\Sr$ which is contained in $H_{m-2}\setminus H_s$ is the union of 
$H_s$-cosets for some $1\leq s\leq m-3$. Since $d\geq m-3\geq s$, 
see (\ref{e21}), and since $L_1$ is a basic set, 
we obtain finally that $\Sr$ is decomposable as required. The proof now is completed. \eproof 


For our purpose, only the S-rings in $\cS^*(m)$ need to be considered. 
An S-ring $\Sr\in \cS^*(m)$ is uniquely determined 
by its basic groups $K_0,\dots,K_{m-1}$ 
since, by definition, its basic relation is $\theta=\omega_m$. 
Now, $K_{m-1}=G_1$, $K_{m-2}\in \{G_1,G_2\}$ (Theorem~\ref{t1}(iii)), and  
for $i<m-2$  the basic group
$K_i$ is determined recursively from $K_{i+1}$ (see
Theorem~\ref{t1}(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\leq m-1$, is built based on the recursion in  Theorem~\ref{t1}(iv). 
As an illustration, $T(4)$ is shown in Figure~\ref{fig1}.  
Then the rings in $\cS^*(m)$ can be naturally identified with the directed 
paths in $T(m)$ of length $m-1$. The S-ring $\Sr\in \cS^*(m)$ having basic 
groups $(K_0,\dots,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 $\cS^*(m)$ by considering the labels of its vertices.  

\begin{figure}
\unitlength 1mm
\begin{picture}(140,65)(-70,0)
\thinlines 
\put(0,60){\circle*{1}} \put(0,60){\makebox(0,0)[b]{$G_1$}} 
\put(-30,50){\circle*{1}} \put(-30,50){\makebox(0,0)[rb]{$G_1$}}
\put(30,50){\circle*{1}} \put(30,50){\makebox(0,0)[lb]{$G_2$}}
\put(0,60){\vector(3,-1){30}} \put(0,60){\vector(-3,-1){30}}
\put(-50,30){\circle*{1}} \put(-50,30){\makebox(0,0)[rb]{$G_1$}}
\put(-30,30){\circle*{1}} \put(-30,30){\makebox(0,0)[rb]{$G_2$}}
\put(-20,30){\circle*{1}} \put(-20,30){\makebox(0,0)[lb]{$G_3$}}
\put(0,30){\circle*{1}}   \put(0,30){\makebox(0,0)[lb]{$G_4$}}
\put(30,30){\circle*{1}}  \put(30,30){\makebox(0,0)[lb]{$G_5$}}
\put(-30,50){\vector(0,-1){20}} \put(-30,50){\vector(1,-2){10}} 
\put(-30,50){\vector(-1,-1){20}} \put(-30,50){\vector(3,-2){30}} 
\put(30,50){\vector(0,-1){20}} \put(30,50){\vector(-4,-1){80}} 
\put(30,50){\vector(-3,-1){60}} 
\put(-50,10){\circle*{1}} \put(-50,10){\makebox(0,0)[rt]{$G_1$}}
\put(-30,10){\circle*{1}} \put(-30,10){\makebox(0,0)[rt]{$G_2$}}
\put(-20,10){\circle*{1}} \put(-20,10){\makebox(0,0)[lt]{$G_3$}}
\put(-10,10){\circle*{1}} \put(-10,10){\makebox(0,0)[lt]{$G_4$}}
\put(0,10){\circle*{1}}   \put(0,10){\makebox(0,0)[lt]{$G_5$}}
\put(20,10){\circle*{1}}  \put(20,10){\makebox(0,0)[lt]{$G_6$}}
\put(30,10){\circle*{1}}  \put(30,10){\makebox(0,0)[lt]{$G_7$}}
\put(40,10){\circle*{1}}  \put(40,10){\makebox(0,0)[lt]{$G_8$}}
\put(-50,30){\vector(0,-1){20}} \put(-50,30){\vector(1,-1){20}}
\put(-50,30){\vector(3,-2){30}} \put(-50,30){\vector(2,-1){40}} 
\put(-30,30){\vector(-1,-1){20}} \put(-30,30){\vector(0,-1){20}} 
\put(-30,30){\vector(3,-2){30}} 
\put(-20,30){\vector(-3,-2){30}} \put(-20,30){\vector(-1,-2){10}} 
\put(-20,30){\vector(0,-1){20}} \put(-20,30){\vector(1,-2){10}} 
\put(0,30){\line(-5,-2){50}} \put(0,30){\vector(-3,-2){30}} 
\put(0,30){\vector(-1,-1){20}} \put(0,30){\vector(-1,-2){10}} 
\put(0,30){\vector(1,-1){20}} \put(0,30){\vector(3,-2){30}} 
\put(30,30){\vector(1,-2){10}} \put(30,30){\vector(-4,-1){70}} 
\put(30,30){\vector(-3,-2){30}} 
\put(30,30){\vector(-4,-1){80}} \put(30,30){\vector(-3,-1){60}}
\end{picture}
\caption{The directed rooted tree $T(4)$}\label{fig1}
\end{figure}

\section{Parameter vectors} 

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

Introduce the set $M=\{0,\dots,m-1\}\times\{0,+,-\}$. 
For the element $(s,\pm)\in M$ and $(s,0)\in M$, respectively, we agree to use the  
notations $s^{\pm}$ and $s$, respectively.   

\begin{de}\label{ipv} 
Let $\Sr\in \cS^*(m)$, and let it have basic groups $K_0,\dots,K_{m-1}$ $(m\geq 2)$.   
The {\bf parameter vector} $\uv=(u_0^{\veps_0},\dots,u_{m-1}^{\veps_{m-1}})\in M^m$ of 
$\Sr$ is defined as  
\begin{equation} \label{dim}
u_i=f_i(\Sr)=\left\{ \begin{array}{rr}m-2-a-i, & \mbox{if }K_i=G_{3a+b}\neq G_1,  \\
m-1-i, & \mbox{if }K_i=G_1, \end{array}\right. 
\end{equation} 
and  
\begin{equation} \label{sign}
\veps_i=\left\{ \begin{array}{rrr}-, & \mbox{if }K_i=G_{3a},\\ 
+, & \mbox{if }K_i=G_{3a+1}\mbox{ and } a>0, \\ 
0, & \mbox{if }K_i=G_1\mbox{ or }K_i=G_{3a+2}.    
\end{array}\right. 
\end{equation} 
The parameter vector
$\uv$ is called {\bf indecomposable} if and only if $\Sr$ is indecomposable. 
\end{de} 

As a direct consequence of Definition~\ref{ipv} we have the following proposition.  

\begin{prop}\label{p31}
If $(u_i^{\veps_i})$ is a parameter vector of length $m$, then 
$$u_i\leq \left\{\begin{array}{rr}m-3-i, & 
\mbox{if }\veps_i\neq 0, \\ 
m-1-i, & \mbox{if }\veps_i=0, \end{array}\right.$$
for all $i\in\{0,\dots,m-1\}$. 
\end{prop}

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^\veps \in M$, where 
$$u=\left\{ \begin{array}{rr}i-1-a, & \mbox{if }3a+b>1,  \\
i, & \mbox{if }3a+b=1, \end{array}\right.$$ 
and 
$$\veps=\left\{ \begin{array}{rrr}+, & \mbox{if }b=1\mbox{ and }a>0,  \\
-, & \mbox{if }b=0,\\ 0, & \mbox{if }b=2\mbox{ or }3a+b=1. \end{array}\right.$$ 
See Figure~\ref{fig2} below, where 
the tree $T(4)$ is shown with its ``new'' labels.   

\begin{figure}[h]
\begin{center}
\unitlength 1mm
\begin{picture}(140,65)(-70,0)
\thinlines 
\put(0,60){\circle*{1}} \put(0,60){\makebox(0,0)[b]{$0$}} 
\put(-30,50){\circle*{1}} \put(-30,50){\makebox(0,0)[rb]{$1$}}
\put(30,50){\circle*{1}} \put(30,50){\makebox(0,0)[lb]{$0$}}
\put(0,60){\vector(3,-1){30}} \put(0,60){\vector(-3,-1){30}}
\put(-50,30){\circle*{1}} \put(-50,30){\makebox(0,0)[rb]{$2$}}
\put(-30,30){\circle*{1}} \put(-30,30){\makebox(0,0)[rb]{$1$}}
\put(-20,30){\circle*{1}} \put(-20,30){\makebox(0,0)[lb]{$0^-$}}
\put(0,30){\circle*{1}}   \put(0,30){\makebox(0,0)[lb]{$0^+$}}
\put(30,30){\circle*{1}}  \put(30,30){\makebox(0,0)[lb]{$0$}}
\put(-30,50){\vector(0,-1){20}} \put(-30,50){\vector(1,-2){10}} 
\put(-30,50){\vector(-1,-1){20}} \put(-30,50){\vector(3,-2){30}} 
\put(30,50){\vector(0,-1){20}} \put(30,50){\vector(-4,-1){80}} 
\put(30,50){\vector(-3,-1){60}} 
\put(-50,10){\circle*{1}} \put(-50,10){\makebox(0,0)[rt]{$3$}}
\put(-30,10){\circle*{1}} \put(-30,10){\makebox(0,0)[rt]{$2$}}
\put(-20,10){\circle*{1}} \put(-20,10){\makebox(0,0)[lt]{$1^-$}}
\put(-10,10){\circle*{1}} \put(-10,10){\makebox(0,0)[lt]{$1^+$}}
\put(0,10){\circle*{1}}   \put(0,10){\makebox(0,0)[lt]{$1$}}
\put(20,10){\circle*{1}}  \put(20,10){\makebox(0,0)[lt]{$0^-$}}
\put(30,10){\circle*{1}}  \put(30,10){\makebox(0,0)[lt]{$0^+$}}
\put(40,10){\circle*{1}}  \put(40,10){\makebox(0,0)[lt]{$0$}}
\put(-50,30){\vector(0,-1){20}} \put(-50,30){\vector(1,-1){20}}
\put(-50,30){\vector(3,-2){30}} \put(-50,30){\vector(2,-1){40}} 
\put(-30,30){\vector(-1,-1){20}} \put(-30,30){\vector(0,-1){20}} 
\put(-30,30){\vector(3,-2){30}} 
\put(-20,30){\vector(-3,-2){30}} \put(-20,30){\vector(-1,-2){10}} 
\put(-20,30){\vector(0,-1){20}} \put(-20,30){\vector(1,-2){10}} 
\put(0,30){\line(-5,-2){50}} \put(0,30){\vector(-3,-2){30}} 
\put(0,30){\vector(-1,-1){20}} \put(0,30){\vector(-1,-2){10}} 
\put(0,30){\vector(1,-1){20}} \put(0,30){\vector(3,-2){30}} 
\put(30,30){\vector(1,-2){10}} \put(30,30){\vector(-4,-1){70}} 
\put(30,30){\vector(-3,-2){30}} 
\put(30,30){\vector(-4,-1){80}} \put(30,30){\vector(-3,-1){60}}
\end{picture}
\end{center}
\caption{$T(4)$ with ``new'' labels}\label{fig2}
\end{figure} 


Now the parameter vector $(u_i^{\veps_i})$ of a given S-ring $\Sr\in\cS^*(m)$ 
can be easily obtained. Consider the directed path of $T(m)$ 
corresponding to $\Sr$, 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}^{\veps_{m-1}}$, and so on.) Based on Figure~\ref{fig2}, we 
list all parameter vectors of length at most $4$ in Table~\ref{tab1}. 
%\medskip 

\begin{table}[h]
\begin{center} 
\begin{tabular}{|l||lllll|}
\hline 
$m$ &  \quad parameter & vectors  &&&   \\ \hline
$2$ &  $(1,0)$       & $ (0,0)^*$ &&&  \\ \hline
$3$ &  $(2,1,0)$     & $(2,0,0)$      & $(1,1,0)$  & $(1,0,0)^*$ & $(0^-,1,0)^*$  \\
    &  $(0^+,1,0)^*$ &  $(0,0,0)^*$   &&&  \\
\hline
$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)^*$ && \\
\hline
\end{tabular} 
\end{center} 
\caption{The parameter vectors of S-rings in $\cS^*(m)$, $m=2,3,4$.}\label{tab1}
\end{table} 

The decomposability of an S-ring in $\cS^*(m)$ 
can easily be checked in terms of its parameter vector
as stated in the following proposition. 

\begin{prop}\label{p32}
If $\uv=(u_i^{\veps_i})$ is the parameter vector of an S-ring $\Sr\in\cS^*(m)$, then  
$\Sr$ is decomposable if and only if there exits some $r\in \{1,\dots,m-1\}$, such that 
$u_i\geq r$ for all $i=0,\dots,m-1-r$.  
\end{prop}  
\proof Recall that $u_i=f_i(\Sr)$, see (\ref{dim}). 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. 
$\Sr$ is decomposable by definition if there exists some $r\in\{1,\dots,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 
$\Sr\in \cS^*(m)$, this is equivalent to saying that every basic set in $L_i$, $i=0,\dots,m-1-r$, is the 
union of some $H_r$-cosets for some $r\in\{1,\dots,m-1\}$. This is equivalent to saying 
that $u_i\geq r$ for all $i=0,\dots,m-1-r$.  \eproof 


Using Proposition~\ref{p32}, it is easy to check that the indecomposable parameter vectors in 
Table~\ref{tab1} are exactly those that are marked with the sign $^*$.  
\medskip

At the end of this section, we establish a formal description of indecomposable parameter  
vectors (Theorem~\ref{t2}). 
To prepare for this description, 
we give next further properties of the parameter vectors. 
Let $\Sr\in\cS^*(m)$, and let $\Sr$ have basic groups 
$$K_0=G_{3a_0+b_0},\dots,K_{m-2}=G_{3a_{m-2}+b_{m-2}},K_{m-1}=G_1.$$ 
Let $\uv=(u_i^{\veps_i})$ denote the parameter vector of $\Sr$.  
For the next three propositions assume that $i\in\{1,\dots,m-1\}$. 

\begin{prop}\label{p33}  
If $\veps_{i-1}\neq 0$ and $\veps_{i}=0$, then $u_{i-1}=u_i-1=m-2-i$.  
Otherwise, $u_{i-1}\geq u_i$.
\end{prop}
\proof Because of (\ref{sign}), the conditions $\veps_{i-1}\neq 0$ 
and $\veps_{i}=0$ are equivalent with   
\begin{equation}\label{e31}
\Big(\, b_{i-1}=0\,\lor\,(b_{i-1}=1\,\land\,a_{i-1}>0)\,\Big)\,\land\, 
\Big(\, 3a_i+b_i=1\,\lor\,b_i=2\, \Big).\end{equation} 
Theorem~\ref{t1}(iv) shows that $(\ref{e31})$ holds exactly when   
$3a_i+b_i=1$ and $3a_{i-1}+b_{i-1}\in \{3,4\}$. By (\ref{dim}), these 
equalities imply $u_{i-1}=m-2-1-(i-1)=m-2-i$ and $u_i=m-1-i$. 
\medskip 

Assume that (\ref{e31}) does not hold. By Theorem~\ref{t1}(iv) we know
that
$a_{i-1}\leq a_i+1$. If $3a_i+b_i\neq 1$, then,
according to (\ref{dim}), we have $u_i=m-2-a_i-i$. 
Therefore,    
$$u_i\leq m-2-(a_{i-1}-1)-i=m-2-a_{i-1}-(i-1)\leq u_{i-1}. $$
Let $3a_i+b_i=1$. Since (\ref{e31}) does not hold, 
we have $3a_{i-1}+b_{i-1} \in\{1,2\}$. 
This implies $u_i=m-1-i$ and $u_{i-1}\in\{m-i,m-1-i\}$, hence $u_{i-1}\geq u_i$ as required.  
The proof is completed.  \eproof  

\begin{cor}\label{cor31}
If $\Sr$ is indecomposable, then $u_i=m-1-i$ if and only if $i=m-1$ or $(i\geq 1\,\land\,  
\veps_{i-1}\neq 0\,\land\,\veps_i=0)$.
\end{cor}
\proof If $i=m-1$, then $K_{m-1}=G_1$, see Theorem~\ref{t1}(iii). This gives  
$u_{m-1}=m-1-(m-1)=0$. If $i\geq 1$ and $\veps_{i-1}\neq 0$ and $\veps_i=0$, then 
$u_i=m-1-i$ by Proposition~\ref{p33}. 

Conversely, assume that $u_i=m-1-i$ holds and $i\in\{0,\dots,m-2\}$. 
Then $3a_i+b_i=1$, see (\ref{dim}). 
If $i=0$, then $L_0$ is a basic set, hence $\Sr$ is decomposable, a contradiction. 
Thus $i\geq 1$ and we can consider $u_{i-1}$.  
According to Proposition~\ref{p33}, we have 
$u_{i-1}\geq u_i$ or $u_{i-1}=u_i-1$.  

Assume that $u_{i-1}\geq u_i$. We show next 
\begin{equation}\label{e32}
u_j\geq m-1-i, \mbox{ for all }j=0,\dots,i.\end{equation} 
We use induction on $j$. The relation in (\ref{e32}) is clear for $j\in\{i,i-1\}$. 
Assume that $i>1$ and that (\ref{e32}) holds for $j\in \{1,\dots,i-1\}$. 
By Proposition~\ref{p33}, 
either $u_{j-1}\geq u_j$ or $u_{j-1}=m-2-j$. Note that in both cases 
$u_{j-1}\geq m-1-i$, as required. 

By choosing $r=m-i-1$ in Proposition~\ref{p32}, 
one obtains via (\ref{e32}) that $\Sr$ is decomposable, 
a contradiction. Therefore, we have $u_{i-1}=u_i-1$. 
By Proposition~\ref{p33}, this implies that   
$\veps_{i-1}\neq 0$ and $\veps_i=0$, and this completes the proof. \eproof 


\begin{prop} \label{p34}  
If $\veps_{i-1}=0$ and $\veps_i\neq 0$, then $u_{i-1}\in \{m-i,m-1-i\}$. 
\end{prop} 
\proof Because of (\ref{sign}), the conditions 
$\veps_{i-1}=0$ and $\veps_{i}\neq 0$ are equivalent with   
$$ \Big(\, 3a_{i-1}+b_{i-1}=1\,\lor\,b_{i-1}=2\, \Big)\,\land\, 
\Big(\, b_i=0\,\lor\,(b_i=1\,\land\,a_i>0)\,\Big). $$ 
Theorem~\ref{t1}(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 (\ref{dim}), we have 
$u_{i-1}=m-1-(i-1)$ or $u_{i-1}=m-2-(i-1)$, i.e., $u_{i-1}\in \{m-i,m-1-i\}$.  \eproof   


\begin{prop} \label{p35} 
If $\veps_{i-1}\neq 0$, $\veps_i\neq 0$ and $u_{i-1}=u_i$, then $\veps_i=+$. 
\end{prop}  
\proof  By (\ref{dim}) and (\ref{sign}), 
the conditions $\veps_{i-1}\neq 0$, $\veps_i\neq 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~\ref{t1}(iv) shows that this may occur only 
when $b_i=1$, which, by (\ref{sign}), gives $\veps_i=+$. \eproof   

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

\begin{theo} \label{t2} 
The parameter vector
$\uv=(u_i^{\veps_i})\in M^m$ {\em(}$m\geq 2${\em)} is indecomposable 
if and only if it 
satisfies the properties:
\begin{enumerate}
\item[{(i)}] for all $i\in\{0,\dots,m-1\}$,  
$u_i\leq \left\{\begin{array}{rr}m-3-i, & 
\mbox{if }\veps_i\neq 0, \\ 
m-1-i, & \mbox{if }\veps_i=0, \end{array}\right.$
\item[{(ii)}] $u_i=m-1-i$ if and only if $i=m-1$ or 
$i\geq 1$ and $\veps_{i-1}\neq 0$ and $\veps_i=0$,  
\item[{(iii)}] if $\veps_{i-1}\neq 0$ and $\veps_i=0$, then 
$u_{i-1}=u_i-1$; otherwise, $u_{i-1}\geq u_{i}$, 
\item[{(iv)}] if $\veps_{i-1}=0$ and $\veps_i\neq 0$, 
then $u_{i-1}\in \{m-i,m-1-i\}$, 
\item[{(v)}] if $\veps_{i-1}\neq 0$, $\veps_i\neq 0$ and $u_{i-1}=u_i$, then $\veps_i=+$.
\end{enumerate} 
\end{theo} 
\proof If $\uv$ is an indecomposable parameter vector, then 
the properties (i)-(v) are just a reformulation of 
Proposition~\ref{p31}, Propositions~\ref{p33}, \ref{p34}, \ref{p35}, 
and Corollary~\ref{cor31}.    
\medskip

Conversely, assume that $\uv=(u_i^{\veps_i})\in M^m$ satisfies (i)-(v). We are going 
to prove by induction on $m$ that $\uv$ 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\times M$ satisfying all  
properties (i)-(v). 

Assume that $m\geq 3$. For a given $u_i^{\veps_i}$, $i\in\{0,\dots,m-1\}$, 
substitute $u_i$ into the equation 
(\ref{dim}). This will determine a unique number $a_i$. Then consider the 
equation in $(\ref{sign})$ which corresponds to
our given $\veps_i$. It will hold for 
a unique $b_i\in\{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,\dots,K_{m-1}$ are 
the basic groups of an indecomposable S-ring $\Sr\in\Sr^*(m)$, for then  
$\uv$ is clearly the parameter vector of $\Sr$. 
We prove first that they are the basic groups of an S-ring in $\Sr^*(m)$ by showing that 
$K_0,\dots,K_{m-1}$ satisfy Theorem~\ref{t1}(iii)-(iv). We distinguish two cases. 
\medskip 

\noindent {\it Case 1:\ $u_1<m-2$.} 

We set $\uv'=(u_1^{\veps_1},\dots,u_{m-1}^{\veps_{m-1}})\in M^{m-1}$. 
It can be checked that in this case $\uv'$ satisfies all properties 
(i)-(v). Therefore, the induction hypothesis yields that $\uv'$ is the  
parameter vector of an indecomposable S-ring $\Sr'$ over $\Z_{2^{m-1}}$. 
It follows from this that the groups $K_1,\dots,K_{m-1}$ satisfy the conditions Theorem~\ref{t1}(iii)-(iv). 
Therefore, we only have to check $K_0$.   

Assume that $\veps_1=0$. Since $u_1<m-2$, it follows that
$K_1=G_{3a_1+2}$. If $\veps_0\neq 0$, then, by 
(ii), we have $u_1=m-2$, a contradiction.  Also, $\veps_0=0$. 
If $K_0\neq G_1$, then $b_0=2$, and, by  (\ref{fi}) and (i),  
$$0\leq a_0=m-2-u_0 \leq m-3-(u_1)+1=a_1+1.$$ 
Therefore, we obtain   
$$K_0\in \{G_1\}\,\cup\,\{G_{3i+2}\,\mid\,0\leq i\leq a_1+1\},$$
as stated in Theorem~\ref{t1}(iv).   

Assume next that $\veps_1 \neq 0$. This is the same as $K_1=3a_1+1$ or  $K_1=3a_1$ for $a_1>0$.  If now $\veps_0=0$, 
then, by (iv), we have $u_0 \in \{m-1,m-2\}$. 
By (\ref{fi}), this implies that $K_0\in\{G_1,G_2\}$.  
If $\veps_0\neq 0$, then $K_1=3a_0+1$ or  $K_1=3a_0$ for $a_0>0$. 
By (\ref{fi}) and 
(i), we have $0\leq a_0\leq 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 $\veps_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\in \{G_2\}\,\cup\,\{G_{3i+1}\,\mid\,0\leq i\leq a_1+1\}\,\cup\,
\{G_{3i+3}\,\mid\,0\leq i\leq a_1\}.$$ 
Thus, $K_0$ satisfies Theorem~\ref{t1}(iv).  
\medskip

\noindent {\it Case 2:\  $u_1=m-2$.} 

Then, according to (\ref{dim}) and (\ref{sign}),
we have $K_1=G_1$ and $\veps_1=0$. 
We set $\uv'=(u_2^{\veps_1},\dots,u_{m-1}^{\veps_{m-1}})\in M^{m-2}$. 
In this case, $u_2<m-3$, since otherwise $\veps_1\neq 0$ would follow 
because of (iii). 
It follows from this that the groups $K_2,\dots,K_{m-1}$ satisfy the conditions Theorem~\ref{t1}(iii)-(iv). 
Therefore, we only have to check $K_1$ and $K_0$.   


Since $K_1=G_1$, it satisfies Theorem~\ref{t1}(iii)-(iv) 
independently of $K_2$.  
According to (ii), we have $\veps_0\neq 0$ and $\veps_1=0$. 
Thus, $u_0=m-3$ because of (i), hence,  
from (\ref{dim}), we get that $K_0\in\{G_3,G_4\}$. 
This shows that $K_0$ satisfies 
Theorem~\ref{t1}(iv), as required.  
\medskip 

We proved that $\uv$ is the parameter vector of an S-ring $\Sr\in\Sr^*(m)$. 
It remains to show that $\Sr$ is indecomposable. 
By way of contradiction, assume that $\Sr$ is decomposable. 
Because of Proposition~\ref{p32}, there is some $r\in \{1,\dots,m-1\}$ such that 
\begin{equation}\label{e33} u_i\geq r \mbox{ for all }i=0,\dots,m-1-r.\end{equation}  
In particular, $u_{m-1-r}\geq r=m-1-(m-1-r)$. Because of (i) and
(ii), we have $u_{m-1-r}=r$,  
$m-1-r>0$, $\veps_{m-1-r}=0$, and $\veps_{u_{m-2-r}}\neq 0$. Now (iii) implies $u_{m-2-r}=u_{m-1-r}-1=r-1$,  
which contradicts (\ref{e33}). The proof of the theorem is now completed. \eproof 

\section{Lattice paths} 

In this section, we consider lattice paths (for short \emph{paths}) 
in the integer plane lattice, which consist of steps $\er=(1,0)$,  $\eu=(0,1)$ and 
$\ed=(1,1)$. A path $\pi$ is uniquely determined by its starting point and the sequence of its 
steps. We express this as $\pi=(s_1,\dots.,s_k$), $s_i\in\{\er,\eu,\ed\}$. 
The path induced by $\pi'=(s_i,s_{i+1},\dots,s_j)$, $1\leq i\leq j\leq k$, 
will be called a \emph{subpath} of $\pi$.\medskip  

In this section we are going to associate a path with 
any indecomposable parameter vector. Let 
$\uv=(u_0^{\veps_0},\dots,u_{m-1}^{\veps_{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 $\pi_i$, whose end point will be denoted by $(x_i,y_i)$. 
As initial value, let $\pi_0$ be the empty path with starting point 
$(0,0)$, so that $(x_0,y_0)=(0,0)$.   

Assume that $\pi_i$ is already defined, connecting $(0,0)$ with 
$(x_i,y_i)$, $0\leq i<m-2$. Then define $\pi_{i+1}$ as 
the concatenation of $\pi_i$ with $\pi'$, where $\pi'$ has starting point 
$(x_i,y_i)$, and where its steps are determined by the following rules:\medskip

\noindent If $\veps_{i}=0$ then  
\begin{equation}\label{zero}
\pi':=\left\{\begin{array}{rr}(\er,\eu), &\mbox{if }i\geq 1,\, 
\veps_{i-1}\neq 0, \\
(\underbrace{\er,\dots,\er}_{r},\eu) &\mbox{if }
i=0\mbox{ or } (i\geq 1,\, \veps_{i-1}=0), 
\end{array}\right.\end{equation}
where $r=\max(m-1-x_i-u_i,0)$. 
\medskip 

\noindent If $\veps_{i}\neq 0$ then  
\begin{equation}\label{pm}
\pi':=\left\{\begin{array}{rr}
(\overbrace{\eu,\dots,\eu,\eu}^{s},\er) &\mbox{if }\veps_i=+, \\ 
(\underbrace{\eu,\dots,\eu}_{s-1},\ed) &\mbox{if }\veps_i=-,
\end{array}\right.\end{equation}
where $s=\max(m-2-y_i-u_i,0)$. 

It is easy to see that for the end point of $\pi_{i+1}$ we have
$$(x_{i+1},y_{i+1})=\left\{\begin{array}{rrr}
(x_i+1,y_i+1),&\mbox{if }i\geq 1,\, \veps_i=0,\, \veps_{i-1}\neq 0, \\
(x_i+r,y_i+1),&\mbox{if }\veps_i=0,\, (i=0\mbox{ or }i\geq 1,\, 
\veps_{i-1}=0), \\
(x_i+1,y_i+s),&\mbox{if }\veps_i\neq 0.\end{array}\right. $$ 

Given this construction, we associate $\uv$ with the path $\pi_{m-1}$. 
We set the notation $\pi(\uv)=\pi_{m-1}$. 

\begin{ex}\label{ex1} $\pi(\uv)$, $\uv=(2^-,2^+,3,0^+,1,0)$. 
\end{ex}   
\noindent By definition $\pi_0$ is the empty path, 
$(x_0,y_0)=(0,0)$. As for $\pi_1$, since $u_0^{\veps_0}=2^-$,  apply 
(\ref{pm}) with $s=2$ to find $\pi_1=\pi'=(\eu,\ed)$, $(x_1,y_1)=(1,2)$. 
$\pi_2$ is the concatenation of $\pi_1$ with $\pi'$, where $\pi'$ 
starts at $(1,2)$ and, according to (\ref{pm}), $\pi'=(\er)$. 
Continuing in this way, we obtain: 
\vspace{1cm}

\begin{center} 
\unitlength 0.75mm
%Step 1
\begin{picture}(25,25)(0,-8)
\thinlines 
\put(0,0){\line(1,0){25}} \put(0,5){\line(1,0){25}} \put(0,10){\line(1,0){25}}  
\put(0,15){\line(1,0){25}} \put(0,20){\line(1,0){25}}  \put(0,25){\line(1,0){25}}  
\put(0,0){\line(0,1){25}} \put(5,0){\line(0,1){25}} \put(10,0){\line(0,1){25}}    
\put(15,0){\line(0,1){25}}  \put(20,0){\line(0,1){25}}  \put(25,0){\line(0,1){25}}  
\put(0,0){\line(1,1){25}}
\thicklines
\put(0,0){\line(0,1){5}} \put(0,5){\line(1,1){5}}
\put(0.3,0){\line(0,1){5}} \put(0,5.3){\line(1,1){5}}
\put(12,-2){\makebox(0,0)[lt]{\scriptsize{$\pi_1$}}}
%\put(0,-5){\makebox(0,0)[lt]{\scriptsize{$(x_1,y_1)=(1,2)$}}}
\end{picture} \quad  
%Step 2
\begin{picture}(25,25)(0,-8)
\thinlines 
\put(0,0){\line(1,0){25}} \put(0,5){\line(1,0){25}} \put(0,10){\line(1,0){25}}  
\put(0,15){\line(1,0){25}} \put(0,20){\line(1,0){25}}  \put(0,25){\line(1,0){25}}  
\put(0,0){\line(0,1){25}} \put(5,0){\line(0,1){25}} \put(10,0){\line(0,1){25}}    
\put(15,0){\line(0,1){25}}  \put(20,0){\line(0,1){25}}  \put(25,0){\line(0,1){25}}  
\put(0,0){\line(1,1){25}}
\thicklines
\put(0,0){\line(0,1){5}} \put(0,5){\line(1,1){5}}
\put(5,10){\line(1,0){5}}
\put(0.3,0){\line(0,1){5}} \put(0,5.3){\line(1,1){5}}
\put(5,9.8){\line(1,0){5}}
\put(12,-2){\makebox(0,0)[lt]{\scriptsize{$\pi_2$}}}
%\put(0,-5){\makebox(0,0)[lt]{\scriptsize{$(x_2,y_2)=(2,2)$}}}
\end{picture} \quad 
%Step 3
\begin{picture}(25,25)(0,-8)
\thinlines 
\put(0,0){\line(1,0){25}} \put(0,5){\line(1,0){25}} \put(0,10){\line(1,0){25}}  
\put(0,15){\line(1,0){25}} \put(0,20){\line(1,0){25}}  \put(0,25){\line(1,0){25}}  
\put(0,0){\line(0,1){25}} \put(5,0){\line(0,1){25}} \put(10,0){\line(0,1){25}}    
\put(15,0){\line(0,1){25}}  \put(20,0){\line(0,1){25}}  \put(25,0){\line(0,1){25}}  
\put(0,0){\line(1,1){25}}
\thicklines
\put(0,0){\line(0,1){5}} \put(0,5){\line(1,1){5}}
\put(5,10){\line(1,0){5}}
\put(10,10){\line(1,0){5}} \put(15,10){\line(0,1){5}}
\put(0.3,0){\line(0,1){5}} \put(0,5.3){\line(1,1){5}}
\put(5,9.8){\line(1,0){5}}
\put(10,9.8){\line(1,0){5}} \put(15.3,10){\line(0,1){5}}
\put(12,-2){\makebox(0,0)[lt]{\scriptsize{$\pi_3$}}}
%\put(0,-5){\makebox(0,0)[lt]{\scriptsize{$(x_3,y_3)=(3,3)$}}}
\end{picture} \quad 
%Step 4
\begin{picture}(25,25)(0,-8)
\thinlines 
\put(0,0){\line(1,0){25}} \put(0,5){\line(1,0){25}} \put(0,10){\line(1,0){25}}  
\put(0,15){\line(1,0){25}} \put(0,20){\line(1,0){25}}  \put(0,25){\line(1,0){25}}  
\put(0,0){\line(0,1){25}} \put(5,0){\line(0,1){25}} \put(10,0){\line(0,1){25}}    
\put(15,0){\line(0,1){25}}  \put(20,0){\line(0,1){25}}  \put(25,0){\line(0,1){25}}  
\put(0,0){\line(1,1){25}}
\thicklines
\put(0,0){\line(0,1){5}} \put(0,5){\line(1,1){5}}
\put(5,10){\line(1,0){5}}
\put(10,10){\line(1,0){5}} \put(15,10){\line(0,1){5}}
\put(15,15){\line(0,1){5}} \put(15,20){\line(1,0){5}}
\put(0.3,0){\line(0,1){5}} \put(0,5.3){\line(1,1){5}}
\put(5,9.8){\line(1,0){5}}
\put(10,9.8){\line(1,0){5}} \put(15.3,10){\line(0,1){5}}
\put(15.3,15){\line(0,1){5}} \put(15,19.8){\line(1,0){5}}
\put(12,-2){\makebox(0,0)[lt]{\scriptsize{$\pi_4$}}}
%\put(0,-5){\makebox(0,0)[lt]{\scriptsize{$(x_4,y_4)=(4,4)$}}}
\end{picture} \quad
%Step 5
\begin{picture}(25,25)(0,-8)
\thinlines 
\put(0,0){\line(1,0){25}} \put(0,5){\line(1,0){25}} \put(0,10){\line(1,0){25}}  
\put(0,15){\line(1,0){25}} \put(0,20){\line(1,0){25}}  \put(0,25){\line(1,0){25}}  
\put(0,0){\line(0,1){25}} \put(5,0){\line(0,1){25}} \put(10,0){\line(0,1){25}}    
\put(15,0){\line(0,1){25}}  \put(20,0){\line(0,1){25}}  \put(25,0){\line(0,1){25}}  
\put(0,0){\line(1,1){25}}
\thicklines
\put(0,0){\line(0,1){5}} \put(0,5){\line(1,1){5}}
\put(5,10){\line(1,0){5}}
\put(10,10){\line(1,0){5}} \put(15,10){\line(0,1){5}}
\put(15,15){\line(0,1){5}} \put(15,20){\line(1,0){5}}
\put(20,20){\line(1,0){5}} \put(25,20){\line(0,1){5}}
\put(0.3,0){\line(0,1){5}} \put(0,5.3){\line(1,1){5}}
\put(5,9.8){\line(1,0){5}}
\put(10,9.8){\line(1,0){5}} \put(15.3,10){\line(0,1){5}}
\put(15.3,15){\line(0,1){5}} \put(15,19.8){\line(1,0){5}}
\put(20,19.8){\line(1,0){5}} \put(25.3,20){\line(0,1){5}}
\put(0,-1){\makebox(0,0)[lt]{\scriptsize{$\pi(\uv)=\pi_5$}}}
%\put(0,-5){\makebox(0,0)[lt]{\scriptsize{$(x_5,y_5)=(5,5)$}}}
\end{picture} 
\end{center} 

Next, we provide more paths associated with indecomposable parameter 
vectors. For sake of simplicity, we put 
$\pi(\uv)=\pi(u_0^{\veps_0},\dots,u_{m}^{\veps_m})$ if 
$\uv=(u_0^{\veps_0},\dots,u_{m}^{\veps_m})$. 

\begin{ex}\label{ex2} The paths associated with indecomposable 
parameter vectors of length $m$, $2\leq m\leq 4$.  
\end{ex}

\noindent \un{$m=2$:}\quad There is only one path: 
$\pi(0,0)=(\er,\eu)$. \medskip 

\noindent \un{$m=3$:}

\begin{center} 
\unitlength 0.75mm
\begin{picture}(10,10)(0,-3)
\thinlines 
\put(0,0){\line(1,0){1}} \put(0,5){\line(1,0){10}} \put(0,10){\line(1,0){10}}     
\put(0,0){\line(0,1){10}} \put(5,0){\line(0,1){10}} \put(10,0){\line(0,1){10}}  \put(0,0){\line(1,1){10}} 
\thicklines
\put(0,0){\line(1,0){10}} \put(10,0){\line(0,1){10}}
\put(0,0.3){\line(1,0){10}} \put(10.3,0){\line(0,1){10}}
\put(0,-2){\makebox(0,0)[lt]{\tiny{$\pi(0,0,0)$}}}
\end{picture} \quad \quad \quad
\begin{picture}(10,10)(0,-3)
\thinlines 
\put(0,0){\line(1,0){10}} \put(0,5){\line(1,0){10}} \put(0,10){\line(1,0){10}}    
\put(0,0){\line(0,1){10}} \put(5,0){\line(0,1){10}} \put(10,0){\line(0,1){10}}  
\put(0,0){\line(1,1){10}} 
\thicklines
\put(0,0){\line(1,0){5}} \put(5,0){\line(0,1){5}}
\put(5,5){\line(1,0){5}} \put(10,5){\line(0,1){5}}
\put(0,0.3){\line(1,0){5}} \put(5.3,0){\line(0,1){5}}
\put(5,5.3){\line(1,0){5}} \put(10.3,5){\line(0,1){5}}
\put(0,-2){\makebox(0,0)[lt]{\tiny{$\pi(1,0,0)$}}}
\end{picture} \quad \quad \quad
\begin{picture}(10,10)(0,-3)
\thinlines 
\put(0,0){\line(1,0){10}} \put(0,5){\line(1,0){10}} \put(0,10){\line(1,0){10}}    
\put(0,0){\line(0,1){10}} \put(5,0){\line(0,1){10}} \put(10,0){\line(0,1){10}}  
\put(0,0){\line(1,1){10}} 
\thicklines
\put(0,0){\line(0,1){5}} \put(0,5){\line(1,0){10}} \put(10,5){\line(0,1){5}}
\put(0.3,0){\line(0,1){5}} \put(0,5.3){\line(1,0){10}} 
\put(10.3,5){\line(0,1){5}}
\put(0,-2){\makebox(0,0)[lt]{\tiny{$\pi(0^+,1,0)$}}}
\end{picture} \quad \quad
\begin{picture}(10,10)(0,-3)
\thinlines 
\put(0,0){\line(1,0){10}} \put(0,5){\line(1,0){10}} \put(0,10){\line(1,0){10}}    
\put(0,0){\line(0,1){10}} \put(5,0){\line(0,1){10}} \put(10,0){\line(0,1){10}}  
\put(0,0){\line(1,1){10}} 
\thicklines
\put(0,0){\line(1,1){5}} \put(5,5){\line(1,0){5}} 
\put(10,5){\line(0,1){5}}
\put(0.3,0){\line(1,1){5}} \put(5,5.3){\line(1,0){5}} 
\put(10.3,5){\line(0,1){5}}
\put(0,-2){\makebox(0,0)[lt]{\tiny{$\pi(0^-,1,0)$}}}
\end{picture} 
\end{center}

\noindent\un{$m=4$:}

\begin{center}
\unitlength 0.75mm
\begin{picture}(15,15)(0,0)
\thinlines 
\put(0,0){\line(1,0){15}} \put(0,5){\line(1,0){15}} \put(0,10){\line(1,0){15}} \put(0,15){\line(1,0){15}}   
\put(0,0){\line(0,1){15}} \put(5,0){\line(0,1){15}} \put(10,0){\line(0,1){15}} \put(15,0){\line(0,1){15}}  
\put(0,0){\line(1,1){15}} 
%path1 
\thicklines
\put(0,0){\line(1,0){15}} \put(15,0){\line(0,1){15}} 
\put(0,0.3){\line(1,0){15}} \put(15.3,0){\line(0,1){15}} 
\put(0,-2){\makebox(0,0)[lt]{\tiny{$\pi(0,0,0,0)$}}}
\end{picture} \qquad  
\begin{picture}(15,15)(0,0)
\thinlines 
\put(0,0){\line(1,0){15}} \put(0,5){\line(1,0){15}} \put(0,10){\line(1,0){15}} \put(0,15){\line(1,0){15}}   
\put(0,0){\line(0,1){15}} \put(5,0){\line(0,1){15}} \put(10,0){\line(0,1){15}} \put(15,0){\line(0,1){15}}  
\put(0,0){\line(1,1){15}} 
%path2 
\thicklines
\put(0,0){\line(1,0){10}} \put(10,0){\line(0,1){10}} \put(10,10){\line(1,0){5}} 
\put(15,10){\line(0,1){5}}
\put(0,0.3){\line(1,0){10}} \put(10.3,0){\line(0,1){10}} 
\put(10,10.3){\line(1,0){5}} 
\put(15.3,10){\line(0,1){5}}
\put(0,-2){\makebox(0,0)[lt]{\tiny{$\pi(1,1,0,0)$}}}
\end{picture} \qquad 
\begin{picture}(15,15)(0,0)
\thinlines 
\put(0,0){\line(1,0){15}} \put(0,5){\line(1,0){15}} \put(0,10){\line(1,0){15}} \put(0,15){\line(1,0){15}}   
\put(0,0){\line(0,1){15}} \put(5,0){\line(0,1){15}} \put(10,0){\line(0,1){15}} \put(15,0){\line(0,1){15}}  
\put(0,0){\line(1,1){15}} 
%path3
\thicklines
\put(0,0){\line(1,0){10}} \put(10,0){\line(0,1){5}} \put(10,5){\line(1,0){5}} 
\put(15,5){\line(0,1){10}}
\put(0,0.3){\line(1,0){10}} \put(10.3,0){\line(0,1){5}} 
\put(10,5.3){\line(1,0){5}} 
\put(15.3,5){\line(0,1){10}}
\put(0,-2){\makebox(0,0)[lt]{\tiny{$\pi(1,0,0,0)$}}}
\end{picture} \qquad  
\begin{picture}(15,15)(0,0)
\thinlines 
\put(0,0){\line(1,0){15}} \put(0,5){\line(1,0){15}} \put(0,10){\line(1,0){15}} \put(0,15){\line(1,0){15}}   
\put(0,0){\line(0,1){15}} \put(5,0){\line(0,1){15}} \put(10,0){\line(0,1){15}} \put(15,0){\line(0,1){15}}  
\put(0,0){\line(1,1){15}} 
%path4 
\thicklines
\put(0,0){\line(1,0){5}} \put(5,0){\line(0,1){10}} \put(5,10){\line(1,0){5}}
\put(10,10){\line(1,0){5}} \put(15,10){\line(0,1){5}} 
\put(0,0.3){\line(1,0){5}} \put(5.3,0){\line(0,1){10}} 
\put(5,10.3){\line(1,0){5}}
\put(10,10.3){\line(1,0){5}} \put(15.3,10){\line(0,1){5}} 
\put(0,-1.5){\makebox(0,0)[lt]{\tiny{$\pi(1,0^+,1,0)$}}}
\end{picture} \qquad  
\begin{picture}(15,15)(0,0)
\thinlines 
\put(0,0){\line(1,0){15}} \put(0,5){\line(1,0){15}} \put(0,10){\line(1,0){15}} \put(0,15){\line(1,0){15}}   
\put(0,0){\line(0,1){15}} \put(5,0){\line(0,1){15}} \put(10,0){\line(0,1){15}} \put(15,0){\line(0,1){15}}  
\put(0,0){\line(1,1){15}} 
%path5
\thicklines
\put(0,0){\line(1,0){5}} \put(5,0){\line(0,1){5}} 
\put(5,5){\line(1,1){5}}
\put(10,10){\line(1,0){5}} \put(15,10){\line(0,1){5}} 
\put(0,0.3){\line(1,0){5}} \put(5.3,0){\line(0,1){5}} 
\put(5.3,5){\line(1,1){5}}
\put(10,10.3){\line(1,0){5}} \put(15.3,10){\line(0,1){5}} 
\put(0,-1.5){\makebox(0,0)[lt]{\tiny{$\pi(1,0^-,1,0)$}}}
\end{picture} \qquad 
\begin{picture}(15,15)(0,0)
\thinlines 
\put(0,0){\line(1,0){15}} \put(0,5){\line(1,0){15}} \put(0,10){\line(1,0){15}} \put(0,15){\line(1,0){15}}   
\put(0,0){\line(0,1){15}} \put(5,0){\line(0,1){15}} \put(10,0){\line(0,1){15}} \put(15,0){\line(0,1){15}}  
\put(0,0){\line(1,1){15}} 
%path6
\thicklines
\put(0,0){\line(1,0){5}} \put(5,0){\line(0,1){5}} \put(5,5){\line(1,0){5}}
\put(10,5){\line(0,1){5}} \put(10,10){\line(1,0){5}} \put(15,10){\line(0,1){5}} 
\put(0,0.3){\line(1,0){5}} \put(5.3,0){\line(0,1){5}} 
\put(5,5.3){\line(1,0){5}}
\put(10.3,5){\line(0,1){5}} \put(10,10.3){\line(1,0){5}} 
\put(15.3,10){\line(0,1){5}} 
\put(0,-2){\makebox(0,0)[lt]{\tiny{$\pi(2,1,0,0)$}}}
\end{picture} \qquad  
\begin{picture}(15,15)(0,0)
\thinlines 
\put(0,0){\line(1,0){15}} \put(0,5){\line(1,0){15}} \put(0,10){\line(1,0){15}} \put(0,15){\line(1,0){15}}   
\put(0,0){\line(0,1){15}} \put(5,0){\line(0,1){15}} \put(10,0){\line(0,1){15}} \put(15,0){\line(0,1){15}}  
\put(0,0){\line(1,1){15}} 
%path7
\thicklines
\put(0,0){\line(1,0){5}} \put(5,0){\line(0,1){5}} 
\put(5,5){\line(1,0){10}} \put(15,5){\line(0,1){10}} 
\put(0,0.3){\line(1,0){5}} \put(5.3,0){\line(0,1){5}} 
\put(5,5.3){\line(1,0){10}} \put(15.3,5){\line(0,1){10}} 
\put(0,-2){\makebox(0,0)[lt]{\tiny{$\pi(2,0,0,0)$}}}
\end{picture} 
\end{center}
\vskip15pt

\begin{center}
\unitlength 0.75mm
%path8 
\hskip-14pt
\begin{picture}(15,15)(0,0)
\thinlines 
\put(0,0){\line(1,0){15}} \put(0,5){\line(1,0){15}} \put(0,10){\line(1,0){15}} \put(0,15){\line(1,0){15}}   
\put(0,0){\line(0,1){15}} \put(5,0){\line(0,1){15}} \put(10,0){\line(0,1){15}} \put(15,0){\line(0,1){15}}  
\put(0,0){\line(1,1){15}} 
\thicklines
\put(0,0){\line(0,1){10}} \put(0,10){\line(1,0){10}}
\put(10,10){\line(1,0){5}} \put(15,10){\line(0,1){5}}
\put(0.3,0){\line(0,1){10}} \put(0,10.3){\line(1,0){10}}
\put(10,10.3){\line(1,0){5}} \put(15.3,10){\line(0,1){5}}
\put(0,-1.5){\makebox(0,0)[lt]{\tiny{$\pi(0^+,0^+,1,0)$}}}
\end{picture} \kern19pt  
%path9 
\begin{picture}(15,15)(0,0)
\thinlines 
\put(0,0){\line(1,0){15}} \put(0,5){\line(1,0){15}} \put(0,10){\line(1,0){15}} \put(0,15){\line(1,0){15}}   
\put(0,0){\line(0,1){15}} \put(5,0){\line(0,1){15}} \put(10,0){\line(0,1){15}} \put(15,0){\line(0,1){15}}  
\put(0,0){\line(1,1){15}} 
\thicklines
\put(0,0){\line(0,1){5}} \put(0,5){\line(1,1){5}}
\put(5,10){\line(1,0){5}}
\put(10,10){\line(1,0){5}} \put(15,10){\line(0,1){5}}
\put(0.3,0){\line(0,1){5}} \put(0.3,5){\line(1,1){5}}
\put(5,10.3){\line(1,0){5}}
\put(10,10.3){\line(1,0){5}} \put(15.3,10){\line(0,1){5}}
\put(0,-1.5){\makebox(0,0)[lt]{\tiny{$\pi(0^-,0^+,1,0)$}}}
\end{picture} \kern19pt  
%path10 
\begin{picture}(15,15)(0,0)
\thinlines 
\put(0,0){\line(1,0){15}} \put(0,5){\line(1,0){15}} \put(0,10){\line(1,0){15}} \put(0,15){\line(1,0){15}}   
\put(0,0){\line(0,1){15}} \put(5,0){\line(0,1){15}} \put(10,0){\line(0,1){15}} \put(15,0){\line(0,1){15}}  
\put(0,0){\line(1,1){15}} 
\thicklines
\put(0,0){\line(0,1){5}} \put(0,5){\line(1,0){5}}
\put(5,5){\line(0,1){5}} \put(5,10){\line(1,0){5}} 
\put(10,10){\line(1,0){5}} \put(15,10){\line(0,1){5}}
\put(0.3,0){\line(0,1){5}} \put(0,5.3){\line(1,0){5}}
\put(5.3,5){\line(0,1){5}} \put(5,10.3){\line(1,0){5}} 
\put(10,10.3){\line(1,0){5}} \put(15.3,10){\line(0,1){5}}
\put(0,-1.5){\makebox(0,0)[lt]{\tiny{$\pi(1^+,0^+,1,0)$}}}
\end{picture} \kern19pt  
%path11
\begin{picture}(15,15)(0,0)
\thinlines 
\put(0,0){\line(1,0){15}} \put(0,5){\line(1,0){15}} \put(0,10){\line(1,0){15}} \put(0,15){\line(1,0){15}}   
\put(0,0){\line(0,1){15}} \put(5,0){\line(0,1){15}} \put(10,0){\line(0,1){15}} \put(15,0){\line(0,1){15}}  
\put(0,0){\line(1,1){15}} 
\thicklines
\put(0,0){\line(0,1){5}} \put(0,5){\line(1,0){5}}
\put(5,5){\line(1,1){5}}  
\put(10,10){\line(1,0){5}} \put(15,10){\line(0,1){5}}
\put(0.3,0){\line(0,1){5}} \put(0,5.3){\line(1,0){5}}
\put(5.3,5){\line(1,1){5}}  
\put(10,10.3){\line(1,0){5}} \put(15.3,10){\line(0,1){5}}
\put(0,-1.5){\makebox(0,0)[lt]{\tiny{$\pi(1^+,0^-,1,0)$}}}
\end{picture} \kern19pt  
%path12
\begin{picture}(15,15)(0,0)
\thinlines 
\put(0,0){\line(1,0){15}} \put(0,5){\line(1,0){15}} \put(0,10){\line(1,0){15}} \put(0,15){\line(1,0){15}}   
\put(0,0){\line(0,1){15}} \put(5,0){\line(0,1){15}} \put(10,0){\line(0,1){15}} \put(15,0){\line(0,1){15}}  
\put(0,0){\line(1,1){15}} 
\thicklines
\put(0,0){\line(1,1){5}} 
\put(5,5){\line(0,1){5}} \put(5,10){\line(1,0){5}}  
\put(10,10){\line(1,0){5}} \put(15,10){\line(0,1){5}}
\put(0.3,0){\line(1,1){5}} 
\put(5.3,5){\line(0,1){5}} \put(5,10.3){\line(1,0){5}}  
\put(10,10.3){\line(1,0){5}} \put(15.3,10){\line(0,1){5}}
\put(0,-1.5){\makebox(0,0)[lt]{\tiny{$\pi(1^-,0^+,1,0)$}}}
\end{picture} \kern19pt  
%path13 
\begin{picture}(15,15)(0,0)
\thinlines 
\put(0,0){\line(1,0){15}} \put(0,5){\line(1,0){15}} \put(0,10){\line(1,0){15}} \put(0,15){\line(1,0){15}}   
\put(0,0){\line(0,1){15}} \put(5,0){\line(0,1){15}} \put(10,0){\line(0,1){15}} \put(15,0){\line(0,1){15}}  
\put(0,0){\line(1,1){15}} 
\thicklines
\put(0,0){\line(1,1){10}} 
\put(10,10){\line(1,0){5}} \put(15,10){\line(0,1){5}}
\put(0.3,0){\line(1,1){10}} 
\put(10,10.3){\line(1,0){5}} \put(15.3,10){\line(0,1){5}}
\put(0,-1.5){\makebox(0,0)[lt]{\tiny{$\pi(1^-,0^-,1,0)$}}}
\end{picture} \kern19pt  
%path14
\begin{picture}(15,15)(0,0)
\thinlines 
\put(0,0){\line(1,0){15}} \put(0,5){\line(1,0){15}} \put(0,10){\line(1,0){15}} \put(0,15){\line(1,0){15}}   
\put(0,0){\line(0,1){15}} \put(5,0){\line(0,1){15}} \put(10,0){\line(0,1){15}} \put(15,0){\line(0,1){15}}  
\put(0,0){\line(1,1){15}} 
\thicklines
\put(0,0){\line(0,1){5}} \put(0,5){\line(1,0){5}}  
\put(5,5){\line(1,0){5}} \put(10,5){\line(0,1){5}} 
\put(10,10){\line(1,0){5}} \put(15,10){\line(0,1){5}} 
\put(0.3,0){\line(0,1){5}} \put(0,5.3){\line(1,0){5}}  
\put(5,5.3){\line(1,0){5}} \put(10.3,5){\line(0,1){5}} 
\put(10,10.3){\line(1,0){5}} \put(15.3,10){\line(0,1){5}} 
\put(0,-1.5){\makebox(0,0)[lt]{\tiny{$\pi(1^+,2,0,0)$}}}
\end{picture} \kern13pt  
%path15
\begin{picture}(15,15)(0,0)
\thinlines 
\put(0,0){\line(1,0){15}} \put(0,5){\line(1,0){15}} \put(0,10){\line(1,0){15}} \put(0,15){\line(1,0){15}}   
\put(0,0){\line(0,1){15}} \put(5,0){\line(0,1){15}} \put(10,0){\line(0,1){15}} \put(15,0){\line(0,1){15}}  
\put(0,0){\line(1,1){15}} 
\thicklines 
\put(0,0){\line(1,1){5}}  
\put(5,5){\line(1,0){5}} \put(10,5){\line(0,1){5}} 
\put(10,10){\line(1,0){5}} \put(15,10){\line(0,1){5}} 
\put(0.3,0){\line(1,1){5}}  
\put(5,5.3){\line(1,0){5}} \put(10.3,5){\line(0,1){5}} 
\put(10,10.3){\line(1,0){5}} \put(15.3,10){\line(0,1){5}} 
\put(0,-1.5){\makebox(0,0)[lt]{\tiny{$\pi(1^-,2,0,0)$}}}
\end{picture}  
\end{center}\bigskip

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  
\emph{Catalan} and \emph{Schr\"oder paths}. 

Catalan paths are defined as paths connecting two points lying on 
the line $y=x$ such that they consist of steps $\er$ and $\eu$, 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$, \cite[Exercise~6.20/c]{st}. 
Schr\"oder paths connect two points lying on 
the diagonal line, consist of steps $\er$, $\eu$ and $\ed$, and 
reach no point below the line $y=x$. The total number of Schr\"oder paths 
from $(0,0)$ to $(n,n)$ is equal to $n$-th Schr\"oder number $s_n$, 
\cite[Exercise~6.39/j]{st}. For our purpose we will need a slight 
modification of the Schr\"oder paths. Namely, we call a path a 
\emph{long Schr\"oder path} if it is the extension of a Schr\"oder path with 
two additional steps $\er$ and $\eu$. 
\medskip  

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

\begin{theo}\label{t3}  
If $m\geq 2$, then the mapping $\uv \mapsto \pi(\uv)$ is a bijection 
from the set of all indecomposable parameter vectors of length $m$ 
to the class of paths described by
\begin{equation}\label{CLS}
\mbox{\begin{small} 
concatenations of Catalan and long Schr\"oder paths from  
$(0,0)$ to $(m-1,m-1)$.
\end{small}}\end{equation} 
\end{theo} 

The proof of Theorem~\ref{t3} 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. 
\medskip

Let $\uv=(u_i^{\veps_i})\in M^m$ be an indecomposable parameter
vector, and let $m\geq 3$. 
We introduce the vector $\uv^{\,\prime}=(w_0^{\xi_0},\dots,w_{m-2}^{\xi_{m-2}})$
by
$$w_0^{\xi_0}=\left\{ \begin{array}{ll} u_1^{\veps_1}, &\mbox{if }u_1<m-2, \\
m-3, &\mbox{otherwise,}\end{array}\right. $$ 
and for $i\in\{1,\dots,m-2\}$ let $w_i^{\xi_i}=u_{i+1}^{\veps_{i+1}}$.   
The vector $\uv^{\,\prime}$ will be called the \emph{derivation} of $\uv$. 


\begin{prop}\label{p41} 
If $\uv$ is an indecomposable parameter  vector of length $m\geq 3$, then so is its derivation  
$\uv^{\,\prime}$. 
\end{prop} 

Let $\pi=(s_1,\dots,s_k)$ be a path starting at $(0,0)$. For the numbers 
$1\leq i_1< \cdots<i_t\leq k$, we denote by $\pi^{-\, i_1,\dots,i_t}$ 
the path starting at $(0,0)$, and whose steps are obtained 
from those of $\pi$ by deleting the steps $s_{i_1},\dots,s_{i_t}$.   
For a path $\pi=(s_1,\dots,s_k)$ connecting $(0,0)$ with 
$(m,m)$, we define its \emph{derivation} as the path $\pi^\prime$ connecting $(0,0)$ with 
$(m-1,m-1)$ such that: 
\begin{equation}\label{der}\pi^\prime=
\left\{ \begin{array}{rrr} \pi^{-\, 1}, & \mbox{if } s_1=\ed, \\
\pi^{-\, 1,l+1}, & \mbox{if }s_1=\cdots =s_l=\er(\eu),\, 
s_{l+1}=\eu(\er), \\
\pi^{-\, (l+1)}, & \mbox{if }s_1=\cdots s_l=\eu,\, s_{l+1}=\ed. 
\end{array}\right.\end{equation} 

\begin{ex}\label{ex3} The derivation of 
$\pi=\pi(3^-,4,0^+,0^+,1,0)$ and $\rho=\pi(3,2,2,0^+,1,0)$. 
{\em(}The derivations are shown after translating them by the vector 
$(1,1)$.{\em)} 
\end{ex} \medskip 

\begin{center}
\unitlength 0.75mm
%example 1
\begin{picture}(25,25)(0,-2)
\thinlines 
\put(0,0){\line(1,0){25}} \put(0,5){\line(1,0){25}} \put(0,10){\line(1,0){25}}  
\put(0,15){\line(1,0){25}} \put(0,20){\line(1,0){25}}  \put(0,25){\line(1,0){25}}  
\put(0,0){\line(0,1){25}} \put(5,0){\line(0,1){25}} \put(10,0){\line(0,1){25}}    
\put(15,0){\line(0,1){25}}  \put(20,0){\line(0,1){25}}  \put(25,0){\line(0,1){25}}  
\put(0,0){\line(1,1){25}}
\thicklines
\put(0,0){\line(1,1){5}} 
\put(5,5){\line(1,0){5}} \put(10,5){\line(0,1){15}}
\put(10,20){\line(1,0){15}} \put(25,20){\line(0,1){5}}
\put(0.3,0){\line(1,1){5}} 
\put(5,5.3){\line(1,0){5}} \put(10.3,5){\line(0,1){15}}
\put(10,20.3){\line(1,0){15}} \put(25.3,20){\line(0,1){5}}
\put(12,-2){\makebox(0,0)[lt]{\scriptsize{$\pi$}}}    
\end{picture} \,  
\begin{picture}(3,25)(0,-2)\thinlines \put(0,13){\makebox(0,0)[lt]{$\mapsto$}}\end{picture} \,  
\begin{picture}(25,25)(0,-2)
\thinlines 
\put(0,0){\line(1,0){25}} \put(0,5){\line(1,0){25}} \put(5,10){\line(1,0){20}}  
\put(5,15){\line(1,0){20}} \put(5,20){\line(1,0){20}}  \put(0,25){\line(1,0){25}}  
\put(0,0){\line(0,1){25}} \put(5,0){\line(0,1){25}} \put(10,5){\line(0,1){20}}    
\put(15,5){\line(0,1){20}}  \put(20,5){\line(0,1){20}}  \put(25,0){\line(0,1){25}}  
\put(5,5){\line(1,1){20}}
\thicklines
\put(5,5){\line(1,0){5}} \put(10,5){\line(0,1){15}}
\put(10,20){\line(1,0){15}} \put(25,20){\line(0,1){5}}
\put(5,5.3){\line(1,0){5}} \put(10.3,5){\line(0,1){15}}
\put(10,20.3){\line(1,0){15}} \put(25.3,20){\line(0,1){5}}
\put(12,-1){\makebox(0,0)[lt]{\scriptsize{$\pi^\prime$}}}    
\end{picture} \quad\quad\quad\quad 
%example 2
\begin{picture}(25,25)(0,-2)
\thinlines 
\put(0,0){\line(1,0){25}} \put(0,5){\line(1,0){25}} \put(0,10){\line(1,0){25}}  
\put(0,15){\line(1,0){25}} \put(0,20){\line(1,0){25}}  \put(0,25){\line(1,0){25}}  
\put(0,0){\line(0,1){25}} \put(5,0){\line(0,1){25}} \put(10,0){\line(0,1){25}}    
\put(15,0){\line(0,1){25}}  \put(20,0){\line(0,1){25}}  \put(25,0){\line(0,1){25}}  
\put(0,0){\line(1,1){25}}
\thicklines
\put(0,0){\line(1,0){10}} \put(10,0){\line(0,1){5}}
\put(10,5){\line(1,0){5}} \put(15,5){\line(0,1){15}} 
\put(15,20){\line(1,0){10}} \put(25,20){\line(0,1){5}}
\put(0,0.3){\line(1,0){10}} \put(10.3,0){\line(0,1){5}}
\put(10,5.3){\line(1,0){5}} \put(15.3,5){\line(0,1){15}} 
\put(15,20.3){\line(1,0){10}} \put(25.3,20){\line(0,1){5}}
\put(12,-2){\makebox(0,0)[lt]{\scriptsize{$\rho$}}}    
\end{picture} \,  
\begin{picture}(3,25)(0,-2)\thinlines \put(0,13){\makebox(0,0)[lt]{$\mapsto$}}\end{picture} \,  
\begin{picture}(25,25)(0,-2)
\thinlines 
\put(0,0){\line(1,0){25}} \put(0,5){\line(1,0){25}} \put(5,10){\line(1,0){20}}  
\put(5,15){\line(1,0){20}} \put(5,20){\line(1,0){20}}  \put(0,25){\line(1,0){25}}  
\put(0,0){\line(0,1){25}} \put(5,0){\line(0,1){25}} \put(10,5){\line(0,1){20}}    
\put(15,5){\line(0,1){20}}  \put(20,5){\line(0,1){20}}  \put(25,0){\line(0,1){25}}  
\put(5,5){\line(1,1){20}}
\thicklines
\put(5,5){\line(1,0){5}} \put(10,5){\line(1,0){5}} \put(15,5){\line(0,1){15}} 
\put(15,20){\line(1,0){10}} \put(25,20){\line(0,1){5}}
\put(5,5.3){\line(1,0){5}} \put(10,5.3){\line(1,0){5}} 
\put(15.3,5){\line(0,1){15}} 
\put(15,20.3){\line(1,0){10}} \put(25.3,20){\line(0,1){5}}
\put(12,-1){\makebox(0,0)[lt]{\scriptsize{$\rho^\prime$}}}    
\end{picture}
\end{center}
\medskip 

The vectors $(3^-,4,0^+,0^+,1,0)$ and 
$(3,2,2,0^+,1,0)$ are indecomposable parameter vectors, see 
Theorem~\ref{t2}. It can be seen that the derivation paths 
are also concatenations of Catalan and long Schr\"oder paths. 
Moreover, $\pi^\prime=\pi(3,0^+,0^+,1,0)$,\break 
$\rho^\prime=\pi(2,2,0^+,1,0)$, and 
$(3,0^+,0^+,1,0)$ and $(2,2,0^+,1,0)$ are the 
derivations of\break 
$(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.

\begin{prop}\label{p42}\
\begin{enumerate}  
\item[(i)] If $\pi$ is a path as described in {\em(\ref{CLS})} with 
$m\geq 3$, then $\pi^\prime$ is also a concatenation of Catalan and 
long Schr\"oder paths, connecting $(0,0)$ with 
$(m-2,m-2)$. 
\item[(ii)] If $\uv$ is an indecomposable parameter vector of length $m$, $m\geq 3$, then  
$(\pi(\uv))^{\ \prime}=\pi(\uv^{\,\prime})$. 
\end{enumerate}\end{prop} 

Now everything is prepared to prove Theorem~\ref{t3}.\medskip 


\noindent{\bf The proof of Theorem~4.3.}\quad  
We proceed by induction on $m$.  The assertion is true for $m=2$, see Table~\ref{tab1} and 
Example~\ref{ex2}. \medskip  

Assume that $m\geq 3$. It follows from (\ref{zero}) and (\ref{pm}) 
that $\uv\mapsto\pi(\uv)$ is an injection. We show next that 
if $\uv$ is an indecomposable parameter vector of length $m$, then 
$\pi(\uv)$ is a path as described in (\ref{CLS}).  
Let $\pi=\pi(\uv)$. We have $\pi^\prime=\pi(\uv^{\,\prime})$, 
see Proposition~\ref{p42}(ii). 
Since $\uv^{\, \prime}$ is an indecomposable parameter vector, see Proposition~\ref{p41},  
$\pi^\prime$ is a concatenation of Catalan and long Schr\"oder paths connecting 
$(0,0)$ with $(m-2,m-2)$. Now one can use (\ref{zero}), (\ref{pm}), 
and (\ref{der}) to conclude that $\pi$ must be a path 
as described in (\ref{CLS}).    
\medskip

The proof will be completed by showing that if $\rho$ is a path which  
connects $(0,0)$ with $(m-1,m-1)$ such that it is a concatenation of Catalan and 
long Schr\"oder paths, then $\rho=\pi(\uv)$ for some indecomposable parameter 
vector $\uv$ of length $m$. Let $\rho=(s_1,\dots,s_k)$.
Use Proposition~\ref{p42}(i) and the induction hypothesis to deduce 
$\rho^\prime=\pi(\vec{v})$ for 
some indecomposable vector $\vec{v}$ of length $m-1$. Furthermore, let 
$\vec{v}=(v_0^{\xi_0},\dots,v_{m-2}^{\xi_{m-2}})$. 
\medskip 

We distinguish
two cases depending on whether $\rho$ starts with 
a Catalan or with 
a long Schr\"oder 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 $\rho$ have first steps 
$s_1=\dots=s_l=\er$, $s_{l+1}=\eu$, $1\leq l\leq m-2$. 
Now define $\uv=(u_i^{\veps_i})$ by
$$u_i^{\veps_i}=\left\{ \begin{array}{rr}(m-1-l)^0,&\mbox{if }i=0,\\  
v_{i-1}^{\xi_{i-1}},&\mbox{if }1<i\leq m-1. \end{array}\right. $$  
We are going to complete the proof by showing 
that $\uv$ is an indecomposable parameter vector of length $m$, and 
$\rho=\pi(\uv)$. Now, $\uv$ being an indecomposable parameter vector 
is equivalent to the conditions  
\begin{eqnarray*}
u_0&\leq& m-2,  \\
\veps_1\neq 0&\Rightarrow & u_0=m-2, \\
u_0& \geq & u_1, 
\end{eqnarray*}
see Theorem~\ref{t2}. It immediately follows that
$u_0\leq m-2$. 
Let $\veps_1\neq 0$. We have $\xi_0\neq 0$.
Moreover, $\rho^\prime$ starts 
with a long Schr\"oder path, see (\ref{pm}). As $\rho$ starts with 
a Catalan subpath, this can only occur if $l=1$, see (\ref{der}).
Hence $u_0=m-2$. It remains to show that $u_0\geq u_1$. 
We have $u_1=v_0\leq m-3$ since $\vec{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 (\ref{der}), the path $\rho^\prime$ starts with the  
Catalan subpath $(s_2,\dots,s_l,s_{l+1},\dots)$. 
Now use (\ref{zero}) to obtain $l-1\leq m-2-v_0$. It follows that
$u_1=v_0\leq m-1-l=u_0$. \medskip


It is clear that $\uv^{\,\prime}=\vec{v}$. 
Therefore, we have $(\pi(\uv))^\prime=\rho^\prime$, see 
Proposition~\ref{p42}(ii). Moreover, for $\pi(\uv)=\rho$ 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 
$\pi(\uv)$ is $(s_1,\dots,s_{l+1})$, see (\ref{zero}). \eproof 

\section{The proof of Theorem 1.1} 

Recall that $I(m,p)$  denotes the number of indecomposable S-rings over $Z_{p^m}$.  
If $m\geq 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 (\ref{CLS}). 
Since the trivial S-ring is always indecomposable, for $m\geq 2$ we have 
\begin{equation}\label{main3}
I(m,2)=1+\#\{\mbox{paths as described in (11)} \}.  
\end{equation} 
Our derivation of the expression for $I(m,2)$ given in Theorem~\ref{main} 
will be based on 
this interpretation. If $n\ge1$,
let $p_n$ denote the number of paths from $(0,0)$ to 
$(n,n)$ as described in (\ref{CLS}), 
and for convenience put $p_0=1$. 
Thus, $I(m,2)=1+p_{m-1}$ if $m\geq 2$. We set $P(x)=\sum_{n\geq 0}p_nx^n$.  

Recall that the total numbers of Catalan and Schr\"oder paths, respectively, 
connecting $(0,0)$ with $(n,n)$ are given by
\begin{equation}\label{numb}
c_n=\frac{1}{n+1}{\binom {2n} n} \mbox{ and } 
s_n=\sum_{k=0}^{n}\frac{1}{k+1}{\binom {2k} k}{\binom {n+k}{2k}}.   
\end{equation} 
The corresponding generating functions are, see \cite[page 178]{st},   
\begin{equation}\label{genf} 
C(x)=\sum_{n\geq 0}c_nx^n=\frac{1-\sqrt{1-4x}}{2x},\quad 
S(x)=\sum_{n\geq 0}s_nx^n=\frac{1-x-\sqrt{1-6x+x^2}}{2x}.
\end{equation} 
If $\ls_n$ denotes the number of long Schr\"oder paths, $n\in \N$, then the 
corresponding generating function is $\lsg(x)=(S(x)-1)x$,
as is immediate to see.\medskip 

\noindent{\bf The proof of Theorem~1.1.}\quad $I(1,2)=1$ is clear, hence  
assume $m\geq 2$. As our paths are concatenations of Catalan and long Schr\"oder paths, 
we have the following recursion: 
$$p_n=\sum_{i=0}^n\ls_ip_{n-i}+\sum_{i=0}^{n-1}c_{i}p_{n-1-i},\quad n\geq 1.$$ 
In terms of generating functions, 
$P(x)=P(x)\lsg(x)+P(x)C(x)x+1$. 
Substitute $\lsg(x)=(S(x)-1)x$ and use 
(\ref{genf}) 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 (\ref{genf}) 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+\sum_{n\geq 2}(\, 4c_{n-1}-2c_n+2s_{n-1}-s_n+
3\sum_{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}=
\sum_{n\geq 0}\frac{1}{3\sqrt{17}}
\Big[\, \Big(\frac{11-3\sqrt{17}}{4}\Big)^{n+1}-
\Big(\frac{11+3\sqrt{17}}{4}\Big)^{n+1}\, \Big]x^n.$$ 
Eventually, these facts are combined to derive the desired expression for 
$p_{m-1}$. The proof now is completed. \eproof 


\section*{Acknowledgements} 

The author thanks Mikhail Klin for helpful remarks and suggestions. 
A three-week 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.   

\begin{thebibliography}{9}
\bibitem{gnp}Ja.~Ju.~Gol'fand, N.~L.~Najmark, R.~P\"oschel.  
\emph{The structure of S-rings over $Z_{2^m}$.} 
Akad. der Wiss. der DDR Inst. f\"ur Math., 
Preprint P-MATH-01/85 (1985), 1--30. 

\bibitem{knp}M.~Ch.~Klin, N.~L.~Najmark, R.~P\"oschel.  
\emph{Schur rings over $Z_{2^m}$.} 
Akad. der Wiss. der DDR Inst. f\"ur Math., 
Preprint P-MATH-14/81 (1981), 1--30. 

\bibitem{kp1}M.~H.~Klin and R.~P\"oschel. 
\emph{The K\"onig 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\'anos Bolyai {\bf 25} (1981), 405--434.

\bibitem{kp2}M.~Ch.~Klin, R.~P\"oschel.  
\emph{Circulant graphs via Schur ring theory. Automorphism groups of 
circulant graphs on $p^m$ vertices, $p$ an odd prime.} 
Manuscript. 

\bibitem{kk}I.~Kov\'acs, M.~Klin.   
\emph{Automorphism groups of circulant graphs on $2^m$ vertices.}
(In preparation.)

\bibitem{k}I.~Kov\'acs.   
\emph{On automorphisms of circulant digraphs on $p^m$ vertices, $p$ an 
odd prime.} Linear Alg. and its Appl. {\bf 356} (2002), 231--252. 

\bibitem{lm}K.~H.~Leung, S.~L.~Ma.  
\emph{The structure of Schur rings over cyclic groups.} 
J. Pure Appl. Algebra {\bf 66} (1990), 287--302. 

\bibitem{lp}V.~Liskovets, R.~P\"oschel.  
\emph{Counting circulant graphs of prime-power order by decomposing into orbit enumeration problems.} 
Discr. Math. {\bf 214} (2000), 173--191. 

\bibitem{mkp}M.~Muzychuk, M.~Klin and R.~P\"oschel.  
\emph{The isomorphism problem for circulant graphs via Schur ring 
theory.} DIMACS Series in Discrete Mathematics and Theoretical Computer 
Science. Vol. {\bf 56} (2001), 241--264.

\bibitem{sch}I.~Schur. 
\emph{Zur Theorie der einfach transitiven Permutationsgruppen.} 
Sitzungsber. Preuss. Akad. Wiss. Phys.-Math. Kl. (1933), 598--623. 

\bibitem{sco}W.~R.~Scott. \emph{Group Theory.} 
Prentice-Hall, 1964. 

\bibitem{st}R.~P.~Stanley. \emph{Enumerative Combinatorics vol II.}  
Cambridge University Press, Cambridge, 1999. 

\bibitem{w}H.~Wielandt. \emph{Finite Permutation Groups.} 
Academic Press, Berlin, 1964.
\end{thebibliography}
\medskip

\vbox{
\begin{small}
\noindent Istv\'an Kov\'acs \\
University of Primorska, Department of Mathematics and Computer Science\\
Cankarjeva 5, Koper 6000, Slovenia \\
\emph{kovacs@pef.upr.si}
\end{small}
}


\end{document}