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

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

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

\begin{center}
\vskip 1cm{\LARGE\bf 
Cyclic Compositions of a 
Positive Integer  \\
\vskip .1in
with Parts Avoiding an Arithmetic Sequence
}
\vskip 1cm
\large
Petros Hadjicostas \\ 
School of Mathematics and Statistics \\ 
Victoria University of Wellington \\
Wellington 6140 \\
New Zealand\\
\href{mailto: peterhadji1@gmail.com}{\tt peterhadji1@gmail.com}
\end{center}

\vskip .2 in

\begin{abstract}
A linear composition of a positive integer $n$ is a finite sequence of
positive integers (called parts) whose sum equals $n$. A cyclic
composition of $n$ is an equivalent class of all linear compositions of
$n$ that can be obtained from each other by a cyclic shift. In this
paper, we enumerate the cyclic compositions of $n$ that avoid an
increasing arithmetic sequence of positive integers.  In the case where
all multiples of a positive integer $r$ are avoided, we show that the
number of cyclic compositions of $n$ with this property equals to or
is one less than the number of cyclic zero-one sequences of length $n$
that do not contain $r$ consecutive ones. In addition, we show that
this number is related to the $r$-step Lucas numbers.
\end{abstract}

\section{Introduction}

Beck and Robbins~\cite{beck2015} use generating functions to give an alternative proof of a result by Robbins~\cite{rob2014, rob2015} regarding the number of $r$-regular (linear) compositions of a positive integer $n$. By a {\it (linear) composition} of a positive integer $n$ of {\it length} $k$ we mean a $k$-tuple
$(\lambda_1,\lambda_2,\ldots,\lambda_k) \in \mathbb{Z}_{&gt;0}^k$ such that
\begin{equation}\label{bailey}
n=\lambda_1+\lambda_2+\cdots+\lambda_k.
\end{equation}
Here the numbers $\lambda_1,\lambda_2,\ldots,\lambda_k$ are called the {\it parts} of the composition.  By an {\it $r$-regular (linear) composition} of $n$ with length $k$ we mean a composition $(\lambda_1,\lambda_2,\ldots,\lambda_k)$ of $n$ such that none of its parts are positive multiples of $r$. A result that 
appears in Beck and Robbins~\cite{beck2015} and Robbins~\cite{rob2014, rob2015}, and which is stated as Theorem~\ref{shelf2} in this paper, gives linear recursive formulas for the number of $r$-regular linear compositions of $n$.

In this paper, we state and prove a similar result for $r$-regular cyclic compositions (see Theorem~\ref{cook}). To achieve that, we first provide a formula for the number of cyclic compositions of a positive integer $n$ with length $k$ whose parts belong to a set $A \subseteq \mathbb{Z}_{&gt;0}$. See  formula~(\ref{123456}) in  Theorem~\ref{shelf1}. This formula is a generalization of formulas found by Sommerville~\cite{Sommer} more than a century ago (see below).

Cyclic compositions of length $k$ of positive integer $n$ can be defined as equivalent classes on the set of all linear compositions of $n$ with length $k$ such that two compositions belong to the same class if and only if one can be obtained from the other by a cyclic shift. If $(\lambda_1,\ldots,\lambda_k)$ is a representative of an equivalent class, we denote the class
by $[(\lambda_1,\ldots,\lambda_k)]_R$. For example, if $n=4$, then we have five equivalent classes (cyclic compositions):
$${\rm (i)} \,\, [(4)]_R, \quad {\rm (ii)} \,\, [(1,3)]_R=[(3,1)]_R, \quad {\rm (iii)}\,\, [(2,2)]_R,$$
$${\rm (iv)} \,\, [(1,1,2)]_R=[(2,1,1)]_R=[(1,2,1)]_R, \quad {\rm (iv)} \,\, [(1,1,1,1)]_R.$$

Given a set $A \subseteq \mathbb{Z}_{&gt;0}$, we denote by $c_A^L(n;k)$ and $c_A^R(n;k)$ the number of linear and cyclic compositions, respectively, of length $k$ of positive integer
$n$ with parts in $A$. We also let
$$c_A^L(n)=\sum_{k=1}^n c_A^L(n;k) \quad \mbox{and} \quad c_A^R(n)=\sum_{k=1}^n c_A^R(n;k).$$
When $A=\mathbb{Z}_{&gt;0}$, it was proven by MacMahon~\cite{fujit1}, and probably others before him, that (for $1 \leq k \leq n$)
\begin{equation}\label{beforehim}
c_{\mathbb{Z}_{&gt;0}}^L(n;k)={n-1 \choose k-1} \quad \mbox{and} \quad c_{\mathbb{Z}_{&gt;0}}^L(n)=2^{n-1}.
\end{equation}
Similarly, it was proven by Sommerville~\cite{Sommer} that, when $n$ is prime and $1 \leq k &lt; n$, $$c_{\mathbb{Z}_{&gt;0}}^{R}(n;k)=\frac{1}{n}{n \choose k}.$$ When $n=2^m$ for some positive integer $m$ and $k$ is an odd positive integer less than $n$, he proved that $$c_{\mathbb{Z}_{&gt;0}}^R(n;k)=\frac{1}{2^m}{2^m \choose k}.$$

Sommerville's~\cite{Sommer} results were generalized more than seven decades later by Razen et al.~\cite{razen}; also see~\cite{akin}, \cite[p.~48]{fla}, \cite{knob33}, \cite[pp.~70--71]{wehr}, and \cite{salvi1}. In these references, it is proven that (for $1 \leq k \leq n$)
\begin{equation}\label{sandra}
c_{\mathbb{Z}_{&gt;0}}^R(n;k)=\frac{1}{n} \sum_{j | \gcd(n,k)} \phi(j) {n/j \choose k/j} \quad \mbox{and} \quad
c_{\mathbb{Z}_{&gt;0}}^R(n)=-1+\frac{1}{n} \sum_{j|n} \phi(j)2^{\frac{n}{j}},
\end{equation}
where $\phi(n)$ is Euler's totient function at $n$. (Here the summation ranges over all positive divisors $j$ of $\gcd(n,k)$ in the first sum and all positive divisors $j$ of $n$ is the second sum.) The numbers $(c_{\mathbb{Z}_{&gt;0}}^R(n): n \in \mathbb{Z}_{&gt;0})$ appear in \seqnum{A037306}. We generalize equations~(\ref{sandra}) to the case when $A$ is any subset of $\mathbb{Z}_{&gt;0}$; see equations~(\ref{123456}) and (\ref{santa1}) in this paper.

We also prove that the number of cyclic $r$-regular compositions of $n$ is closely related to the number of cyclic 0-1 sequences of length $n$ that do not contain $r$
consecutive ones;  see Theorem~\ref{cook}. A 0-1 sequence of length $n$, say $(\delta_1,\ldots,\delta_n)$ with $\delta_i \in \{0,1\}$ for $i=1,2,\ldots,n$, gives rise to a cyclic sequence $[(\delta_1,\ldots,\delta_n)]_R$ in the same way cyclic compositions were defined above. For example, there are 4 cyclic 0-1 sequences of length 3:
$${\rm (i)}\,\, [(0,0,0)]_R, \quad {\rm (ii)}\,\, [(1,0,0)]_R=[(0,1,0)]_R=[(0,0,1)]_R,$$
$${\rm (iii)} \,\, [(0,1,1)]_R=[(1,0,1)]_R=[(1,1,0)]_R, \quad {\rm (iv)}\,\, [(1,1,1)]_R.$$
The total number of 0-1 cyclic sequences of length $n$ is $c_{\mathbb{Z}_{&gt;0}}^R(n)+1.$ This was proven by MacMahon~\cite{1111}. See also~Bender~\cite{2222} and Zhang and Hadjicostas~\cite{zhang2}.

