\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{slashbox,color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}
\DeclareMathOperator{\LG}{LG}
\DeclareMathOperator{\ZG}{ZG}
\DeclareMathOperator{\h}{ht}
\usepackage{caption}
\captionsetup[table]{name=Figure}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{identity}[theorem]{Identity}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}


\begin{center}
\vskip 1cm{\LARGE\bf
Integer Compositions and
\vskip .1in
Higher-Order Conjugation}
\vskip 1cm \large
Augustine O. Munagi\\
School of Mathematics\\
University of the Witwatersrand\\
Wits 2050, Johannesburg\\
South Africa\\
\href{mailto:augustine.munagi@wits.ac.za}{\tt augustine.munagi@wits.ac.za}\\
\end{center}

\vskip .2 in

\begin{abstract}
We consider the classical MacMahon conjugation of compositions or ordered
partitions of positive integers. Using both algebraic and graphical
methods we provide a natural extension of the standard conjugation of a
composition to higher orders. The higher-order conjugates of a composition
are obtained by varying the increments used in standard conjugation
to turn strings of ones into larger summands and vice versa. It turns
out that every nontrivial composition has an integral conjugation order
beyond which it is not conjugable. We also discuss recursive conjugation
and provide enumeration formulas and combinatorial identities between
different classes of compositions.
\end{abstract}


\section{Introduction}\label{intro}
A composition of a positive integer $n$ is an ordered partition of $n$ or a sequence of positive integers that sum to $n$. The terms of the sequence are called parts and $n$ is the \emph{weight} of the composition.
For example 4 has eight compositions namely
$$(4), (3, 1), (1, 3), (2, 2), (2, 1, 1), (1, 2, 1), (1, 1, 2), (1, 1, 1, 1).$$

It is well known that there are $c(n)=2^{n-1}$ compositions of $n$, and $c(n,k)={n-1 \choose k-1}$ compositions of $n$ with exactly $k$ parts which are also called $k$-compositions (see for example \cite{An,HM}).

The \emph{conjugate} of a composition may be obtained by drawing its \emph{zig-zag graph}. Here each part is represented by a row of dots such that the first dot on a row is aligned with the last dot on the previous row. For example, the zig-zag graph of $(5,3,1,2,2)$ is shown in Figure \ref{fig1}.

\begin{table}[ht]
\centering
\renewcommand{\tabcolsep}{1.4mm}
\begin{tabular}[t]{ccccccccc}
   $\bullet$&$\bullet$&$\bullet$&$\bullet$&$\bullet$&&&&\\[-0.8mm]
   &&&&$\bullet$&$\bullet$&$\bullet$&&\\[-0.8mm]
   &&&&&&$\bullet$&&\\[-0.8mm]
   &&&&&&$\bullet$&$\bullet$&\\[-0.8mm]
   &&&&&&&$\bullet$&$\bullet$
   \end{tabular}
\caption{Zig-zag graph of $(5,3,1,2,2)$}\label{fig1}
\end{table}   

The conjugate is the composition corresponding to the columns of zig-zag graphs, from left to right. Thus the conjugate of $(5,3,1,2,2)$, from the Figure \ref{fig1}, is $(1,1,1,1,2,1,3,2,1)$.  The conjugate of a composition $C$ will be denoted by $C'$.

This is an expository paper aimed at providing a natural extension of the definition of the standard conjugation of a composition using algebraic and graphical methods. This will be followed by a brief discussion of how the resulting viewpoint refines or enlarges some familiar topics in the theory.

