<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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{color}
\usepackage{fullpage}
\usepackage{float}

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

\usepackage{caption}

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

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\newcommand{\Y}{\mathscr{Y}}

\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}

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

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

\renewcommand*{\thefootnote}{\fnsymbol{footnote}}

\begin{center}
\vskip 1cm{\LARGE\bf Aperiodic Compositions and  \\
\vskip .1in
Classical Integer Sequences}
\vskip 1cm
\large
Margherita Maria Ferrari and Norma Zagaglia Salvi\footnote{
 Work partially supported by MIUR (Ministero dell'Istruzione, dell'Universit\`a e della Ricerca).}\\
Department of Mathematics\\
Politecnico di Milano\\
Milano, 20133\\
Italy \\
\href{mailto:margheritamaria.ferrari@polimi.it}{\tt margheritamaria.ferrari@polimi.it} \\
\href{mailto:norma.zagaglia@polimi.it}{\tt norma.zagaglia@polimi.it}\\
\end{center}

\vskip .2 in

\renewcommand*{\thefootnote}{\arabic{footnote}}
\setcounter{footnote}{0}

\begin{abstract}
In this paper we define the notion of singular
composition of a positive integer.
We provide a characterization of these compositions, together with methods for decomposing and also
extending a singular composition in terms of other singular compositions. Consecutive
extensions of particular compositions determine sequences of
integers which coincide with classical integer sequences involving Fibonacci
and Lucas numbers.
\end{abstract}


\section{Introduction}

Let $k,n$ be integers where $1 \leq k \leq n$, and let $\alpha=(a_1,a_2,\ldots,a_k)$ denote a composition of $n$ into $k$ parts \cite{Riordan}.
We call $\alpha$ \emph{$(h,i)$-singular} if
\begin{equation}\label{definizione}
(a_1, a_2, \ldots, a_i + a_{i+1}, \ldots, a_k) = (a_{1+h}, a_{2+h}, \ldots, a_{i+h} + a_{i+1+h}, \ldots, a_{k+h}),
\end{equation}
where $1 \leq h \leq k-1$, $1 \leq i \leq k$ and the indices are modulo $k$.
Note that shifting a $(h,i)$-singular composition of one position to the right, we obtain a $(h,i+1)$-singular composition.
Consequently, the choice of a single index $i$ is sufficient for identifying such compositions.

Thus we fix $i=1$ and we call the composition $\alpha=(a_1,a_2,\ldots,a_k)$ \emph{$h$-singular} if
\begin{equation}\label{primo}
(a_1+a_2, a_3, \ldots, a_k)= (a_{1+h}+a_{2+h},a_{3+h}, \ldots,a_{k+h}).
\end{equation}

A $k$-composition of $n$ is \emph{singular} when it is $h$-singular for a suitable value of $1 \leq h \leq k-1$.

\begin{example}
The $5$-composition $(1,2,2,1,2)$ of $n=8$ is $2$-singular.
\end{example}

Kramer \cite{Kramer} used singular compositions in order to define the middle levels partition graph of $n$.

The \emph{concatenation} of the compositions $\alpha = (a_1, a_2,\ldots, a_k)$ and $\beta = (b_1, b_2, \ldots, b_h)$ of the positive integers $n$ and $m$ respectively is the composition $\alpha\beta = (a_1, a_2, \ldots, a_k, b_1, b_2, \ldots, b_h)$
of $n+m$. We let $\alpha^i$ denote the concatenation of $\alpha$ with itself $i$ times. A composition $\alpha$ is \emph{periodic} if $\alpha=\pi^j$, where $1&lt;j\leq k$ and $\pi$ is a suitable composition.

Fibonacci and Lucas numbers will appear in some of our results. Recall that the Fibonacci sequence $(F_n)_{n\geq0}$ is defined by setting $F_0=0$, $F_1=1$ and $F_n = F_{n-1} + F_{n-2}$, for $n \geq 2$. The Lucas sequence $(L_n)_{n\geq0}$ is defined by setting $L_0=2$, $L_1=1$ and $L_n = L_{n-1} + L_{n-2}$, for $n \geq 2$.

The paper is outlined as follows. In Section \ref{Characterization} we determine a characterization of aperiodic singular compositions which allows us to obtain a method for constructing such compositions (Theorem \ref{soluzione}). In Section \ref{DecExt} we study decompositions (Theorem \ref{emme}) and also
extensions (Theorem \ref{estensione}) of a singular composition in terms of other singular
compositions. In Section \ref{Sequences} we prove that consecutive extensions
of particular compositions determine sequences of integers which
coincide with classical sequences involving Fibonacci and Lucas
numbers. We conclude the paper by posing a more general definition of singular
composition together with an open problem.


\section{A characterization of singular compositions}\label{Characterization}

Let $\alpha$ be an $h$-singular $k$-composition of $n$; from (\ref{primo}) it follows that $(a_3, \ldots, a_k) =(a_{3+h}, \ldots,a_{k+h})$.

This equality determines the function $f_h: \{3, 4, \ldots, k\} \rightarrow \{3+h, 4+h, \ldots, k+h\}$ on the indices of the elements of previous sequences such that
$$
f_h( i ) = i + h,
$$
where $3 \leq i \leq k$ and the integers are modulo $k$.
We may represent $f_h$ in two-line notation
\begin{equation}\label{ftwoline}
  \begin{pmatrix}
        3  \  \ \  \ 4 \ \  \cdots \ k\\
        3+h \ 4+h \ \cdots \ k+h \\
  \end{pmatrix}.
\end{equation}
Note that the second line is obtained by shifting of $h$ positions to the left the elements of the sequence $(1, 2, 3, 4, \ldots, k)$ and ignoring the first two elements $1+h$ and $2 + h$. A consequence is that the elements $1$ and $2$, which do not belong to the first line, belong to the second one, except for $h = 1$ and $h = k-1$. Indeed for $h=1$ the second line contains $1$, but not $2$; for $h = k-1$ the second line contains $2$, but not $1$.
In a similar way, the elements $1+h$ and $2+h$ do not belong to the second line while they belong to the first one, except for $h=1$ and $h = k-1$.

\begin{proposition}\label{periodic}
An $h$-singular $k$-composition of $n$, where $h$ and $k$ are not coprime,
 is periodic.
\end{proposition}

\begin{proof}
Let $\gcd(k,h)= t &gt; 1$, where $h = th', k = tk'$ and $\gcd(k',h')=1$.
Note that the sets $H_i = \{i, i+h, \ldots, i+(k'-1)h\}$, $1 \leq i \leq t$,
determine a partition of the set $[k]$. Then, for an $h$-singular
$k$-composition $\alpha=(a_1, a_2, \ldots, a_k)$, the elements of the sets $\{a_i, a_{i+h}, \ldots, a_{i+(k'-1)h}\}$,
$1 \leq i \leq t$, coincide and $\alpha$ turns out to be the
concatenation $(a_1, a_2, \ldots, a_t)^{k'}$.
\end{proof}

Throughout the paper we consider only aperiodic compositions.

Beggas et al. \cite{Widened} proved that a particular bijection, called
widened permutation, between two $n$-sets having $n-1$ elements
in common has a decomposition into a linear order and a
possible permutation. In this case we have a similar function in
which the two sets have $n-2$ elements in common, but for $h=1$ and $h = k-1$.

\begin{lemma}\label{ciclo}
Let $h,k$ be coprime integers, where $1\leq h\leq k-1$.
The function $f_h$ does not contain cycles.
\end{lemma}

\begin{proof}
By way of contradiction we assume there is a cycle
$$
C = (d, d+h, \ldots, d + (r-1)h),
$$
where $1 \leq d \leq k$ and $d + rh \equiv d$ (mod $k$).
This means that $rh \equiv 0$ (mod $k$) and therefore $k$ divides $rh$.
Then, because $\gcd(k,h)=1$, $k$ divides $r$. The unique possibility is $r = k$; so the cycle contains all the elements. But this implies the impossible condition that also every line of (\ref{ftwoline}) contains all the elements.
\end{proof}

\begin{theorem}\label{ordlin}
Let $h,k$ be coprime integers, where $1\leq h\leq k-1$. The function
$f_h$ is decomposed into the linear orders:

\begin{enumerate}
\item
\begin{equation}\label{uno}
 E_h = (1 + h, 1 + 2h, \ldots, 1+rh)
\end{equation}
and
\begin{equation}\label{due}
F_h =  (2+h, 2 + 2h, \ldots, 2 + sh),
\end{equation}
where $r = h^{-1}$, $s = (k-1)h^{-1}$ in $\mathbb{Z}_k$, for $h\neq 1,k-1$;

\item
$E_1 = (2)$ and $F_1 = (3,4,\ldots,k,1)$, for $h=1$;

\item
$E_{k-1} = (k,k-1,\ldots,2)$ and $F_{k-1} = (1)$, for $h=k-1$.
\end{enumerate}
\end{theorem}

\begin{proof}
Let $h\neq 1,k-1$. Starting from $1+h$ we obtain the sequence $(1+h, 1+2h, \ldots, 1+rh= a)$,
where $a$ is one of the two elements which are in the second but not in the first line.
So we have either $a = 1$ or $a=2$. If $a=1$, we obtain the impossible relation $rh \equiv 0$ (mod $k$). If $a = 2$, we obtain $rh\equiv 1$ (mod $k$), which is satisfied for $r = h^{-1}$ in $\mathbb{Z}_k$.
Now starting from $2+h$ we obtain the sequence $(2+h, 2+2h, \ldots, 2 + sh =b)$,
where either $b = 1$ or $b = 2$. The unique possibility is $b = 1$, which holds for $s = (k-1)h^{-1}$ in $\mathbb{Z}_k$. By Lemma \ref{ciclo} the function does not contain cycles; therefore it is decomposed into the previous linear orders.

Now let $h=1$. The function $f_1$ is decomposed into $F_1 =
(3,4,\ldots,k,1)$ and $E_1 =(2)$. In the case $h=k-1$, $f_{k-1}$
is decomposed into $E_{k-1}=(k,k-1,\ldots,2)$
and $F_{k-1}=(1)$. This completes the proof of the theorem.
\end{proof}

In the following we let $E_h$ and $F_h$ also denote the sets of the elements of the assigned linear orders.

\begin{corollary}
For every $1\leq h\leq k-1$ such that $\gcd(k,h)=1$, $ E_h \cup F_h =
[k]$ and, for $k &gt; 2$, $\mid E_h \mid \neq \mid F_h \mid$.
\end{corollary}

\begin{proof}
If $k-h^{-1}= h^{-1}$, then $k=2h^{-1}$ and $kh=2$ in $\mathbb{Z}_k$. This implies that $2\equiv 0$ (mod $k$), a
contradiction for $k &gt; 2$.
\end{proof}

\begin{lemma}\label{diversi}
Let $h_1,h_2$ be two integers such that $1 \leq h_1 &lt; h_2 \leq k-1$ and $\gcd(k,h_1)=\gcd(k,h_2)=1$. Then $E_{h_1} \neq E_{h_2} $ and $F_{h_1}\neq F_{h_2}$.
\end{lemma}

\begin{proof}
The cardinalities of $E_{h_1}$ and $E_{h_2}$ coincide with $h_1^{-1}$ and $h_2^{-1}$ in $\mathbb{Z}_k$ respectively. Because $ h_1 &lt; h_2 $, their inverses are distinct; then also the sets
$E_{h_1}$ and  $ E_{h_2}$ are distinct. The same argument applies for $F_{h_1}$ and $F_{h_2}$.
\end{proof}

The following result is straightforward.

\begin{corollary}
If $k$ is a prime integer, then all the sets $E_h$ (respectively $F_h$), $1 \leq h \leq k-1$, are distinct.
\end{corollary}

Note that when $k$ and $h$ are coprime, then also $k$ and $k-h$ are coprime. In the following result we establish a relation between $E_{k-h}$ (respectively $F_{k-h}$) and $F_h$ (respectively $E_h$).

\begin{proposition}\label{scambio}
For every $1 \leq h \leq \lfloor \frac{k}{2} \rfloor$ such that $\gcd(k,h) = 1$, $E_{k-h} = (F_h \setminus \{1\}) \cup \{2\}$ and $F_{k-h} =  (E_h \setminus \{2\}) \cup \{1\}$.
\end{proposition}

\begin{proof}
The result is easy to prove for $h=1$. Let $h' = k - h$. Since $\gcd(k,h)=1$, then $\gcd(k,h')=1$,
$E_{h'} = \{1 + h', 1 + 2h', \ldots, 1+(r'-1)h', 2\}$ and $F_{h'} = \{2 + h', 2 + 2h', \ldots, 2+(s'-1)h', 1\}$, where $r' = (h')^{-1}$ and $s' = k - (h')^{-1}$ in $\mathbb{Z}_k$.\\
Let $s$ denote $k - h^{-1}$ in $\mathbb{Z}_k$; it follows that
$$
1 + k-h \equiv 2 + (s-1)h\pmod k.
$$

Then $1 + 2(k-h) \equiv 2 + (s-2)h$ and so on until $1 + (s-1)(k-h) \equiv 2 +
h$ and $1 + s(k-h) \equiv 2$ (mod $k$). Thus
$E_{k-h} = \{2 + (s-1)h, 2 + (s-2)h, \ldots, 2 + h, 2\} = (F_h \setminus \{1\}) \cup \{2\}$.

Moreover, $2 + k-h \equiv 1 + (r-1)h$ (mod $k$), where $r = h^{-1}$ in $\mathbb{Z}_k$; thus
$F_{k-h} = \{1 + (r-1)h, 1 + (r-2)h, \ldots, 1+h, 1\} = (E_h\setminus \{2\}) \cup \{1\}$.
\end{proof}

\begin{corollary}\label{concluso}
If $\alpha = (a_1,a_2,\ldots, a_k)$ is an aperiodic $h$-singular $k$-composition of $n$, then every
$a_i$ is equal to $a_1$ or $a_2$, $1\leq i\leq k$, as long as $i \in F_h$ or $i \in E_h$ respectively. Then $a_1$ and $a_2$ are distinct,
and they satisfy the relation
\begin{equation}\label{equality}
 (k - h^{-1})a_1 + h^{-1}a_2 = n.
\end{equation}
\end{corollary}

\begin{corollary}
If an aperiodic composition contains more than two distinct elements, then it is not singular.
\end{corollary}

Previous results allow us to give a characterization of singular compositions, which turns
out to be a method for their construction.

\begin{theorem}\label{soluzione}
Let $h,k,n$ be positive integers such that $1 \leq h&lt;k \leq n$ and $\gcd(k,h) = 1$. An aperiodic $k$-composition $\alpha = (a_1, a_2,\ldots, a_k)$ is $h$-singular if and only if $a_1\neq a_2$ and the pair of
elements $(a_1,a_2)$ is a solution of the equation
\begin{equation}\label{somma2}
(k - h^{-1})x_1 +  h^{-1}x_2 = n,
\end{equation}
where $h^{-1}, k - h^{-1} \in \mathbb{Z}_k$, and each $a_i$ coincides with $a_1$ or $a_2$ for $i \in F_h$ or $i \in E_h$ respectively.
\end{theorem}

\begin{proof}
If $\alpha$ is $h$-singular, then by Corollary \ref{concluso} the property holds.\\
Now let us assume that the pair of distinct integers $(a_1,
a_2)$ is solution of the equation (\ref{somma2}) and each $a_i$
coincides with $a_1$ or $a_2$ for $i \in F_h$ or $i \in E_h$
respectively. Hence, for $h\neq 1,k-1$, the composition $\alpha=(a_1,a_2,\ldots,a_k)$ which has the elements $a_1$ and $a_2$ in the positions given by (\ref{due}) and
(\ref{uno}) respectively, is $h$-singular. Lastly, if $h=1$,
$\alpha=(a_1,a_2,a_1,\ldots,a_1)$ is $1$-singular, while if $h=k-1$, $\alpha=
(a_1,a_2,\ldots,a_2)$ is $(k-1)$-singular.
\end{proof}

\begin{example}
The list of $h$-singular $9$-compositions with $a_1 =1$ and $a_2 = 2$ is
\begin{enumerate}
\item
for $h=1$, $\alpha_1 = (1,2,1,1,1,1,1,1,1)$;
\item
for $h=2$, $\alpha_2 = (1,2,2,1,2,1,2,1,2)$;
\item
for $h=4$, $\alpha_4 = (1,2,2,2,2,1,2,2,2)$;
\item
for $h=5$, $\alpha_5 = (1,2,1,1,1,2,1,1,1)$;
\item
for $h=7$, $\alpha_7 = (1,2,1,2,1,2,1,2,1)$;
\item
for $h=8$, $\alpha_8 = (1,2,2,2,2,2,2,2,2)$
\end{enumerate}
where the corresponding integers are $n_1 =10$, $n_2 =14$, $n_4 =16$, $n_5=11$, $n_7=13$ and $n_8 =17$. Note that the compositions $\alpha_5$, $\alpha_7$ and $\alpha_8$ are obtained from $\alpha_4$, $\alpha_2$ and $\alpha_1$ respectively, by exchanging $1$ with $2$ after the first two positions.
\end{example}

Let $\alpha=(a_1,a_2,\ldots,a_k)$ be an $h$-singular composition.
By Proposition \ref{scambio}, it follows that by exchanging $a_1$ and $a_2$ after the first two positions, we obtain a $(k-h)$-singular composition.
We now prove that by exchanging only the first two elements we obtain again a $(k-h)$-singular composition.

\begin{proposition}
Let $\alpha = (a_1,a_2,\ldots, a_k)$ be an aperiodic $h$-singular composition of $n$, where $1 \leq h \leq k-1$. Then $\alpha^*=(a_2,a_1,a_3,\ldots, a_k)$ is a $(k-h)$-singular composition of $n$, obtained from $\alpha$ by rotation.
\end{proposition}

\begin{proof}
Consider the composition $\alpha^*=(a^*_1,a^*_2,\ldots,a^*_k)=(a_2,a_1,a_3,\ldots,a_k)$ of
$n$. The set $E^*$ of indices of the elements equal to $a^*_2$ in $\alpha^*$ satisfies $E^*=(F_h\setminus\{1\})\cup\{2\}=E_{k-h}$ (Proposition \ref{scambio}). The same relation holds for $F^*=F_{k-h}$, where $F^*$ is the set of indices of the elements
equal to $a^*_1$ in $\alpha^*$. Then $\alpha^*$ is a $(k-h)$-singular composition of $n$.
Note that the composition $\alpha'=(a_{1+h},a_{2+h},\ldots,a_k,a_1,\ldots,a_h)$ is $(k-h)$-singular and is obtained from $\alpha$ by rotation. Moreover $a_2=a_{1+h}$ and $a_1=a_{2+h}$. Since the first two elements of $\alpha^*$ coincide with the first two of $\alpha'$ and both the compositions are $(k-h)$-singular, $E^*=E'$ and $F^*=F'$. Thus $\alpha^*=\alpha'$, and the result follows.
\end{proof}

\section{Decompositions and extensions}\label{DecExt}

In this section we investigate two decompositions and some extensions of an aperiodic singular composition.

\begin{theorem}\label{emme}
Let $\alpha=(a_1,a_2,\ldots,a_k)$ be an aperiodic $h$-singular $k$-composition of $n$, where $k = hq + r$ and $1\leq r&lt;h$. Then $\alpha =\lambda \mu \lambda \cdots \lambda$, where $\lambda = (a_1,a_2,
\ldots, a_h)$, $\mu$ is the sequence of the last $r$ elements of $\lambda$ and $q$ is the multiplicity of $\lambda$. Moreover $\lambda$ is a $(h-r)$-singular $h$-composition of $a_1 + \cdots + a_h$.
\end{theorem}

\begin{proof}
Since $\alpha$ is $h$-singular, the sequences $\beta=(a_{1}+ a_{2}, a_3, \ldots, a_k)$ and
$\gamma =(a_{1+h}+ a_{2+h}, a_{3+h}, \ldots, a_{k+h})$ coincide. In particular this holds for the subsequences $\beta'$ and $\gamma'$ obtained by deleting the first $h-1$ elements of $\beta$ and $\gamma$ respectively.
If $1\leq h\leq\lfloor\frac{k}{2}\rfloor$, by comparing
$\beta'=(a_{1+h},a_{2+h},\ldots, a_k)$ and $\gamma'=(a_{1+2h},a_{2+2h},\ldots, a_k,a_1,\ldots,
a_h)=(a_{1+2h},\ldots, a_k)\lambda$, where $\lambda = (a_1,a_2,
\ldots, a_h)$, we obtain that the sequence $(a_{k-(h-1)}, \ldots, a_k)$ formed by the last $h$ elements of $\beta'$ coincides with $\lambda$.
Then the sequence of length $h$ in $\gamma'$ which precedes the last subsequence $\lambda$ coincides again with $\lambda$. We continue until we find a subsequence $\mu$ of length less than $h$ in $\beta'$, which is formed by the last $r$ elements of $\lambda$. Thus $\mu = (a_{h - (r-1)}, a_{h-(r-2)},\ldots, a_h)$.
If $\lfloor\frac{k}{2}\rfloor&lt;h\leq k-1$, by comparing $\beta'$ and $\gamma'=\mu$ we obtain $\alpha=\lambda\mu$.
In both cases $\alpha = \lambda \mu \lambda\cdots \lambda$, where $\lambda$ occurs $q$ times.

Let us assume that $r&gt;1$. Since $\alpha$ is $h$-singular, the sequence
$$
(a_1+a_2, a_3, \ldots, a_h, a_{h - (r-1)}, a_{h - (r-2)}, \ldots, a_h)\lambda^{q-1}
$$
coincides with
$$
(a_{h - (r-1)}+a_{h - (r-2)}, a_{h - (r-3)}, \ldots, a_h)\lambda^q.
$$
Therefore the sequences of the first $h-1$ elements coincide
$$
(a_1+a_2, a_3, \ldots, a_h)
=
(a_{h - (r-1)}+a_{h - (r-2)}, a_{h - (r-3)}, \ldots, a_h, a_1, \ldots, a_{h - r}).
$$
Thus the composition $\lambda$ is $(h-r)$-singular.
A similar argument applies in the case $r=1$.
\end{proof}

\begin{proposition}
Let $\alpha=(a_1,a_2,\ldots,a_k)$ be an aperiodic $h$-singular $k$-composition of $n$, where $k = hq + r$ and $1&lt;r&lt;h$. Then $\alpha = \sigma\lambda \cdots \lambda$, where $\lambda = (a_1,a_2, \ldots, a_h)$,
$\sigma = (a_1, a_2,\ldots, a_r)$ and the multiplicity of $\lambda$ is $q $. Moreover $\lambda$ is a $(h-r)$-singular $h$-composition of $a_1 + \cdots + a_h$.
\end{proposition}

\begin{proof}
Let $\lambda = (a_1,a_2,\ldots, a_h)$ and $\sigma = (a_1, a_2, \ldots, a_r)$. By applying the same argument used in the proof of Theorem \ref{emme} to the subsequences obtained by deleting the first $r-1$ elements of $\beta$ and $\gamma$, the result follows.
\end{proof}

\begin{corollary}
In the case of $r = 1$, there is not a decomposition $\alpha = \sigma \lambda\lambda \cdots \lambda$.
\end{corollary}

\begin{proof}
In the case of $r = 1$, $\sigma$ is reduced to the element $a_1$. This implies the relation $a_1 + a_2 = 2a_1$; then $a_2 = a_1$, a contradiction to the assumption that $\alpha$ is aperiodic.
\end{proof}

\begin{corollary}
 If $k = hq + r$ and $1&lt; r&lt; h$, then $\sigma \lambda = \lambda \mu$.
\end{corollary}

Now we investigate an operation which can be considered the inverse of the decomposition; namely we want to determine an extension of a singular composition which turns out to be again a singular composition.

\begin{theorem}\label{estensione}
Let $\alpha$ be an aperiodic $h$-singular $k$-composition of $n$, and let $\nu$ denote the sequence formed by the last $k-h$ elements of $\alpha$. The $k'$-composition $\beta = \alpha \nu \alpha \cdots \alpha$, where $k' = kq' + k-h$ and $q'$ is the multiplicity of $\alpha$, is $k$-singular.
\end{theorem}

\begin{proof}
Let $\alpha = (a_1, a_2, \ldots, a_k)$ be an aperiodic $h$-singular $k$-composition of $n$, where $k&gt;2$ and $1\leq h&lt;k-1$.
The composition $\beta = \alpha \nu \alpha \cdots \alpha$, where $\nu$ denotes the sequence formed by the last $k-h$ elements of $\alpha$, is $k$-singular if
$$
(a_1+a_2, \ldots, a_k, a_{1+h}, \ldots, a_k)\alpha^{q'-1}=(a_{1+h}+a_{2+h}, \ldots, a_k)\alpha^{q'}.
$$
In order to prove the equality, it is sufficient to show that
\begin{equation}\label{nuova}
(a_1+a_2, a_3, \ldots, a_k, a_{1+h}, \ldots, a_k) = (a_{1+h}+a_{2+h}, \ldots, a_k, a_1,\ldots,a_k).
\end{equation}
Since $\alpha$ is $h$-singular, $(a_1+a_2, a_3, \ldots, a_k ) = (a_{1+h} + a_{2+h}, \ldots, a_k, a_1, \ldots, a_{h})$.
Thus the left side of (\ref{nuova}) coincides with $(a_{1+h} + a_{2+h}, \ldots, a_k, a_1,\ldots, a_{h}, a_{1+h}, \ldots, a_k)$ and the result follows. A similar argument applies in the cases $k=2$ and $h=k-1$.
\end{proof}


\section{Classical integer sequences}\label{Sequences}

Let $\alpha$ be an $h$-singular $k$-composition of $n$. The composition $\beta = \alpha \nu \alpha \cdots \alpha$, where $\nu$ is the sequence formed by the last $k-h$ elements of $\alpha$ and $\alpha$ is repeated $q$ times, is called a \emph{$q$-extension} of $\alpha$.
By consecutive extensions, we determine a sequence of singular compositions and
therefore a sequence of integers corresponding to the numbers of their parts.

\subsection{Fibonacci sequences}

Let us consider the $h_0$-singular $k_0$-composition $\alpha_0 = (a,b)$, with $a \neq b$, $k_0=2$ and $h_0=1$.
The $2$-extension of $\alpha_0$ is the $h_1$-singular $k_1$-composition $\alpha_1 = \alpha_0 \nu_0 \alpha_0 = (a,b,b,a,b)$, where $k_1 = k_0\cdot2+1$, $h_1 = k_0 = 2$ and $\nu_0$ is the composition formed by last $(k_0 - h_0)=1$ element of $\alpha_0$.
The consecutive $2$-extension is the $h_2$-singular $k_2$-composition $\alpha_2 = \alpha_1 \nu_1 \alpha_1 = (a,b,b,a,b,b,a,b,a,b,b,a,b) $, where $k_2= k_1\cdot2+3$, $h_2 = k_1$ and $\nu_1$ is the composition formed by last $(k_1 - h_1)=3$ elements of $\alpha_1$ and so on.

The first values of the sequence of the numbers $(k_n)_{n\geq0}$ of parts of the $2$-extensions of $\alpha_0$ are
$$
2, 5, 13, 34, 89, 233, \ldots
$$
These numbers appear as the first integers, but the first two, in the sequence  \seqnum{A001519} \cite{sloane}, which is obtained from the recursive relation
\begin{equation}\label{ricorrenza}
a_n = 3a_{n-1} - a_{n-2},
\end{equation}
with the initial conditions $a_0 = 1$, $a_1 = 1$.
We prove that the integers $k_n$ satisfy the same recursive relation.

\begin{lemma}\label{2estensione}
The integers $k_n$ of the parts of the $2$-extensions of the $1$-singular $2$-composition $(a, b)$, with $a \neq b$,
satisfy the recursive relation:
$$
k_n = 3k_{n-1} - k_{n-2}
$$
with the initial conditions $k_0 = 2$, $k_1 = 5$.
\end{lemma}

\begin{proof}
Recall that, by Theorem \ref{estensione},
$$
k_n = 2k_{n-1} + k_{n-1} - h_{n-1}.
$$
Because $h_{n-1} = k_{n-2}$, the result follows.
\end{proof}

The following corollary is straightforward.

\begin{corollary}
The integers $h_n$ associated to the $2$-extensions of the $1$-singular $2$-composition $(a, b)$, with $a \neq b$,
satisfy the recursive relation:
$$
h_n = 3h_{n-1} - h_{n-2}
$$
with the initial conditions $h_0 = 1$, $h_1 = 2$.
\end{corollary}

It is easy to prove that the generating function of the sequence of the integers $k_n$ is
$$
\frac{2 - x}{1 - 3x + x^2},
$$
and 
$$k_n = \frac{2 + \sqrt{5}}{\sqrt{5}}(\frac{3 + \sqrt{5}}{2})^n + \frac{-2 + \sqrt{5}}{\sqrt{5}}(\frac{3 - \sqrt{5}}{2})^n.$$

\begin{proposition}\label{secondo}
The sequence
\begin{equation}\label{sequenzaFib}
k_0, k_1 - h_1, k_1, k_2 - h_2, k_2, k_3 - h_3, \ldots
\end{equation}
coincides with the sequence of Fibonacci numbers $F_n$, with initial conditions $F_2=2, F_3=3$.
\end{proposition}

\begin{proof}
We have to prove that every element of (\ref{sequenzaFib}) is the sum of the preceding two elements
and the initial conditions coincide. For $i\geq 1$, $k_i = k_{i}-h_{i} + k_{i-1}$,
because $h_{i} = k_{i-1}$. Moreover, for $i\geq 2$, $k_i - h_i = k_{i-1} + k_{i-1} - h_{i-1}$
by Lemma \ref{2estensione}.
Because $k_0=2$, $k_1=5$ and $h_1=2$, the initial conditions are $2$ and $3$, which coincide with $F_2$ and $F_3$ of the Fibonacci sequence \seqnum{A000045}.
\end{proof}

Another consequence of  Proposition \ref{secondo} is that the elements $k_i$, $i\geq 0$, form a bisection of the Fibonacci sequence;
this result turns out to be one of the comments to \seqnum{A001519}.

By repeating the previous procedure for $q&gt; 2$, we easily obtain a sequence
satisfying the recursive relation
$$
a_n = (q+1)a_{n-1} - a_{n-2},
$$
with the initial conditions $a_0 = 2$, $a_1 = 2q+1$.

In the particular case of $q=3$, we obtain the sequence whose first elements are
$$
2, 7, 26, 97, \ldots
$$
which coincides with \seqnum{A001075}, but the first element.

Again, for $q=4$ we obtain a sequence whose first elements are
$$
2, 9, 43, 206, \ldots
$$
which coincides with \seqnum{A002310}, but the first element.

\subsection{Lucas sequences}

The first values of the sequence of the numbers $(p_n)_{n\geq0}$ of parts of the $2$-extensions of the $2$-singular $3$-composition $(a, b, b)$, with $a\neq b$, are
$$
3, 7, 18, 47, 123,  \ldots
$$
These integers coincide with the first integers, but the first one, of \seqnum{A005248}, which is obtained from the recursive relation \eqref{ricorrenza}, with the initial conditions $a_0 = 2$, $a_1 = 3$.

Using the same procedure of Lemma \ref{2estensione}, the numbers $p_n$ satisfy the same recursive relation with initial conditions $p_0=3$ and $p_1=7$.
Moreover the generating function of the sequence of the integers $p_n$ is
$$
\frac{3 - 2x}{1 - 3x + x^2},
$$
and 
$$p_n = (\frac{3 + \sqrt{5}}{2})^{n+1} + (\frac{3 - \sqrt{5}}{2})^{n+1}.$$


\begin{proposition}
The sequence
\begin{equation}
h_0, p_0-h_0, p_0, p_1 - h_1, p_1, p_2 - h_2, p_2, p_3 - h_3, \ldots
\end{equation}
coincides with the sequence of Lucas numbers $L_n$, with initial conditions $L_0=2, L_1=1$.
\end{proposition}

Another consequence of the previous result is that the elements $p_i$, $i\geq 0$, form a bisection of the Lucas sequence \seqnum{A000032}, as noted in a comment to \seqnum{A005248}.

\subsection{Other integer sequences}

We now consider the sequence of the numbers $(t_n)_{n\geq0}$ of parts of $2$-extensions of the $3$-singular $4$-compositions
$(a, b, b, b)$, with $a \neq b$, that is
$$
4, 9, 23, 60, 157, \ldots
$$

This sequence, which is not contained in \cite{sloane}, satisfies the recursive relation \eqref{ricorrenza},
with initial conditions $t_0=4$ and $t_1=9$.
The corresponding generating function is
$$
\frac{4 - 3x}{1 - 3x + x^2},
$$
and 
$$t_n = \frac{3 + 2\sqrt{5}}{\sqrt{5}}(\frac{3 + \sqrt{5}}{2})^n + \frac{-3 + 2\sqrt{5}}{\sqrt{5}}(\frac{3 - \sqrt{5}}{2})^n.$$


By continuing, we may obtain other integer sequences by $q$-extension, with $q \geq 2$,
of the singular composition $(a, b, \ldots, b)$, where $b$ occurs more than three times.

\section{Conclusion}

The notion of singular composition can be generalized as follows.
We call the composition $\alpha= (a_1, a_2, \ldots, a_k)$ \emph{$(h,i,j)$-singular},  if
\begin{align}\label{altra}
&amp;(a_1, a_2, \ldots, a_{i-1}, a_i + a_j, a_{i+1}, \ldots, a_{j-1}, a_{j+1}, \ldots, a_k) =\nonumber\\
&amp;=(a_{1+h}, a_{2+h}, \ldots, a_{i-1+h}, a_{i+h} + a_{j+h}, a_{i+1+h}, \ldots, a_{j-1+h}, a_{j+1+h}, \ldots, a_{k+h}),
\end{align}
where $1 \leq h \leq k-1$, $1 \leq i&lt;j \leq k$ and the indices are modulo $k$.

This definition leads to compositions which can not be obtained from equation (\ref{definizione}).
In fact, $(1,1,2,2,2)$ satisfies
$(a_1+a_3,a_2,a_4,a_5)=(a_{1+h}+a_{3+h},a_{2+h},a_{4+h},a_{5+h})$ for $h=4$, but it does not satisfy any equation (\ref{definizione}).

Thus this definition poses the problem to find necessary and sufficient conditions based on which a given aperiodic sequence with two distinct elements satisfies (\ref{altra}).

\section{Acknowledgments}
The authors thank the anonymous referee for his valuable suggestions which led to an improvement of the manuscript.

\bigskip

\begin{thebibliography}{99}
\bibitem{Widened}
F. Beggas, M. M. Ferrari, and N. Zagaglia Salvi, Combinatorial interpretations and enumeration of particular bijections,
{\it Riv. Mat. Univ. Parma} {\bf 8} (2017). To appear.

\bibitem{Kramer}
A.-V. Kramer, A particular Hamiltonian cycle on middle levels in the De
Bruijn digraph, {\it Discrete Math.} {\bf 312} (2012), 608--613.

\bibitem{Riordan}
J. Riordan, \emph{An Introduction to Combinatorial Analysis}, Wiley, 1958.

\bibitem{sloane} N. J. A. Sloane, The on-line encyclopedia of integer sequences, 2017. Available at \url{https://oeis.org}.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary 05A17; Secondary 11B39. 

\noindent \emph{Keywords:} ordered partition, composition, singular composition, Fibonacci number, Lucas number.

\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A000032},
\seqnum{A000045},
\seqnum{A001075},
\seqnum{A001519},
\seqnum{A002310}, and
\seqnum{A005248}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 20 2017;
revised versions received  May 11 2017; August 2 2017.
Published in {\it Journal of Integer Sequences}, September 5 2017.

\bigskip
\hrule
\bigskip

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


\end{document}

                                                                                

</pre></body></html>