If in a cyclic 0-1 sequence $[(\delta_1,\ldots,\delta_n)]_R$ we identify 1 with a black bead and  0 with a white bead, then we get a {\it (fixed) necklace} with $n$ beads; e.g., see~Graham et al.~\cite[Section 4.9]{graham}. In Knopfmacher and Robbins~\cite{knob33}, a bijection is given between necklaces of $n$ beads with $k$ black and~$n~-~k$ white beads, and cyclic compositions of $n$ with $k$ parts. This bijection, however, does not seem to help in establishing a connection between the number of cyclic
$r$-regular compositions of $n$ with the number of 0-1 cyclic sequences of length $n$ that do not contain $r$ consecutive ones, which is one the main topics of this paper. The bijection in Knopfmacher and Robbins~\cite{knob33} does, however, prove that the number of necklaces
with $n$ beads of which $k$ are black and the rest white is given by the number $c^R_{\mathbb{Z}_{&gt;0}}(n;k).$ In addition, it also establishes  MacMahon's~\cite{1111} result that the total number of necklaces with $n$ beads which are either black or white is  $c_{\mathbb{Z}_{&gt;0}}^R(n)+1$
(where the extra 1 corresponds to the necklace consisting of $n$ white beads).

The organisation of the paper is as follows. In Section~\ref{main111}, we first provide a formula that connects $c_A^R(n;k)$ to $c_A^L(n/s; k/s)$, where
$s$ ranges over the common divisors of $n$ and $k$.
We also provide a formula that connects $c_A^R(n)$ to $c_A^L(n/s)$, where $s|n$, through a sequence of integers $(g_A(n): n \in \mathbb{Z}_{&gt;0}),$
which is interesting on its own right. We provide a generating function and recursive formulas for this sequence of integers (see Lemma~\ref{richard}). Using these results, we provide a generating function for the numbers $c_A^R(n)$ (see Corollary~\ref{torrr}), and we mention that this generating function is reminiscent of the theory in Flajolet and Soria~\cite{fla2}.
For the case when $A$ is the set of positive integers that avoid all multiples of a fixed integer, we remind the reader of a theorem in Beck and Robbins~\cite{beck2015} and
Robbins~\cite{rob2015} that provides
recursive formulas for the numbers $c_A^L(n)$, and then (in Corollary~\ref{bobo}) we proceed to state a similar theorem for the numbers $g_A(n)$. This result involves the generalized Lucas numbers.  In Theorem~\ref{shelf3}, we correct a result that appeared in Beck and Robbins~\cite{beck2015} for the case when $A$ avoids an increasing arithmetic sequence, and we state a similar result for the numbers $g_A(n)$ in Corollary~\ref{bvc}.

The proofs of most results in Section~\ref{main111} appear in Section~\ref{profits} of the paper. Section~\ref{examples} contains examples that illustrate the theory and results of this paper, while Section~\ref{remarks} contains some concluding remarks.

Note that some of the sequences in this paper maybe shifted versions of the corresponding cited sequences in OEIS~\cite{EEE1}. Not all authors agree on what is the first term of each sequence.

\section{The main results}\label{main111}

The following theorem connects the numbers of linear and cyclic compositions of $n$ with parts in $A$, and it allows us to prove our claims in this paper. This result is important because the theory of enumeration of all linear compositions with parts in $A$ is more well-established~\cite{heubach, heubach1} than the corresponding theory for the enumeration of cyclic compositions with parts in $A$. (Proofs of the results in this section, which have not been proven elsewhere, appear in the next section of the paper.)

\begin{theorem}\label{shelf1}
The number of cyclic compositions of $n$ of length $k$ with parts in $A$ is given by
\begin{equation}\label{123456}
c_A^R(n;k)=\frac{1}{k} \sum_{s|\gcd(n,k)} \phi(s) \, c_A^L\left(\frac{n}{s}; \frac{k}{s}\right).
\end{equation}
Also, the total number of cyclic compositions (of any length) of $n$ with parts in $A$ is
\begin{equation}\label{santa1}
c_A^R(n)=\frac{1}{n}\sum_{d|n} \phi(d) g_A\left(\frac{n}{d}\right),
\end{equation}
where
\begin{equation}\label{nana}
g_A(s)=s \sum_{k=1}^s \frac{c_A^L(s;k)}{k} \quad \mbox{for $s \in \mathbb{Z}_{&gt;0}$}.
\end{equation}
\end{theorem}

The numbers $(g_A(n): n \in \mathbb{Z}_{&gt;0})$ are used throughout this paper, and they satisfy some useful recurrences; see equations (\ref{true2}) and (\ref{true3})
in the lemma below.

\begin{lemma}\label{richard}
The generating function of the numbers $g_A(n)$ is given by
\begin{equation}\label{true1}
\sum_{n\geq 1} g_A(n) x^{n} =\frac{\sum_{s \in A} s x^{s}}{1-\sum_{s \in A} x^s}.
\end{equation}
For each positive integer $n$,
\begin{equation}\label{true2}
g_A(n)=\sum_{s=1}^{n-1} g_A(s)I(n-s \in A)+n\,I(n \in A)
\end{equation}
and
\begin{equation}\label{true3}
g_A(n)=\sum_{s=1}^{n-1} s\,I(s\in A) \,c_A^L(n-s) +n\,I(n \in A),
\end{equation}
where $I(x \in A)=1$ if $x \in A$, and zero otherwise.
\end{lemma}

Since an empty sum is by definition zero, equations~(\ref{true2}) and~(\ref{true3})
in Lemma~\ref{richard} give $g_A(1)=I(1 \in A)$. This of course agrees with the equation $g_A(1)=c_A^L(1;1)=I(1 \in A).$

\begin{remark}
{\rm Using the generating function of the numbers $c_A^L(n)$ (see~Beck and Robbins~\cite{beck2015} and Moser and Whitney~\cite{moser}, or see equation (\ref{suko}) in this paper), one can easily show that, for $n \in \mathbb{Z}_{&gt;0},$
\begin{equation}\label{remark}
c_A^L(n)=\sum_{s=1}^{n-1} c_A^L(s)\, I(n-s \in A)+I(n \in A).
\end{equation}
}
\end{remark}

The following result is reminiscent of the theory in Flajolet and Sedgewick~\cite[pp.~27 and~729--730]{fla} and Flajolet and Soria~\cite{fla2} about the generating function of cycles of unlabelled combinatorial structures, but we derive it independently  using Theorem~\ref{shelf1} and Lemma~\ref{richard} above.

\begin{corollary}\label{torrr}
The generating function of the total number of cyclic compositions (of any length) of $n$ with parts in $A$, i.e., $c_A^R(n)$, is
$$\sum_{n \geq 1} c_A^R(n) x^n =\sum_{n \geq 1} \frac{\phi(n)}{n} \log \frac{1}{1-\sum_{s \in A} x^{sn}}.$$
\end{corollary}