Percy Alexander MacMahon (1854--1929) introduced the zig-zag graph in \cite{Ma4}. Subsequently, in the classic text \emph{Combinatory Analysis}, he contrasted the zig-zag graph with the partition Ferrers graph and remarked that the latter was rigidly fixed between two perpendicular axes \cite[Sec. IV, p. 153]{Ma1}. However, he had previously defined conjugation using the {\it Line Graph} \cite{Ma1, Ma3} which provided an intuitive complementary relationship between a pair of mutually conjugate compositions. MacMahon also explained a diagram-free short-cut for writing the conjugates directly (now called the `DD' method) \cite{Ma3}.

In recent years conjugate compositions have played a pivotal role in the discovery of composition analogues of classical partition identities while affording natural insights into difficult proofs, see for example \cite{G,Mu1,Mu2,Mu3}. The contemporary text \cite{HM} provides a wide-ranging coverage of the subject.

Agarwal \cite{Ag} introduced $n$-color compositions which are extended compositions in which a part of size $m$ may come in $m$ different colors. Subsequently, Brian Hopkins \cite{Hop} devised a MacMahon-type zig-zag graph for $n$-color compositions by replacing the original zig-zag graph dots with unit squares and then placing dots in some of the squares to indicate colors of part sizes. However, the graphical conjugation operation proposed by Hopkins failed to yield conjugates to many $n$-color compositions.
Several other generalizations of compositions have appeared in the literature in the form of weighted compositions \cite{Eg1, Eg2}, locally restricted compositions \cite{BC1,BC2} and compositions whose parts belong to a prescribed integer set \cite{HM,HMa}, and so forth. But none of these species of compositions emerged with specialized conjugation considerations.

Two further methods of obtaining the conjugate composition are outlined in Section \ref{prelim} together with other essential preliminaries. In Section \ref{ration} we introduce the concept of higher-order conjugation of a composition and show the extended line graph representation. Section \ref{conjht} deals with the highest possible order to which a composition is conjugable while Section \ref{reciprec} considers an additional conjugation-like operation and recursive conjugation. In Section \ref{zigzag} we discuss the derivation of higher-order conjugate compositions from zig-zag graphs. The enumeration of conjugable compositions of a given order is discussed in Section \ref{count}. Lastly, Section \ref{identity} considers a few combinatorial identities between different classes of compositions.


\section{Preliminaries}\label{prelim}
We summarize two other methods of obtaining the conjugate of a composition employed by MacMahon \cite{Ma1,Ma3}.

\begin{enumerate}
\item[LG:] {\bf Line Graph.} 
In the line-graph of a composition $C$, denoted by $\LG(C)$, the weight $n$ is depicted as a line divided into $n$ equal segments and separated by $n-1$ gaps. A composition $C=(c_1,\dots,c_k)$ of $n$ then corresponds to a choice of $k-1$ from the $n-1$ gaps, indicated with dots, such that each part $c_j$ is represented by $c_j$ equal contiguous segments, $1\le j\le k$.
For example the line graph of the composition $C = (3, 1, 1, 2, 4, 1)$ of 12 is

$\LG(C):\ ---\cdot-\cdot-\cdot--\cdot----\cdot-$.

The conjugate $C'$ is the composition whose line graph is obtained by placing dots in the gaps which previously had no dots, that is,

$\LG(C'):\ -\cdot-\cdot----\cdot--\cdot-\cdot-\cdot--$.

Hence $C' = (1, 1, 4, 2, 1, 1, 2)$.

We observe that the LG method gives the number of parts of $C'$ directly as $n-k+1$.
\end{enumerate}

\begin{enumerate}
\item[DD:] {\bf Direct Detection of Conjugates.}
First, we write compositions \emph{symbolically} by representing a maximal string of 1's of length $x$ by $1^x$, where two adjacent \emph{big parts} (i.e., parts $>1$) are assumed to be separated by $1^0$. For example $(1,1,1,5,1,1,8,2,1,5) = (1^3,5,1^2,8,1^0,2,1,5)$.

The general composition in \emph{symbolic form} $C = (\dots,1^{a_u},b_v,1^{a_{u+1}},b_{v+1},\dots)$, has the following four types (with $b_i>1$ for all $i$):
\begin{enumerate}
\item[(i)] $C=(1^{a_1},b_1,1^{a_2},b_2,\dots,b_r,1^{a_{r+1}}),\ a_1,a_{r+1}>0,\, a_i\ge 0,\, i>1$;

\item[(ii)] $C=(1^{a_1},b_1,1^{a_2},b_2,\dots,1^{a_r},b_r),\ a_1>0,\, a_i\ge 0,\, i>1$;

\item[(iii)] $C=(b_1,1^{a_1},b_2,1^{a_2},\dots,b_{r},1^{a_r}),\ a_i\geq 0,\, i\neq r,\, a_r>0$;

\item[(iv)] $C=(b_1,1^{a_1},b_2,1^{a_2},\dots,b_{r-1},1^{a_{r-1}},b_r),\ a_i\geq 0,\, 1\leq i< r$.
\end{enumerate}
The Direct Detection (DD) technique is an easily-mastered rule for writing down the conjugate of a composition in symbolic form by inspection \cite{Mu1,Mu2}.

The respective conjugates of the four types of compositions are given according to the rule below.
\begin{enumerate}
\item[(i')] $C' =(a_1+1,1^{b_1-2},a_2+2,1^{b_2-2},\dots,1^{b_r-2},a_{r+1}+1)$;

\item[(ii')] $C' =(a_1+1,1^{b_1-2},a_2+2,1^{b_2-2},\dots,a_r+2,1^{b_r-1})$;

\item[(iii')] $C' =(1^{b_1-1},a_1+2,1^{b_2-2},a_2+2,\dots,1^{b_r-2},a_{r}+1)$;

\item[(iv')] $C' =(1^{b_1-1},a_1+2,1^{b_2-2},a_2+2,\dots,a_{r-1}+2,1^{b_{r}-1})$.
\end{enumerate}
The DD technique shows that $C$ and $C'$ have the same number of 
symbolic parts.   

For example, the conjugate of 
$(5,3,1,2,2)=(5,1^0,3,1,2,1^0,2)$ is given by 

$(1^4,2,1,3,1^0,2,1)$.

\end{enumerate}

In the sequel compositions of the form $(1^n)$ or $(n)$ will be called \emph{trivial}. Thus a \emph{nontrivial} composition  contains 1 and a big part or at least two big parts.

The four types of compositions in (i) to (iv) will be referred to as $1c1,\, 1c2,\, 2c1$ and $2c2$,  compositions, respectively. Thus a $1c1$ composition has the first and last parts equal to 1, a $1c2$ composition has a first part 1 and a last part $>1$, and so forth. Their conjugates in (i') to (iv') are $2c2,\, 2c1,\, 1c2$ and $1c1$ compositions.
We will mostly use $1c2$ or $2c1$ compositions for demonstrations because they possess the features of all four types. Note that a $1c2$ or $2c1$ composition is never trivial.

A nontrivial composition in symbolic form consists of an alternation of big parts and strings of 1's.
Initial and final strings of 1's or big parts are \emph{boundary} objects while others are \emph{interior} or \emph{intermediate} objects.

A composition $C$ is deemed to be empty (or non-existent), denoted by $C=\emptyset$, if a defining inequality is violated.
For example, if $C$ is a $1c2$ composition (see (ii) above), then $C=\emptyset$ if
$b_i<2$ for some $i$ or $a_1<1$ or $a_i<0,\ i=2,3,\dots,r$.


\section{Higher-order conjugation} \label{ration}
Consider the general $1c2$ composition
\begin{equation*}\label{comp1c2}
C=(1^{a_1},b_1,1^{a_2},b_2,\dots,1^{a_r},b_r),\ a_1>0,\, a_i\ge 0,\, i>1,\, b_i>1,\ \forall\, i.
\end{equation*}
As already seen, the conjugate using the DD conjugation rule, is

\begin{equation*}\label{classconj}
C' =(a_1+1,1^{b_1-2},a_2+2,1^{b_2-2},\dots,a_r+2,1^{b_r-1}).
\end{equation*}

This is the classical conjugation, and we say that it is of order 1. Notice that this process involves subtracting 1 from a boundary big part, and subtracting $2=2\times 1$ from an intermediate big part to make 1's (and correspondingly adding 1 to a boundary string of 1's, and adding 2 to an intermediate string of 1's, to make a big part).

For example, $C=(1^3,6,4,1^2,5)=(1^3,6,1^0,4,1^2,5)$ has the conjugate of order 1 given by
$$C'=(3+1,1^{6-2},0+2,1^{4-2},2+2,1^{5-1})=(4,1^{4},2,1^{2},4,1^{4}).$$
On the other hand, $C$ has the order-2 conjugate
$$C'' =(3+2,1^{6-4},0+4,1^{4-4},2+4,1^{5-2})=(5,1^{2},4,1^{0},6,1^{3}).$$
In the second conjugation, we subtracted 2 from a boundary big part, and subtracted $4=2\times 2$ from an intermediate big part, to make 1's.

However, $C'''=\emptyset\ $: interior big parts of size at least 6 are required.
This may be extended to higher orders.

\begin{definition}[Conjugate of Order $t$]\label{deftconjt}
Let $t$ be a positive integer. A nontrivial composition $C$ possesses a conjugate of order $t$ if every boundary big part of $C$ is greater than $t$ and every interior big part is greater than or equal to $2t$.

Let $C$ be a composition that possesses a conjugate of order $t$. Then to obtain the conjugate of order $t$, we subtract $t$ from each boundary big part and subtract $2t$ from every intermediate big part to make 1's, and correspondingly add $t$ to a boundary string of 1's, and add $2t$ to an intermediate string of 1's, to make a big part.
\end{definition}

Thus a $1c2$ composition $C$ that possesses a conjugate of order $t>0$ has the form
\begin{gather} 
C = (1^{a_1},b_1,1^{a_2},\dots,1^{a_r},b_r), \nonumber \\ 
a_1\geq 1,\, a_i\geq 0, i>1,\, b_i\geq 2t,\, 1\leq i\leq r-1,\, b_r> t.\label{ordert1}
\end{gather}

The conjugate of order $t$ is a composition $E$ given by
\begin{equation}\label{ordert2}
E=({a_1+t},1^{b_1-2t},{a_2+2t},1^{b_2-2t},\dots,{a_r+2t},1^{b_r-t}).
\end{equation}

Notice that $E$ is a $2c1$ composition as expected.
It is easily checked that the parts of $E$ satisfy $a_1+t> t$, $b_i-2t\geq 0$ and $b_r-t>0$. So the parts of $E$ fulfill the same properties as the parts of $C$. Therefore $E$ in turn possesses a conjugate of order $t$. It may be verified that the conjugate of $E$, of order $t$, is $C$.

\begin{definition}\label{deftconj}
Given a positive integer $t$, a composition is \emph{$t$-conjugable} if it possesses a conjugate of order $t$.
A $t$-conjugable composition $C$ is also said to possess a \emph{$t$-conjugate}, denoted successively, for $t=1,2,3,\dots$, by $C^\prime,C'',C''',\dots,C^{(t)},C^{(t+1)},\dots$.
\end{definition}

The trivial compositions $(1^n)$ and $(n)$ possess conjugates of arbitrary order. So they are conventionally $m$-conjugable for all positive integers $m$.
\begin{equation*}\label{trivconj}
(1^n)^{(m)}=(n)\qquad \mbox{and}\qquad (n)^{(m)}=(1^n),\quad m>0.
\end{equation*}

The following characterization is equivalent to the first part of Definition \ref{deftconjt}.
\begin{theorem}\label{lemconj}
A nontrivial $t$-conjugable composition $(c_1,c_2,\dots,c_k)$ satisfies the properties:
\begin{enumerate}
\item[(i)] if $x=c_1>1$ or $x=c_k>1$, then $x>t$,

\item[(ii)] if $i\neq 1,k$ and $c_i>1$, then $c_i\geq 2t$.
\end{enumerate}
\end{theorem}

Clearly $C$ is $t$-conjugable if and only if $C^{(t)}$ is $t$-conjugable.
So $t$-conjugation is an involution on the set of $t$-conjugable compositions of $n$ (a fact that is well-known for $t=1$).

It is clear that a $t$-conjugable composition is $s$-conjugable for $s=1,2,\dots,t$.

\subsection{The extended line graph}
The line graph representation of $C^{(t)}$ is obtained from that of $C$ as a natural extension of the $t=1$ case.

Let $C$ be a $t$-conjugable composition of $n$ with line graph $\LG(C)$.
Then $\LG(C^{(t)})$ is obtained from $\LG(C)$ with the following rule.
\begin{center}
{\it Place a dot in any gap that previously had no dot except the

first $t-1$ gaps immediately before or after a previous dot.}
\end{center}

Thus the case $t=1$ gives no exception for inserting dots into previously empty gaps to obtain $\LG(C')$. But to obtain $\LG(C'')$ every gap immediately before or after a previous dot in $\LG(C)$ must also be skipped, and so forth.

For example, consider the composition of $n=23$ given by $C = (1,6,9,1,1,5)$. Then we have
$$\LG(C):\ -\cdot ------\cdot---------\cdot-\cdot-\cdot-----.$$
Using the rule we obtain
$$\LG(C''):\ ---\cdot-\cdot-\cdot----\cdot-\cdot-\cdot-\cdot-\cdot-\cdot------\cdot-\cdot-\cdot-.$$
Thus $\, C''=(3,1^2,4,1^5,6,1^3).$

Observe that the rule also restores $\LG(C)$ by using $\LG(C'')$ to construct the line graph of the 2-conjugate of $C''$ since $\LG((C'')'')=\LG(C)$.

The Zig-zag graph representation of $t$-conjugable compositions is discussed in Section \ref{zigzag}.


\section{The conjugate height}\label{conjht}
To every nontrivial composition $C$ is associated a unique positive integer $m<\infty$ such that $C$ is $m$-conjugable and not $(m+1)$-conjugable.

\begin{definition}\label{def0}
The \emph{conjugate height} of a nontrivial composition $C$ is the greatest positive integer $m$ such that $C$ is $m$-conjugable.

If the conjugate height of $C$ is $m$ we also write $\h(C)=m$.
\end{definition}
By this definition every nontrivial composition $C$ of $n\geq 3$ satisfies
\begin{equation}\label{defht1}
1\leq \h(C)\leq n-2,\quad n>2,
\end{equation}
where equality holds on the right for the compositions $(1,n-1),(n-1,1)$.
There is no nontrivial composition of $n$ with height greater than $n-2$.

If $\h(C)=t>1$, then $C$ is $(t-1)$-conjugable. If $\h(C)=t$, then $C^{(t+1)}=\emptyset$.

\begin{theorem}\label{lem0}
A nontrivial $t$-conjugable composition $C=(c_1,c_2,\dots,c_k)$ has conjugate height $t$ if and only if either of the following conditions hold:
\begin{enumerate}
\item[(i)] Every $c_i>1,\, 2\leq i\leq k-1$ satisfies $c_i\geq 2t$ and $t+1\in \{c_1,c_k\}$.

\item[(ii)] $c_i\in \{2t,2t+1\}$ for some $i\neq 1,k$, and $c_1,c_k\geq t+1$.
\end{enumerate}
\end{theorem}
\begin{proof}
We use the standard $1c2$ composition $C = (1^{a_1},b_1,1^{a_2},b_2,\dots,1^{a_r},b_r)$. Thus $c_k=b_r$, and any $c_i>1$ corresponds to $b_i$ for some $i=1,\dots,r-1$.

Assume $\h(C)=t$. Then $C^{(t)}$ exists but not $C^{(t+1)}$. Consider
\begin{gather} 
C^{(t)}=({a_1+t},1^{b_1-2t},\dots,a_r+2t,1^{b_r-t})\neq \emptyset,\label{eqlem01} \\
C^{(t+1)}=({a_1+t+1},1^{b_1-2t-2},\dots,a_r+2t+2,1^{b_r-t-1})=\emptyset.\label{eqlem02}
\end{gather}
Since $C^{(t+1)}=\emptyset$, Equations \eqref{eqlem01} and \eqref{eqlem02} imply that $b_r$ may satisfy
$b_r-t>0$ and $b_r-t-1<1$, which imply $1\leq b_r-t\leq 1$ or $b_r=t+1$ (where we have used Theorem \ref{lemconj}).\\
Alternatively, we might have $b_i-2t\geq 0$ and $b_i-2t-2<0$ for some $i\in \{1,\dots,r-1\}$. This gives $0\leq b_i-2t\leq 1$ or $2t\leq b_i\leq 2t+1$. So conditions (i) and (ii) hold.

Conversely (i) implies that $b_r=t+1$. But from \eqref{eqlem02} $C^{(t+1)}=\emptyset$ since its last string of 1's will be $1^{b_r-t-1}=1^0$.
Condition (ii) implies that $b_i\in \{2t,2t+1\},\, i\ne r$. Then $1^{b_i-2t-2}=1^{u},\, u<0$; thus $C^{(t+1)}=\emptyset$.
So $\h(C)=t$ and the assertion is proved.
\end{proof}

The set of compositions with height $\geq t$ is precisely the set of $t$-conjugable compositions: $C^{(t)}\neq \emptyset \iff \h(C)\geq t$.

Let $G_t(n)$ be the set of compositions of $n$ with conjugate height $t$ and let $C_t(n)$ be the set of $t$-conjugable compositions of $n$ with $g_t(n)=|G_t(n)|$ and $c_t(n)=|C_t(n)|$. Then we have $g_1(n)\geq g_2(n)\geq\cdots\geq g_{n-2}(n)\geq g_{x}(n),\, x\geq n-1$, even though $G_i(n)\cap G_j(n)=\emptyset,\, i\neq j$.

However, $c_1(n)\geq c_2(n)\geq\cdots\geq c_{n-2}(n)\geq c_x(n)$ with $C_1(n)\supseteq C_2(n)\supseteq\cdots\supseteq C_{n-2}(n)\supseteq C_x(n)$. Hence $c_1(n)=c(n)=2^{n-1}$, and
\begin{equation}\label{ctversusgt}
C_t(n)=\bigcup\limits_{i\geq t}G_i(n)\quad \mbox{and}\quad G_t(n)=C_t(n)\setminus C_{t+1}(n).
\end{equation}
For example, $g_1(6)=22,\, g_2(6)=4,\, g_3(6)=2,\, g_4(6)=2$ and $g_x(6)=2,\ x\geq 5$, where the enumerated sets are shown below.

\begin{enumerate}
\item[$G_1(6)$:] $(2, 4),(4, 2),(1, 2, 3),(1, 3, 2),(2, 1, 3),(2, 2, 2),(2, 3, 1),(3, 1, 2),(3, 2, 1),$

$(1, 1, 2, 2),(1, 1, 3, 1),(1, 2, 1, 2),(1, 2, 2, 1),(1, 3, 1, 1),(2, 1, 1, 2),(2, 1, 2, 1),$

$(2, 2, 1, 1),(1, 1, 1, 1, 2),(1, 1, 1, 2, 1),(1, 1, 2, 1, 1),(1, 2, 1, 1, 1),(2, 1, 1, 1, 1);$
\item[$G_2(6)$:] $(3, 3),(1, 4, 1),(1, 1, 1, 3),(3, 1, 1, 1);$
\item[$G_3(6)$:] $(1, 1, 4),(4, 1, 1);$
\item[$G_4(6)$:] $(1, 5),(5, 1)$;
\item[$G_x(6)$:] $(6),(1,1,1,1,1,1)$.
\end{enumerate}

If $C$ and $E$ are compositions of $n$ with $\h(C)=\h(E)=t$, then $\h(C^{(t)})\ne \h(E^{(t)})\, $ in general. For example consider the $2$-conjugates of $C=(1^4,5,1^8,4,1^6)$ and $E=(1^4,5,1^5,7,1^6)$. Then $C''=(6,1,12,1^0,8)$ satisfies $\h(C'')=5$ while $E''=(6,1,9,1^3,8)$ gives $\h(E'')=4$.

When $C^{(t)}\neq \emptyset$, it is clear that $\h(C)\leq \h(C^{(t)})$; but when do we have $\, \h(C)=\h(C^{(t)})$?

The following criterion is obtained by applying Theorem \ref{lem0} to $C^{(t)}$ with height $m$ and the fact that the big parts of $C^{(t)}$ are determined by the strings of 1's in $C$.

\begin{corollary}\label{coro1xx}
Let $C$ be a $t$-conjugable composition with height $m$ ($m\geq t$). Then $C^{(t)}$ has height $m$ if and only if

(i) every boundary string $1^a$ in $C$ satisfies $a= m-t+1$ and every interior string $1^a$ satisfies $a\geq 2(m-t)$, or

(ii) every boundary string $1^a$ in $C$ satisfies $a\geq m-t+1$ and every interior string $1^a$ satisfies $a\in \{2(m-t),2(m-t)+1\}$,
\end{corollary}

In particular, when $m=t$, we obtain the next result.	
\begin{corollary}\label{coro1}
Let $C$ be a composition with height $t$. Then $C^{(t)}$ has height $t$ if and only if $C$ contains an isolated 1 or a pair of consecutive big parts (i.e., $C$ is not reciprocal (see definition in Section \ref{reciprec})).
\end{corollary}

\begin{proposition}\label{propht} If $C$ is a composition with height $t\geq s>0$, then $\h((C^{(t)})^{(s)})=s$.

In particular $\h((C^{(t)})')=1$.
\end{proposition}
\begin{proof} Assume that $\h(C)=t$. Then for some interior part $b\in \{2t,2t+1\}$, the operations $C\rightarrow C^{(t)}\rightarrow (C^{(t)})^{(s)}$ induce $b\rightarrow 1^{b-2t}\rightarrow b-2t+2s$ which imply that $b-2t+2s\in \{2s,2s+1\}$. Alternatively for a boundary big part $b=t+1$ we have $b\rightarrow 1^{b-t}\rightarrow b-t+s$ which imply that $b-t+s=s+1$.
\end{proof}



\section{Reciprocal compositions and recursive conjugation}\label{reciprec}
Let $C = (\dots,1^{a_u},b_v,1^{a_{u+1}},b_{v+1},\dots)$ be a composition of $n$ such that $a_i,b_i\geq 2$ for all $i$. We define the \emph{reciprocal} of $C$, denoted by $r(C)$, to be the composition obtained by replacing each string $1^{a_i}$ with $a_i$ and each big part  $b_i$ with $1^{b_i}$, i.e.,
\begin{equation*}\label{recipdefn}
r(C) = (\dots,{a_u},1^{b_v},{a_{u+1}},1^{b_{v+1}},\dots),\quad a_i,b_i>1.
\end{equation*}
Note that $r(C)=\emptyset$ if $a_i<2$ for some $i$. Thus the reciprocal operation is an involution on the set of compositions with no adjacent big parts in which every string of 1's occurs with multiplicity $\geq 2$.
If $r(C)\neq \emptyset$, we call $C$ a \emph{reciprocal composition}.

For example, $r((1^2,4,1^2,3,1^3))=(2,1^4,2,1^3,3)$, and $r((1^2,4,1))=\emptyset$.

Let $C=(1^{a_1},b_1,\dots,1^{a_s},b_s)$.
Then observe from \eqref{ordert1} that when $t=0$ in $C^{(t)}$ we obtain $r(C)$:
\begin{align*}
(C^{(t)})_{|t=0}=C^{(0)}&=({a_1+0},1^{b_1-2(0)},a_2+2(0),\dots,a_s+2(0),1^{b_s-0})\\
&=({a_1},1^{b_1},a_2,\dots,a_s,1^{b_s})\\
&=r(C).
\end{align*}
However, the resulting expression for $r(C)$ may not be defined.

Thus it is intuitive to define $C^{(0)}$ as $r(C)$, so that when $r(C)\neq \emptyset$ we have
$$r(r(C))=r(C^{(0)})=(C^{(0)})^{(0)}=C.$$

\begin{lemma}\label{reciplemmma}
If $C$ is $t$-conjugable, then $C^{(j)}$ is reciprocal, where $j=1,2,\dots,t-1$:
\begin{equation}\label{recipchain}
C^{(t)}\neq \emptyset \implies r(C^{(j)})\neq \emptyset,\, 1\leq j < t.
\end{equation}
\end{lemma}
This follows from the defining inequalities for $C^{(t)}$ in \eqref{ordert1}: each string of 1's in $C^{(j)}$ has the form $1^{b_i-2j},\ i<r$, or $1^{b_r-j}$, and either exponent is at least 2 because $b_i\geq 2t$ and $b_r\geq t+1$ with $j<t$.

Equation \eqref{recipchain} implies
\begin{equation*}\label{tiny1x}
\h(C)>t\iff r(C^{(t)})\neq\emptyset.
\end{equation*}

\begin{proposition}\label{prop0} Let $C$ be a composition. Then
\begin{equation*}\label{tiny2x}
\h(C)\geq t\ \mbox{and}\ \h(r(C))\geq u\implies \h(C^{(t)})\geq t+u.
\end{equation*}
In particular $\ \h(C)\geq t\ \mbox{and}\ r(C)\neq\emptyset\iff \h(C^{(t)})>t.$
\end{proposition}
\begin{proof} We have that $\, r(C)\neq\emptyset$ and $\h(C)\geq t\iff$ every $1^a$ has $a>1\iff$ every boundary big part $b$ in $C^{(t)}$ satisfies $b>t+1$ and every interior big part $b$ satisfies $b>2t+1\iff \h(C^{(t)})> t$.
\end{proof}

Note that $(C^{(t)})'\neq C^{(t+1)}$. The correct relation is
$$(C^{(t)})' = r(C^{(t-1)}),\ t>0.$$
This may be extended as follows:
\begin{theorem}\label{thmconj2} We have
\begin{equation}\label{recipconj1}
(C^{(t)})^{(u)} = r(C^{(t-u)}),\ 0\leq u\leq t.
\end{equation}
\end{theorem}
Note that $u=0$ and $u=t$ require $C^{(t)}$ and $C$ to be reciprocal respectively.
\begin{proof} Compute directly:

$C= (1^{a_1},{b_1},1^{a_2},{b_2},\dots,1^{a_s},{b_s}).$

$C^{(t)} = ({a_1+t},1^{b_1-2t},{a_2+2t},1^{b_2-2t},\dots,{a_s+2t},1^{b_s-t}).$

$(C^{(t)})^{(u)} = (1^{a_1+t-u},{b_1-2t+2u},1^{a_2+2t-2u},\dots,{b_s-t+u}) = r(C^{(t-u)}).$
\end{proof}

The following restatement provides a recursive procedure for computing $C^{(t)}$.
\begin{corollary}\label{thmconj3} We have
\begin{equation}\label{recipconj}
C^{(t)} = r(C^{(t-u)})^{(u)},\ 0\leq u\leq t.
\end{equation}
\end{corollary}
Note that because of \eqref{recipchain}, Equation \eqref{recipconj1} or \eqref{recipconj} holds whenever $C^{(t)}$ exists.
The process can be iterated. Let $t=t_1+\cdots +t_s,\, t_i>0,\, \forall\, i$. Then writing $r(C^{(t_i)})^{t_j}$ instead of $(r(C^{(t_i)}))^{t_j}$ we have
$$C^{(t)} = r( r( \cdots (r(C^{(t_1)})^{(t_2)}\cdots)^{(t_{s-1})})^{(t_s)}),$$
where the reciprocal operation is applied $s-1$ times.

For example we obtain the $5$-conjugate of $C=(1^3,15,1,7)$ using the decomposition $5=2+1+2$:
\begin{align*}
C^{(5)} &= r(r(C'')')''\\
&=r(r((5,1^{11},5,1^5))')''\\
& =r((1^5,{11},1^5,5)')''\\
& =r((6,1^{9},7,1^4))''\\
& =(1^6,{9},1^7,4)''\\
& =(8,1^{5},11,1^2).
\end{align*}

If $C^{(t+1)}\neq\emptyset$, then \eqref{recipconj} implies $(C^{(t+1)})^{(t)} = r(C'),\ \forall\ t\geq 0$.
But when $r(C)\neq\emptyset$, we have
\begin{equation}\label{stelleqn2z}
(C^{(t)})^{(t+1)} = r(C)'.
\end{equation}
Indeed since $r(C)\neq \emptyset$ the following computation is justified by Proposition \ref{prop0} when 

$C=(1^{a_1},b_1,1^{a_2},\dots,1^{a_r},b_r)$ with $\h(C^{(t)})>t$:
\begin{align*}
r(C)' &= (({a_1},1^{b_1},{a_2},\dots,{a_r},1^{b_r}))'\\
&=(1^{a_1-1},b_1+2,1^{a_2-2},\dots,1^{a_r-2},b_r+1)\\
& =((a_1+t,1^{b_1-2t},a_2+2t,\dots, a_r+2t,1^{b_r-t}))^{(t+1)}\\
& =(C^{(t)})^{(t+1)}.
\end{align*}
Thus using \eqref{stelleqn2z} the reciprocal of a $t$-conjugable reciprocal composition has the following expression.
\begin{equation*}\label{recipexpress}
r(C) = ((C^{(t)})^{(t+1)})'.
\end{equation*}
In particular the following relation holds for every reciprocal composition $C$.
\begin{equation*}\label{recipexpressx}
r(C)=((C')'')'.
\end{equation*}

However, $r(C)'=(C')''\iff \h(C')>1$. Hence the next result follows.

\begin{proposition}\label{cipchar}
A composition $C$ is reciprocal if and only if $\h(C')\geq 2$. Hence the number of reciprocal compositions of $n$ is equal to the number of 2-conjugable compositions of $n$ (cf.\ see \eqref{formht2}).
\end{proposition}


\section{Zig-zag graphs and higher-order conjugates}\label{zigzag}
Given a $t$-conjugable composition $C$ we show how $C^{(t)}$ is obtained using zig-zag graphs. The zig-zag graph of $C$ will be denoted by $\ZG(C)$.

We emphasize that the zig-zag graph is primarily structured for the classical\\ 
1-conjugation. So $C^{(t)}$ may only be obtained indirectly through $\ZG(C)$ when $t>1$.

Generally $C^{(t)}$ is obtained from $\ZG(C)$ by reading off the composition corresponding to the columns of the zig-zag graph of a certain (transitional) composition $X_t(C)$ satisfying $C^{(t)}=X_t(C)'$, where $\ZG(X_t(C))$ is visually compatible with $\ZG(C)$.

It is expected that $X_1(C)=C$. In general we set $X_t(C)=r(C^{(t-1)})$ because $C^{(t)}=r(C^{(t-1)})'$ from \eqref{recipconj}.
The visual connection between $\ZG(C)$ and $\ZG(r(C^{(t-1)}))$ is evident from the following procedure.

\begin{enumerate}
\item[] {\bf Algorithm to obtain $\ZG(r(C^{(t-1)}))$ from $\ZG(C)$}.
\begin{enumerate}
\item[(i)] Draw $\ZG(C)$ depicting the dots as open circles;
\item[(ii)] Shade the first or last $b-t+1$ circles if the first or last row contains $b>1$ circles, and shade the middle $b-2(t-1)$ circles in every other row containing $b>1$ circles.
\item[(iii)] Straighten each `zig-zag' string of unshaded circles and align them vertically so that each string of shaded circles is in a different row from an unshaded circle.
\end{enumerate}
\end{enumerate}

The figure obtained in step (iii) is $\ZG(r(C^{(t-1)}))$, that is, $\ZG((C^{(t)})')$.

This procedure is reversible as one may verify by switching the roles of $C$ and $C^{(t)}$; note that $\, r((C^{t})^{t-1})=r(r(C'))=C'$.

We illustrate the process with $C = (1^2,8,1,6,5)$. Assume that $t=3$, that is, we wish to obtain $C'''$ using $\ZG(C)$.
Then the first diagram in Figure \ref{fig2} shows $\ZG(C)$ after the execution of step (ii) of the algorithm; the second diagram shows $\ZG(r(C''))$.

Now the conjugate $C'''$ is given by the composition corresponding to the columns of  $\ZG(r(C''))$, that is, $C''' = (5,1^2,7,6,1^2)$.

Note that
$r(C'')=r((1^2,8,1,6,5)'')=r((4,1^4,5,1^2,4,1^3))=(1^4,4,1^5,2,1^4,3)=(C''')'$.

\begin{table}[ht]
\begin{center}
\renewcommand{\tabcolsep}{0.8mm}
\begin{tabular}[t]{ccccccccccccccccc}
&&&&&&&&&&&&&&&&\\
&&&&&&&&&&&&&&&&\\
   &&&&&&&&&&&&&&&&\\
$\circ$&&&&&&&&&&&&&&&&\\[-1.0mm]
   $\circ$&&&&&&&&&&&&&&&&\\[-1.0mm]
   $\circ$&$\circ$&$\bullet$&$\bullet$&$\bullet$&$\bullet$&$\circ$&$\circ$&&&&&&&&&\\[-1.0mm]
   &&&&&&&$\circ$&&&&&&&&&\\[-1.0mm]
   &&&&&&&$\circ$&$\circ$&$\bullet$&$\bullet$&$\circ$&$\circ$&&&&\\[-1.0mm]
   &&&&&&&&&&&&$\circ$&$\circ$&$\bullet$&$\bullet$&$\bullet$\\
  \end{tabular}
$\qquad{} \qquad{} $
\begin{tabular}[t]{ccccccc}
   $\circ$&&&&&&\\[-1.0mm]
   $\circ$&&&&&&\\[-1.0mm]
   $\circ$&&&&&&\\[-1.0mm]
   $\circ$&&&&&&\\[-1.0mm]
   $\bullet$&$\bullet$&$\bullet$&$\bullet$&&&\\[-1.0mm]
   &&&$\circ$&&&\\[-1.0mm]
   &&&$\circ$&&&\\[-1.0mm]
   &&&$\circ$&&&\\[-1.0mm]
   &&&$\circ$&&&\\[-1.0mm]
   &&&$\circ$&&&\\[-1.0mm]
   &&&$\bullet$&$\bullet$&&\\[-1.0mm]
   &&&&$\circ$&&\\[-1.0mm]
   &&&&$\circ$&&\\[-1.0mm]
   &&&&$\circ$&&\\[-1.0mm]
   &&&&$\circ$&&\\[-1.0mm]
   &&&&$\bullet$&$\bullet$&$\bullet$
  \end{tabular}
\end{center}
\caption{Zig-zag graphs of $C = (1^2,8,1,6,5)$ and $r(C'')$}\label{fig2}
\end{table}


\section{Enumeration}\label{count}
Let $c_t(n,k)$ denote the number of $t$-conjugable $k$-compositions of $n$. 
Thus $c_t(n)=\sum_k c_t(n,k)$.

Note that if $t>1$ and $n-t+1\leq k\leq n-1$, then $c_t(n,k)=0$ since the longest composition after $(1^n)$ is $(1,\dots,1,t+1)$ or $(t+1,1,\dots,1)$ and any composition of the form $(1,\dots,1,x),\, 2\leq x\leq t$ is not $t$-conjugable.

\subsection{Formulas for the number of conjugable compositions}
Following MacMahon \cite{Ma1,Ma3} we demonstrate how to use the line graph to obtain the formula for $c_t(n,k)$ for various types of compositions.

Let $c_t(n,k\mid P):=$ number of $t$-conjugable $k$-compositions of $n$ that satisfy condition $P$. 
For example, consider the function $c_t(n,k\mid \mbox{parts}>1)$.
Then an enumerated composition has the form
$$C=(b_1,b_2,\dots,b_{k-1},b_k),\, b_1,b_k\geq t+1,\, b_i\geq 2t,\, 2\leq i\leq k-1.$$
The line graph of $C$ contains $n-2t-2\geq 0$ central lines as shown in \eqref{genlg}.

\begin{equation}\label{genlg}
\underbrace{---\cdots ---}_{t+1\, \mbox{\footnotesize lines}}\underbrace{\overbrace{----\cdots----}^{n-2t-1\, \mbox{\footnotesize gaps}}}_{n-2t-2\, \mbox{\footnotesize lines}}\underbrace{---\cdots---}_{t+1\, \mbox{\footnotesize lines}}
\end{equation}

In order to specify $C$ we create $k-2$ adjacent strings of lines in-between the $n-2t-1$ central gaps such that the length of each string is at least $2t$. To achieve this we apply the known formula $w(n,k,v)={n-(v-1)(k-1)\choose k}$ which is the number of subsets $\{n_1,\dots,n_k\}\subseteq \{1,\dots,n\}$ satisfying $|n_i-n_j|\geq v,\, i\neq j$ \cite{CK}.

Hence the desired number of compositions is given by $w(n-2t-1,k-1,2t)$, that is,

\begin{equation}\label{bpform}
c_t(n,k\mid \mbox{parts}>1)={n-2t-1-(2t-1)(k-2)\choose k-1}.
\end{equation}
A similar method may be applied to the function $c_t(n,k\mid \mbox{$2c2$ and $s$ ones})$, that is, the number of $t$-conjugable $2c2$ compositions of $n$ into $k$ parts containing $s$ interior 1's, $s\geq 0$. Thus $\, c_t(n,k\mid \mbox{$2c2$ and $0$ ones})=c_t(n,k\mid \mbox{parts}>1)$.

Using \eqref{genlg} we find that $c_t(n,k\mid \mbox{$2c2$ and $s$ ones})={k-2\choose s}w(n-s-2t-1,k-s-1,2t)$, that is,
$$c_t(n,k\mid \mbox{$2c2$ and $s$ ones})={k-2\choose s}{n-s-2t-1-(2t-1)(k-s-2)\choose k-s-1},$$
where $n\geq 2t+2+s+2t(k-1-s),\, k>1$.

Further variations of the shape of $C$ and the formulas are clearly possible.

For a general formula we need the generating function for $c_t(n,k)$.

\begin{theorem}\label{thmctgfk} Let $n\geq k>1$ be integers. Then for all integers $t>0$,
\begin{equation*}\label{eqnctgfk}
\sum_{n=k}^\infty c_t(n,k) x^n = \frac{(x-x^2+x^{t+1})^2(x-x^2+x^{2t})^{k-2}}{(1-x)^k}.
\end{equation*}
\end{theorem}
In particular,
\begin{equation*}\label{formkt1}
\sum_{n=k}^\infty c_1(n,k) x^n = \frac{x^k}{(1-x)^k}=\sum_{n=k}^\infty {n-1\choose k-1}x^n.
\end{equation*}
\begin{proof}
We use the following decomposition of an enumerated composition $C$, where $k>1$.
$C=$(a composition into one part $\in \{1,t+1,t+2,\dots\}$)

$\times$(a $(k-2)$-composition using the parts $1,2t,2t+1,\dots$)

$\times$(a composition into one part $\in \{1,t+1,t+2,\dots\}$).

Hence the generating function is given by
$$(x+x^{t+1}+x^{t+2}+\cdots)(x+x^{2t}+x^{2t+1}+\cdots)^{k-2}(x+x^{t+1}+x^{t+2}+\cdots),$$
That is,
$$\sum_{n=k}^\infty c_t(n,k) x^n = \left(x+\frac{x^{t+1}}{1-x}\right)^2\left(x+\frac{x^{2t}}{1-x}\right)^{k-2}$$
which simplifies to the stated result.
\end{proof}

Now if $\displaystyle \frac{(x-x^2+x^{2t})^{k-2}}{(1-x)^k} = \sum_{n\geq k}V(n,k)x^n$, then it is a routine process to show that

\begin{equation}\label{eqntrinom1}
V_t(n,k)=\sum_{r=0}^{n-k+2}\sum_{j=0}^{n-k+2}(-1)^{r+j}{k-2\choose r}{n-j+1\choose k-1}{k-2-r\choose j-r(2t-1)}.
\end{equation}
Therefore the full generating function is given by
\begin{align*}
\sum_{n=k}^\infty c_t(n,k) x^n &= (x-x^2+x^{t+1})^2\sum_{n=k}^\infty V_t(n,k) x^n.\\
&= (x^2-2x^3+x^4+2x^{t+2}-2x^{t+3}+x^{2t+2})\sum_{n=k}^\infty V_t(n,k) x^n.
\end{align*}
This gives the following formula.
\begin{theorem}\label{thmctnk0} We have
\begin{align*}
c_t(n,k) =& V_t(n-2,k)-2V_t(n-3,k)+V_t(n-4,k)\\
&+2V_t(n-t-2,k)-2V_t(n-t-3,k)+V_t(n-2t-2,k),
\end{align*}
where $V_t(n,k)$ is defined in \eqref{eqntrinom1}.
\end{theorem}
In particular since $c_1(n,k) = V_1(n-2,k)$ we equate this with a known formula to get the identity:
$${n-1\choose k-1}=
\sum_{r=0}^{n-k}\sum_{j=0}^{n-k}(-1)^{r+j}{k-2\choose r}{n-j-1\choose k-1}{k-2-r\choose j-r}.$$

The generating function for $c_t(n)=\sum_{k} c_t(n,k)$ is given by
\begin{align*}
\sum_{n=1}^\infty c_t(n) x^n &= (x+x^2+\cdots)+\sum_{k=2}^\infty \frac{(x-x^2+x^{t+1})^2(x-x^2+x^{2t})^{k-2}}{(1-x)^k}\\
&= \frac{x+x^{2}-x^{t+1}}{1-x-x^t}.
\end{align*}

\begin{theorem}\label{thmctgf} We have
\begin{equation*}\label{eqnctgf}
\sum_{n=1}^\infty c_t(n) x^n = \frac{x(1+x-x^{t})}{1-x-x^t}.
\end{equation*}
\end{theorem}

In order to obtain an explicit formula for $c_t(n)$ we first consider the function $A(n,t)$ given by
\begin{equation}\label{naragf}
\frac{x}{1-x-x^t}=\sum_{n=1}^\infty A(n,t)x^n.
\end{equation}
When $t=1$ and $t=2$ one immediately recognizes the generating functions of two famous enumerators in combinatorial mathematics, namely,
$A(n,1)=2^{n-1}$, the number of all subsets of $\{1,\dots,n-1\}$ or the number of
all compositions of $n$; and $A(n,2)=F_n$, the $n$th Fibonacci number ($F_1=F_2=1,\, F_n=F_{n-1}+F_{n-2},\, n>2$).

For the general coefficient one can show that
\begin{equation}\label{naraform}
A(n,t)=\sum_{i=0}^{\lfloor\frac{n-1}{t}\rfloor}{n-1-(t-1)i\choose i},\quad n>0,
\end{equation}
which is a generalized `Narayana's cows' sequence \cite[\seqnum{A000930}]{Sl}.

Since $\displaystyle \sum\limits_{n\geq 1}c_t(n) x^n =(1+x-x^{t})\sum_{n\geq 1}A(n,t)x^n$, we obtain
\begin{equation}\label{naratype}
c_t(n) = A(n,t) + A(n-1,t) - A(n-t,t).
\end{equation}
The formula \eqref{naratype} may be simplified using \eqref{naraform} and the Pascal triangle recurrence.

\begin{theorem}\label{thmhtformula} Given any positive integers $n,t$ with $1\leq t\leq n-2$ we have
\begin{equation}\label{htform1}
c_t(n)=2\sum_{i=0}^{\lfloor\frac{n-2}{t}\rfloor}{n-2-(t-1)i\choose i},
\end{equation}
where $\, c_t(1)=1,\, c_t(n)=2,\, t\geq n-1$.
\end{theorem}
\noindent In particular we see that $\, c_1(n) = 2\cdot 2^{n-2}=2^{n-1}$,
and
\begin{equation}\label{formht2}
c_2(n)=2\sum_{i=0}^{\lfloor\frac{n-2}{2}\rfloor}{n-2-i\choose i}=2F_{n-1},\quad n>1.
\end{equation}


\subsubsection{Recurrence relations}
Theorem \ref{thmctgf} translates into the following recurrence relation but we also give a direct combinatorial proof.

\begin{theorem}\label{thmct} Given positive integers $n,\, t$ with $n\geq 2t+2$, then
\begin{gather*} 
c_t(n)=c_t(n-1)+c_t(n-t),\\
c_t(1)=1,\, c_t(n)=2,\, 1\leq n\leq t+1;\, c_t(n)=2(n-t),\, t+2\leq n\leq 2t+1.
\end{gather*}
\end{theorem}
\begin{proof} Let $H_t(n)$ be the set enumerated by $c_t(n)$. A composition $C=(u_1,u_2,\dots,)$ in $H_t(n)$, falls under one of the four categories:
\begin{enumerate}
\item $u_1=1$,

\item $u_1=t+1$,

\item $t+2\leq u_1\leq 2t,\ t>1$, and

\item $u_1\geq 2t+1$:
\end{enumerate}
Delete $u_1=1$ from $C$ in (1) or subtract 1 from $u_1$ in (3) to obtain a member of $H_t(n-1)$.
Subtract $t$ from $u_1$ in (2) or (4) to obtain a member of $H_t(n-t)$.

Conversely, if $(e_1,e_2,\dots)\in H_t(n-1)$ satisfies $e_1=1$ or $e_1\geq 2t$, then $C=(1,e_1,e_2,\dots)\in H_t(n)$, otherwise $C=(1+e_1,e_2,\dots)\in H_t(n)$. If $(e_1,e_2,\dots)\in H_t(n-t)$, then $(t+e_1,e_2,\dots)\in H_t(n)$.

The compositions $(1^n)$ and $(n)$ are $t$-conjugable for any integer $t>0$. So by convention we set $c_1(1)=1=c_t(1)$ and $c_t(n)=2,\, 1\leq n\leq t+1$. Then for $t+2\leq n\leq 2t+1$ we see that $c_t(n)=c_t(n-1)+2$, where $C$ is obtained by adding 1 to the big part in a composition enumerated by $c_t(n-1)$ or by inserting 1 into $(1^{n-1})$ or by using a member of $\{(1^{n-t-1},t+1),(t+1,1^{n-t-1})\}$. Then the recurrence $c_t(n)=c_t(n-1)+2$, with $c_{t}(t+1)=2$, has the solution $c_t(n)=2(n-t)$.
\end{proof}

Another recurrence is given in terms of the number of compositions  with last part 1. Denote the number of compositions in $H_t(n)$ with last part $x$ by $c_t(n)_x$. Then
$$c_t(n) = 2c_t(n)_1,\ c_t(t)_1=1.$$
Indeed we have $c_t(n) = c_t(n)_1 + c_t(n)_{>1}$. But since every composition enumerated by $c_t(n)_{>1}$ has a conjugate with last part 1, we see that $c_t(n)_{>1}=c_t(n)_1$. Hence the assertion follows.

\subsection{Number of compositions with a fixed conjugate height}
Let $g_t(n,k)$ denote the number of $k$-compositions of $n$ with conjugate height exactly $t$ so that $g_t(n)=\sum_k g_t(n,k)$.

The formulas for $g_t(n,k)$ and $g_t(n)$ are derived from those of $c_t(n,k)$ and $c_t(n)$ (cf.\ Equation \eqref{ctversusgt}).
\begin{gather} 
g_t(n,k)=c_t(n,k)-c_{t+1}(n,k),\quad n\geq t>1,\nonumber \\
g_t(n)=c_t(n)-c_{t+1}(n),\quad n\geq t>1. \label{ftform}
\end{gather}

From Equations \eqref{ftform} and \eqref{htform1} we obtain
\begin{corollary}\label{corogtform} Given any positive integers $n,t$, then
\begin{equation*}\label{gtform1}
g_t(n)=2\sum_{i=0}^{\lfloor\frac{n-2}{t}\rfloor}{n-2-(t-1)i\choose i}-2\sum_{i=0}^{\lfloor\frac{n-2}{t+1}\rfloor}{n-2-ti\choose i}.
\end{equation*}
\end{corollary}
Note that $g_t(n)>0$ only for $n\geq t+2$ in view of \eqref{defht1}. The case $t=1$ gives
$$g_1(n)=2^{n-1}-2F_{n-1},\ n>1.$$

The following result is a consequence of the generating function of $c_t(n)$.
\begin{corollary}\label{corof1} We have
$$\sum_{n=1}^\infty g_t(n) x^n = \frac{2x^{t+2}(1-x)}{(1-x-x^t)(1-x-x^{t+1})}.$$
\end{corollary}

This generating function implies the following recurrence relation.

\begin{corollary}\label{corof2} Given integers $n,t$ with $t>1,\, n\geq 2t+2$, we have
\begin{gather*} 
g_t(n)=2g_t(n-1)-g_t(n-2)+g_t(n-t)-g_t(n-t-2)-g_t(n-2t-1),\\
g_t(n)=0,\ \mbox{for}\ 1\leq n\leq t+1,\, g_1(4)=4\ \mbox{and}\ g_t(n)=2,\ \mbox{for}\ t+2\leq n\leq 2t+1.
\end{gather*}
\end{corollary}

An open problem is to find a direct combinatorial proof of Corollary \ref{corof2}.

Figure \ref{fig3} shows some values of the enumeration functions $c_t(n)$ and $g_t(n)$ for small $n$. The second columns of the tables give the sequences $c_1(n)=2^{n-1}$ and $g_1(n)=2^{n-1}-2F_{n-1},\, n>0$, respectively.

\begin{table}[ht]
\begin{center}
\renewcommand{\tabcolsep}{1.3mm}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\multicolumn{9}{c}{$c_t(n)$} \\\hline
\backslashbox{$n$}{$t$}&1&2&3&4&5&6&7&8\\\hline
1&1&1&1&1&1&1&1&1\\
2&2&2&2&2&2&2&2&2\\
3&4&2&2&2&2&2&2&2\\
4&8&4&2&2&2&2&2&2\\
5&16&6&4&2&2&2&2&2\\
6&32&10&6&4&2&2&2&2\\
7&64&16&8&6&4&2&2&2\\
8&128&26&12&8&6&4&2&2\\
9&256&42&18&10&8&6&4&2\\
10&512&68&26&14&10&8&6&4\\\hline
\end{tabular}
$\qquad{} $
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\multicolumn{9}{c}{$g_t(n)$} \\\hline
\backslashbox{$n$}{$t$}&1&2&3&4&5&6&7&8\\\hline
1&0&0&0&0&0&0&0&0\\
2&0&0&0&0&0&0&0&0\\
3&2&0&0&0&0&0&0&0\\
4&4&2&0&0&0&0&0&0\\
5&10&2&2&0&0&0&0&0\\
6&22&4&2&2&0&0&0&0\\
7&48&8&2&2&2&0&0&0\\
8&102&14&4&2&2&2&0&0\\
9&214&24&8&2&2&2&2&0\\
10&444&42&12&4&2&2&2&2\\\hline
\end{tabular}
\end{center}
\caption{The numbers $c_t(n)$ and $g_t(n)$ for $1\leq n\leq 10$ and $1\leq t\leq 8$}\label{fig3}.
\end{table}

We remark that the binomial coefficient sequences ${n\choose k},\, n\geq k\geq 0$, in Sloane \cite{Sl} are reproduced here in the form of the enumeration function $c_1(n,k)$ (see Theorem \ref{thmctgfk}).

The 2-conjugable compositions of $n$ are enumerated by the double Fibonacci numbers $2F_n$ (\seqnum{A055389}).
The sequences $\frac{1}{2}c_t(n),\, t\geq 1$ occur in \cite{Sl} as a family of sequences that satisfy the recurrence of Theorem \ref{thmct}: \seqnum{A000045}, \seqnum{A000079}, \seqnum{A000930}, \seqnum{A003269}, \seqnum{A003520}, \seqnum{A005708}, \seqnum{A005709}, \seqnum{A005710}, \seqnum{A005711}.

The functions $c_t(n,2),\, t=1,2,3,\, n>t$ agree with \seqnum{A233583} for suitable sets of initial values, while $c_2(n,3),\, n>7$ coincides with \seqnum{A145018}. On the other hand, $\frac{1}{2}g_t(n)$ is listed only for $t=1$, namely \seqnum{A027934}.

Lastly we note that the following sequences are given in \cite{Sl} as coefficients in the expansions of the rational function $\frac{(1-x)}{1-x-x^t},\, t>3\, $ (cf.\ Equation \eqref{naragf}): \seqnum{A017898}, \seqnum{A017899}, \seqnum{A017900}, \seqnum{A017901}, \seqnum{A017902}, \seqnum{A017903}, \seqnum{A017904}.



\section{Combinatorial identities}\label{identity}
Call a composition $s$-separated if every pair of consecutive big parts is separated by $s$ ones, i.e., $C$ has the form $C=(\dots,b_i,1^s,b_{i+1},1^s,b_{i+2},1^s,\dots),\, b_j>1,\, \forall\, j$.

Then the following result is a consequence of conjugation.
\begin{lemma}\label{idsep1} The number of $t$-conjugable $2c2$ compositions of $n$ that are $s$-separated is equal to the number of $t$-conjugable $1c1$ compositions of $n$ using only the parts $1$ and $2t+s$:
$$c_t(n\mid 2c2,\mbox{$s$-separated}) = c_t(n\mid 1c1,\mbox{parts}\, 1,2t+s).$$
\end{lemma}

For a generating function proof we have
$$\sum_{n=2}^\infty c_t(n,k\mid 1c1,\mbox{parts 1},2t+s)x^n=(x)(x+x^{2t+s})^{k-2}(x),\, k\geq 2;$$
\begin{align*}
\sum_{n=r}^\infty c_t(n &\mid 2c2, \mbox{$s$-separated, $r$ parts}>1) x^n,\, r\geq 2\\
&= (x^{t+1}+x^{t+2}+\cdots)(x^{2t}+x^{2t+1}+\cdots)^{r-2}(x^{t+1}+x^{t+2}+\cdots)(x^s)^{r-1}\\
& = \left(\frac{x^{t+1}}{1-x}\right)^{2}\left(\frac{x^{2t}}{1-x}\right)^{r-2}x^{s(r-1)}.
\end{align*}
The lemma then follows from the easily verified identity
$$\sum_{k\geq 2} x^2(x+x^{2t+s})^{k-2}=\frac{x^2}{1-x}+\sum_{r=2}^\infty \left(\frac{x^{t+1}}{1-x}\right)^{2}\left(\frac{x^{2t}}{1-x}\right)^{r-2}x^{s(r-1)} = \frac{x^2}{1-x-x^{2t+s}},$$
where $(x^2+x^3+\cdots)=x^2/(1-x)$ is the generating function for 1-part $2c2$ compositions.

Since a positive integer may have different compositions of the form $(2t,s)$ for different choices of $t$ and $s$, the next assertion follows from Lemma \ref{idsep1}.

\begin{theorem}\label{coridsep1} Let $2t+s=2h+u$ for positive integers $ t,s,h,u$. Then
$$c_{t}(n\mid 2c2,\mbox{$s$-separated}) = c_{h}(n\mid 2c2,\mbox{$u$-separated}),\ \forall\ n>1.$$
\end{theorem}
For example, since $5=2\cdot 1+3=2\cdot 2+1$, we have $c_{1}(n\mid 2c2,\mbox{$3$-separated}) = c_{2}(n\mid 2c2,\mbox{$1$-separated})$ for all $n>1$. Thus when $n=18$, some (bijective) pairs of enumerated objects follow:

$c_1(18\mid 2c2, 3\mbox{-separated}): (18),(4, 1^3, 11),(3, 1^3, 7, 1^3, 2),(2, 1^3, 3, 1^3, 2, 1^3, 2),\dots ;$

$c_2(18\mid 2c2, 1\mbox{-separated}): (18),(5, 1, 12),(4, 1, 9, 1, 3),(3, 1, 5, 1, 4, 1, 3),\dots.$

The case $s=0$ in Lemma \ref{idsep1} leads to a 5-way combinatorial identity. We provide only bijective proofs below.

\begin{theorem}\label{idt1} Let $t$ be a positive integer. Then the following enumeration functions are equal.
\begin{enumerate}
\item[(i)] $c_t(n\mid \mbox{no 1's})$;

\item[(ii)] $c_t(n-2\mid \mbox{parts}\, 1,2t)$;

\item[(iii)] $c_{2t}(n\mid \mbox{first part 1})$;

\item[(iv)] $c_{t}(n-1\mid \mbox{parts}\equiv 1\pmod{2t})$;

\item[(v)] $c_{t}(n+2t-2\mid \mbox{parts}\geq 2t)$.
\end{enumerate}
The common value, from Equation \eqref{bpform}, is given by
$$\sum_k {n-2t-1-(2t-1)(k-2)\choose k-1}.$$
\end{theorem}\label{thmid5}
\begin{proof} We will replace the lower-case letter $c$ in each enumeration function with the upper-case $C$ to denote the corresponding enumerated set. 

\begin{enumerate}
\item[(i)]  $\iff$ (ii). There is an obvious bijection
\begin{equation}\label{bijn1}
\alpha: C_t(n-2\mid \mbox{parts}\, 1,2t)\rightarrow C_t(n\mid 1c1,\mbox{parts}\, 1,2t),
\end{equation}
where $\alpha((c_1,\dots,c_k))=(1,c_1,\dots,c_k,1)$. Thus (i) $\iff$ (ii) is essentially a restatement of Lemma \ref{idsep1} with $s=0$.

\item[(ii)]  $\iff$ (iii). By \eqref{bijn1} and Lemma \ref{idsep1} it will suffice to establish the bijection
$$\varphi: C_t(n\mid 1c1,\mbox{parts 1},2t)\rightarrow C_{2t}(n\mid \mbox{1st part 1}).$$
Each $U\in C_t(n\mid 1c1,\mbox{parts 1},2t)$ has the symbolic form

$U=(1^{a_1},2t,1^{a_2},2t,\dots,1^{a_{r}},2t,1^{a_{r+1}}),\, a_1,a_{r+1}\geq 1,\, a_i\geq 0,1<i<r+1$.

Now define $\varphi$ as follows.

If $r$ is even, then $\varphi(U)=(1^{a_1},4t+a_2,1^{a_3},4t+a_4,1^{a_5},\dots,4t+a_r,1^{a_{r+1}})$, giving a $1c1$ member of $C_{2t}(n\mid \mbox{1st part 1})$.

If $r$ is odd, then $\varphi(U)=(1^{a_1},4t+a_2,1^{a_3},4t+a_4,1^{a_5},\dots,4t+a_{r-1},1^{a_{r}},2t+a_{r+1})$, giving a $1c2$ member of $C_{2t}(n\mid \mbox{1st part 1})$.
Clearly $\varphi$ is one-to-one.

Conversely, since each interior big part $b$ of any $E\in C_{2t}(n\mid \mbox{1st part 1})$ satisfies $b\geq 4t$, it splits into three symbolic parts $(2t,1^a,2t),\, a\geq 0$. Correspondingly a boundary big part $b$ of $E$ satisfies $b\geq 2t+1$ and splits into $(2t,1^a),\, a>0$. So $E$ can be transformed into a unique member of $C_t(n\mid 1c1,\mbox{parts 1},2t)$. Hence the existence of $\varphi^{-1}$ is guaranteed.


\item[(ii)] $\iff$ (iv). An integer of the form $2tj+1,\, j>0$ has a composition of the form  $(1,2t,\dots,2t)$. If we apply this transformation to each big part of  $C\in C_{t}(n-1\mid \mbox{parts}\equiv 1\pmod{2t})$, and delete the first part ($=1$), we obtain a unique member of $C_t(n-2\mid \mbox{parts}\, 1,2t)$.

\item[(i)] $\iff$ (v). Since any $(c_1,\dots,c_k)\in C_t(n\mid \mbox{no 1's})$ satisfies $c_1,c_k>t$ and $c_i\geq 2t,\, 1<i<k$, it follows that $(c_1+t-1,c_2,\dots,c_{k-1},c_k+t-1)\in C_t(n+2t-2\mid \mbox{parts}\geq 2t)$.
\end{enumerate}
\end{proof}


\section{Acknowledgment} The author is grateful to the editor and the referee for valuable comments which facilitated the revision of this paper. This work is based on research supported in part by the National Research Foundation of South Africa (Grant number 115024).


\begin{thebibliography}{20}
\bibitem{Ag} A. K. Agarwal, $n$-color compositions, \emph{Indian J. Pure Appl. Math.} \textbf{31} (2000), 1421--1427.

\bibitem{An} G. E. Andrews, \emph{The Theory of Partitions}, Cambridge University Press, 1998.

\bibitem{BC1} E. A. Bender and E. R. Canfield, Locally restricted compositions I. Restricted adjacent differences, \emph{Electron. J. Combin}. \textbf{12} (2005), Paper R57.

\bibitem{BC2} E. A. Bender and E. R. Canfield, Locally restricted compositions II. General restrictions and infinite matrices, \emph{Electron. J. Combin}. \textbf{16} (2009), Paper R108.

\bibitem{CK} C. Chuan-Chong and K. Khee-Meng, \emph{Principles and Techniques in Combinatorics}, World Scientific, 1992.

\bibitem{Eg1} S. Eger, Restricted weighted integer compositions and extended binomial coefficients, \emph{J. Integer Seq.} \textbf{16} (2013), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL16/Eger/eger6.html}{Article 13.1.3}.

\bibitem{Eg2} S. Eger, Some Elementary Congruences for the number of weighted integer compositions, \emph{J. Integer Seq.} \textbf{18} (2015), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL18/Eger/eger11.html}{Article 15.4.1}.

\bibitem{G} Y. Guo, Inverse-conjugate compositions with odd parts, \emph{Ars Combinatoria}, \textbf{135} (2017), 93--102.

\bibitem{HM} S. Heubach and T. Mansour, \emph{Combinatorics of Compositions and Words}, Discrete Mathematics and its Applications, CRC Press, 2010.

\bibitem{HMa} S. Heubach and T. Mansour, Compositions of $n$ with parts in a set, \emph{Congressus Numerantium} \textbf{168} (2004), 127--143.

\bibitem{Hop} B. Hopkins, Spotted tilings and $n$-color compositions, \emph{Integers} \textbf{12B} (2012), Paper A6.

\bibitem{Ma1} P. A. MacMahon, \emph{Combinatory Analysis}, Volume 1, Cambridge University Press, 1915

\bibitem{Ma3} P. A. MacMahon, Memoir on the theory of the compositions of numbers, \emph{Philos. Trans. Roy. Soc. London Ser. A}, \textbf{184} (1893), 835--901.

\bibitem{Ma4} P. A. MacMahon, Second memoir on the theory of the
compositions of numbers, \emph{Philos. Trans. Roy. Soc. London Ser. A},
\textbf{207} (1908), 65--134.

\bibitem{Mu1} A. O. Munagi, Euler-type identities for integer compositions
via zig-zag graphs, \emph{Integers} \textbf{12} (2012), Paper A60.

\bibitem{Mu2} A. O. Munagi, Primary classes of compositions of numbers,
\emph{Ann. Math. Inform}. \textbf{41} (2013), 193--204.

\bibitem{Mu3} A. O. Munagi, Zig-zag graphs and partition identities of
A. K. Agarwal, \emph{Ann. Comb}. \textbf{19} (2015), 557--566.

\bibitem{Sl} N. J. A. Sloane, \emph{The On-Line Encyclopedia of Integer
Sequences}, \url{https://oeis.org}.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 \emph{Mathematics Subject Classification}: Primary: 05A17 Secondary: 11P81, 05A15, 05A19.
\medskip

\noindent {\it Keywords}: composition, zig-zag graph, line graph, direct detection, conjugate, height, reciprocal.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences:
\seqnum{A000045},
\seqnum{A000079},
\seqnum{A000930},
\seqnum{A003269},
\seqnum{A003520},
\seqnum{A005708},
\seqnum{A005709},
\seqnum{A005710},
\seqnum{A005711},
\seqnum{A017898},
\seqnum{A017899},
\seqnum{A017900},
\seqnum{A017901},
\seqnum{A017902},
\seqnum{A017903},
\seqnum{A017904},
\seqnum{A027934},
\seqnum{A055389},
\seqnum{A145018}, and
\seqnum{A233583}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  May 29 2018;
revised versions received  August 30 2018; August 31 2018.
Published in {\it Journal of Integer Sequences}, November 25 2018.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                




.
