\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{mathtools}

\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}

\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}{\rm \underline{#1}}}

\newcommand{\nat}{\mathbb{N}}
\newcommand{\actnat}{\mathbb{N}_0}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\C}{\mathbb{C}}

\begin{document}

\begin{center}
\includegraphics[width=4in]{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 Compositions with an Odd Number of Parts, \\
\vskip 0.1in
and Other Congruences
}
\vskip 1cm
\large
Joshua P.\ Bowman\\
Natural Science Division \\ 
Seaver College \\ 
Pepperdine University \\ 
24255 Pacific Coast Highway \\ 
Malibu, CA 90263 \\
USA\\
\href{mailto:joshua.bowman@pepperdine.edu}{\tt joshua.bowman@pepperdine.edu} \\
\end{center}

\vskip .2 in
\begin{abstract}
This article begins with a description of three notions of compositions that have parts in a fixed set of positive integers: linear compositions, circular compositions, and cyclic compositions. We describe some relations among these notions and review generating functions to count each type of composition. The main result of the paper generalizes these known results to count compositions in which the number of parts is required to be congruent to $q$ modulo $m$ for some fixed $0 \leq q \leq m-1$. The particular case $m = 2$, $q = 1$ yields the compositions with an odd number of parts. The latter sections apply the main theorem to several special cases, including compositions in which the parts are allowed to be drawn from a multiset.
\end{abstract}

\section{Introduction}\label{S:intro}

Compositions of natural numbers are fundamental objects in combinatorics, partly because they are defined using the basic operation of addition, and partly because of their equivalence with other types of combinatorial objects. For instance, the results in this paper were initially motivated by a counting problem in graph theory (see Remark \ref{R:pepp}). 

The name of compositions was given by MacMahon \cite{Mac} within the context of the theory of partitions. In a partition of a natural number, the order of the parts (i.e., terms) is irrelevant, whereas in a composition the order of the parts matters. The ordered nature of a composition makes it convenient to represent in a variety of ways, which share a ``linear'' character. A graph with $n$ vertices and $n-1$ edges arranged in a line can represent a composition of $n$ by removing edges so that the remaining components have numbers of vertices equal to the sizes of the parts of the composition. A binary sequence of length $n$ that starts with $0$ can also represent a composition by treating each appearance of $0$ and any following $1$s as a single part of the composition. Both of these representations make it clear that the number of compositions of $n$ is $2^{n-1}$ for all $n\geq1$.

Between the fully ordered notion of a composition and the fully unordered notion of a partition lies an intermediate type of object, that of a cyclic composition, which was introduced by Sommerville \cite{Somm}. In a cyclic composition, the order of the parts is counted up to cyclic permutation. Cyclic compositions are often said to count ``necklaces'' composed of white and black beads; a necklace can be rotated (but not flipped) without changing the underlying object. We add the caveat that at least one black bead must be included, to mark the ``start'' of a part of the composition. Cyclic compositions may also be represented by binary sequences that loop around and have no fixed starting point; in this context, we insist that $0$ appears at least once in the sequence.

Linear compositions and cyclic compositions are related to a third type of composition, for which I have not found a standard name, so I will call it a ``circular composition.'' This is essentially a linear composition that has been placed in a circular arrangement of $n$ points, with a designated initial point, which may lie inside a part of the composition. When the group of rotations acts on circular compositions, the orbits of this action may also be identified with cyclic compositions.

Circular compositions are called ``bracelets'' by Benjamin and Quinn \cite{BenQui}; however, in the \emph{OEIS} \cite{OEIS} the term ``bracelets'' refers to necklaces for which reflections are allowed in addition to rotations, so that terminology is not consistent across the literature. In addition, care is needed in comparing the present work with other sources, because ``circular'' is sometimes used synonymously with ``cyclic,'' e.g., by Hadjicostas \cite{Hadj}, whereas I distinguish them.

These three types of compositions---linear, circular, and cyclic---are not often considered collectively, despite their close relations to each other. A notable exception is in the article by Zhang and Hadjicostas \cite{ZH2015}, where they are treated as binary sequences and called L-type, C-type, and CR-type, for sequences on a line, on a circle, and on a circle with rotations, respectively. No group action is explicitly used in this previous work, however.

It is often convenient, desirable, or necessary to impose restrictions on the parts that form a composition. One commonly restricts the \emph{sizes} of the parts: for example, one asserts that they may not exceed a certain number. Counting linear compositions of $n$ whose parts must be $1$ or $2$ leads to the famous Fibonacci numbers, and counting circular compositions with the same restriction leads to the almost-as-famous Lucas numbers (see \S\ref{SS:maxN}). Cyclic compositions whose parts must be $1$ or $2$ are counted by a certain weighted average of Lucas numbers, which depends on the set of divisors of $n$ (see equation \eqref{Eq:cycliccoeff}). Hadjicostas \cite{Hadj} considers linear compositions and cyclic compositions whose parts avoid an arithmetic sequence; when the parts are required to be odd, the Fibonacci and Lucas numbers appear again (cf.~\S\ref{SS:odd}).

In this paper, we combine restrictions on sizes with restrictions on the \emph{number} of parts in the composition. Counting compositions with a fixed number of parts can be done using multinomial coefficients. We will consider the related problem of counting compositions whose numbers of parts satisfy a congruence condition---that is, given a fixed $m \geq 1$ and $0 \leq q < m$, we will only allow compositions that have $k$ parts, where $k \equiv q$ (mod $m$).

Congruence generalizes the notion of parity---evenness and oddness. Here is a simple example of how parity can matter in a composition. The braid group $B_2$ on two strands is generated by a single element $\gamma$, which exchanges the endpoints of the strands. An element $\gamma^n \in B_2$ exchanges the endpoints if and only if $n$ is odd. (See Figure~\ref{F:braids}, top.) In other words, the ``pure'' braid subgroup in $B_2$ is generated by $\gamma^2$. When the braid $\gamma^n$ is arranged in a circle by joining the endpoints, the result is a knot if $n$ is odd and a link if $n$ is even. (See Figure~\ref{F:braids}, bottom.) Concatenating copies of $\gamma$ to produce $\gamma^n$ corresponds to forming a composition of $n$ in which all parts have size $1$. One can easily consider other braid-like objects composed of smaller patterns having defined sizes, each of which permutes the endpoints of the strands in some manner; concatenation of the small patterns produces an object whose size is the sum of the smaller sizes, and whose eventual permutation of the endpoints depends, at least in part, on the number of small patterns used. Indeed, such a framework was part of the initial motivation for the current project \cite{Palmer}.

Similar situations arise throughout group theory and topology: for example, when considering orientability, cohomology with coefficients in $\Z/m\Z$, monodromy of fibrations, etc.

\begin{figure}
\centering
\includegraphics[width=5in,height=.65in]{braid-9-short.png}

\includegraphics[scale=.2]{circle-braid-8.png}\hspace{.5in}
\includegraphics[scale=.2]{circle-braid-9.png}
\caption{Some topological consequences of parity. {\sc Top:} A braid on two strands switches the order of the endpoints if and only if the number of crossings is odd. {\sc Bottom:} A pair of strands winding around a circle forms two loops (a link) if the number of crossings is even, one loop (a knot) if the number of crossings is odd.}
\label{F:braids}
\end{figure}

Parity and other congruence restrictions can also arise in the theory of probability and games of chance. For example, a question addressed by Mairan \cite{Mairan} and taken up later by Laplace \cite{Lapl} asks: if a random nonzero number of tokens is taken from a given pile, is it more likely that the number is even or odd? This problem was later generalized to the case of other congruences (see Remark \ref{R:tokens}), and its solution turns out to provide the answer to one of the counting problems in this paper as well (see \S\ref{SS:allsize}).

Here is an outline of the rest of the paper. Section~\ref{S:bg} provides formal definitions of the three types of compositions under consideration and recalls their counting formulas without restrictions on the number of parts. Section~\ref{S:main} presents the main theorem. Section~\ref{S:examples} applies the main theorem to several examples that vary in their restrictions on the sizes of parts. Finally, section~\ref{S:multiset} extends the scope of the main theorem to compositions whose parts are drawn from a multiset, meaning that each size may appear with multiplicity greater than 1. 

The initialism \emph{OEIS} refers to \emph{The On-Line Encyclopedia of Integer Sequences} \cite{OEIS}, and \emph{AC} refers to the text \emph{Analytic Combinatorics} \cite{AC}. Hereafter citations of the \emph{OEIS} and \emph{Analytic Combinatorics} will not include a reference to the bibliography. 

\section{Background}\label{S:bg}

To begin, we review the three notions of compositions that are the focus of this paper, establish several pieces of notation, and summarize some proof techniques that will be useful later for the main theorem. None of the results in this section are new. 

A comment on notation: with each set $A$ whose elements are positive integers, we will associate three sequences $b(A;n)$, $c(A;n)$, and $d(A;n)$. The generating functions of these sequences will be called $f^A(x)$, $g^A(x)$, and $h^A(x)$, respectively.

Let $\nat$ denote the set of positive integers $\{1,2,3,\dots\}$, and let $\actnat = \{0\}\cup\nat$ denote the set of nonnegative integers. Given $n \in \actnat$, a \emph{composition of $n$} is a sum of elements of $\nat$ whose total is $n$, for which the order of the terms in the sum matters. That is, $s+t$ and $t+s$ are considered different sums unless $s=t$, although their total is the same. These will also be called \emph{ordinary} or \emph{linear} compositions. Each term in a composition is called a \emph{part}. The total of the empty sum, having zero parts, is $0$ by definition.

Given a set $A \subseteq \nat$ and a number $n \in \actnat$, a \emph{composition of $n$ with parts in $A$} (or, more briefly, an \emph{$A$-composition of $n$}) is a composition of $n$ whose parts are elements of $A$. The empty sum is considered an $A$-composition of $0$ for all sets $A$. 

Let $(i(A;n))_{n=1}^\infty$ be the \emph{indicator sequence} of $A$, defined by 
\[
i(A;n) = 
\begin{cases}
1\text, & \text{if $n \in A$;} \\
0\text, & \text{if $n \notin A$,}
\end{cases}
\]
and let $j^A(x)$ be the (ordinary) generating function of $(i(A;n))_{n=0}^\infty$, namely 
\[
j^A(x) 
= \sum_{n=1}^\infty i(A;n) x^n\text.
\]
Then the coefficient of $x^n$ in $\left(j^A(x)\right)\!{}^k$ is equal to the number of $A$-compositions of $n$ having exactly $k$ terms. To allow for the possibility of an empty sum, we use the convention that $\left(j^A(x)\right)\!{}^0 = 1$.

Let $b(A;n)$ be the total number of $A$-compositions of $n$, and let $f^A(x)$ be the generating function of $(b(A;n))_{n=0}^\infty$. Summing $\left(j^A(x)\right)\!{}^k$ over $k$, we obtain the well-known formula 
\[
f^A(x) 
= \sum_{n=0}^\infty b(A;n) x^n 
= \sum_{k=0}^\infty\left(j^A(x)\right)\!{}^k 
= \frac{1}{1 - j^A(x)}\text.
\]
As Cameron \cite{Cam} says, this formula ``will look either obvious or artificial, depending on your background.'' In our convention, $b(A;0) = 1$ for all sets $A$. 

The \emph{OEIS}, following Bernstein and Sloane \cite{BerSlo}, calls $(b(A;n))_{n=1}^\infty$ the INVERT transform of $(i(A;n))_{n=1}^\infty$. In \emph{AC} it corresponds to the ``sequence'' construction {\sc Seq}.

The notion of a ``cyclic composition'' of $n$, originally introduced by Sommerville \cite{Somm}, comes from considering cyclic permutations of the terms in a sum. That is, we define $\sim$ to be the equivalence relation on compositions that is generated by $n_1 + n_2 + \cdots + n_k \sim n_2 + \cdots + n_k + n_1$; then a \emph{cyclic $A$-composition of $n$} is an equivalence class of $A$-compositions of $n$ under the relation $\sim$. Let $d(A;n)$ be the number of cyclic $A$-compositions of $n$. The generating function of $(d(A;n))_{n=1}^\infty$, as it appears in the article of Flajolet and Soria \cite{FS}, is 
\begin{equation}\label{Eq:hA}
h^A(x) 
= \sum_{n=1}^\infty d(A;n) x^n
= \sum_{k=1}^\infty \frac{\phi(k)}{k} 
  \log\frac{1}{1 - j^A(x^k)}\text,
\end{equation}
where $\phi(k)$ is the Euler totient function. For reasons that will be made clear below, we assume $d(A;0) = 0$, not $1$. 

The \emph{OEIS} calls $(d(A;n))_{n=1}^\infty$ the CIK transform of $(i(A;n))_{n=1}^\infty$, using nomenclature that is explained by Bower \cite{Bower}. In \emph{AC} it corresponds to the ``cycle'' construction {\sc Cyc}.

To understand the formula for $h^A(x)$, it is useful to introduce a third type of composition, together with a group action whose orbits are the cyclic compositions of $n$. Let $C_n$ be the cycle graph on $n$ vertices. To distinguish the vertices of $C_n$ from elements of $\nat$, we will say that the vertex set of $C_n$ is $\{v_1,\dots,v_n\}$; then the edges of $C_n$ are $e_i=\{v_i,v_{i+1}\}$ for $1\leq i< n$ as well as $e_n=\{v_n,v_1\}$. A \emph{circular composition of $n$} is the collection of connected components that remain when one or more edges are removed from $C_n$. Each connected component can be either a path or a single vertex. By analogy with sums, each element in a circular composition will be called a \emph{part}, and the \emph{size} of the part is the number of vertices it contains. If the sizes of the parts belong to $A$, then it is a \emph{circular $A$-composition of $n$}. (See Figure~\ref{fig:circcomp} for examples.) Let $c(A;n)$ be the number of circular $A$-compositions of $n$. 

\begin{figure}
\centering
\includegraphics{circcomp2.pdf}\hspace{1in}
\includegraphics{circcomp1.pdf}
\caption{Two circular compositions of $10$ that are in the same orbit under the action of $\Z/10\Z$ by rotations. Both are equivalent as cyclic compositions to the sum $1 + 3 + 4 + 2$.}
\label{fig:circcomp}
\end{figure}

The cases $n=0$ and $n=1$ in the preceding paragraph deserve clarification. Although we allow for a sum to have zero terms, we do not permit a graph to have zero vertices, and so $c(A;0) = 0$ for all sets $A$. This convention will also simplify some later formulas. The graph $C_1$ has only one vertex $v_1$, and its only edge is a loop from $v_1$ to itself. Thus $1$ has exactly one circular composition, obtained by removing the single edge from $C_1$. Therefore $c(A;1)$ equals one if $1 \in A$ and zero otherwise.

The circular $A$-compositions of $n$ can be enumerated in the following manner. Say that the \emph{first part} of a circular composition of $n$ is the part in $C_n$ containing $v_1$. Let $k\in A$ be the size of the first part. Then $v_1$ can appear in any of the $k$ positions in this part. To complete the circular composition of $n$, select an ordinary composition of $n-k$. By the multiplication principle, the total number of circular $A$-compositions of $n$ is 
\[
c(A;n) = \sum_{k=1}^n k\,i(A;k)\,b(A;n-k)\text.
\]
Therefore the generating function for $(c(A;n))_{n=1}^\infty$ is 
\begin{gather*}
\begin{aligned}
g^A(x) 
&= \sum_{n=1}^\infty c(A;n)x^n 
= \sum_{n=1}^\infty \sum_{k=1}^n k\,i(A;k)\,b(A;n-k)x^n \\
&= \left(\sum_{n=1}^\infty n\,i(A;n)x^n\right)
  \left(\sum_{n=0}^\infty b(A;n)x^n\right)
= \frac{x\frac{d}{dx}j^A(x)}{1 - j^A(x)}\text,
\end{aligned}
\end{gather*}
where we have used the fact that 
\[
\sum_{n=1}^\infty n\,i(A;n)x^n
= x\sum_{n=1}^\infty n\,i(A;n)x^{n-1}
= x\frac{d}{dx}\sum_{n=1}^\infty i(A;n)x^n
= x\frac{d}{dx}j^A(x)\text.
\]

In the \emph{OEIS}, the sequence $(c(A;n))_{n=1}^\infty$ does not have a particular designation as it relates to $(i(A;n))_{n=1}^\infty$, but in the language of \emph{AC}, it corresponds to a direct product of the ``pointing'' operation $\Theta$ and the ``sequence'' construction {\sc Seq}, applied to the set $A$.

\begin{remark}
Hadjicostas gives the same formula for $g^A(x)$ in \cite[Lemma 2]{Hadj}, but without assigning it a clear combinatorial meaning. There is a difference in notation; the symbol $g_A(n)$ in \cite{Hadj} becomes $c(A;n)$ here, and the generating functions in \cite{Hadj} are not given names. 
\end{remark}

We are ready to derive the formula for $h^A(x)$ that was presented in equation \eqref{Eq:hA}. The group $\Z/n\Z$ acts on $C_n$ by $t \cdot v_i = v_{t+i}$ for $t \in \Z/n\Z$ (addition in the index is calculated modulo $n$). This action induces an action of $\Z/n\Z$ on the set of circular $A$-compositions of $n$. (Again see Figure~\ref{fig:circcomp} for examples of two circular compositions that are in the same orbit under this action.) Then $d(A;n)$ equals the number of orbits of circular $A$-compositions under the action of $\Z/n\Z$.

\begin{figure}
    \centering
    \includegraphics{covering.pdf}
    \caption{The inverse image of a circular composition of $5$ via the graph cover $C_{15}\to C_5$ that sends $v_i$ to $v_{i\bmod5}$. The resulting circular composition of $15$ has threefold symmetry because, under the action of $\Z/15\Z$, it is fixed by the subgroup $\langle5\rangle$, which has order $3$.}
    \label{fig:covering}
\end{figure}

Let $\mathrm{Fix}(t)$ be the set of circular $A$-compositions of $n$ fixed by $t\in\Z/n\Z$. Now, a circular composition of $n$ is fixed by $t$ if and only if it is fixed by every element of the subgroup $\langle t\rangle$. Recall that $\Z/n\Z$ has one subgroup of order $k$ for each divisor $k$ of $n$. A circular composition of $n$ is fixed by the subgroup of order $k$ if and only if it is the inverse image of a circular composition of $n/k$ by the canonical graph cover $C_n \to C_{n/k}$, which is induced by $i \mapsto i\bmod{n/k}$. (See Figure~\ref{fig:covering} for an example.) We know the number of circular $A$-compositions of $n/k$ to be $c(A;n/k)$, and the subgroup of order $k$ in $\Z/n\Z$ has $\phi(k)$ generators. By the orbit counting theorem for group actions (a.k.a.\ Burnside's lemma), we have 
\begin{equation}\label{Eq:cycliccoeff}
d(A;n) 
= \frac{1}{n} \sum_{t=0}^{n-1} \#\mathrm{Fix}(t)
= \frac{1}{n} \sum_{k\mid n} \phi(k) c(A;n/k)\text.
\end{equation}
Because $k \mid n$ if and only if $n = k\ell$ for some $\ell\geq1$, we can write 
\begin{gather*}
\begin{aligned}
h^A(x) 
&= \sum_{n=1}^\infty \sum_{k\mid n} \frac{\phi(k)}{n}c(A;n/k) x^n 
= \sum_{k=1}^\infty \sum_{\ell=1}^\infty \frac{\phi(k)}{k\ell} c(A;\ell) x^{k\ell} \\
&= \sum_{k=1}^\infty \frac{\phi(k)}{k} \sum_{\ell=1}^\infty \frac{c(A;\ell)}{\ell} x^{k\ell} 
= \sum_{k=1}^\infty \frac{\phi(k)}{k} \log\frac{1}{1 - j^A(x^k)}\text,
\end{aligned}
\end{gather*}
where we have used the fact that  
\[
\sum_{n=1}^\infty \frac{c(A;n)}{n} x^{n} 
= \int_0^x \frac{g^A(u)}{u}\,du 
= \int_0^x \frac{\frac{d}{du}j^A(u)}{1 - j^A(u)}\,du 
= \log\frac{1}{1 - j^A(x)}\text.
\]

\begin{remark}
This proof of the formula in equation \eqref{Eq:hA} is essentially the same as the one given by Hadjicostas \cite{Hadj}, and it resembles the earlier proof of Flajolet and Soria \cite{FS}, which also appears in \emph{AC}, but I find the systematic use of a group action and covering spaces to be clarifying. 
\end{remark}

\section{Main theorem}\label{S:main}

Given $m \geq 1$ and $q \in \{0,\dots,m-1\}$, let $b(A,m,q;n)$ be the number of linear $A$-compositions of $n$ such that the number of parts is congruent to $q$ modulo $m$, let $c(A,m,q;n)$ be the number of circular $A$-compositions of $n$ such that the number of parts is congruent to $q$ modulo $m$, and let $d(A,m,q;n)$ be the number of cyclic $A$-compositions of $n$ such that the number of parts is congruent to $q$ modulo $m$. Evidently, 
\begin{align*}
b(A,1,0;n) &= b(A;n) 
= \sum_{q=0}^{m-1} b(A,m,q;n)\text, \\
c(A,1,0;n) &= c(A;n) 
= \sum_{q=0}^{m-1} c(A,m,q;n)\text, \qquad\text{and} \\
d(A,1,0;n) &= d(A;n) 
= \sum_{q=0}^{m-1} d(A,m,q;n)\text.
\end{align*}
Moreover, for all $n \ge 1$, we have 
\[
d(A,m,q;n) \leq b(A,m,q;n) \leq c(A,m,q;n)\text.
\]
Our main result is a collection of formulas for the generating functions of these sequences.

\begin{theorem}\label{T:main}
Let $A \subseteq \nat$ be a set of natural numbers with indicator sequence $i(A;n)$, and let $j^A(x)$ be the generating function of $(i(A;n))_{n=0}^\infty$. Given $m \geq 1$ and $0 \leq q \leq m-1$, the generating functions of the sequences $(b(A,m,q;n))_{n=0}^\infty$, $(c(A,m,q;n))_{n=0}^\infty$, and $(d(A,m,q;n))_{n=0}^\infty$ are, respectively,  
\begin{align*}
f^A_{m,q}(x) 
&= \sum_{n=0}^\infty b(A,m,q;n) x^n 
 = \frac{(j^A(x))^q}{1 - (j^A(x))^m}\text, \\
g^A_{m,q}(x) 
&= \sum_{n=0}^\infty c(A,m,q;n) x^n 
 = \begin{cases}
   \dfrac{x(j^A(x))^{m-1}}{1 - (j^A(x))^m}\dfrac{d}{dx}j^A(x)\text,
   &\text{if $q = 0$;} \medskip \\
   \dfrac{x(j^A(x))^{q-1}}{1 - (j^A(x))^m}\dfrac{d}{dx}j^A(x)\text,
   &\text{if $q \ne 0$,} 
   \end{cases} \qquad\text{and}\\
h^A_{m,q}(x) 
&= \sum_{n=0}^\infty d(A,m,q;n) x^n 
 = \sum_{\mathclap{\substack{ks \equiv q\!\!\!\! \pmod{m}\\0\leq s\leq m-1}}}
   \frac{\phi(k)}{k} L_{m,s}\big(j^A(x^k)\big)\text,
\end{align*}
where 
\[
L_{m,s}(y) = 
\begin{cases}
\dfrac{1}{m} \log \dfrac{1}{1 - y^m}\text, 
& \text{if $s = 0$;} \\[10pt]
\displaystyle\int_0^y \frac{u^{s-1}\,du}{1 - u^m}\text, 
& \text{if $s \ne 0$.}
\end{cases}
\]
\end{theorem}

\begin{remark}\label{R:Lpowerseries}
The functions $L_{m,s}(y)$ can be expressed as the following power series:
\[
L_{m,0}(y) 
= \sum_{k=1}^\infty \frac{y^{km}}{km}\text,\qquad\text{and}\qquad
L_{m,s}(y) 
= \sum_{k=0}^\infty \frac{y^{s+km}}{s+km}
\quad\text{for}\quad 1\leq s \leq m-1\text.
\]
They satisfy $L_{m,0}(y) + \cdots + L_{m,m-1}(y) = -\log(1-y) = L_{1,0}(y)$.
\end{remark}

\smallskip

\begin{proof}[Proof of Theorem~\ref{T:main}]
The number of $A$-compositions of $n$ with $mp+q$ parts is given by the coefficient of $x^n$ in $\big(j^A(x)\big){}^{mp+q}$. Summing over $p$, we obtain 
\[
\sum_{n=0}^\infty b(A,m,q;n)x^n 
= \sum_{p=0}^\infty \big(j^A(x)\big){}^{mp+q}
= \big(j^A(x)\big){}^{q} 
  \sum_{p=0}^\infty \big(j^A(x)\big){}^{mp} 
= \frac{(j^A(x))^q}{1 - (j^A(x))^m}\text.
\]
Next, a circular $A$-composition of $n$ with $mp+q$ terms begins with a first part whose size is in $A$ together with a position of $v_1\in C_n$ within the first part, and it is completed by a linear (i.e., ordinary) $A$-composition with $mp + q - 1$ parts. Recall that a circular composition cannot have zero parts, and so $p$ and $q$ cannot simultaneously be zero. If $q = 0$, we have 
\begin{align*}
\sum_{n=0}^\infty c(A,m,0;n)x^n 
&= \sum_{p=1}^\infty 
   \left(x\frac{d}{dx}j^A(x)\right) 
   \big(j^A(x)\big){}^{mp-1} \\
&= \big(j^A(x)\big)^{m-1}
   \left(x\frac{d}{dx}j^A(x)\right) 
   \sum_{p=1}^\infty 
   \big(j^A(x)\big){}^{m(p-1)} \\
&= \frac{x(j^A(x))^{m-1}}{1 - (j^A(x))^m}
   \frac{d}{dx}j^A(x)\text,
\end{align*}
and if $q \ne 0$ then 
\begin{align*}
\sum_{n=0}^\infty c(A,m,q;n)x^n 
&= \sum_{p=0}^\infty 
   \left(x\frac{d}{dx}j^A(x)\right) 
   \big(j^A(x)\big){}^{mp+q-1} \\
&= \big(j^A(x)\big)^{q-1}
   \left(x\frac{d}{dx}j^A(x)\right) 
   \sum_{p=0}^\infty 
   \big(j^A(x)\big){}^{mp} \\
&= \frac{x(j^A(x))^{q-1}}{1 - (j^A(x))^m}
   \frac{d}{dx}j^A(x)\text.
\end{align*}

To count the number of cyclic $A$-compositions of $n$ whose number of parts equals $mp + q$ for some $p$, we let $\Z/n\Z$ act on the set of circular $A$-compositions as in section \ref{S:bg}. Again we need to count the number of fixed points for the subgroup of order $k$, where $k$ divides $n$. In order for a circular composition of $n/k$ to correspond to a circular composition of $n$ with $mp + q$ parts, it must have $s$ parts, where $ks = mp+q$; that is, we need only consider compositions of $C_{n/k}$ with $s$ terms, where $ks \equiv q$ (mod $m$). Therefore, we can write
\begin{align*}
\sum_{n=0}^\infty d(A,m,q;n)x^n 
&= \sum_{n=1}^\infty \qquad
   \sum_{\mathclap{\substack{ks \equiv q\!\!\!\! \pmod{m}\\k\mid n,\,0\leq s\leq m-1}}} 
   \frac{\phi(k)}{n}c(A,m,s;n/k) x^n \\
&= \sum_{\mathclap{\substack{ks \equiv q\!\!\!\! \pmod{m}\\0\leq s\leq m-1}}} \qquad\sum_{\ell=1}^\infty \frac{\phi(k)}{k\ell} c(A,m,s;\ell) x^{k\ell} \\
&= \sum_{\mathclap{\substack{ks \equiv q\!\!\!\! \pmod{m}\\0\leq s\leq m-1}}} \frac{\phi(k)}{k} \sum_{\ell=1}^\infty \frac{c(A,m,s;\ell)}{\ell} x^{k\ell}\text.
\end{align*}
Using the formula for $c(A,m,q;n)$ derived previously, we obtain 
\[
\sum_{\ell=1}^\infty \frac{c(A,m,0;\ell)}{\ell} y^{\ell} 
= \int_0^y \frac{g^A_{m,0}(u)}{u}\,du 
= \int_0^y \frac{\frac{d}{du}(j^A(u))^{m-1}}{1 - (j^A(u))^m}\,du 
= \frac1m \log\frac1{1-(j^A(u))^m}\text,
\]
and, when $s > 0$, 
\[
\sum_{\ell=1}^\infty \frac{c(A,m,s;\ell)}{\ell} y^{\ell} 
= \int_0^y \frac{g^A_{m,s}(u)}{u}\,du 
= \int_0^y \frac{\frac{d}{du}(j^A(u))^{s-1}}{1 - (j^A(u))^m}\,du \text.
\]
Setting $x^k = y$ in the previous equation establishes the desired formula.
\end{proof}

\begin{remark}\label{R:pepp}
The genesis of this paper was the need---which arose for a different counting problem in graph theory---to calculate the number of circular $A$-compositions with an odd number of parts, i.e., $c(A,2,1;n)$, for a certain set $A$. Credit goes to John Palmer, who discovered this application of circular compositions while working on an undergraduate research project at Pepperdine \cite{Palmer}. I could not find a formula for $c(A,2,1;n)$ in the literature, and in proving it I realized that it was no harder to prove the general congruence case. Because of the close connection between circular compositions and cyclic compositions, it seemed worthwhile to include a formula for $d(A,m,q;n)$ as well.
\end{remark}

In light of the preceding remark, we shall single out the cases of compositions having an odd or an even number of parts in a corollary.

\begin{corollary}\label{Cor:odd_and_even}
Given a set $A \subseteq \nat$, the sequences $b(A,2,q;n)$ and $c(A,2,q;n)$, with $q \in \{0,1\}$, have the respective generating functions 
\[
f^A_{2,q}(x) 
= \frac{1}{2} f^A(x) 
   + \frac{1}{2}
   \left(\frac{(-1)^q}{1 + j^A(x)}\right) 
\qquad\text{and}\qquad
g^A_{2,q}(x) 
= \frac{1}{2} g^A(x) 
  + \frac{1}{2} 
  \left(\frac{(-1)^{q+1} x\frac{d}{dx}j^A(x)}{1 + j^A(x)}\right)\text.
\]
For $d(A,2,0;n)$ and $d(A,2,1;n)$, the generating functions are 
\begin{gather*}
h^A_{2,0}(x) 
= \frac12 \sum_{k=1}^\infty 
  \frac{\phi(k)}{k}\log\frac{1}{1-(j^A(x^k))^2}
  + \frac12 \sum_{r=1}^\infty 
    \frac{\phi(2r)}{2r} 
    \log\frac{1+j^A(x^{2r})}{1-j^A(x^{2r})}\\
\text{and} \qquad 
h^A_{2,1}(x) 
= \frac12 \sum_{r=0}^\infty 
  \frac{\phi(2r+1)}{2r+1} 
  \log\frac{1+j^A(x^{2r+1})}{1-j^A(x^{2r+1})}\text.
\end{gather*}
\end{corollary}

\begin{proof}[Proof of Corollary~\ref{Cor:odd_and_even}]
The formulas for $f^A_{2,q}(x)$ and $g^A_{2,q}(x)$ follow immediately from Theorem~\ref{T:main} combined with the algebraic identities $1/(1-u^2) = 1/(2(1-u))+1/(2(1+u))$ and $u/(1-u^2) = 1/(2(1-u))-1/(2(1+u))$.

For $h^A_{2,0}(x)$, we need two additional observations: first, $ks \equiv 0$ (mod $2$) if either $s = 0$ or $k \in 2\nat$; and second, 
\[
L_{2,1}(y) 
= \int_0^y \frac{du}{1-u^2} 
= \frac12 \log\frac{1 + y}{1 - y}\text.
\]
For $h^A_{2,1}(x)$, note that the only values of $k$ and $s$ with $0 \leq s < 2$ that satisfy $ks \equiv 1$ (mod $2$) are $s = 1$ and $k \in \nat\setminus2\nat$.
\end{proof}

The statement of Corollary~\ref{Cor:odd_and_even} illustrates that each $b(A,m,q;n)$ or $c(A,m,q;n)$ can be thought of as $(1/m)b(A;n)$ or $(1/m)c(A;n)$, respectively, plus some appropriate ``correction term'' that depends on $q$ and determines how the compositions are distributed among the congruence classes modulo $m$. As we shall see in the examples of the following sections, these correction terms may be bounded or unbounded as functions of $n$, and for certain sets $A$ they may even cancel out the primary term entirely for some values of $n$. The situation for $d(A,m,q;n)$ is more complicated, due to its dependence on divisibility properties of $n$.

\section{Examples}\label{S:examples}

The framework of $A$-compositions whose numbers of parts are congruent to $q$ mod $m$ provides a unifying perspective on a variety of integer sequences.

\subsection{Trivial cases}\label{SS:trivial}

It is often valuable to examine ``trivial'' cases to determine to what extent a set of formulas applies. Let us therefore begin with the empty set $A = \emptyset$. The only possible $\emptyset$-composition is the empty sum. The generating function of $(i(\emptyset;n))_{n=0}^\infty$ is $j^\emptyset(x) = 0$. The formulas of Theorem~\ref{T:main} yield $f^\emptyset_{m,q}(x) = 1$ if $q=0$ (\emph{OEIS} \seqnum{A000007}), zero otherwise (\emph{OEIS} \seqnum{A000004}), following the convention $0^0 = 1$, and $g^\emptyset_{m,q}(x) = h^\emptyset_{m,q}(x) = 0$ for all $m$ and $q$, which matches the expectation that $0$ is the only number with an $\emptyset$-composition, and no number has a circular or cyclic $\emptyset$-composition.

The next simplest case is $A = \{1\}$. Then $j^{\{1\}}(x) = x$, and from Theorem~\ref{T:main} we have 
\begin{gather*}
f^{\{1\}}_{m,q}(x) 
= \frac{x^q}{1-x^m}\text, \qquad
g^{\{1\}}_{m,q}(x) 
= h^{\{1\}}_{m,q}(x) 
= \begin{cases}
  \dfrac{x^m}{1-x^m}\text, & \text{if $q = 0$;} 
  \medskip \\
  \dfrac{x^q}{1-x^m}\text, & \text{if $q \ne 0$.}
  \end{cases}
\end{gather*}
Thus $b(\{1\},m,q;n)$ equals one when $n$ is congruent to $q$ mod $m$, and zero otherwise. The same is true for $c(\{1\},m,q;n)$ and $d(\{1\},m,q;n)$, except when $q=n=0$. We get the equality $h^{\{1\}}_{m,q}(x) = g^{\{1\}}_{m,q}(x)$ from the fact that when $n \geq 1$, there is only one circular composition, and consequently only one cyclic composition, of $n$ with parts in $\{1\}$. 

\subsection{A useful lemma}

Before going on, we exhibit a partial fraction decomposition for a type of rational expression that has already appeared and will continue to arise in the current study. 

\begin{lemma}\label{L:partfrac}
Given integers $\alpha$ and $\beta$ such that $0 \leq \alpha < \beta$, set $\zeta = e^{2\pi i/\beta}$. Then 
\[
\frac{u^\alpha}{1-u^\beta} 
= \frac{1}{\beta}
  \sum_{k=0}^{\beta-1} 
  \frac{\zeta^{-k\alpha}}{1-\zeta^k u}\text.
\]
\end{lemma}
\begin{proof}
We begin with the ordinary partial fraction decomposition of $u^\alpha/(u^\beta-1)$. In other words, we seek constants $c_k$ such that 
\[
\frac{u^\alpha}{u^\beta-1} 
= \sum_{k=0}^{\beta-1} 
  \frac{c_k}{u-\zeta^k}\text.
\]
Because each root $\zeta^k$ of $u^\beta-1$ is simple, these coefficients $c_k$ can be computed as residues of $u^\alpha/(u^\beta-1)$. That is, 
\[
c_k 
= \lim_{u\to\zeta^k} 
  (u-\zeta^k)\frac{u^\alpha}{u^\beta-1}
= \lim_{u\to\zeta^k} 
  \frac{u^\alpha}{(u^\beta-1)/(u-\zeta^k)} 
= \frac{\zeta^{k\alpha}}{\beta\zeta^{k(\beta-1)}}
= \frac{1}{\beta}\zeta^{k\alpha+k}\text.
\]
Thus 
\[
\frac{u^\alpha}{1-u^\beta} 
= \frac1\beta\sum_{k=0}^{\beta-1} 
  \frac{\zeta^{k\alpha+k}}{\zeta^k - u}
= \frac1\beta\sum_{k=0}^{\beta-1} 
  \frac{\zeta^{k\alpha}}{1 - \zeta^{-k}u}
= \frac1\beta\sum_{k=0}^{\beta-1} 
  \frac{\zeta^{-k\alpha}}{1 - \zeta^k u}\text,
\]
as claimed.
\end{proof}

\begin{remark}
One immediate application of Lemma~\ref{L:partfrac} is that the functions $L_{m,s}(y)$ appearing in Theorem~\ref{T:main} can be expressed using complex logarithms and $m$th roots of unity. Set $\zeta = \exp(2\pi i/m)$, then use $\alpha = s-1$ and $\beta = m$ in Lemma~\ref{L:partfrac} to get 
\[
L_{m,s}(y) 
= \int_0^y \frac{u^{s-1}\,du}{1 - u^m}
= \frac1m 
   \sum_{t=0}^{m-1} 
   \int_0^y \frac{\zeta^{(1-s)t}\,du}{1 - \zeta^t u} 
= \frac{1}{m} 
   \sum_{t=0}^{m-1} \zeta^{-st} \mathop{\mathrm{Log}}
   \frac{1}{1 - \zeta^t y}\text,
\]
where $\mathop{\mathrm{Log}}$ denotes the principal logarithm, with a branch cut along the negative real axis.
\end{remark}


\subsection{Compositions allowing parts of any size}\label{SS:allsize}

Now we turn to $\nat$-compositions; that is, we will impose restrictions only on the number of parts, not their sizes. The generating function of $(i(\nat;n))_{n=1}^\infty$ is the geometric series 
\[
j^{\nat}(x) 
= \sum_{n=1}^\infty x^n 
= \frac{x}{1-x}\text.
\]
From this, we know 
\[
x\frac{d}{dx}j^{\nat}(x) 
= \sum_{n=1}^\infty nx^n 
= \frac{x}{(1-x)^2}\text.
\]
By Theorem~\ref{T:main}, 
the generating functions for $(b(\nat,m,q;n))_{n=0}^\infty$ and $(c(\nat,m,q;n))_{n=0}^\infty$ are 
\[
f^{\nat}_{m,q}(x) 
= \frac{x^q/(1-x)^q}{1-x^m/(1-x)^m} 
\hspace{.5in}
\text{and}
\hspace{.5in}
g^{\nat}_{m,q}(x) 
= \begin{cases}
  \dfrac{x^m/(1-x)^{m+1}}{1-x^m/(1-x)^m}\text,
  &\text{if $q = 0$;} \\[10pt]
  \dfrac{x^q/(1-x)^{q+1}}{1-x^m/(1-x)^m}\text,
  &\text{if $q \ne 0$.}
  \end{cases}
\]
In Theorem~\ref{T:Ncomp}, we will see explicit formulas for $b(\nat,m,q;n)$ and $c(\nat,m,q;n)$, but first we examine two relationships between these sequences, which generalize some obvious relationships between $b(\nat;n)$ and $c(\nat;n)$. For comparison, recall that 
\[
b(\nat;n) 
= \begin{cases}
  1\text, & \text{if $n = 0$;} \\
  2^{n-1}\text, & \text{if $n \geq 1$;}
  \end{cases}
\hspace{.5in}
\text{and}
\hspace{.5in}
c(\nat;n) = 2^n - 1
\]
(\emph{OEIS} \seqnum{A011782} and \seqnum{A000225}). These satisfy 
\[
b(\nat;n) 
= c(\nat;n) - c(\nat;n-1) 
= c(\nat;n-1) + 1
\]
for $n \geq 1$.

\begin{lemma}\label{L:bcdiff}
For all $0 \leq q < m$ and $n \geq 1$ we have 
\begin{equation}\label{Eq:firstdiff}
b(\nat,m,q;n) 
= c(\nat,m,q;n) - c(\nat,m,q;n-1)\text,
\end{equation}
and when $m > 1$ 
\begin{equation}\label{Eq:congclass}
b(\nat,m,q;n) 
= \begin{cases}
  c(\nat,m,m-1;n-1)\text, & \text{if $q = 0$;} \\
  c(\nat,m,0;n-1) + 1\text, & \text{if $q = 1$;} \\
  c(\nat,m,q-1;n-1)\text, & \text{otherwise.}
  \end{cases}
\end{equation}
\end{lemma}

Below are two proofs of each equality: one analytic, using generating functions, and one bijective, using direct correspondences between sets.

\begin{proof}[Analytic proof of Lemma \ref{L:bcdiff}]
From the formulas for $f^{\nat}_{m,q}(x)$ and $g^{\nat}_{m,q}(x)$, we have 
\[
f^{\nat}_{m,0}(x) 
= 1 + (1 - x) g^{\nat}_{m,0}(x)\text,
\]
and if $q \ne 0$ then 
\[
f^{\nat}_{m,q}(x) 
= (1 - x) g^{\nat}_{m,q}(x)\text.
\]
Equality \eqref{Eq:firstdiff} is immediate.

For equality \eqref{Eq:congclass}, we consider by cases:
\begin{align*}
f^{\nat}_{m,0}(x) 
&= \frac{1}{1 - x^m/(1-x)^m} 
 = 1 + \frac{x^m/(1-x)^m}{1 - x^m/(1-x)^m}
 = 1 + x g^{\nat}_{m,m-1}(x)\text, \\
f^{\nat}_{m,1}(x) 
&= \frac{x/(1-x)}{1 - x^m/(1-x)^m} 
 = \frac{x}{1-x} + \frac{x^{m+1}/(1-x)^{m+1}}{1 - x^m/(1-x)^m} 
= \frac{x}{1-x} + x g^{\nat}_{m,0}(x)\text, \\
f^{\nat}_{m,q}(x) 
&= \frac{x^q/(1-x)^q}{1-x^m/(1-x)^m} 
 = xg^{\nat}_{m,q-1}(x)
\quad\text{when}\quad 2 \leq q \leq m-1\text.
\end{align*}
Equality \eqref{Eq:congclass} follows.
\end{proof}
\begin{proof}[Bijective proof of Lemma \ref{L:bcdiff}]
Recall that a circular composition of $n$ consists of the connected components that remain when one or more edges are removed from the cycle graph $C_n$. Each ordinary (linear) composition of $n$ may be identified with a circular composition of $n$ in which the edge $e_n = \{v_n,v_1\}$ has been removed. A circular composition of $n$ in which the edge $e_n$ remains can be identified with a circular composition of $n-1$ by collapsing the edge $e_n$ to a single vertex. 

Since the circular compositions of $n$ can be partitioned according to whether $e_n$ is removed or kept, we have $c(\nat,m,q;n) = b(\nat,m,q;n) + c(\nat,m,q;n-1)$, which is equivalent to \eqref{Eq:firstdiff}. 

For \eqref{Eq:congclass}, note that collapsing $e_n$ in $C_n$ to a single vertex almost induces a bijection from linear compositions of $n$ to circular compositions of $n-1$: the difference is that the composition of $n$ having a single part, namely $n$ itself, does not have any corresponding circular composition of $n-1$, because after $e_n$ is collapsed, no edges in $C_{n-1}$ have been removed. Now observe that collapsing $e_n$, when starting with a linear composition of $n$, reduces the total number of parts by $1$, because the parts that contain $v_1$ and $v_n$ are merged.
\end{proof}

Let $\lfloor\,\cdot\,\rfloor$ denote the floor function.

\begin{theorem}\label{T:Ncomp}
Given $0 \leq q < m$ and $n \geq 1$, we have 
\begin{align*}
b(\nat,m,q;n) 
&= \frac{2^{n-1}}{m} 
  + \frac{2}{m} \sum_{k=1}^{\lfloor (m-1)/2 \rfloor} 
     \left(2\cos\frac{\pi k}{m}\right)^{n-1}
     \cos\frac{\pi k(n + 1 - 2q)}{m} 
\hspace{.8in}\text{and}\\
c(\nat,m,q;n) 
&= \begin{cases}
  \displaystyle
  -1
  + \frac{2^n}{m} 
  + \frac{2}{m} \sum_{k=1}^{\lfloor (m-1)/2 \rfloor}
     \left(2\cos\frac{\pi k}{m}\right)^n 
     \cos\frac{\pi kn}{m}\text, 
     & \text{if $q = 0$;} \\
  \displaystyle
  \frac{2^n}{m} 
  + \frac{2}{m} \sum_{k=1}^{\lfloor (m-1)/2 \rfloor} 
     \left(2\cos\frac{\pi k}{m}\right)^n 
     \cos\frac{\pi k(n - 2q)}{m}\text,
     & \text{if $q \ne 0$.}
\end{cases}
\end{align*}
\end{theorem}

\begin{proof}
By Lemma~\ref{L:bcdiff}, we can express $b(\nat,m,q;n)$ in terms of $c(\nat,m,q;n)$, and so we will calculate $c(\nat,m,q;n)$ first. Throughout the proof, let $\zeta = e^{i\,2\pi/m}$. 

In the case $q \ne 0$, we set $a = q$, $b = m$, and $u = x/(1-x)$ in Lemma~\ref{L:partfrac} to obtain 
\begin{align*}
g^{\nat}_{m,q}(x) 
&= \frac{x^q/(1-x)^{q+1}}{1-x^m/(1-x)^m} 
 = \frac{1}{1-x}\left(\frac{x^q/(1-x)^q}{1-x^m/(1-x)^m}\right) \\
&= \frac{1}{1-x}
   \left(\frac1m
   \sum_{k=0}^{m-1} \frac{\zeta^{-kq}}{1-\zeta^k x/(1-x)}\right) \\ 
&= \frac1m
   \sum_{k=0}^{m-1} \frac{\zeta^{-kq}}{1-x-\zeta^k x} 
 = \frac1m
   \sum_{k=0}^{m-1} \frac{\zeta^{-kq}}{1-(1+\zeta^k) x} \\
&= \frac1m 
   \sum_{k=0}^{m-1} 
   \sum_{n=0}^\infty
   \zeta^{-kq}(1+\zeta^k)^n x^n\text.
\end{align*}
When $q = 0$, set $\alpha = 0$, $\beta = m$, and $u = x/(1-x)$ in Lemma~\ref{L:partfrac} to obtain 
\begin{align*}
g^{\nat}_{m,0}(x) 
&= \frac{x^m/(1-x)^{m+1}}{1-x^m/(1-x)^m} 
 = \frac{1}{1-x}\left(\frac{x^m/(1-x)^m}{1-x^m/(1-x)^m}\right) \\
&= \frac{1}{1-x}\left(-1 + \frac{1}{1-x^m/(1-x)^m}\right) \\
&= -\frac{1}{1-x}
   + \frac1m \sum_{k=0}^{m-1} 
     \frac{1}{1 - (1+\zeta^k) x} \\
&= -\sum_{n=0}^\infty x^n 
   + \frac1m 
     \sum_{k=0}^{m-1} 
     \sum_{n=0}^\infty (1+\zeta^k)^n x^n\text.
\end{align*}
Now take note of three things. First, in both cases the constant terms, with $n=0$, cancel out, which is to be expected because $g^{\nat}_{m,q}(0) = 0$. Second, the $k=0$ term in each case becomes 
\[
\frac1m \sum_{n=1}^\infty 2^n x^n\text,
\]
which will represent the dominant term $(1/m)2^n$ in the expression for $c(\nat,m,q;n)$. Third, if $m$ is even, then $\zeta^{m/2} = -1$, and so the $k = m/2$ portion of the double summation reduces to $1/m$, which does not contribute to any terms of positive order in the power series. 

These observations, along with the convention that $0^0 = 1$, allow us to write both forms (for $q=0$ and $q\ne0$) together as 
\begin{equation}\label{Eq:gmqnat}
g^{\nat}_{m,q}(x) 
= -0^q\sum_{n=1}^\infty x^n
   + \frac1m \sum_{n=1}^\infty 2^n x^n 
   + \frac1m 
     \sum_{n=1}^\infty
     \sum_{k=1}^{m-1} 
     \zeta^{-kq}(1+\zeta^k)^n x^n\text.
\end{equation}
To reach the formulas for $c(\nat,m,q;n)$ that appear in the statement of Theorem~\ref{T:Ncomp}, we just need to rearrange the coefficient of $x^n$ in the final term of \eqref{Eq:gmqnat}: 
\begin{align*}
\sum_{k=1}^{m-1} \zeta^{-kq}(1+\zeta^k)^n &=\sum_{k=1}^{\lfloor (m-1)/2 \rfloor} 
\big(e^{-i\,2\pi kq/m} (1+e^{i\,2\pi k/m})^n + e^{i\,2\pi kq/m} (1+e^{-i\,2\pi k/m})^n\big) \\
&= \sum_{k=1}^{\lfloor (m-1)/2 \rfloor}
   \left(e^{i\pi k(n-2q)/m} + e^{-i\pi k(n-2q)/m}\right)
   \left(e^{i\pi k/m} + e^{-i\pi k/m}\right)^n \\
&= 2 \sum_{k=1}^{\lfloor (m-1)/2 \rfloor} 
     \cos(\pi k(n - 2q)/m)
     \big(2\cos (\pi k/m)\big)^n \text.
\end{align*}
This completes the proof of the formula for $c(\nat,m,q;n)$.

To obtain $(b(\nat,m,q;n))_{n=1}^\infty$ from $(c(\nat,m,q;n))_{n=1}^\infty$, we can use either equality \eqref{Eq:firstdiff} or \eqref{Eq:congclass} from Lemma \ref{L:bcdiff}. Each approach has pros and cons. Using \eqref{Eq:firstdiff} means we can make a single argument for all values of $q$, but it requires the somewhat obscure identity 
\[
2\cos (\pi k/m)\cos(\pi k(n - 2q)/m)
- \cos(\pi k(n - 1 - 2q)/m) 
= \cos(\pi k(n + 1 - 2q)/m)\text,
\]
which can be derived by rearranging the trigonometric formula 
\[
2\cos\eta\cos\theta = \cos(\eta+\theta) + \cos(\eta-\theta)\text.
\]
Using \eqref{Eq:congclass}, on the other hand, just requires direct substitution, but three separate cases need to be considered. The details are left to the reader.
\end{proof}

\begin{remark}\label{R:tokens}
In a circular composition of $n$, the number of parts equals the number of edges that are removed from $C_n$ to obtain the composition. With this in view, determining $c(\nat,m,q;n)$ goes back to an old problem, which may be expressed thusly: ``Given a collection of $n$ tokens, how many ways can a random nonempty sample of tokens be selected in such a manner that the number selected is congruent to $q$ modulo $m$?'' Cournot \cite{Cournot} posed the problem and solved it for $m \leq 4$; a complete solution was provided by Ramus \cite{Ramus}, whose method is more or less reproduced in the approach used here to calculate $c(\nat,m,q;n)$. 
\end{remark}

The generating function of the sequence $(d(\nat;n))_{n=0}^\infty$ is 
\[
h^{\nat}(x) = \sum_{k=1}^\infty \frac{\phi(k)}{k} \log \frac{1 - x^k}{1 - 2x^k}\text,
\]
and the number of cyclic compositions of $n$ is 
\[
d(\nat;n) 
= \frac{1}{n}\sum_{k\mid n} \phi(k)\big(2^{n/k} - 1\big)
= -1 + \frac{1}{n}\sum_{k\mid n} \phi(k)2^{n/k}
\]
(\emph{OEIS} \seqnum{A008965}). An exact formula for $d(\nat,m,q;n)$, using the expression that was derived in the proof of Theorem~\ref{T:main}, is available in terms of the values of $c(\nat,m,q;n/k)$ where $k \mid n$, but to write it out for general $m$ and $q$ would be cumbersome. We will restrict ourselves to the case $m = 2$. It follows from Theorem~\ref{T:Ncomp} (but it is also easy to work out by hand) that $c(\nat,2,0;n) = 2^{n-1} - 1$ and $c(\nat,2,1;n) = 2^{n-1}$. Thus, 
\begin{align*}
d(\nat,2,0;n)
&= \frac{1}{n} \sum_{k\mid n} \phi(k) c(\nat,2,0;n/k) 
   + \frac{1}{n} \sum_{k\mid n,\,\text{$k$ even}} \phi(k) c(\nat,2,1;n/k) \\
&= -1 + \frac{1}{2n} \sum_{k\mid n} \phi(k) 2^{n/k} 
   + \frac{1}{2n} \sum_{k\mid n,\,\text{$k$ even}} \phi(k) 2^{n/k} \\
&= -1 + \frac{1}{n} \sum_{k\mid n,\,\text{$k$ even}} \phi(k) 2^{n/k} 
   + \frac{1}{2n} \sum_{k\mid n,\,\text{$k$ odd}} \phi(k) 2^{n/k} 
\end{align*}
(\emph{OEIS} \seqnum{A056295}), and
\[
d(\nat,2,1;n)
= \frac{1}{n} \sum_{k\mid n,\,\text{$k$ odd}} \phi(k) c(\nat,2,1;n/k) 
= \frac{1}{2n} \sum_{k\mid n,\,\text{$k$ odd}} \phi(k) 2^{n/k}
\]
(\emph{OEIS} \seqnum{A000016}).

\subsection{Compositions with parts no greater than $N$}\label{SS:maxN}

For $N \in \nat$, let $[N] = \{1,2,\dots,N\}$. Fix an $N \geq 2$. Then 
\begin{align*}
j^{[N]}(x) 
&= \sum_{k=1}^N x^k
 = \frac{x-x^{N+1}}{1-x}
 \qquad\text{and} \\
x\frac{d}{dx}j^{[N]}(x) 
&= \sum_{k=1}^N kx^k 
 = \frac{x - (N+1)x^{N+1} + Nx^{N+2}}{(1-x)^2}
 = \frac{1}{1-x}\left(-Nx^{N+1} + \sum_{k=1}^{N} x^k\right)\text,
\end{align*}
whence 
\begin{align*}
f^{[N]}(x) 
&= \frac{1}{1-\sum_{k=1}^N x^k} 
 = \frac{1-x}{1-2x+x^{N+1}} 
 \qquad\text{and} \\
g^{[N]}(x) 
&= \frac{\sum_{\ell=1}^N \ell x^\ell}{1-\sum_{k=1}^N x^k} 
 = \frac{(x-x^{N+1})/(1-x) - Nx^{N+1}}{1-2x+x^{N+1}}\text.
\end{align*}

It is convenient at this point to recall the $N$-step generalizations of the Fibonacci and Lucas numbers, denoted by $F^{(N)}_n$ and $L^{(N)}_n$: these are 
\[
F^{(N)}_n 
= \begin{cases}
  0\text, &\text{if $n \leq 0$;} \\
  1\text, &\text{if $n = 1$;} \\
  F^{(N)}_{n-1} + \cdots + F^{(N)}_{n-N}\text, &\text{if $n \geq 2$,} \\
  \end{cases}
\]
and 
\[
L^{(N)}_n 
= \begin{cases}
  -1\text, &\text{if $n < 0$;} \\
  N\text, &\text{if $n = 0$;} \\
  L^{(N)}_{n-1} + \cdots + L^{(N)}_{n-N}\text, &\text{if $n \geq 1$.} \\
  \end{cases}
\]
Here we are following the conventions used by Noe and Post \cite{NP}. In particular, $(F^{(2)}_n)_{n=0}^\infty$ is the standard Fibonacci sequence (\emph{OEIS} \seqnum{A000045}), and $(L^{(2)}_n)_{n=0}^\infty$ is the standard Lucas sequence (\emph{OEIS} \seqnum{A000032}). One may quickly deduce that $F^{(N)}_n = 2^{n-2}$ for $2 \leq n \leq N+1$ and $L^{(N)}_n = 2^n - 1$ for $1 \leq n \leq N$.

The generating functions of $\big(F^{(N)}_n\big){}_{n=0}^\infty$ and $\big(L^{(N)}_n\big){}_{n=0}^\infty$ are, respectively,
\[
f^{(N)}(x) 
= \frac{x}{1 - \sum_{k=1}^N x^k}
\qquad\text{and}\qquad
g^{(N)}(x) 
= \frac{N - \sum_{\ell=1}^{N-1} (N-\ell) x^\ell}{1 - \sum_{k=1}^N x^k}\text.
\]
From the equalities 
\[
f^{(N)}(x) 
= x f^{[N]}(x) 
\qquad\text{and}\qquad
g^{(N)}(x) 
= g^{[N]}(x) + N\text,
\]
we see that the number of $[N]$-compositions and the number of circular $[N]$-compositions of $n$ are respectively given by 
\[
b([N];n) = F^{(N)}_{n+1} 
\qquad\text{and}\qquad
c([N];n) 
= \begin{cases}
  0\text, &\text{if $n = 0$;} \\
  L^{(N)}_n\text, &\text{otherwise.}
  \end{cases}
\]

In principle, we could follow the same process as we did for $b(\nat,m,q;n)$ and $c(\nat,m,q;n)$ to calculate $b([N],m,q;n)$ and $c([N],m,q;n)$ for all $m,q,n$, but the expressions would not be nearly as neat. In \S\ref{SS:allsize} we relied on the fact that $j^\nat(x)$ has degree $1$ as a rational function, whereas the degree of $j^{[N]}(x)$ is $N\geq2$; solving the equation $j^{[N]}(x) = \zeta$ is generally a difficult task. So we will instead give attention only to the cases where $m = 2$, for which we can apply Corollary~\ref{Cor:odd_and_even}.

\begin{theorem}\label{T:halffib}
For all $N \geq 2$ and $n \geq 1$, we have 
\begin{align*}
b([N],2,0;n) 
&= \frac12 F^{(N)}_{n+1} + 
\begin{cases}
1/2\text, & \text{if $n \equiv 0\pmod{N+1}$;} \\
-1/2\text, & \text{if $n \equiv 1\pmod{N+1}$;} \\
0\text, & \text{otherwise,}
\end{cases} \\
b([N],2,1;n) 
&= \frac12 F^{(N)}_{n+1} + 
\begin{cases}
-1/2\text, & \text{if $n \equiv 0\pmod{N+1}$;} \\
1/2\text, & \text{if $n \equiv 1\pmod{N+1}$;} \\
0\text, & \text{otherwise,}
\end{cases} \\
c([N],2,0;n) 
&= \frac12 L^{(N)}_{n} + 
\begin{cases}
N/2\text, & \text{if $n \equiv 0\pmod{N+1}$;} \\
-1/2\text, & \text{otherwise,}
\end{cases} \qquad\text{and}\\
c([N],2,1;n)
&= \frac12 L^{(N)}_{n} + 
\begin{cases}
-N/2\text, & \text{if $n \equiv 0\pmod{N+1}$;} \\
1/2\text, & \text{otherwise.}
\end{cases}
\end{align*}
\end{theorem}

When $N = 2$, the formulas of Theorem~\ref{T:halffib} produce the sequences \emph{OEIS} \seqnum{A094686}, \seqnum{A093040}, \seqnum{A100886}, and \seqnum{A366043}. See Figures \ref{F:3comp_evenodd}--\ref{F:circcomp6_evenodd} for illustrations of $c([3],2,0;n)$ and $c([3],2,1;n)$ when $4 \leq n \leq 6$; the relevant sequences are \emph{OEIS} \seqnum{A366044} and \seqnum{A366045}.

\begin{figure}[htb]
\centering
\begin{minipage}{4in}
\centering
\includegraphics{circcomp4a.pdf}\quad
\includegraphics{circcomp4c.pdf}\quad
\includegraphics{circcomp4b.pdf}\medskip

\includegraphics{circcomp4d.pdf}\quad
\includegraphics{circcomp4e.pdf}\quad
\includegraphics{circcomp4f.pdf}\quad
\includegraphics{circcomp4g.pdf}
\end{minipage}
\begin{minipage}{2in}
\centering
\includegraphics{circcomp4h.pdf}\quad
\includegraphics{circcomp4i.pdf}\medskip

\includegraphics{circcomp4j.pdf}\quad
\includegraphics{circcomp4k.pdf}
\end{minipage}

\caption{Among the eleven circular compositions of $4$ with parts in $[3] = \{1,2,3\}$, seven have an even number of parts, and four have an odd number of parts.}
\label{F:3comp_evenodd}
\end{figure}

\begin{figure}[htb]
\centering
\begin{minipage}{3in}
\centering
\includegraphics{circcomp5-2111a.pdf}\quad
\includegraphics{circcomp5-2111b.pdf}\quad
\includegraphics{circcomp5-2111c.pdf}\bigskip

\includegraphics{circcomp5-2111d.pdf}\quad
\includegraphics{circcomp5-2111e.pdf}\quad
\includegraphics{circcomp5-32a.pdf}\quad
\includegraphics{circcomp5-32b.pdf}\bigskip

\includegraphics{circcomp5-32c.pdf}\quad
\includegraphics{circcomp5-32d.pdf}\quad
\includegraphics{circcomp5-32e.pdf}
\end{minipage}
\hfill
\begin{minipage}{3in}
\centering
\includegraphics{circcomp5-11111.pdf}\quad
\includegraphics{circcomp5-221a.pdf}\quad
\includegraphics{circcomp5-221b.pdf}\quad
\includegraphics{circcomp5-221c.pdf}\bigskip

\includegraphics{circcomp5-221d.pdf}\quad
\includegraphics{circcomp5-221e.pdf}\quad
\includegraphics{circcomp5-311a.pdf}\quad
\includegraphics{circcomp5-311b.pdf}\bigskip

\includegraphics{circcomp5-311c.pdf}\quad
\includegraphics{circcomp5-311d.pdf}\quad
\includegraphics{circcomp5-32e.pdf}
\end{minipage}

\caption{Among the twenty-one circular $[3]$-compositions of $5$, ten have an even number of parts, and eleven have an odd number of parts.}
\label{F:circcomp5_evenodd}
\end{figure}

\begin{figure}[htb]
\centering
\begin{minipage}{3in}
\centering
\includegraphics{circcomp6-111111.pdf}\quad
\includegraphics{circcomp6-2121a.pdf}\quad
\includegraphics{circcomp6-2121b.pdf}\quad
\includegraphics{circcomp6-2121c.pdf}\bigskip

\includegraphics{circcomp6-2211a.pdf}\quad
\includegraphics{circcomp6-2211b.pdf}\quad
\includegraphics{circcomp6-2211c.pdf}\quad
\includegraphics{circcomp6-2211d.pdf}\bigskip

\includegraphics{circcomp6-2211e.pdf}\quad
\includegraphics{circcomp6-2211f.pdf}\quad
\includegraphics{circcomp6-3111a.pdf}\quad
\includegraphics{circcomp6-3111b.pdf}\bigskip

\includegraphics{circcomp6-3111c.pdf}\quad
\includegraphics{circcomp6-3111d.pdf}\quad
\includegraphics{circcomp6-3111e.pdf}\quad
\includegraphics{circcomp6-3111f.pdf}\bigskip

\includegraphics{circcomp6-33a.pdf}\quad
\includegraphics{circcomp6-33b.pdf}\quad
\includegraphics{circcomp6-33c.pdf}
\end{minipage}
\hfill
\begin{minipage}{3in}
\centering
\includegraphics{circcomp6-21111a.pdf}\quad
\includegraphics{circcomp6-21111b.pdf}\quad
\includegraphics{circcomp6-21111c.pdf}\quad
\includegraphics{circcomp6-21111d.pdf}\bigskip

\includegraphics{circcomp6-21111e.pdf}\quad
\includegraphics{circcomp6-21111f.pdf}\quad
\includegraphics{circcomp6-222a.pdf}\quad
\includegraphics{circcomp6-222b.pdf}\bigskip

\includegraphics{circcomp6-312a.pdf}\quad
\includegraphics{circcomp6-312b.pdf}\quad
\includegraphics{circcomp6-312c.pdf}\quad
\includegraphics{circcomp6-312d.pdf}\bigskip

\includegraphics{circcomp6-312e.pdf}\quad
\includegraphics{circcomp6-312f.pdf}\quad
\includegraphics{circcomp6-321a.pdf}\quad
\includegraphics{circcomp6-321b.pdf}\bigskip

\includegraphics{circcomp6-321c.pdf}\quad
\includegraphics{circcomp6-321d.pdf}\quad
\includegraphics{circcomp6-321e.pdf}\quad
\includegraphics{circcomp6-321f.pdf}
\end{minipage}

\caption{Among the thirty-nine circular $[3]$-compositions of $6$, nineteen have an even number of parts, and twenty have an odd number of parts.}
\label{F:circcomp6_evenodd}
\end{figure}

The appearance of congruence classes modulo $N+1$ in the statement of Theorem~\ref{T:halffib} may initially come as a surprise; as we shall see, it is a consequence of the fact that $1+j^{[N]}(x) = (1 - x^{N+1})/(1-x)$. 

\begin{proof}[Proof of Theorem~\ref{T:halffib}]
By Corollary~\ref{Cor:odd_and_even}, for $q \in \{0,1\}$, we have 
\begin{align*}
&f^{[N]}_{2,q}(x) 
= \frac{1}{2} f^{[N]}(x) 
   + \frac{(-1)^q}{2}
   \left(\frac{1}{1 + j^{[N]}(x)}\right) 
\qquad\text{and}
\\
&g^{[N]}_{2,q}(x) 
= \frac{1}{2} g^{[N]}(x) 
  + \frac{(-1)^{q+1}}{2} 
  \left(\frac{x\frac{d}{dx}j^{[N]}(x)}{1 + j^{[N]}(x)}\right)\text.
\end{align*}
Because we already know that 
\[
f^{[N]}(x) = \frac{1}{x}f^{(N)}(x)
\qquad\text{and}\qquad
g^{[N]}(x) = g^{(N)}(x) - N\text,
\]
we only need to show that the latter terms match the bracketed expressions in the theorem statement. So we observe that 
\[
\frac{1}{1 + j^{[N]}(x)} 
= \frac{1}{1+x+\cdots+x^N} 
= \frac{1 - x}{1 - x^{N+1}} 
= \sum_{k=0}^\infty x^{k(N+1)} 
   - \sum_{\ell=0}^\infty x^{\ell(N+1)+1}\text, 
\]
and 
\begin{align*}
\frac{x\frac{d}{dx}j^{[N]}(x)}{1 + j^{[N]}(x)} 
&= \frac{x + \cdots + x^N - Nx^{N+1}}{1 - x^{N+1}} 
= - \sum_{k=1}^\infty Nx^{k(N+1)} 
  + \sum_{p=1}^N \sum_{\ell=0}^\infty x^{\ell(N+1)+p}\text, 
\end{align*}
from which the claimed formulas follow.
\end{proof}

For the remainder of the paper, we will use the standard notation $F_n = F^{(2)}_n$ and $L_n = L^{(2)}_n$ to denote the usual $2$-step Fibonacci and Lucas sequences.

\subsection{Compositions with odd parts}\label{SS:odd}

Let $O = \nat\setminus2\nat$ be the set of odd natural numbers. 
From the expressions 
\[
j^O(x) 
= \frac{x}{1 - x^2}
\qquad\text{and}\qquad
x\frac{d}{dx}j^O(x) 
= \frac{x+x^3}{(1-x^2)^2} 
= \frac{1+x^2}{1-x^2}\cdot j^O(x)\text,
\]
we obtain 
\begin{align*}
f^O(x) 
&= \frac{1 - x^2}{1 - x - x^2}
 = 1 + \frac{x}{1 - x - x^2} 
 = 1 + f^{(2)}(x) \qquad\quad\;\text{and}\\
g^O(x) 
&= \frac{x + x^3}{(1 - x^2)(1 - x - x^2)} 
 = \frac{2 - x}{1 - x - x^2} - \frac{2}{1 - x^2} 
 = g^{(2)}(x) - \frac{2}{1 - x^2}\text.
\end{align*}
We conclude that 
\[
b(O;n) 
= \begin{cases}
  1\text, & \text{if $n = 0$;} \\
  F_n\text, & \text{if $n \geq 1$,}
  \end{cases}
\qquad\text{and}\qquad
c(O;n) 
= \begin{cases}
  L_n\text, & \text{if $n \in O$;} \\
  L_n - 2\text, & \text{if $n \in 2\nat$} 
  \end{cases}
\]
(\emph{OEIS} \seqnum{A324969} and \seqnum{A001350}). 

The values of $b(O;n)$ and $c(O;n)$ have nice combinatorial explanations. For ordinary compositions, we employ the fact, recorded in \S\ref{SS:maxN}, that $b(\{1,2\};n-1) = F_n$. Here is an explicit bijection from $\{1,2\}$-compositions of $n-1$ to $O$-compositions of $n$. Begin with a composition of $n-1$ into $1$s and $2$s. Append a $1$ to the start of the sum; then add each part equal to $1$ together with any following $2$s, until another $1$ is reached, to produce an odd number. For example, if we append a $1$ to the beginning of the $\{1,2\}$-composition $8 = 2+1+2+2+1$, we get $1+2+1+2+2+1$, which becomes the $O$-composition $9 = 3 + 5 + 1$. This process can be reversed to produce a $\{1,2\}$-composition of $n-1$ from an $O$-composition of $n$: split each part in the $O$-composition into a $1$ followed by a suitable number of $2$s, then remove the initial $1$. Thus $b(O;n) = b(\{1,2\},n-1) = F_n$.

For circular compositions, we can do nearly the same thing, except we do not need to append an additional $1$; we simply use the orientation of the cycle graph $C_n$ to create a path with an odd number of vertices from each part of size $1$ and any subsequent parts of size $2$, until another part of size $1$ is reached. If $n$ is odd, then every circular $\{1,2\}$-composition of $n$ must have at least one part of size $1$. Thus $c(O;n) = c(\{1,2\};n) = L_n$ when $n$ is odd. However, if $n$ is even, it has two circular compositions all of whose parts have size $2$, resulting from the two possible positions of $v_1$ within the first part, and these do not correspond to any $O$-compositions. Thus $c(O;n) = c(\{1,2\};n) - 2 = L_n - 2$ when $n$ is even. (The fact that $c(O;0) = L_0 - 2 = 2 - 2 = 0$ is fortuitous.)

Although we eschewed the case of general $m$ and $q$ in \S\ref{SS:maxN} due to the high degree of $j^{[N]}(x)$, the rational function $j^O(x)$ has only the manageable degree $2$, and indeed the resulting expressions for $f^O_{m,q}(x)$ and $g^O_{m,q}(x)$ have a lovely relationship with the Fibonacci and Lucas polynomials, whose definitions and basic properties we recall next.

Given $z \in \C$, let $\psi_z$ and $\omega_z$ be the solutions to $x^2 - zx - 1 = 0$, so that $\psi_z + \omega_z = z$ and $\psi_z\omega_z = -1$. For $n \in \actnat$, the \emph{$n$th Fibonacci polynomial} $\mathcal{F}_n : \C\to\C$ is defined by 
\[
\mathcal{F}_n(z) 
= \frac{\psi_z^n-\omega_z^n}{\psi_z-\omega_z}\text, 
\]
and the \emph{$n$th Lucas polynomial} $\mathcal{L}_n : \C \to \C$ is defined by 
\[
\mathcal{L}_n(z) 
= \psi_z^n + \omega_z^n\text.
\]
From these definitions, it follows that 
\begin{align*}
z\mathcal{F}_n(z) 
&= (\psi_z+\omega_z)\cdot\frac{\psi_z^n-\omega_z^n}{\psi_z-\omega_z} 
 = \frac{\psi_z^{n+1}-\omega_z^{n+1}}{\psi_z-\omega_z} + \psi_z\omega_z\cdot\frac{\psi_z^{n-1}-\omega_z^{n-1}}{\psi_z-\omega_z} \\
&= \mathcal{F}_{n+1}(z) - \mathcal{F}_{n-1}(z)\text,
\end{align*}
and 
\begin{align*}
\mathcal{L}_n(z)
&= (\psi_z^n + \omega_z^n)\cdot\frac{\psi_z-\omega_z}{\psi_z-\omega_z} 
 = \frac{\psi_z^{n+1} - \omega_z^{n+1}}{\psi_z - \omega_z} + \frac{\psi_z^{n-1} - \omega_z^{n-1}}{\psi_z - \omega_z} \\
&= \mathcal{F}_{n+1}(z) + \mathcal{F}_{n-1}(z)\text.
\end{align*}
In particular, the $\mathcal{F}_n$ and $\mathcal{L}_n$ satisfy the same recurrence relation, namely  
\[
\mathcal{F}_{n+1}(z) = z\mathcal{F}_n(z) + \mathcal{F}_{n-1}(z)
\qquad\text{and}\qquad
\mathcal{L}_{n+1}(z) = z\mathcal{L}_n(z) + \mathcal{L}_{n-1}(z)
\]
for $n \geq 1$. The initial values are 
\begin{gather*}
\mathcal{F}_0(z) = 0\text, \qquad
\mathcal{F}_1(z) = 1\text, \qquad \mathcal{F}_2(z) = z\text, \\
\mathcal{L}_0(z) = 2\text, \qquad
\mathcal{L}_1(z) = z\text, \qquad \mathcal{L}_2(z) = z^2 + 2\text,
\end{gather*}
and so $\mathcal{F}_n(1) = F_n$ and $\mathcal{L}_n(1) = L_n$ for all $n \in \actnat$. Indeed, the definitions of $\mathcal{F}_n(1)$ and $\mathcal{L}_n(1)$ simply become Binet's formulas for $F_n$ and $L_n$, because $\{\psi_1,\omega_1\} = \{(1+\sqrt5)/2,(1-\sqrt5)/2\}$.

The coefficients of $\mathcal{F}_n$ and $\mathcal{L}_n$ can be given explicitly using binomial coefficients:
\[
\mathcal{F}_n(z) 
= \sum_{k=0}^{\lfloor (n-1)/2 \rfloor} 
  \binom{n-k-1}{k} z^{n-2k-1}
\qquad\text{and}\qquad
\mathcal{L}_n(z) 
= \sum_{k=0}^{\lfloor n/2 \rfloor} 
  \frac{n}{n-k}\binom{n-k}{k} z^{n-2k}\text,
\]
as may be shown by induction.

Using the factorization $1 - zx - x^2 = (1 - \psi_z x)(1 - \omega_z x)$, we can obtain the generating function $f(x,z)$ for the sequence $(\mathcal{F}_n(z))_{n=0}^\infty$:
\begin{align*}
f(x,z) 
&= \sum_{n=0}^\infty \mathcal{F}_n(z) x^n
= \sum_{n=0}^\infty \left(\frac{\psi_z^n-\omega_z^n}{\psi_z-\omega_z}\right) x^n = \frac{1}{\psi_z-\omega_z} \left(\sum_{n=0}^\infty \psi_z^n x^n - \sum_{n=0}^\infty \omega_z^n x^n\right) \\
&= \frac{1}{\psi_z-\omega_z} \left(\frac{1}{1 - \psi_z x} 
  - \frac{1}{1 - \omega_z x}\right) 
= \frac{x}{1 - zx - x^2}\text.
\end{align*}
From the relation $\mathcal{L}_n(z) = \mathcal{F}_{n+1}(z) + \mathcal{F}_{n-1}(z)$ it follows that generating function $g(x,z)$ for the sequence $(\mathcal{L}_n(z))_{n=0}^\infty$ is 
\[
g(x,z) 
= \sum_{n=0}^\infty \mathcal{L}_n(z) x^n
= 1 + \left(\frac1x + x\right)\!f(x,z)
= 1 + \frac{1+x^2}{1-zx-x^2} 
= \frac{2-zx}{1-zx-x^2}\text.
\]
The additional term of $1$ is needed to match the condition $\mathcal{L}_0(z) = 2$, and it agrees with the convention that $\mathcal{F}_{-1}(z) = 1$, which is consistent with the definition we are using. It will also be beneficial for us to have the generating function for $(\mathcal{L}_n(z) - 1 - (-1)^n)_{n=0}^\infty$, which is 
\[
\sum_{n=0}^\infty \big(\mathcal{L}_n(z) - 1 - (-1)^n\big)x^n 
= \frac{2-zx}{1-zx-x^2} - \frac{2}{1-x^2} 
= \frac{1+x^2}{1-x^2}\cdot\frac{zx}{1-zx-x^2}\text.
\]

Now we are ready to compute the values of $b(O,m,q;n)$ and $c(O,m,q;n)$.

\begin{theorem}\label{T:odd}
Given $m \ge 1$, set $\zeta = e^{2\pi i/m}$. For all $0 \leq q < m$ and $n \geq 1$, we have 
\begin{align*}
b(O,m,q;n) 
&= \frac{1}{m} \sum_{k=0}^{m-1} 
   \zeta^{k(1-q)}\mathcal{F}_n(\zeta^k) 
 = \sum_{k\in S(m,n,q)}
   \binom{n-k-1}{k}
\hspace{.6in}\text{and}\\
c(O,m,q;n) 
&= - \big(1+(-1)^n\big)\cdot0^q
  + \frac{1}{m} \sum_{k=0}^{m-1} 
     \zeta^{-kq}\mathcal{L}_n(\zeta^k)
 = \sum_{k\in S(m,n,q)}
   \frac{n}{n-k}\binom{n-k}{k}
\end{align*}
where $S(m,n,q)$ is the set of solutions to $2k \equiv n - q$ {\rm (mod $m$)} such that $0 \leq k \leq \lfloor (n-1)/2 \rfloor$.
\end{theorem}

\begin{proof}
We will repeatedly use, without further notice, the fact that $\sum_{k=0}^{m-1} \zeta^{k\alpha} = 0$ unless $\alpha$ is a multiple of $m$, in which case the sum equals $m$.

Using Lemma~\ref{L:partfrac} with $u = x/(1-x^2)$, $\alpha = q$, and $\beta = m$, we have 
\begin{align*}
f^{O}_{m,q}(x) 
&= \frac{x^q/(1-x^2)^q}{1-x^m/(1-x^2)^m} 
 = \frac1m
   \sum_{k=0}^{m-1} \frac{\zeta^{-kq}}{1-\zeta^k x/(1-x^2)}  
 = \frac1m
   \sum_{k=0}^{m-1} \frac{\zeta^{-kq}(1-x^2)}{1-\zeta^k x - x^2} \\
&= \frac1m
   \sum_{k=0}^{m-1} \frac{\zeta^{-kq}(1-\zeta^k x-x^2)+\zeta^{k(1-q)}x}{1-\zeta^k x - x^2} 
 = \frac1m
   \sum_{k=0}^{m-1} \left(\zeta^{-kq} + \frac{\zeta^{k(1-q)}x}{1-\zeta^k x - x^2}\right) \\
&= 1\cdot0^q 
   + \frac1m
     \sum_{k=0}^{m-1} \zeta^{k(1-q)} 
     \sum_{n=0}^\infty 
     \big(\mathcal{F}_n(\zeta^k)\big) x^n \\
&= 1\cdot0^q 
   + \frac1m
     \sum_{n=0}^\infty 
     \sum_{k=0}^{m-1} \zeta^{k(1-q)} 
     \sum_{\ell=0}^{\lfloor(n-1)/2\rfloor} 
     \binom{n-\ell-1}{\ell} \zeta^{k(n-2\ell-1)} x^n \\
&= 1\cdot0^q 
   + \frac1m
     \sum_{n=0}^\infty 
     \sum_{\ell=0}^{\lfloor(n-1)/2\rfloor} 
     \binom{n-\ell-1}{\ell} 
     \sum_{k=0}^{m-1} 
     \zeta^{k(n-2\ell-q)} x^n \text.
\end{align*}
All terms in the final sum cancel except those for which $n-2\ell-q \equiv 0$ (mod $m$), which is precisely the condition that $\ell \in S(m,n,q)$.

For circular compositions, we observe that 
\begin{align*}
g^{O}_{m,q}(x) 
&= \frac{x^q(1+x^2)/(1-x^2)^{q+1}}{1-x^m/(1-x^2)^m} 
= \frac{1+x^2}{1-x^2}\cdot \big(f^O_{m,q}(x) - 1\cdot0^q\big) \\
&= \frac1m
   \sum_{k=0}^{m-1} \frac{1+x^2}{1-x^2} \cdot \frac{\zeta^{k(1-q)}x}{1-\zeta^k x - x^2} 
 = \frac1m
   \sum_{k=0}^{m-1} \zeta^{-kq} \cdot \frac{1+x^2}{1-x^2} \cdot \frac{\zeta^k x}{1-\zeta^k x - x^2} \\
&= \frac1m
   \sum_{k=0}^{m-1} \zeta^{-kq} \sum_{n=0}^\infty \big(\mathcal{L}_n(\zeta^k) - 1 - (-1)^n\big)x^n \\
&= - \big(1 + (-1)^n\big)x^n\cdot0^q
   + \frac1m
     \sum_{k=0}^{m-1} \zeta^{-kq}
     \sum_{n=0}^\infty 
     \big(\mathcal{L}_n(\zeta^k)\big)x^n \\
&= - \big(1 + (-1)^n\big)x^n\cdot0^q
   + \frac1m
     \sum_{n=0}^\infty 
     \sum_{k=0}^{m-1} \zeta^{-kq}
     \sum_{\ell=0}^{\lfloor n/2 \rfloor} 
  \frac{n}{n-\ell}\binom{n-\ell}{\ell} \zeta^{k(n-2\ell)} x^n \\
&= - \big(1 + (-1)^n\big)x^n\cdot0^q
   + \frac1m
     \sum_{n=0}^\infty 
     \sum_{\ell=0}^{\lfloor n/2 \rfloor} 
     \frac{n}{n-\ell}\binom{n-\ell}{\ell} 
     \sum_{k=0}^{m-1} 
     \zeta^{k(n-2\ell-q)} x^n\text.
\end{align*}
Again, all terms cancel except those for which $n-2\ell-q \equiv 0$ (mod $m$).
\end{proof}

Having reached the result of Theorem~\ref{T:odd} via generating functions, we can also give a combinatorial explanation of the formulas in its statement that employ binomial coefficients, using the previously-described connection between $O$-compositions and $\{1,2\}$-compositions. 

Suppose $n = 2p + q$, with $p,q \geq 0$. The number of ways to arrange $p$ parts equal to $2$ and $q$ parts equal to $1$ into a $\{1,2\}$-composition of $n$ is $\binom{n-p}{p}$. When a $\{1,2\}$-composition of $n$ that starts with $1$ is converted into an $O$-composition of $n$ as previously described (group each part equal to $1$ with all succeeding parts equal to $2$), the number of parts in the resulting $O$-composition is equal to the number of $1$s in the initial composition of $n$. If this number of parts is required to be congruent to $q$ modulo $m$, then $p$ must satisfy $n - 2p \equiv q$ (mod $m$). No more than $\lfloor(n-1)/2\rfloor$ parts of the $\{1,2\}$-composition of $n$ can equal $2$, because the first part must be $1$, so in fact $p$ must belong to the set $S(m,n,q)$ appearing in the statement of Theorem~\ref{T:odd}. Thus, we have reaffirmed that 
\[
b(O,m,q;n) = \sum_{p\in S(m,n,q)} \binom{n-1-p}{p}\text.
\]

To determine a circular $\{1,2\}$-composition of $n$, we can first choose an ordinary composition, then a position in $C_n$ at which to begin this composition. Consider circular compositions with $q$ parts equal to $1$ and $p$ parts equal to $2$. Then there are $\binom{n-p}{p}$ ways to arrange these parts into an ordinary composition, and $n$ possible initial positions. However, following this process produces each circular composition $n-p$ times, by choosing the first vertex of each part as the initial position. So the total number of such circular compositions is $\frac{n}{n-p}\binom{n-p}{p}$. Because we only want to consider circular $\{1,2\}$-compositions that correspond to circular $O$-compositions, we restrict to $p \leq \lfloor(n-1)/2\rfloor$, and again, if $q$ is treated as a residue class modulo $m$, then the values of $p$ are restricted to $S(m,n,q)$. Thus, we have reaffirmed that 
\[
c(O,m,q;n) = \sum_{p\in S(m,n,q)} \frac{n}{n-p}\binom{n-p}{p}\text.
\]

Note that $S(m,n,q)$ is empty when $m$ is even and $n$ and $q$ have opposite parity, and therefore $b(O,m,q;n) = c(O,m,q;n) = 0$ in this circumstance (and also $d(O,m,q;n) = 0$). This result may be seen as an elementary consequence of the fact that a sum of an even number of odd parts must be even, and a sum of an odd number of odd parts must be odd. 
It follows immediately that, for $n \geq 1$,
\begin{align*}
b(O,2,0;2n) 
&= b(O;2n) = F_{2n}\text, 
&&b(O,2,1;2n-1) 
 = b(O;2n-1) = F_{2n-1}\text, \\ 
c(O,2,0;2n) 
&= c(O;2n) = L_{2n} - 2\text, 
&&c(O,2,1;2n-1) 
 = c(O;2n-1) = L_{2n-1}
\end{align*}
(\emph{OIES} \seqnum{A088305}, \seqnum{A001519}, \seqnum{A004146}, \seqnum{A002878}), and consequently, by \eqref{Eq:cycliccoeff}, 
\begin{align*}
d(O,2,0;2n) &= d(O;2n) 
= \frac{1}{2n}\sum_{k\mid2n}\phi(k)\big(L_{2n/k}-1-(-1)^{2n/k}\big)\qquad\text{and} \\
d(O,2,1;2n-1) &= d(O;2n-1)
= \frac{1}{2n-1}\sum_{k\mid(2n-1)}\phi(k)L_{(2n-1)/k}
\end{align*}
(\emph{OEIS} \seqnum{A365857} and \seqnum{A365858}), keeping in mind that every divisor of $2n-1$ must be odd. 

That is, restricting $O$-compositions to either an even number of parts or an odd number of parts results in a \emph{bisection} of each counting sequence, alternating with terms equal to $0$.


\section{Compositions with parts in a multiset}\label{S:multiset}

The entire discussion in sections \ref{S:bg} and \ref{S:main} applies \emph{mutatis mutandis} to compositions with parts in a multiset, in which elements are allowed to appear with multiplicity greater than one. These are also known as compositions with color. Subscripts are used to distinguish the copies of an element; for instance, a multiset that contains $2$ appearing with multiplicity three would have three elements of size $2$, labeled $2_1$, $2_2$, $2_3$, and collectively represented as $2_{[3]}$. More generally, $n_{[\mu]}$ represents a collection of $\mu$ copies of $n$, and a multiset $M$ with underlying set $A$ and multiplicity function $\mu$ will be represented by 
\[
M = \{a_{[\mu(a)]} : a \in A\}
= A_{[\mu]}\text.
\] 
Each of the possible subscripts for an element of $M$ is called a \emph{color}. An $\nat_{[\mu]}$-composition will also be called a \emph{$\mu$-color composition}.

If we require the multiplicity of each element to be finite, then a multiset $M$ of positive integers is encoded by its indicator sequence $i(M;n) : \nat \to \actnat$, where $i(M;n) = \mu(n)$. This indicator sequence has the generating function 
\[
j^M(x) = \sum_{n=1}^\infty i(M;n)x^n
\]
in the same way as before, and the generating functions $f^M_{m,q}(x)$, $g^M_{m,q}(x)$, and $h^M_{m,q}(x)$ for the sequences $b(M,m,q;n)$, $c(M,m,q;n)$, and $d(M,m,q;n)$ can be constructed just as in Theorem~\ref{T:main}, with $M$ in place of $A$.

\subsection{$\kappa$-color compositions with constant $\kappa$}

Fix a natural number $\kappa \geq 2$. The multiset 
\[
\nat_{[\kappa]} 
= \{n_{[\kappa]}:n\in\nat\}
= \{1_1,\dots,1_\kappa,2_1,\dots,2_\kappa,3_1,\dots,3_\kappa,4_1,\dots,4_\kappa,\dots\} 
\]
contains each natural number with multiplicity $\kappa$, and a $\nat_{[\kappa]}$-composition is also called a \emph{$\kappa$-color composition}. The function $j^{\nat_{[\kappa]}}(x)$ is 
\[
j^{\nat_{[\kappa]}}(x) 
= \kappa j^{\nat}(x) 
= \frac{\kappa x}{1-x}\text.
\]
Thus 
\[
f^{\nat_{[\kappa]}}(x) 
= \frac{1}{1-\kappa x/(1-x)} 
= \frac{1-x}{1-(1+\kappa)x} 
= 1 + \frac{\kappa x}{1 - (1+\kappa)x} 
= 1 + \sum_{n=1}^\infty \kappa(1+\kappa)^{n-1}x^n\text,
\]
and so the number of $\kappa$-color compositions of $n$ is given by 
\[
b(\nat_{[\kappa]};n) 
= \begin{cases}
  1\text, & \text{if $n = 0$;} \\
  \kappa(1+\kappa)^{n-1}\text, & \text{if $n \geq 1$.}
  \end{cases}
\]
The case $n \geq 1$ corresponds to the equality 
\[
\sum_{k=1}^{n} \binom{n-1}{k-1}\kappa^k = \kappa(1+\kappa)^{n-1}\text,
\]
where the $k$th term in the sum counts the number of $\kappa$-color compositions having $k$ parts.

\begin{remark}
Andrews \cite{Andrews} calls $\kappa$-color compositions ``multicompositions'' or ``$\kappa$-compositions''; however, he adds the restriction that the final part of every composition must be the initial color (i.e., the subscript of the final part must be $1$), which removes a factor of $\kappa$ from the formula for $b(\nat_{[\kappa]};n)$ when $n \geq 1$.
\end{remark}

For circular compositions, we have 
\[
g^{\nat_{[\kappa]}}(x) 
= \frac{\kappa x/(1-x)^2}{1-\kappa x/(1-x)} 
= \frac{\kappa x/(1-x)}{1-(1+\kappa)x} 
= \frac{1}{1-(1+\kappa)x}-\frac{1}{1-x} 
= \sum_{n=0}^\infty \big((1+\kappa)^n-1\big) x^n\text,
\]
and so the number of circular $\kappa$-color compositions of $n$ is given by 
\[
c(\nat_{[\kappa]};n) = (1+\kappa)^n - 1\text.
\]
The case $n \geq 1$ corresponds to the equality 
\[
\sum_{k=1}^{n} \binom{n}{k}\kappa^k = (1+\kappa)^n-1\text,
\]
where the $k$th term in the sum counts the number of circular $\kappa$-color compositions having $k$ parts.

Using methods similar to those of \S\ref{SS:allsize}, one obtains \begin{align*}
b(\nat_{[\kappa]},m,q;n) 
&= \frac{\kappa(1+\kappa)^{n-1}}{m} 
  + \frac{\kappa}{m} \sum_{k=1}^{m-1} 
     e^{i\,2\pi k(1-q)/m}\left(1+\kappa e^{i\,2\pi k/m}\right)^{n-1}\text, \\
c(\nat_{[\kappa]},m,q;n) 
&= \begin{cases}
  \displaystyle
  -1
  + \frac{(1+\kappa)^n}{m} 
  + \frac{1}{m} \sum_{k=1}^{m-1}
     \left(1+\kappa e^{i\,2\pi k/m}\right)^n\text, 
     & \text{if $q = 0$;} \\
  \displaystyle
  \frac{(1+\kappa)^n}{m} 
  + \frac{1}{m} \sum_{k=1}^{m-1} 
     e^{-i\,2\pi kq/m}\left(1+\kappa e^{i\,2\pi k/m}\right)^n\text,
     & \text{if $q \ne 0$.}
\end{cases}
\end{align*}
For $m = 2$, $q \in \{0,1\}$, we get 
\begin{align*}
b(\nat_{[\kappa]},2,q;n) 
&= \frac{\kappa}{2}\big((1+\kappa)^{n-1} - (-1)^q (1-\kappa)^{n-1}\big)\text, \\ 
c(\nat_{[\kappa]},2,q;n) 
&= \frac12\big((1+\kappa)^n + (-1)^q (1-\kappa)^n\big) - 1\cdot0^q\text.
\end{align*}

\begin{remark}
Each quantity $e^{i\,2\pi k(1-q)/m}(1+\kappa e^{i\,2\pi k/m})^{n-1}$ and $e^{-i\,2\pi kq/m}(1+\kappa e^{i\,2\pi k/m})^n$ in the expressions for $b(\nat_{[\kappa]},m,q;n)$ and $c(\nat_{[\kappa]},m,q;n)$ appears in a sum along with its complex conjugate. The expressions can therefore be written exclusively in terms of trigonometric and inverse trigonometric functions, to eliminate the use of complex numbers, but for general $\kappa$ the resulting formulas become somewhat unwieldy.
\end{remark}

\subsection{Linear and circular $\nu$-color compositions}\label{SS:ncolor}

Let $\nu : \nat \to \nat$ be the identity function $\nu(n) = n$. The multiset 
\[
\nat_{[\nu]} 
= \{n_{[n]}:n\in\nat\}
= \{1_1,2_1,2_2,3_1,3_2,3_3,4_1,4_2,4_3,4_4,\dots\} 
\]
has indicator sequence $i(\nat_{[\nu]};n) = \nu(n) = n$. Linear compositions with parts in $\nat_{[\nu]}$ are precisely the ``$n$-color compositions'' defined by Agarwal \cite{Agarwal}. We will use the term \emph{$\nu$-color composition} instead, as it matches our previously established vocabulary, and moreover our habit has been to let $n$ represent the total of a composition. The function $j^{\nat_{[\nu]}}(x)$ becomes 
\[
j^{\nat_{[\nu]}}(x) = \sum_{n=1}^\infty nx^n = \frac{x}{(1-x)^2}\text.
\]
This is the same as the function $x\frac{d}{dx}j^{\nat}(x)$, which we saw in \S\ref{SS:allsize}. Consequently, 
\[
x\frac{d}{dx} j^{\nat_{[\nu]}}(x) 
= \sum_{n=1}^\infty n^2 x^n 
= \frac{x(1+x)}{(1-x)^3}\text.
\]
Thus, we have 
\begin{align*}
f^{\nat_{[\nu]}}(x) 
&= \frac{1}{1 - x/(1-x)^2}
 = \frac{1 - 2x + x^2}{1 - 3x + x^2}
 = 1 + \frac{x}{1 - 3x + x^2} 
\qquad\text{and}\\
g^{\nat_{[\nu]}}(x) 
&= \frac{x(1+x)/(1-x)^3}{1 - x/(1-x)^2} 
 = \frac{x+x^2}{(1-x)(1 - 3x + x^2)} 
 = \frac{2-3x}{1-3x+x^2} - \frac{2}{1-x}\text.
\end{align*}

\begin{remark}
Agarwal \cite{Agarwal} does not treat the empty sum as a composition, and so he omits the constant term $1$ from the generating function that corresponds to our $f^{\nat_{[\nu]}}(x)$.
\end{remark}

These $\nu$-color compositions are closely connected to compositions whose parts are odd. Indeed, if we set $O = \nat\setminus2\nat$ as in \S\ref{SS:odd}, we have the following result.

\begin{theorem}\label{T:multiodd}
Given $m \geq 1$, $0 \leq q < m$, and $n\in\nat$, we have  
\begin{align*}
b(\nat_{[\nu]},m,q;n) 
&= b(O,2m,2q;2n) 
 = \sum_{k\in T(m,n,q)}\binom{2n-k-1}{k}
\hspace{.4in}\text{and}\\
c(\nat_{[\nu]},m,q;n) 
&= c(O,2m,2q;2n)
 = \sum_{k\in T(m,n,q)}\frac{2n}{2n-k}\binom{2n-k}{k}\text,
\end{align*}
where $T(m,n,q)$ is the set of solutions to $k \equiv n - q$ {\rm (mod $m$)} such that $0 \leq k \leq n-1$.
\end{theorem}

In particular, Theorem~\ref{T:multiodd} implies that 
\[
b(\nat_{[\nu]};n) 
= \begin{cases}
  1\text, & \text{if $n = 0$;} \\
  F_{2n}\text, & \text{if $n \geq 1$,}
  \end{cases}
\qquad\text{and}\qquad
c(\nat_{[\nu]};n) 
= L_{2n} - 2
\]
(\emph{OEIS} \seqnum{A088305} and \seqnum{A004146}). 

The key observation for the proof of Theorem~\ref{T:multiodd} is that 
\begin{equation}\label{Eq:multioddj}
j^{\nat_{[\nu]}}(x^2) = \big(j^O(x)\big)^2
\end{equation}
because both sides equal $x^2/(1-x^2)^2$. Following a first, analytic proof of Theorem~\ref{T:multiodd}, we will see a combinatorial interpretation of equation \eqref{Eq:multioddj} and an accompanying bijective proof of Theorem~\ref{T:multiodd}. The next lemma applies to both proofs.

\begin{lemma}
Let $S(m,n,q)$ and $T(m,n,q)$ be defined as in the statements of Theorem~\ref{T:odd} and Theorem~\ref{T:multiodd}, respectively. Then $S(2m,2n,2q) = T(m,n,q)$.
\end{lemma}
\begin{proof}
We have the following chain of equivalences:
\begin{align*}
2k \equiv 2n-2q \pmod{2m} 
&\iff (\exists\ell)(2k = 2n - 2q + 2m\ell) \\
&\iff (\exists\ell)(k = n - q +  m\ell) \\
&\iff k \equiv n-q \pmod{m}\text.
\end{align*}
In addition, $0 \leq k \leq \lfloor (2n-1)/2 \rfloor$ is equivalent to $0 \leq k \leq n-1$. 
\end{proof}

\begin{proof}[Analytic proof of Theorem \ref{T:multiodd}]
For ordinary compositions, applying equation \eqref{Eq:multioddj} to the formula from  Theorem~\ref{T:main} yields directly 
\[
f^{\nat_{[\nu]}}_{m,q}(x^2) 
= \frac{(j^{\nat_{[\nu]}}(x^2))^q}{1 - (j^{\nat_{[\nu]}}(x^2))^m}
= \frac{(j^O(x))^{2q}}{1 - (j^O(x))^{2m}}
= f^O_{2m,2q}(x)\text.
\]

For circular compositions, we need an additional relation. Differentiating both sides of \eqref{Eq:multioddj} and dividing by $2$ yields 
\begin{equation}\label{Eq:multioddjdiff}
x\frac{d}{du}j^{\nat_{[\nu]}}(u)\bigg\vert_{u=x^2} 
= j^O(x)\frac{d}{dx}j^O(x)\text.
\end{equation}
Now \eqref{Eq:multioddj} and \eqref{Eq:multioddjdiff} can be applied to the formula from Theorem~\ref{T:main} to obtain 
\begin{align*}
g^{\nat_{[\nu]}}_{m,q}(x^2) 
&= \frac{x^2(j^{\nat_{[\nu]}}(x^2))^{q-1}}{1-(j^{\nat_{[\nu]}}(x^2))^m}\frac{d}{du}j^{\nat_{[\nu]}}(u)\bigg\vert_{u=x^2} \\
&= \frac{x(j^O(x))^{2q-2}}{1-(j^O(x))^{2m}}j^O(x)\frac{d}{dx}j^O(x) \\
&= \frac{x(j^O(x))^{2q-1}}{1-(j^O(x))^{2m}}\frac{d}{dx}j^O(x) \\
&= g^O_{2m,2q}(x)
\end{align*}
when $0 < q < m$, and similarly for $q = 0$.
\end{proof}

We observed at the start of the section that $j^{\nat_{[\nu]}}(x) = x\frac{d}{dx}j^{\nat}(x)$. This equality is not merely convenient; it is suggestive. The operator $x\frac{d}{dx}$ on functions corresponds to a ``pointing'' or ``marking'' operation on elements of a set (see, e.g., \cite[\S I.6.2]{AC}). In the case of circular $\nat$-compositions, the location of the initial vertex $v_1$ is marked within the first part. Similarly, a $\nu$-color composition can be interpreted as a $\nat$-composition in which every part has a marking. Therefore, we can represent a $\nu$-color composition---whether linear, circular, or cyclic---graphically as the associated uncolored composition, with one vertex in each part marked to indicate its color. This identification between colors and marked vertices is possible because all three kinds of composition we are considering have a notion of ``orientation,'' which allows us to enforce a consistent order on the vertices within each part. 

\begin{remark}
We now also have a natural interpretation for the $n^2$ coefficients that appear in the power series expression for $x\frac{d}{dx} j^{\nat_{[\nu]}}(x)$: the first part in a circular $\nu$-color composition is ``doubly marked'': once by color, and once by the location of the vertex $v_1$.
\end{remark}

The graphical representation of $\nu$-color compositions is closely related to their connection with $O$-compositions. First, notice that equation \eqref{Eq:multioddj} can be written out in power series as 
\[
\sum_{n=1}^\infty nx^{2n} = \left(\sum_{p=1}^{\infty}x^{2p-1}\right)^2\text.
\]
Expressed combinatorially, this equation says that there are $n$ ways to write $2n$ as a composition of two positive odd numbers. This fact may also be seen directly using the bijections $\chi : \nat_{[\nu]} \to O \times O$ and $\chi^{-1} : O \times O \to \nat_{[\nu]}$ defined by 
\[
\chi : n_k \mapsto (2k-1,2(n-k)+1)
\qquad\text{and}\qquad
\chi^{-1} : (2k-1,2\ell-1) \mapsto (k+\ell-1)_k\text.
\]
These are additive homomorphisms (when $O\times O$ is considered as a subset of $\nat\times\nat$), and so they may be used to convert compositions between the two forms. For example, the elements $4_1$, $4_2$, $4_3$, and $4_4$ correspond to the sums 
\[
1+7\text, \qquad
3+5\text, \qquad
5+3\text, \qquad
7+1\text,
\]
respectively, and the $\nu$-color composition $2_2 + 3_1 + 4_3$ of $9$ corresponds to the $O$-composition $3 + 1 + 1 + 5 + 5 + 3$ of $18$. Graphically, this correspondence appears as follows. Start with a $\nu$-color composition, replace each vertex with a pair of vertices joined by an edge, and remove the edge between each pair of vertices that came from a marked vertex. (See Figure~\ref{fig:color_to_odd}.) 

\begin{figure}
\centering
\includegraphics{color_to_odd.pdf}
\caption{A $\nu$-color composition of $9$ and the corresponding $O$-composition of $18$. Marked vertices in the $\nu$-color composition are shown as empty circles.}
\label{fig:color_to_odd}
\end{figure}

\begin{proof}[Bijective proof of Theorem \ref{T:multiodd}]

For ordinary compositions, the function $\chi : \nat_{[\nu]} \to O\times O$ provides a direct bijection between $\nat_{[\nu]}$-compositions and $O$-compositions with an even number of parts: 
\[
\sum_{\ell=1}^p (a_\ell)_{k_\ell} 
\qquad\longleftrightarrow\qquad
\sum_{\ell=1}^p \big((2k_\ell - 1) + (2(a_\ell - k_\ell) + 1)\big)\text.
\]

For circular compositions, the situation is a little more subtle, because we must take into account where the vertex $v_1$ is located within the first part. Here is one way to create a canonical correspondence. Identify $C_{2n}$ with the \emph{incidence graph} of $C_n$. That is, label the vertices of $C_{2n}$ as $v_1$, $e_1$, \dots, $v_n$, $e_n$, with an edge between $v_i$ and $e_j$ if and only if $v_i$ and $e_j$ are incident in $C_n$. Given a circular $O$-composition $\sigma$ of $2n$, i.e., a partition of $C_{2n}$ into connected subgraphs each having an odd number of vertices, create a circular $\nu$-color composition in the following way: consider the final vertex in each part of $\sigma$; if it is labeled as an edge of $C_n$, then remove it from $C_n$, and if it is labeled as a vertex of $C_n$, then mark it (cf.\ Figure~\ref{fig:color_to_odd}, which illustrates the same process for linear compositions). Because the parts of $\sigma$ have odd sizes, their final vertices will alternate between edges and vertices of $C_n$. This is a bijection.
\end{proof}

\begin{remark}
Agarwal \cite{Agarwal,Agarwal2} first stated the equalities $b(\nat_{[\nu]};n) = F_{2n} = b(O;2n)$ and proved them using generating functions. Hopkins \cite{Hopk} gave a bijective proof of the same equalities using ``spotted tilings'' that are similar to the graphical representations with marked vertices described here. Gibson et al.\ \cite{Gibson} provided an explanation of the equality $c(\nat_{[\nu]};n) = L_{2n} - 2$ via spanning trees of wheel graphs instead of using circular $O$-compositions.
\end{remark}

\subsection{Duality in cyclic $\nu$-color compositions}\label{SS:dual}

When we pass from circular compositions to cyclic compositions, we lose the notion of a ``first part.'' As a consequence, the correspondence between cyclic $\nu$-color compositions of $n$ and cyclic $O$-compositions of $2n$ is no longer one-to-one, as it was in the case of ordinary and circular compositions. The group $\Z/2n\Z$ that acts on circular $O$-compositions of $2n$ to produce cyclic $O$-compositions is twice as large as the group $\Z/n\Z$ that acts on circular $\nat_{[\nu]}$-compositions of $n$ to produce cyclic $\nat_{[\nu]}$-compositions, and so one might guess there would be twice as many of the latter as the former. However, that is not the whole story. A comparison between 
\[
d(\nat_{[\nu]};n) 
= -2 + \frac1n\sum_{k\mid n}\phi(k)L_{2n/k} 
\]
(\emph{OEIS} \seqnum{A032198}) and twice the value of $d(O;2n)$ (see the end of \S\ref{SS:odd}) reveals a discrepancy. The rest of the section will be devoted to studying this discrepancy.

\begin{remark}
Cyclic $\nu$-color compositions were studied and enumerated by Gibson et al.\ \cite{Gibson}. 
\end{remark}

Using \eqref{Eq:hA} and \eqref{Eq:multioddj} we find 
\[
h^{\nat_{[\nu]}}(x^2) 
= \sum_{k=1}^\infty\frac{\phi(k)}{k} \log\frac{1}{1-j^{\nat_{[\nu]}}(x^2)} 
= \sum_{k=1}^\infty\frac{\phi(k)}{k} \log\frac{1}{1-(j^{O}(x))^2}\text.
\]
Now recall from \S\ref{SS:odd} that the even part of $h^O(x)$ is simply $h^O_{2,0}(x)$, because an odd integer cannot have any $O$-compositions with an even number of parts. By Corollary~\ref{Cor:odd_and_even} 
\[
h^O_{2,0}(x) 
= \frac12 \sum_{k=1}^\infty 
  \frac{\phi(k)}{k}\log\frac{1}{1-(j^O(x^k))^2}
  + \frac12 \sum_{r=1}^\infty 
    \frac{\phi(2r)}{2r} 
    \log\frac{1+j^O(x^{2r})}{1-j^O(x^{2r})}\text,
\]
which means that 
\[
2h^O_{2,0}(x) - h^{\nat_{[\nu]}}(x^2) 
= \sum_{k=1}^\infty 
    \frac{\phi(2k)}{2k} 
    \log\frac{1+j^O(x^{2k})}{1-j^O(x^{2k})} 
= \sum_{k=1}^\infty 
    \frac{\phi(2k)}{2k} 
    \log\frac{1+x^{2k}-x^{4k}}{1-x^{2k}-x^{4k}}\text.
\]
Set 
\begin{equation}\label{Eq:hstar}
h^*(x) = \sum_{k=1}^\infty 
    \frac{\phi(2k)}{2k} 
    \log\frac{1+x^{k}-x^{2k}}{1-x^{k}-x^{2k}}
\end{equation}
so that $2h^O_{2,0}(x) = h^{\nat_{[\nu]}}(x^2) + h^*(x^2)$, and define the sequence $(d^*(n))_{n=1}^\infty$ by 
\[
h^*(x) = \sum_{n=1}^\infty d^*(n)x^n\text.
\]
By construction, $d^*(n)$ measures the difference between the number of cyclic $\nu$-color compositions of $n$ and twice the number of cyclic $O$-compositions of $2n$. In symbols, $d^*(n) = 2d(O;2n) - d(\nat_{[\nu]};n)$.

The next theorem provides a direct combinatorial interpretation of $d^*(n)$. Following its proof, we will define a notion of ``duality'' for cyclic $\nu$-color compositions---i.e., a canonical involution on the set of cyclic $\nu$-color compositions---and observe how the sequence $d^*(n)$ arises naturally in this context. It will turn out that cyclic $O$-compositions with an odd number of parts also play a crucial role. 

Given $n \in \nat$, let  
\[
n_O = \max\{a\in O:a\mid n\}
\]
be the greatest odd factor of $n$. Then we have the following result.

\begin{theorem}\label{T:greatestodd}
For all $n \in \nat$, we have $d^*(n) = d(O;n_O) = \displaystyle\frac{1}{n_O}\sum_{k\mid n_O} \phi(k) L_{n_O/k}$.
\end{theorem}

In words, Theorem~\ref{T:greatestodd} says that $d^*(n)$ equals the number of cyclic $O$-compositions of $n_O$. Thus, the values of $d^*(n)$ for $1 \leq n \leq 20$ are 
\[
1\text,\; 
1\text,\; 
2\text,\; 
1\text,\; 
3\text,\; 
2\text,\; 
5\text,\; 
1\text,\; 
10\text,\; 
3\text,\; 
19\text,\; 
2\text,\; 
41\text,\; 
5\text,\; 
94\text,\; 
1\text,\; 
211\text,\; 
10\text,\; 
493\text,\; 
3
\]
(\emph{OEIS} \seqnum{A365859}).
Note that Theorem~\ref{T:greatestodd} implies $d^*(2n) = d^*(n)$ for all $n \in \nat$, a fact which will become evident in the course of the proof, and is also visible in the first few terms above.

The proof of Theorem~\ref{T:greatestodd} will use the following property of the totient function $\phi$:
\[
\phi(2k) = 
\begin{cases}
\phi(k)\text, & \text{if $k\in O$;} \\
2\phi(k)\text, & \text{if $k\in 2\nat$.}
\end{cases}
\]

\begin{proof}
First we separate the terms in the definition of $h^*(x)$ according to the parity of their indices. The even-indexed terms from \eqref{Eq:hstar} produce 
\[
\sum_{r=1}^\infty \frac{\phi\big(2(2r)\big)}{2(2r)}\log\frac{1+x^{2r}-x^{2(2r)}}{1-x^{2r}-x^{2(2r)}} \\
= \sum_{r=1}^\infty \frac{\phi(2r)}{2r}\log\frac{1+x^{2r}-x^{2(2r)}}{1-x^{2r}-x^{2(2r)}}
 = h^*(x^2)\text,
\]
while the odd-indexed terms yield 
\[
\sum_{k\in O} \frac{\phi(2k)}{2k} \log\frac{1+x^k-x^{2k}}{1-x^k-x^{2k}} 
= \frac12 \sum_{k\in O} \frac{\phi(k)}{k} \log\frac{1+x^k-x^{2k}}{1-x^k-x^{2k}} 
= h^O_{2,1}(x)\text, 
\]
where the final equality follows from Corollary~\ref{Cor:odd_and_even}. Thus we we can write 
\[
h^*(x) 
= h^O_{2,1}(x) + h^*(x^2) 
= h^O_{2,1}(x) + h^O_{2,1}(x^2) + h^*(x^4) 
= \cdots 
= \sum_{p=0}^\infty h^O_{2,1}\big(x^{2^p}\big)\text,
\]
which, together with the equation $d(O;n_O) = d(O,2,1;n_O)$ from \S\ref{SS:odd}, implies the theorem, because each natural number is uniquely expressible as a power of $2$ times an odd number, and $h^O_{2,1}(x)$ contains only odd powers (as shown in \S\ref{SS:odd}).
\end{proof}

\begin{figure}
    \centering
    \begin{minipage}{2in}
    \centering
    \includegraphics{cyclic_ncolor_comp10-1.pdf}
    \end{minipage}\hspace{.5in}
    \begin{minipage}{2in}
    \centering
    \includegraphics{cyclic_ncolor_comp10-2.pdf}
    \end{minipage}
    \caption{A pair of dual cyclic $\nu$-color compositions of $10$. The orientations of the images have been arranged to illustrate the correspondence between marked vertices in one composition and removed edges in the other. {\sc Left:} $1_1 + 3_2 + 4_2 + 2_1$. {\sc Right:} $2_2 + 2_1 + 3_2 + 3_3$.}
    \label{fig:dualexs}
\end{figure}

Now for the promised notion of duality. 

The cycle graph $C_n$ is ``self-dual'' in the sense that if the roles of edges and vertices are exchanged, the resulting object is isomorphic to $C_n$. From this perspective, the roles of removed edges and marked vertices in $\nu$-color compositions are also dual to each other. In particular, each marked vertex must lie between two removed edges, and each removed edge must lie between two marked vertices. This process is also compatible with the action of the rotation group $\Z/n\Z$. So when we pass to the dual of $C_n$, converting marked vertices to removed edges and vice versa, each cyclic $\nu$-color composition becomes a new one, the \emph{dual} of the first. This process is clearly an involution. Figure~\ref{fig:dualexs} shows an example of a dual pair for $n=10$. Figure \ref{fig:colorcomp5} shows all classes of dual compositions for the case $n = 5$.

\begin{figure}
\centering
\fbox{\includegraphics{color5-11111.pdf}}
\fbox{\includegraphics{color5-1112a.pdf}
\includegraphics{color5-1112b.pdf}}
\fbox{\includegraphics{color5-113a.pdf}
\includegraphics{color5-113b.pdf}}
\fbox{\includegraphics{color5-113c.pdf}
\includegraphics{color5-122a.pdf}}\smallskip

\fbox{\includegraphics{color5-122b.pdf}
\includegraphics{color5-122c.pdf}}
\fbox{\includegraphics{color5-122d.pdf}}
\fbox{\includegraphics{color5-14a.pdf}
\includegraphics{color5-14b.pdf}}
\fbox{\includegraphics{color5-14c.pdf}
\includegraphics{color5-23a.pdf}}\smallskip

\fbox{\includegraphics{color5-14d.pdf}
\includegraphics{color5-23b.pdf}}
\fbox{\includegraphics{color5-23c.pdf}
\includegraphics{color5-23d.pdf}}
\fbox{\includegraphics{color5-23e.pdf}
\includegraphics{color5-23f.pdf}}\smallskip

\fbox{\includegraphics{color5-5a.pdf}
\includegraphics{color5-5b.pdf}}
\fbox{\includegraphics{color5-5c.pdf}
\includegraphics{color5-5d.pdf}}
\fbox{\includegraphics{color5-5e.pdf}}
\caption{Among the twenty-five cyclic $\nu$-color compositions of $5$, three are self-dual; they are the classes of the sums $1_1+1_1+1_1+1_1+1_1$, $1_1+2_2+2_1$, and $5_3$. The rest fall into eleven dual pairs. These fourteen dual classes correspond to the fourteen cyclic $O$-compositions of $10$.}
\label{fig:colorcomp5}
\end{figure}

This duality of cyclic $\nu$-color compositions is directly connected to their relation with cyclic $O$-compositions. The function $\chi$ of \S\ref{SS:ncolor} induces a map from the set of cyclic $\nu$-color compositions of $n$ to the set of cyclic $O$-compositions of $2n$. Two cyclic $\nu$-color compositions are dual precisely when they map to the same cyclic $O$-composition. The duality corresponds to regrouping the parts of the cyclic $O$-composition, of which there are necessarily an even number, into new adjacent pairs. If a cyclic $O$-composition corresponds to only one cyclic $\nu$-color composition, then that $\nu$-color composition is \emph{self-dual}.

A key question, then, is how many cyclic $\nu$-color compositions of $n$ are self-dual? It is convenient to think of $C_{2n}$ as the incidence graph of $C_n$, so that the vertices of $C_{2n}$ alternately correspond to vertices and edges of $C_n$, as in the second proof of Theorem~\ref{T:multiodd} above. Given an $O$-composition of $C_{2n}$, the final vertex of each part of the composition then corresponds to either a removed edge or a marked vertex in $C_n$. The index-$2$ subgroup of $\Z/2n\Z$ acting on $C_{2n}$ preserves the bipartite structure and thus corresponds to rotations of $C_n$. Any rotation of odd index in $\Z/2n\Z$, however, switches the edges and vertices of $C_n$ and thus corresponds to an exchange of duals.

We are therefore looking to count the number of $O$-compositions of $2n$ that are invariant under a rotation of odd index in $\Z/2n\Z$. Any such composition is the pullback of an $O$-composition of $(2n)_O$, which, to be clear, is the largest odd number that divides $2n$. Of course $(2n)_O = n_O$, and so we are counting the number of $O$-compositions of $n_O$, up to rotation, which is precisely what $d(O;n_O) = d^*(n)$ measures. 

\begin{remark}
Now the reason for the ``star'' notation in $d^*(n)$, and by extension, $h^*(x)$, should be clear: it refers to the presence of duality in defining the quantity.
\end{remark}

For example, the number of self-dual cyclic $\nu$-color compositions of $9$ is 
\[
d^*(9) 
= d(O;9)
= \frac19 \big(\phi(1)L_9 + \phi(3)L_3 + \phi(9)L_1\big) 
= \frac19 (1\cdot 76 + 2\cdot 4 + 6\cdot 1) = 10\text.
\]
They are shown in Figure \ref{F:color9selfdual}. In Figure \ref{fig:colorcomp5} we see that $d^*(5) = 3$, so we may also conclude that $d^*(10) = d^*(5) = 3$. On the other hand, $d^*(8) = d^*(4) = d^*(2) = d^*(1) = 1$, and thus there is only one self-dual cyclic $\nu$-color composition of $8$, in which all parts have size $1$. The same is true for every power of $2$.

\begin{figure}
\centering
\includegraphics{color9-111111111.pdf}\quad\;
\includegraphics{color9-1111113.pdf}\quad\;
\includegraphics{color9-11115.pdf}\quad\;
\includegraphics{color9-11133.pdf}\quad\;
\includegraphics{color9-11313.pdf}\vspace{.25in}

\includegraphics{color9-117.pdf}\quad\;
\includegraphics{color9-135.pdf}\quad\;
\includegraphics{color9-153.pdf}\quad\;
\includegraphics{color9-333.pdf}\quad\;
\includegraphics{color9-9.pdf}
\caption{The ten self-dual cyclic $\nu$-color compositions of $9$.}
\label{F:color9selfdual}
\end{figure}

The following theorem summarizes the results of the last few paragraphs.

\begin{theorem}
The number of dual classes of cyclic $\nu$-color compositions of $n$ equals $d(O;2n)$, i.e., the number of cyclic $O$-compositions of $2n$. The number of self-dual cyclic $\nu$-color compositions of $n$ equals $d^*(n)$, i.e., the number of cyclic $O$-compositions of $n_O$.
\end{theorem}

It would be interesting to know if this duality present within the set of cyclic $\nu$-color compositions has additional applications.

\section{Acknowledgments}

The images in Figure~\ref{F:braids} were produced using the Desmos graphing calculator, which is available at \href{https://www.desmos.com/calculator}{\tt www.desmos.com/calculator}. All other images were made using MetaPost, which is supported by the \TeX\ Users Group at \href{https://tug.org/metapost.html}{\tt tug.org/metapost.html}.

\begin{thebibliography}{99}
\bibitem{Agarwal} A. K. Agarwal, $n$-colour compositions, \emph{Indian J. Pure Appl. Math.} {\bf31} (2000), 1421--1437.
\bibitem{Agarwal2} A. K. Agarwal, An analogue of Euler's identity and new combinatorial properties of $n$-colour compositions, \emph{J. Comput. Appl. Math.} {\bf160} (2003), 9--15.
\bibitem{Andrews} G. E. Andrews, The theory of compositions, IV: Multicompositions, \emph{Math. Student}, Special Centenary Volume (2007), 25--31. 
\bibitem{BenQui} A. T. Benjamin and J. J. Quinn, \emph{Proofs That Really Count: The Art of Combinatorial Proof}, Cambridge University Press, 2003.
\bibitem{BenQuiMM} A. T. Benjamin and J. J. Quinn, The Fibonacci numbers---exposed more discretely, \emph{Math. Mag.} {\bf76} (2003), 182--192.
\bibitem{BerSlo} M. Bernstein and N. J. A. Sloane, Some canonical sequences of integers, \emph{Linear Algebra Appl.} {\bf226--228} (1995), 57--72.
\bibitem{Bower} C. G. Bower, Further transformations of integer sequences,\\ \href{https://oeis.org/transforms2.html}{\texttt{https://oeis.org/transforms2.html}}. Accessed February 29 2024.
\bibitem{Palmer} J. P. Bowman and J. Palmer, Hamiltonian cycles in quartic circulant graphs. In progress.
\bibitem{Cam} P. Cameron, Some sequences of integers, \emph{Discrete Math.} {\bf75} (1989), 89--102.
\bibitem{Char} C. A. Charalambides, Lucas numbers and polynomials of order $k$ and the length of the longest circular success run, \emph{Fibonacci Quart.} {\bf29} (1991), 290--297.
\bibitem{Cournot} A.-A. Cournot, Solution d'un probl\`{e}me d'analyse combinatoire, \emph{Bulletin des Sciences Math\'{e}matiques, Physiques et Chimiques} {\bf11} (1829), 93--97.
\bibitem{AC} P. Flajolet and R. Sedgewick, \emph{Analytic Combinatorics}, Cambridge University Press, 2009.
\bibitem{FS} P. Flajolet and M. Soria, The cycle construction, \emph{SIAM J. Discrete Math.} {\bf4} (1991), 58--60.
\bibitem{Gibson} M. M. Gibson, D. Gray, and H. Wang, Combinatorics of $n$-color cyclic compositions, \emph{Discrete Math.} {\bf341} (2018), 3209--3226.
\bibitem{Hadj} P. Hadjicostas, Cyclic compositions of a positive integer with parts avoiding an arithmetic sequence, \emph{J. Integer Sequences} {\bf19} (2016), \href{https://cs.uwaterloo.ca/journals/JIS/VOL19/Hadjicostas/hadji2.html}{Article 16.8.2}.
\bibitem{Hopk} B. Hopkins, Spotted tilings and $n$-color compositions, \emph{Integers} {\bf12B} (2012/13), \#A6.
\bibitem{Lapl} P.-S. Laplace, M\'emoire sur les suites r\'ecurro-r\'ecurrentes et sur leurs usages dans la th\'eorie des hasards, \emph{M\'em. Acad. R. Sci. Paris (Savants \'etrangers)} {\bf6} (1774), 353--371.
\bibitem{Mac} P. MacMahon, Memoir on the theory of the compositions of numbers, \emph{Philos. Trans. Roy. Soc. A.} {\bf184} (1893), 835--901.
\bibitem{NP} T. D. Noe and J. V. Post, Primes in Fibonacci $n$-step and Lucas $n$-step sequences, \emph{J. Integer Sequences} {\bf8} (2005), 
\href{https://cs.uwaterloo.ca/journals/JIS/VOL8/Noe/noe5.html}{Article 05.4.4}.
\bibitem{OEIS} OEIS Foundation Inc., \emph{The On-Line Encyclopedia of Integer Sequences}, 2023. Published electronically at \href{https://oeis.org}{\texttt{https://oeis.org}}. 
\bibitem{Mairan} J.-J. d'Ortous de Mairan, Sur le jeu de pair ou non, \emph{Hist. de L'Acad. R. Sci. Paris} (1728), 53--57.
\bibitem{Ramus} C. Ramus, Solution g\'en\'erale d'un probl\`eme d'analyse combinatoire, \emph{J. Reine Angew. Math.} {\bf11} (1834), 353--355.
\bibitem{Somm} D. M. Y. Sommerville, On certain periodic properties of cyclic compositions of numbers, \emph{Proc. Lond. Math. Soc.} {\bf 7} (1909), 263--313.
\bibitem{ZH2015} L. Zhang and P. Hadjicostas, On sequences of independent Bernoulli trials avoiding the pattern `$11\cdots1$', \emph{Math. Scientist} {\bf40} (2015), 89--96.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2020 \textit{Mathematics Subject Classification}: Primary 05A15; Secondary 05A17, 05A19, 11A07, 11B39.

\noindent {\textit{Keywords}:} composition, cyclic composition, circular composition, parity, congruence, generating function.

\bigskip
\hrule
\bigskip

\noindent \noindent (Concerned with sequences 
\seqnum{A000004},
\seqnum{A000007},
\seqnum{A000016},
\seqnum{A000032},
\seqnum{A000045},
\seqnum{A000204},
\seqnum{A000225},
\seqnum{A001350},
\seqnum{A001519},
\seqnum{A002878},
\seqnum{A004146},
\seqnum{A008965},
\seqnum{A011782},
\seqnum{A025192},
\seqnum{A032198},
\seqnum{A056295},
\seqnum{A088305},
\seqnum{A093040},
\seqnum{A094686},
\seqnum{A100886},
\seqnum{A324969},
\seqnum{A365857},
\seqnum{A365858},
\seqnum{A365859},
\seqnum{A366043},
\seqnum{A366044}, and
\seqnum{A366045}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  October 2 2023;
revised versions received October 9 2023; February 29 2024; March 1 2024.  
Published in {\it Journal of Integer Sequences}, March 9 2024.

\bigskip
\hrule
\bigskip

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

\end{document}