Robbins~\cite{rob2015} and Beck and Robbins~\cite{beck2015} have shown the following result for the special case when we count all $r$-regular linear compositions of $n$.

\begin{theorem}\label{shelf2}
If $r$ is a fixed positive integer and $A$ is the set all of positive integers that are not multiples of $r$, then the number of linear compositions of $n$ with parts in $A$,
i.e., $c_A^L(n)$, is given by the sequence $(f_n: n\in \mathbb{Z}_{&gt;0})$ defined recursively through
\begin{eqnarray*}
f_j &amp; = &amp; 2^{j-1} \quad \mbox{for $1 \leq j \leq r-1$},\\
f_r &amp; = &amp; 2^{r-1}-1,\\
f_j &amp; = &amp; f_{j-1}+f_{j-2}+\cdots+f_{j-r} \quad \mbox{for $j&gt;r$}.
\end{eqnarray*}
\end{theorem}

Clearly, for $r=1$ the sequence $(f_n: n\in \mathbb{Z}_{&gt;0})$ is a sequence of 0's.
As noted in ~Beck and Robbins~\cite{beck2015}, the case $r=2$ gives rise to the Fibonacci numbers, while the cases $r=3$ and $r=4$ give rise to {\it one version} of {\it Tribonacci} and {\it Tetranacci} numbers, that is, \seqnum{A001590} and \seqnum{A001631}, respectively. These sequences should not be confused, however, with the Tribonacci and Tetranacci sequences \seqnum{A000073} and \seqnum{A000078}, respectively, which are special cases of the $r$-step (or $r$-generalized) Fibonacci sequences, which are mentioned, for example, in Miles~\cite{miles} and Zhang and Hadjicostas~\cite{zhang2}. These $r$-step Fibonacci sequences are first cousins of the
$r$-step Lucas numbers defined below, which are needed in this paper.

For positive integer $r$, following Noe and Vos Post~\cite{noe} and Zhang and Hadjicostas~\cite{zhang2},
we may define the $r$-generalized Lucas numbers $(L_n^{(r)}: n \in \mathbb{Z})$ by
\begin{equation}\label{1A}
L_n^{(r)}=-1 \quad \mbox{for $n&lt;0$}, \quad L_0^{(r)}=r,
\end{equation}
and by the recursion
\begin{equation}\label{2B}
L_n^{(r)}=\sum_{i=1}^r L_{n-i}^{(r)} \quad \mbox{for all $n \geq 1$}.
\end{equation}
For $r=1$, starting from $n=0$, we get a sequence of 1's, while the case $r=2$ corresponds to \seqnum{A000032}, and it is the usual Lucas sequence. Starting at $n=0$, the cases $r=3$ and $r=4$ correspond to \seqnum{A001644} and \seqnum{A073817}, respectively.

\begin{corollary}\label{bobo}
Let $r$ be a fixed positive integer and $A$ be the set all of positive integers that are not multiples of $r$. Then the sequence $$(g_A(n)+rI(r|n): \, n \in \mathbb{Z}_{&gt;0})$$ satisfies
the same $r$-order recurrence that the sequence $(c_A^L(n): \, n \in \mathbb{Z}_{&gt;0})$ satisfies in Theorem~\ref{shelf2}, but (in general) with different initial conditions.
More specifically, $$g_A(n)=L_n^{(r)}-rI(r|n) \quad \mbox{for all $n \in \mathbb{Z}_{&gt;0}$.}$$
\end{corollary}

Let $\rho_n^{(r)}$ be the number of cyclic sequences of length $n$ consisting of 0's and 1's that do not contain $r$ consecutive 1's. For example, $\rho^{(3)}_4=4$ because we have the following cyclic sequences of length $n=4$ that avoid $r=3$ consecutive 1's:
$${\rm (i)}\,\, [(0,0,0,0)]_R, \quad {\rm (ii)}\,\, [(0,0,0,1)]_R, \quad {\rm (iii)}\,\, [(0,0,1,1)]_R, \quad {\rm (iv)}\,\, [(0,1,0,1)]_R.$$
(To be able to define $\rho_n^{(r)}$ for any $n,r \in \mathbb{Z}_{&gt;0},$ we make the convention that a sequence of length $n$ with all 1's contains $r$ consecutive 1's even if
$n&lt;r$.) For $r=2$ and $r=3$ the sequences of numbers $\rho_n^{(r)}$ 
appear in \seqnum{A000358} and \seqnum{A093305}, respectively.

Using Theorem~\ref{shelf1}, Corollary~\ref{bobo}, and a result from Zhang and Hadjicostas~\cite{zhang2}, we prove in the next section the following theorem.

\begin{theorem}\label{cook}
If $r$ is a fixed positive integer and $A$ is the set all of positive integers that are not multiples of $r$, then the number of cyclic compositions of $n$ with parts in $A$,
i.e., $c_A^R(n)$, is given by
\begin{equation}\label{cookcook}
c_A^{R}(n)=-I(r | n)+\frac{1}{n} \sum_{d | n} \phi\left(\frac{n}{d}\right) L_d^{(r)}=-I(r|n)+\rho^{(r)}_n,
\end{equation}
where $I(r|n)=1$ if $r|n$, and zero otherwise.
\end{theorem}
In other words, the previous theorem says that when $r$ does not divide $n$, the number of $r$-regular cyclic compositions of $n$ equals the number of cyclic sequences of length $n$ consisting of 0's and 1's that not contain $r$ consecutive 1's. Otherwise, if $r$ divides $n$, then $c_A^{(R)}(n)=\rho^{(r)}_n-1.$

When $A$ is the set of all positive integers that do not include any member of an increasing arithmetic sequence, say of the form $m+jr$ for $j \in \mathbb{Z}_{\geq 0}$, where $r$ and $m$ are positive integers with $m&lt;r$, we may derive a result like Corollary~\ref{bobo} above, but not as elegant. This is done in Corollary~\ref{bvc} below.

Before we do that, we remind the reader of a result in Beck and Robbins~\cite{beck2015} about the number of linear compositions of $n$ with parts that are not members of an increasing arithmetic sequence of positive integers. Unfortunately, some of the initial conditions in the recurrence in Theorem~4 in Beck and Robbins~\cite{beck2015} are not correct, so we correct them here. The proof of the corrected Theorem~4, stated as Theorem~\ref{shelf3} below, is similar to the proofs in Beck and Robbins~\cite{beck2015}, and hence it is omitted; one can also prove it using equation~(\ref{remark}) in this paper. (The notation $B-C$ denotes set difference between the sets $B$ and $C.$)

\begin{theorem}\label{shelf3}
Let $r$ and $m$ be fixed integers with $1 \leq m &lt; r$, and let
\begin{equation}\label{door}
A=\mathbb{Z}_{&gt;0}-\{m+jr:\, j \in \mathbb{Z}_{\geq 0}\}.
\end{equation}
Then the number of linear compositions of $n$ with parts in $A$, i.e., $c_A^L(n)$, is given by the sequence $(f_n: n\in \mathbb{Z}_{&gt;0})$ defined recursively through
\begin{eqnarray*}
f_n &amp; = &amp; 2^{n-1} \quad \mbox{for $1 \leq n \leq m-1$},\\
f_m &amp; = &amp; 2^{m-1}-1,\\
f_n &amp; = &amp; \sum_{i=1 \atop i \neq m}^{n-1} f_{n-i}+1 \quad \mbox{for $m+1 \leq n \leq r$},\\
f_n &amp; = &amp; \sum_{i=1 \atop i \neq m}^{r-1}f_{n-i}+2f_{n-r} \quad \mbox{for $n&gt;r$}.
\end{eqnarray*}
\end{theorem}

Using Lemma~\ref{richard}, we can prove the result below. Here, $I[n \not \equiv m \,\, ({\rm mod} \,\, r)]=1$ when $r$ does not divide $n-m$, and zero otherwise.

\begin{corollary}\label{bvc}
Let $r$ and $m$ be fixed integers with $1 \leq m &lt; r$, and assume $A$ is given by equation (\ref{door}). Then the sequence $(g_A(n): \, n \in \mathbb{Z}_{&gt;0})$ satisfies
\begin{eqnarray*}
g_A(n) &amp; = &amp; 2^{n}-1 \quad \mbox{for $1 \leq n \leq m-1$},\\
g_A(m) &amp; = &amp; 2^{m}-m-1,\\
g_A(n) &amp; = &amp; \sum_{i=1 \atop i \neq m}^{n-1} g_A(n-i)+n \quad \mbox{for $m+1 \leq n \leq r$},\\
g_A(n) &amp; = &amp; \sum_{i=1 \atop i \neq m}^{r-1}g_A(n-i)+2g_A(n-r)+r\, I[n \not \equiv m \,\, ({\rm mod} \,\, r)] \quad \mbox{for $n&gt;r$}.
\end{eqnarray*}
\end{corollary}

There is some similarity between the four equalities in Theorem~\ref{shelf3} and those in Corollary~\ref{bvc}, but the two results
yield different sequences (for fixed values of $m$ and $r$). For example, when $m=1&lt;r$, the sequence $(f_n: n \in \mathbb{Z}_{&gt;0})$ in Theorem~\ref{shelf3} is defined through
$$f_1=0, \quad f_n=\sum_{i=2}^{n-1} f_{n-i}+1 \quad \mbox{for $2 \leq n \leq r$},$$
and
$$f_n=\sum_{i=2}^{r-1} f_{n-i}+2f_{n-r} \quad \mbox{for $n\geq r+1$}.$$
On the other hand, the sequence $(g_A(n): n \in \mathbb{Z}_{&gt;0})$ in Corollary~\ref{bvc} is defined through
$$g_A(1)=0, \quad g_A(n)  =  \sum_{i=2}^{n-1} g_A(n-i)+n \quad \mbox{for $2 \leq n \leq r$},$$
and
$$g_A(n)  =  \sum_{i=2}^{r-1}g_A(n-i)+2g_A(n-r)+r\, I(r \nmid n-1) \quad \mbox{for $n&gt;r$}.$$

\section{Proofs} \label{profits}
In this section we prove Theorems~\ref{shelf1} and~\ref{cook}, Corollaries~\ref{torrr}, \ref{bobo} and \ref{bvc}, and Lemma~\ref{richard} from the previous section. Before we do that, we illustrate that Theorem~\ref{shelf1} works even when $A=\mathbb{Z}_{&gt;0}.$  Equation~(\ref{123456}) in Theorem~\ref{shelf1} becomes
$$c_A^R(n,k)=\frac{1}{k} \sum_{s | \gcd(n,k)} \phi(s) \, {(n/s)-1 \choose (k/s)-1}$$ $$=\frac{1}{n} \sum_{s | \gcd(n,k)} \phi(s) \, \frac{n/s}{k/s}{(n/s)-1 \choose (k/s)-1}
=\frac{1}{n} \sum_{s | \gcd(n,k)} \phi(s) \, {n/s \choose k/s},$$
which is the first equation in (\ref{sandra}). Also, when $A=\mathbb{Z}_{&gt;0}$, we can use the first equation in (\ref{beforehim}) and equation (\ref{nana}) to obtain
\begin{equation}\label{stat1}
g_A(n)=n \sum_{k=1}^n \frac{{n-1 \choose k-1}}{k}=2^n-1.
\end{equation}
We leave it to the reader to prove the second equation in~(\ref{stat1}); e.g. use the binomial theorem and integration. It follows from Theorem~\ref{shelf1} that
$$c_A^R(n)=\frac{1}{n}\sum_{d|n} \phi(d) \left(2^{n/d}-1\right)=\frac{1}{n}\sum_{d|n}\phi(d) 2^{n/d}-\frac{1}{n}\sum_{d|n}\phi(d),$$
which gives the second equation in (\ref{sandra}) because $\sum_{d|n} \phi(d)=n$; see~Apostol~\cite[Section 2.3]{apostol}.

\begin{proof}[{\bf Proof of Theorem~\ref{shelf1}}]
Consider an arbitrary circular composition $[(\lambda_1,\ldots,\lambda_k)]_R$ of $n$ with length $k$ and with parts in $A$. Place
the $\lambda_i$'s of this composition on a circle (i.e., $\lambda_1$ follows $\lambda_n$). We define the {\it period} $h$ of this circular composition to be the length of the shortest subsequence of $\lambda_i$'s with consecutive indices that is able to re-produce $[(\lambda_1,\ldots,\lambda_k)]_R$ by repeating itself $k/h$ times. Because of equation (\ref{bailey}), we must have that the positive integer $k/h$ divides $n.$

The set of all linear compositions of $n$ with length $k$ and parts in $A$ can be partitioned into equivalent classes representing all circular compositions of $n$ with length $k$ and parts in $A$. These equivalent classes can be classified according to their period $h$, and each equivalent class with period $h$ produces exactly $h$ linear compositions of $n$ with length $k$ and with parts in $A$. If we denote by $c_A^R(n;k;h)$ the number of all circular compositions of $n$ with length $k$, period $h$, and parts in $A$, then
$$c_A^L(n;k)=\sum_{h|k\,\, \&amp; \,\, \frac{k}{h}|n} h \, c_A^R(n;k;h).$$
Let $s=\frac{k}{h},$ in which case
\begin{equation}\label{student}
c_A^L(n;k)=\sum_{s|\gcd(n,k)} \frac{k}{s} \, c_A^R\left(n; k ; \frac{k}{s}\right)=\sum_{s|\gcd(n,k)} \frac{k}{s} \, c_A^R\left(\frac{n}{s}; \frac{k}{s}; \frac{k}{s}\right).
\end{equation}
The last step follows from the fact that a circular composition of $n$ with length $k$ and period $k/s$ can be partitioned into $s$ identical
circular compositions of $n/s$ with length $k/s$ and period $k/s$. Similarly,
\begin{eqnarray*}
c_A^R(n;k) &amp; = &amp; \sum_{h|k \,\, \&amp; \,\, \frac{k}{h} | n} c_A^R(n;k;h)\\
&amp; = &amp; \sum_{s|\gcd(n,k)} c_A^R\left(n; k; \frac{k}{s}\right)=\sum_{s|\gcd(n,k)}
c_A^R\left(\frac{n}{s}; \frac{k}{s}; \frac{k}{s}\right).
\end{eqnarray*}

Letting $a=\gcd(n,k),$ $n^*=n/a$, $k^*=k/a$, and $v=a/s$, we get
\begin{equation}\label{total1}
c_A^R(n^*a,k^*a)=\sum_{s|a} c_A^R\left(\frac{n^*a}{s}; \frac{k^*a}{s}; \frac{k^*a}{s}\right)=\sum_{v|a} c_A^R(n^* v; k^* v; k^*v)
\end{equation}
and
\begin{equation}\label{total2}
c_A^L(n^*a;k^*a)=\sum_{v|a} k^* v \, c_A^R(n^* v; k^* v; k^*v).
\end{equation}

Fixing $n^*$ and $k^*$ while varying $a$ (and this can be done because $n$ and $k$ are arbitrary positive integers with $1 \leq k \leq n$), we apply the M\"{o}bius `inversion principle' on equation (\ref{total2}); see~Graham et al.~\cite[Section 4.9]{graham}. We then get, for $v \in \mathbb{Z}_{&gt;0}$,
\begin{equation}\label{trasg1}
k^* v \, c_A^R(n^*v; k^*v;k^*v)=\sum_{w|v} \mu(w)\, c_A^L\left(\frac{n^*v}{w}; \frac{k^*v}{w}\right).
\end{equation}
Here $\mu(d)$ is the M\"{o}bius function at integer $d,$ which equals 1 if $d$ is square-free with an even number of prime factors, $-1$ if $d$ is square-free with an odd number of prime factors, and 0 otherwise; e.g., see~Apostol~\cite[Chapter 2]{apostol}.

It follows from equations (\ref{total1}) and (\ref{trasg1}) that
\begin{eqnarray*}
c_A^R(n^*a,k^*a) &amp; = &amp; \sum_{v|a} \frac{1}{k^*v}\sum_{w|v} \mu(w)\, c_A^L\left(\frac{n^*v}{w}; \frac{k^*v}{w}\right)\\
&amp; = &amp; \frac{1}{k^*a}\sum_{v|a} \frac{a}{v} \left(\sum_{w|v} \mu(w)\, c_A^L\left(\frac{n^*v}{w}; \frac{k^*v}{w}\right)\right)\\
&amp; = &amp; \frac{1}{k^*a} \sum_{v|a} \left(\sum_{w|v} \frac{v}{w} \mu(w)\right)  c_A^L\left(\frac{n^*a}{v}; \frac{k^*a}{v}\right).
\end{eqnarray*}
The last step follows from the associativity of Dirichlet convolutions; see again Apostol~\cite[Chapter 2]{apostol}. Using the formula
$$v \sum_{w|v} \frac{\mu(w)}{w}=\phi(v),$$
which is a standard result from Number Theory (e.g. see~Apostol~\cite[Theorem 2.3]{apostol}), we get
$$c_A^R(n^*a,k^*a)=\frac{1}{k^*a} \sum_{v|a}  \phi(v) \, c_A^L\left(\frac{n^*a}{v}; \frac{k^*a}{v}\right).$$
Using the equalities $n=n^*a$, $k=k^*a$, and $a=\gcd(n,k)$ in the above equation, we obtain equation~(\ref{123456}).
The methodology we used above is due to Bender~\cite{2222}.

To prove equation~(\ref{santa1}) we sum both sides of (\ref{123456}) from $k=1$ to $k=n$:
$$c_A^R(n)=\sum_{k=1}^n c_A^R(n;k)=\sum_{k=1}^n \sum_{d|\gcd(n,k)} \frac{1}{k} \phi(d) \, c_A^L\left(\frac{n}{d}; \frac{k}{d}\right).$$
Letting $t=n/d$ and $\ell=k/d$, and switching the order of summation in the last double sum above, we get
$$c_A^R(n)=\sum_{t|n} \sum_{\ell=1}^t \frac{\phi(n/t)}{\ell n/t} \, c_A^L(t; \ell)=\frac{1}{n} \sum_{t|n} \phi\left(\frac{n}{t}\right) \, t \sum_{\ell=1}^t \frac{c_A^L(t; \ell)}{\ell}.$$
Using equation (\ref{nana}), we can easily get equation~(\ref{santa1}).
\end{proof}

\begin{proof}[{\bf Proof of Lemma~\ref{richard}}]
According to Beck and Robbins~\cite{beck2015} and Hoggatt and Lind~\cite{hoggart}, the bivariate generating function of the numbers $c_A^L(n;k)$ is given by
\begin{equation}\label{trust1}
C_A^L(x,y)=1+\sum_{n,k \geq 1} c_A^L(n;k) x^n y^k=\frac{1}{1-y \sum_{s \in A} x^s},
\end{equation}
which implies
$$\sum_{n,k\geq 1} c_A^L(n;k)x^n y^{k-1}=\frac{\sum_{s \in A}x^s}{1-y\sum_{s \in A} x^s}.$$
Integrating both sides of the above equation with respect to $y$, from 0 to $z$, we obtain
$$\sum_{n\geq 1} \left(\sum_{k \geq 1} \frac{c_A^L(n;k)}{k}z^k\right) x^n=\int_0^z \frac{\sum_{s \in A}x^s}{1-y \sum_{s \in A} x^s}\, dy=-\log\left(1-z \sum_{s \in A} x^s\right).$$
Setting $z=1$ in the above equations and differentiating with respect to $x$, we get
\begin{equation}\label{ALS}
\sum_{n\geq 1} g_A(n) x^{n-1} =\frac{d}{dx}\left[-\log\left(1-\sum_{s \in A}x^s\right)\right]=\frac{\sum_{s \in A} s x^{s-1}}{1-\sum_{s \in A} x^s}.
\end{equation}
(Note that we have used the fact that $c_A^L(n;k)=0$ for $k&gt;n$.) This proves equation~(\ref{true1}). Also,
$$\left(\sum_{n \geq 1} g_A(n) x^n \right)\left(1-\sum_{s \geq 1} I(s \in A) x^s\right)=\sum_{s \geq 1} s I(s \in A)x^s.$$
Multiplying the two power series on the left-hand side of the above equation, and equating coefficients of $x^s$ from the resulting equality, we get
$$g_A(s)-\sum_{t =1}^{s-1} g_A(t) I(s-t \in A)=s I(s \in A),$$
and this proves equation~(\ref{true2}).

Finally, we know from~Beck and Robbins~\cite{beck2015} and Moser and Whitney~\cite{moser} that the generating function of the numbers $c_A^L(n)$ is
\begin{equation}\label{suko}
C_A^L(x)=1+\sum_{n\geq 1} c_A^L(n)\,x^n=\frac{1}{1-\sum_{s \in A} x^m}.
\end{equation}
This of course follows from equation (\ref{trust1}) by setting $y=1$, i.e., $$C_A^L(x)=C_A^L(x,y=1).$$ Using then equation~(\ref{true1}), we obtain
$$\left(\sum_{s \geq 1} s \, I(s \in A)\, x^s\right)\left(1+\sum_{n \geq 1} c_A^L(n)\,x^n\right)=\sum_{n \geq 1} g_A(n)\,x^n,$$
from which we can easily prove equation~(\ref{true3}).
\end{proof}

\begin{proof}[{\bf Proof of Corollary~\ref{torrr}.}]
Using Theorem~\ref{shelf1}, we have
$$\sum_{n \geq 1} c_A^R(n) x^n=\sum_{n\geq 1} \frac{1}{n} \sum_{d|n} \phi(d) g_A\left(\frac{n}{d}\right)x^n.$$
We want to change the order of summation in the right-hand side of the above equation. We let $n=td$, and then we have
\begin{equation}\label{12344}
\sum_{n \geq 1} c_A^R(n) x^n=\sum_{d\geq 1} \sum_{t\geq 1} \frac{\phi(d)}{td} g_A(t) x^{td}=\sum_{d\geq 1} \frac{\phi(d)}{d} \sum_{t \geq 1} \frac{g_A(t)}{t} (x^d)^t.
\end{equation}
Integrating both sides of the first equation in (\ref{ALS}) from $x=0$ to $x=z$, we obtain
\begin{equation}\label{12345A}
\sum_{n \geq 1} \frac{g_A(n)}{n} z^n=-\log\left(1-\sum_{s \in A} z^s\right)=\log \frac{1}{1-\sum_{s\in A} z^s}.
\end{equation}
Letting $z=x^d$, it then follows from equations (\ref{12344}) and (\ref{12345A}) that
$$\sum_{n \geq 1} c_A^R(n) x^n=\sum_{d\geq 1} \frac{\phi(d)}{d} \log \frac{1}{1-\sum_{s\in A} x^{sd}},$$
and this completes the proof of the corollary.
\end{proof}

\begin{proof}[{\bf Proof of Corollary~\ref{bobo}}]
We note that equation~(\ref{true2}) in Lemma~\ref{richard} implies
$$g_A(n)=\sum_{s=1}^{n-1} g_A(s) I(r \nmid n-s)+n I(r \nmid n).$$
Note that $r \nmid n-s$ if and only if $r \nmid n-r-s$, and $r \nmid n$ if and only if $r \nmid n-r.$ Thus, for $n&gt;r$,
\begin{eqnarray*}
g_A(n) &amp; = &amp; \sum_{s=n-r+1}^{n-1} g_A(s) + \sum_{s=1}^{n-r-1} g_A(s) I(r \nmid n-r-s)\\
&amp; &amp; +(n-r)I(r\nmid n-r)+rI(r \nmid n)\\
&amp; = &amp;  \sum_{s=n-r+1}^{n-1} g_A(s)+g_A(n-r)+rI(r \nmid n)\\
&amp; = &amp; \sum_{s=n-r}^{n-1} g_A(s)+rI(r \nmid n).
\end{eqnarray*}
It is then easy to prove that, for $n&gt;r$,
$$g_A(n)+r I(r|n)=\sum_{s=n-r}^{n-1} [g_A(s)+r I(r|s)],$$
i.e., the sequence of numbers $(g_A(n)+r I(r|n):\, n \in \mathbb{Z}_{&gt;0})$ satisfies the same recurrence as the $r$-step Lucas numbers described by
equations (\ref{1A}) and (\ref{2B}). In addition, if  $1\leq k \leq n \leq r$, then
$$c_A^L(n;k)=c_{\mathbb{Z}_{&gt;0}}^L(n;k)={n-1 \choose k-1}$$
except when $n=r$ and $k=1$, in which case, $c_A^L(r;1)=0.$ It follows from equation (\ref{stat1}) that
$$g_A(n)=2^n-1-rI(r|n)=L_n^{(r)}-rI(r|n) \quad \mbox{for $n=1,2,\ldots,r$}.$$
Therefore, $g_A(n)=L_n^{(r)}-rI(r|n)$ for all $n \in \mathbb{Z}_{&gt;0}$.
\end{proof}

\begin{proof}[{\bf Proof of Theorem~\ref{cook}}]
The equality
$$\rho_n^{(r)}=\frac{1}{n} \sum_{d|n} \phi\left(\frac{n}{d}\right) L_d^{(r)},$$
where $\rho_n^{(r)}$ is the number of cyclic 0-1 sequences of length $n$ that do not contain $r$ consecutive 1's, has been proven in Zhang and Hadjicostas~\cite{zhang2}.

The first equality in (\ref{cookcook})  follows from Theorem~\ref{shelf1}, Corollary~\ref{bobo}, and the fact that
\begin{equation}\label{fact}
\frac{r}{n}\sum_{d|n} \phi\left(\frac{n}{d}\right) I(r|d)=I(r|n).
\end{equation}
We leave it to the reader to prove equation (\ref{fact}).
\end{proof}

\begin{proof}[{\bf Proof of Corollary~\ref{bvc}.}]
When $1 \leq n \leq m-1$, we have $c_A^L(n)=c_{\mathbb{Z}_{&gt;0}}^L(n)=2^{n-1}$, which is the total number of linear compositions of $n$ (of any length)
with parts in the set of positive integers. It then follows from equation~(\ref{true3}) that
$$g_A(n)=\sum_{s=1}^{n-1} s \, 2^{n-s-1}+n=2^n-1.$$
When $n=m$, we have
$$g_A(m)=\sum_{i=1}^{m-1} s\, 2^{m-s-1}+0=2^m-m-1.$$
For $m+1 \leq n \leq r$, the equation
$$g_A(n)=\sum_{i=1 \atop i \neq m}^{n-1} g_A(n-i)+n$$
follows immediately from equation (\ref{true2}).

When $n &gt;r$, equation (\ref{true2}) implies
\begin{eqnarray*}
g_A(n) &amp; = &amp; \sum_{s=n-r}^{n-1} g_A(s)I(n-s \in A)+\sum_{s=1}^{n-r-1} g_A(s)I(n-r-s \in A)\\
&amp; &amp; +(n-r)I(n-r \in A)+r I(n \in A)
\end{eqnarray*}
because $x \in A$ if and only $x-r \in A$ for $x&gt;r.$ Thus, for $n&gt;r$, by applying equation (\ref{true2}) again for $n-r$ rather than $n$, we
get
\begin{eqnarray*}
g_A(n) &amp; = &amp; \sum_{s=n-r+1 \atop s \neq n-m}^{n-1} g_A(s)+2g_A(n-r)+rI(n \in A)\\
&amp; = &amp; \sum_{s=1 \atop s \neq m}^{r-1} g_A(n-s)+2g_A(n-r)+r I[n \not \equiv m \, ({\rm mod}\, r)],
\end{eqnarray*}
and this completes the proof of the corollary.
\end{proof}

\section{Examples} \label{examples}
In this section, we illustrate the results of the paper for the cases $m=0 &lt; r=2$ and $m=1&lt;r=2,$ i.e., when $A$ consists of the positive odd integers
and the positive even integers, respectively. Instead of using the subscript $A$ for the quantities $c_A^L(n),$ $g_A(n)$ and $c_A^R(n)$, we use the subscript
`$2,0$' for the first case and the subscript `$2,1$' for the second case. Values of these three quantities for each of the two cases are given in Table~\ref{ononon}
from $n=1$ to $n=20.$

The generating functions of the three quantities when $A$ is the set of all odd positive integers are
\begin{eqnarray*}
1+\sum_{n\geq 1} c_{2,0}^L(n) x^n &amp; = &amp; \frac{1-x^2}{1-x-x^2},\\
\sum_{n \geq 1} g_{2,0}(n) x^n &amp; = &amp; \frac{x(x^2+1)}{(1-x-x^2)(1-x^2)},\\
\sum_{n\geq 1} c_{2,0}^R(n) x^n &amp; = &amp; \sum_{n \geq 1} \frac{\phi(n)}{n} \log \frac{1-x^{2n}}{1-x^n-x^{2n}}.
\end{eqnarray*}

The generating functions of the three quantities when $A$ is the set of all even positive integers are
\begin{eqnarray*}
1+\sum_{n\geq 1} c_{2,1}^L(n) x^n &amp; = &amp; \frac{1-x^2}{1-2x^2},\\
\sum_{n \geq 1} g_{2,1}(n) x^n &amp; = &amp; \frac{2x^2}{(1-2x^2)(1-x^2)},\\
\sum_{n\geq 1} c_{2,1}^R(n) x^n &amp; = &amp; \sum_{n \geq 1} \frac{\phi(n)}{n} \log \frac{1-x^{2n}}{1-2x^{2n}}.
\end{eqnarray*}

By using a symbolic computation package that has calculus and number theory capabilities, one can expand the above six generating functions
around $x=0$ far enough in order to obtain the results in Table~\ref{ononon}.

\begin{table}
\begin{center}
\begin{tabular}{|r||r|r||r|r||r|r|}\hline
$n$ &amp; $c_{2,0}^L(n)$ &amp; $c_{2,1}^L(n)$ &amp; $g_{2,0}(n)$ &amp; $g_{2,1}(n)$ &amp; $c_{2,0}^R(n)$ &amp; $c_{2,1}^R(n)$ \\ \hline
1 &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 \\ \hline
2 &amp; 1 &amp; 1 &amp; 1  &amp; 2 &amp; 1 &amp; 1 \\ \hline
3 &amp; 2 &amp; 0 &amp; 4 &amp; 0 &amp; 2 &amp; 0 \\ \hline
4 &amp; 3 &amp; 2 &amp; 5 &amp; 6 &amp; 2 &amp; 2 \\ \hline
5 &amp; 5 &amp; 0 &amp; 11 &amp; 0 &amp; 3 &amp; 0 \\ \hline
6 &amp; 8 &amp; 4 &amp;16  &amp; 14 &amp; 4 &amp; 3\\ \hline
7 &amp; 13 &amp; 0 &amp; 29  &amp; 0 &amp; 5 &amp; 0 \\ \hline
8 &amp; 21 &amp; 8 &amp; 45 &amp; 30 &amp; 7 &amp; 5 \\ \hline
9 &amp; 34 &amp; 0 &amp; 76 &amp; 0 &amp; 10 &amp; 0 \\ \hline
10 &amp; 55 &amp; 16 &amp; 121 &amp; 62 &amp; 14 &amp; 7\\ \hline
11 &amp; 89 &amp; 0 &amp; 199 &amp; 0 &amp; 19 &amp; 0\\ \hline
12 &amp; 144 &amp; 32 &amp; 320 &amp;126 &amp; 30 &amp; 13 \\ \hline
13 &amp; 233 &amp; 0 &amp; 521 &amp; 0 &amp; 41&amp; 0\\ \hline
14 &amp; 377 &amp; 64 &amp; 841 &amp; 254 &amp; 63 &amp; 19 \\ \hline
15 &amp; 610 &amp; 0 &amp; 1364 &amp; 0 &amp; 94 &amp; 0 \\ \hline
16 &amp; 987 &amp; 128 &amp; 2205 &amp; 510 &amp; 142 &amp; 35 \\ \hline
17 &amp; 1597 &amp; 0 &amp; 3571 &amp; 0 &amp; 211 &amp; 0\\ \hline
18 &amp; 2584 &amp; 256 &amp; 5776 &amp; 1022 &amp; 328 &amp; 59 \\ \hline
19 &amp; 4181 &amp; 0 &amp; 9349 &amp; 0 &amp; 493 &amp; 0 \\ \hline
20 &amp; 6765 &amp; 512 &amp; 15125 &amp; 2046 &amp; 765 &amp; 107 \\ \hline
\end{tabular}
\end{center}
\caption{Evaluations of various sequences for the cases $m=0 &lt; r=2$ and $m=1 &lt; r=2$.}\label{ononon}
\end{table}

Alternatively, we can find recurrences for the first two quantities in each case. For the first case:
\begin{eqnarray*}
&amp; &amp; c_{2,0}^L(1)=c_{2,0}^L(2)=1, \\
&amp; &amp; c_{2,0}^L(n)=c_{2,0}^L(n-1)+c_{2,0}^L(n-2) \quad \mbox{for $n&gt;2$};\\
&amp; &amp; g_{2,0}(1)=1, \quad g_{2,0}(2)=1, \\
&amp; &amp; g_{2,0}(n)=g_{2,0}(n-1)+g_{2,1}(n-2)+2I(2 \nmid n) \quad \mbox{for $n&gt;2$.}
\end{eqnarray*}
Of course the sequence $(c_{2,0}^L(n): n\in \mathbb{Z}_{&gt;0})$ is the classical Fibonacci sequence, while the sequence $(g_{2,0}(n): n \in \mathbb{Z}_{&gt;0})$ satisfies
$$g_{2,0}(n)=L_n^{(2)}-2I(2|n)=L_n^{(2)}-[1+(-1)^n] \quad \mbox{for all $n \in \mathbb{Z}_{&gt;0}$},$$
and it is given by \seqnum{A001350}. These numbers are called ``associate Mersenne numbers" by Haselgrove~\cite{hass} in an article that he published in 1949 in the Cambridge University Mathematics Society magazine {\it Eureka.}  (It is actually one of three sequences that he calls like that.) The sequence $(c_{2,0}^R(n): n \in \mathbb{Z}_{n&gt;0})$ can be calculated through equations (\ref{cookcook}) and it appears in \seqnum{A032189}.

For the second case, using Theorem~\ref{shelf3} and Corollary~\ref{bvc}, we find
\begin{eqnarray*}
&amp; &amp; c_{2,1}^L(1)=0, \quad c_{2,1}^L(2)=1, \\
&amp; &amp; c_{2,1}^L(n)=2 c_{2,1}^L(n-2) \quad \mbox{for $n&gt;2$};\\
&amp; &amp; g_{2,1}(1)=0, \quad g_{2,1}(2)=2, \\
&amp; &amp; g_{2,1}(n)=2g_{2,1}(n-2)+2I(2 \mid n) \quad \mbox{for $n&gt;2$.}
\end{eqnarray*}
In this case, it is easy to prove that for all $n \geq 1$:
$$c_{2,1}^L(n)=2^{\frac{n}{2}-1} \, I(2 |n)\quad \mbox{and} \quad g_{2,1}(n)=(2^{\frac{n}{2}+1}-2) \, I(2|n).$$
The sequence $(c_{2,1}^R(n): n \in \mathbb{Z}_{n&gt;0})$ can be calculated through equation~(\ref{santa1}). Obviously, $c_{2,1}^R(2n-1)=0$ for $n \in \mathbb{Z}_{&gt;0},$ while
the sequence $(c_{2,1}^R(2n): \, n \in \mathbb{Z}_{n&gt;0})$ appears in~\seqnum{A008965}.


\section{Concluding remarks} \label{remarks}
The various $r$-step Lucas numbers $L_n^{(r)}$, defined by equations (\ref{1A}) and (\ref{2B}),
have been studied extensively and satisfy various combinatorial identities involving binomial coefficients; e.g., see Charalambides~\cite{chara}.
When $A$ is the set of all positive integers that are not multiples of a positive integer $r$, we managed to express $c_A^R(n)$ in terms of $L_n^{(r)}$ through
equation~(\ref{cookcook}) in Theorem~\ref{cook}. It would be nice to find a similar elegant equality for the numbers $c_A^R(n)$ in terms of well-studied sequences
of integers for the case
$$A=\mathbb{Z}_{&gt;0}-\{m+jr: \, j \in \mathbb{Z}_{&gt;0}\}$$
when $r,m \in \mathbb{Z}_{&gt;0}$ with $1 \leq m &lt;r$.

Finally, it would be nice to find a {\it simple} and {\it elegant} combinatorial argument to prove
$$c_A^R(n)=-I(r|n)+\rho_n^{(r)}$$
when $A=\mathbb{Z}_{&gt;0}-\{rj: \, j \in \mathbb{Z}_{&gt;0}\}.$ Is there a `quasi-bijection' between the number of cyclic compositions of $n$ that are not multiples of $r$ with
the number of cyclic 0-1 sequences of length $n$ that do not contain $r$ consecutive 1s?

\section{Acknowledgement}
The author wishes to thank statistician Lingyun Zhang whose ideas and work have inspired this paper.

\begin{thebibliography}{1}
\bibitem{EEE1} The On-Line Encyclopedia of Integer Sequences, 2016, available at \url{http://oeis.org}.

\bibitem{akin} E.~Akin and M.~Davis, Bulgarian solitaire, {\it Amer.~Math.~Monthly} {\bf 92} (1985), 237--250.

\bibitem{apostol} T.~M.~Apostol, {\it Introduction to Analytic Number Theory}, Springer, 2010.

\bibitem{beck2015} M.~Beck and N.~Robbins, Variations on a generating-function theme: enumerating compositions with parts avoiding an arithmetic sequence, {\it Amer.~Math.~Monthly} {\bf 122} (2015), 256--263.

\bibitem{2222} E.~A.~Bender, M\"obius inversion counting,
in K. H. Rosen, J. G. Michaels, J. L. Gross, J. W. Grossman, and
D. R. Shier, eds.,
{\it Handbook of Discrete and Combinatorial Mathematics},
CRC Press, 2000, pp.~127--129.

\bibitem{chara} Ch.~A.~Charalambides, Lucas numbers and polynomials of
order $k$ and the length of the longest circular success run, {\it
Fibonacci Quart.}~{\bf 29} (1991), 290--297.

\bibitem{fla} P.~Flajolet and R.~Sedgewick, {\it Analytic Combinatorics}, Cambridge University Press, 2009.

\bibitem{fla2} P.~Flajolet and M.~Soria, The cycle construction, {\it SIAM J. 
Discrete Math.}~{\bf 4}  (1991), 58--60.

\bibitem{graham} R.~L.~Graham, D.~E.~Knuth, and O.~Patashnik, {\it Concrete Mathematics,} Addison-Wesley, 1989.

\bibitem{hass} C. ~B.~Haselgrove, A note on Fermat's last theorem and the Mersenne numbers, {\it Eureka}~{\bf 11} (1949), 19--22.

\bibitem{heubach} S.~Heubach and T.~Mansour, Compositions of $n$ with parts in a set,  {\it Congr. Numer.}~{\bf 168} (2004), 127--143.

\bibitem{heubach1} S.~Heubach and T.~Mansour, {\it Combinatorics of
Compositions and Words,} CRC Press, 2010.

\bibitem{hoggart} V.~E.~Hoggatt, Jr., and D.~A.~Lind, Fibonacci and
binomial properties of weighted compositions, {\it J.~Combin.~Theory}
{\bf 4} (1968), 121--124.

\bibitem{knob33} A.~Knopfmacher and N.~Robbins, Some properties of
cyclic compositions, {\it Fibonacci Quart.}~{\bf 48} (2010), 249--255.

\bibitem{1111} P.~A.~MacMahon, Application of a theory of permutations
in circular procession to the theory of numbers, {\it Proc.~London
Math.~Soc.}~{\bf 23} (1892), 305--313.

\bibitem{fujit1} P.~A.~MacMahon, Memoir on the theory of the
compositions of numbers, {\it Philos. Trans. Roy. Soc. London~A} {\bf
184} (1893), 835--901.

\bibitem{miles} E.~P.~Miles, Jr., Generalized Fibonacci numbers and
associated matrices, {\it Amer.~Math.~Monthly} {\bf 67} (1960),
745--752.

\bibitem{moser} L.~Moser and E.~L.~Whitney, Weighted compositions, {\it
Canad.~Math.~Bull.}~{\bf 4} (1961), 39--43.

\bibitem{noe} T.~D.~Noe, and J.~Vos Post, Primes in Fibonacci $n$-step
and Lucas $n$-step sequences, {\it J.~Integer Sequences}~{\bf 8} (2005),
\href{https://cs.uwaterloo.ca/journals/JIS/VOL8/Noe/noe5.html}{Article 05.4.4}.

\bibitem{razen} R.~Razen, J.~Seberry, and K.~Wehrhahn, Ordered partitions and codes generated by circulant matrices, {\it J.~Combin.~Theory Ser.~A}~{\bf 27} (1979), 333--341.

\bibitem{rob2014} N.~Robbins, On Tribonacci numbers and 3-regular compositions, {\it Fibonacci Quart.}~{\bf 52} (2014), 16--19.


\bibitem{rob2015} N.~Robbins, On $r$-regular compositions, {\it J.~Comb.~Math.~Combin.~Comput.}~{\bf 96} (2016), 195-199. 

\bibitem{Sommer} D.~Y.~M.~Sommerville, On certain periodic properties
of cyclic compositions of integers, {\it Proc.~London~Math.~Soc.~Ser.~2}
{\bf 7} (1908), 263--313.

\bibitem{wehr} K.~H.~Wehrhahn, {\it Combinatorics: An Introduction}, 2nd
ed., Carslaw Publications, 1992.

\bibitem{salvi1} N.~Zagaglia Salvi, {\it Ordered partitions and
colourings of cycles and necklaces}, {\it Bull.~Inst.~Combin. Appl.}
{\bf 27} (1999), 37--40.

\bibitem{zhang2} L.~Zhang and P.~Hadjicostas, On sequences of
independent Bernoulli trials avoiding the pattern~``11...1", {\it
Math.~Scientist} {\bf 40} (2015), 89--96.

\end{thebibliography}


\bigskip
\hrule
\bigskip

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

\noindent \emph{Keywords: } cyclic composition, Euler's totient function, generalized Lucas number, generating function.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A000032},
\seqnum{A000073},
\seqnum{A000078},
\seqnum{A000358},
\seqnum{A001350},
\seqnum{A001590},
\seqnum{A001631},
\seqnum{A001644},
\seqnum{A008965},
\seqnum{A032189},
\seqnum{A037306},
\seqnum{A073817}, and
\seqnum{A093305}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received June 18 2016; revised version received October 8 2016. 
Published in {\it Journal of Integer Sequences}, October 10 2016.

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