\documentclass[12pt,reqno]{article}

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

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

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

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

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

\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{epic}
\usepackage{curves}
\usepackage{amsthm}
\newcommand{\sqbinom}[2]{\begin{bmatrix}#1\\#2\end{bmatrix}}
\numberwithin{equation}{section}


\makeatletter
\newfont{\footsc}{cmcsc10 at 8truept}
\newfont{\footbf}{cmbx10 at 8truept}
\newfont{\footrm}{cmr10 at 10truept}

\makeatother \pagestyle{plain}
\newcommand{\nfact}[1]{^{\textstyle !}_{#1}}
\newtheorem{cor}{Corollary}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\newtheorem{theo}{Theorem}
\numberwithin{theo}{section}
\newtheorem{lem}[theo]{Lemma}
\newcommand{\RN}{\mathcal{R}}

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

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf Periodicity and Parity Theorems for a Statistic on $r$-Mino Arrangements
}
\vskip 1cm
\large
Mark A. Shattuck and Carl G. Wagner\\
Mathematics Department\\
University of Tennessee\\
Knoxville, TN 37996-1300\\
USA \\
\href{mailto:shattuck@math.utk.edu}{\tt shattuck@math.utk.edu} \\
\href{mailto:wagner@math.utk.edu}{\tt wagner@math.utk.edu} \\
\end{center}

\vskip .2 in
\begin{abstract}
We study polynomial generalizations of the $r$-Fibonacci and $r$-Lucas
sequences which arise in connection with a certain statistic on linear
and circular $r$-mino arrangements, respectively. By considering
special values of these polynomials, we derive periodicity and parity
theorems for this statistic on the respective structures.
\end{abstract}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 






\section{Introduction}
If $r\geq 2$, the $r$-Fibonacci numbers $F_{n}^{(r)}$ are defined by
$F_0^{(r)}=F_1^{(r)}=\cdots=F_{r-1}^{(r)}=1$, with $F_n^{(r)}=F_{n-1}^{(r)}+F_{n-r}^{(r)}$ if $n\geq r$.
The $r$-Lucas numbers $L_n^{(r)}$ are defined by $L_1^{(r)}=L_2^{(r)}=\cdots=L_{r-1}^{(r)}=1$ and
$L_r^{(r)}=r+1$, with $L_n^{(r)}=L_{n-1}^{(r)}+L_{n-r}^{(r)}$ if $n\geq r+1$. If $r=2$, the $F_n^{(r)}$
and $L_n^{(r)}$ reduce, respectively, to the classical Fibonacci and Lucas numbers (parametrized as in Wilf \cite{wilf1},
by $F_0=F_1=1$, etc., and $L_1=1$, $L_2=3$, etc.).

Polynomial generalizations of $F_n$ and/or $L_n$ have arisen as generating functions for statistics on
binary words \cite{carlitz}, lattice paths \cite{cigler3}, and linear and circular domino arrangements \cite{shattuck1}.
Generalizations of $F_n^{(r)}$ and/or $L_n^{(r)}$ have arisen similarly in connection with statistics on
Morse code sequences \cite{cigler2} as well as on linear and circular $r$-mino arrangements \cite{shattuck2}.

Cigler \cite{cigler1} introduces and studies a new class of $q$-Fibonacci polynomials, generalizing the classical
sequence, which arise in connection with a certain statistic on Morse code sequences in which the dashes
have length 2. The same statistic, which we'll denote by $\pi$, applied more generally to linear
$r$-mino arrangements, leads to the polynomial generalization
\begin{equation}\label{e1.1}
F_n^{(r)}(q,t):=\sum_{0 \leq k \leq \lfloor n/r \rfloor} q^{\binom{k+1}{2}}\binom{n-(r-1)k}{k}_qt^k
\end{equation}
of $F_n^{(r)}$. A natural extension of this $\pi$ statistic to circular $r$-mino arrangements leads to
the new polynomial generalization
\begin{equation}\label{e1.2}
L_n^{(r)}(q,t):=\sum_{0 \leq k \leq \lfloor n/r \rfloor}
q^{\binom{k+1}{2}}\left[\frac{(r-1)k_q+(n-(r-1)k)_q}{(n-(r-1)k)_q}\right]\binom{n-(r-1)k}{k}_qt^k
\end{equation}
of $L_n^{(r)}$.

In addition to deriving the above closed forms for $F_n^{(r)}(q,t)$ and $L_n^{(r)}(q,t)$, we present
both algebraic and combinatorial evaluations of $F_n^{(r)}(-1,t)$ and $L_n^{(r)}(-1,t)$, as well as
determine when the sequences $F_n^{(r)}(-1,1)$ and $L_n^{(r)}(-1,1)$ are periodic. Our algebraic proofs
make frequent use of the identity \cite[pp.\ 201--202]{wagner1}
\begin{equation}\label{e1.3}
\sum_{n\geq 0} {\binom{n}{k}}_qx^n=\frac{x^k}{(1-x)(1-qx)\cdots(1-q^kx)}, \qquad k\in\mathbb{N}.
\end{equation}
Our combinatorial proofs are based on the fact that $F_n^{(r)}(q,t)$ and $L_n^{(r)}(q,t)$ are bivariate
generating functions for a pair of statistics defined, respectively, on linear and circular arrangements
of $r$-minos. We also describe some variants of the $\pi$ statistic on circular domino arrangements
which lead to additional polynomial generalizations of the Lucas sequence.

In what follows, $\mathbb{N}$ and $\mathbb{P}$ denote, respectively, the nonnegative and positive
integers. Empty sums take the value $0$ and empty products the value 1, with $0^0:=1$. If $q$ is an
indeterminate, then $0_q:=0$, $n_q:=1+q+\dots+q^{n-1}$ for $n \in \mathbb{P}$,
$0_q^{\mbox{\normalsize$!$}} := 1$, $n_q^{\mbox{\normalsize$!$}} := 1_q 2_q \cdots n_q$ for $n \in
\mathbb{P}$, and
\begin{equation}\label{e1.4}
\binom nk_{\!q}:=\begin{cases} \frac{n\nfact q}{k\nfact
q(n-k)\nfact q}, &\text{if }0\leqslant k\leqslant n;\\\\
0, &\text{if }k<0\text{ or }0\leqslant n<k.
\end{cases}
\end{equation}
A useful variation of \eqref{e1.4} is the well known formula \cite[p.\ 29]{stanley1}
\begin{equation}\label{e1.5}
\binom{n}{k}_q=\sum_{\substack{d_0+d_1+\cdots+d_k=n-k\\
d_i\in\mathbb{N}}}q^{0d_0+1d_1+\cdots +kd_k}=\sum_{t\geq 0}p(k,n-k,t)q^t,
\end{equation}
where $p(k,n-k,t)$ denotes the number of partitions of the integer $t$ with at most $n-k$ parts, each no
larger than $k$.

\section{Linear $r$-Mino Arrangements}
Let $\mathcal{R}_{n,k}^{(r)}$ denote the set of coverings of the numbers $1,2,\dots,n$ arranged in a row
by $k$ indistinguishable $r$-minos and $n-rk$ indistinguishable squares, where pieces do not overlap, an
\emph{r-mino}, $r\geq 2$, is a rectangular piece covering $r$ numbers, and a \emph{square} is a piece
covering a single number. Each such covering corresponds uniquely to a word in the alphabet $\{r,s\}$
comprising $k$ $r$'s and $n-rk$ $s$'s so that
\begin{equation}\label{e2.1}
|\mathcal{R}_{n,k}^{(r)}| = \binom{n-(r-1)k}{k}, \qquad 0 \leq k \leq \lfloor n/r \rfloor,
\end{equation}
for all $n\in\mathbb{P}$. (If we set $\mathcal{R}_{0,0}^{(r)}=\{\emptyset\}$, the ``empty covering,''
then \eqref{e2.1} holds for $n=0$ as well.) In what follows, we will identify coverings $c$ with such
words $c_1c_2\cdots$ in $\{r,s\}$. With
\begin{equation}\label{e2.2}
\mathcal{R}_n^{(r)} := \bigcup_{0 \leq k \leq \lfloor n/r \rfloor} \mathcal{R}_{n,k}^{(r)}, \qquad n \in
\mathbb{N},
\end{equation}
\noindent it follows that
\begin{equation}\label{e2.3}
|\mathcal{R}_n^{(r)}| = \sum_{0 \leq k \leq \lfloor n/r \rfloor} \binom{n-(r-1)k}{k} = F_n^{(r)},
\end{equation}
\noindent where $F_0^{(r)} = F_1^{(r)} = \cdots = F_{r-1}^{(r)} = 1$, with $F_n^{(r)} = F_{n-1}^{(r)} +
F_{n-r}^{(r)}$ if $n \geq r$. Note that
\begin{equation}\label{e2.4}
\sum_{n \geq 0} F_n^{(r)}x^n = \frac{1}{1-x-x^r}.
\end{equation}

Given a covering $c=c_1c_2\cdots$, let
\begin{equation}\label{e2.5}
\pi(c):=\sum_{i:c_i=r}i;
\end{equation}
note that $\pi(c)$ gives the total resulting when one counts the number of pieces preceding each
$r$-mino, inclusive, and adds up these numbers.

Let
\begin{equation}\label{e2.6}
F_n^{(r)}(q,t) := \sum_{c \in \mathcal{R}_n^{(r)}} q^{\pi(c)} t^{v(c)}, \qquad n \in \mathbb{N},
\end{equation}
where $v(c):=$ the number of $r$-minos in the covering $c$.

Categorizing linear covers of $1,2,\dots,n$ according to whether the piece covering $n$ is a square or
$r$-mino yields the recurrence relation
\begin{equation}\label{e2.7}
F_n^{(r)}(q,t) = F_{n-1}^{(r)}(q,t) + q^{n-r+1}tF_{n-r}^{(r)}\left(q,{t}/{q^{r-1}}\right), \qquad n \geq
r,
\end{equation}
\noindent with $F_i^{(r)}(q,t)=1$ if $0\leq i\leq r-1$, since the total number of pieces in
$c\in\mathcal{R}_{m}^{(r)}$ is $m-(r-1)v(c)$. Categorizing covers of 1,2,...,$n$ according to whether
the piece covering 1 is a square or $r$-mino yields
\begin{equation}\label{e2.8'}
F_n^{(r)}(q,t)=F_{n-1}^{(r)}(q,qt)+qtF_{n-r}^{(r)}(q,qt), \qquad n\geqslant r.
\end{equation}
By combining relations \eqref{e2.7} and \eqref{e2.8'}, one gets a recurrence for $F_n^{(r)}(q,t)$ for
each number $q$ and $t$. For example when $r=3$, this is
\begin{eqnarray}\label{e2.9'}
F_n^{(3)}(q,t)=F_{n-1}^{(3)}(q,t)+q^{n-2}tF_{n-5}^{(3)}(q,t)&+&q^{n-3}(1+q)t^2F_{n-7}^{(3)}(q,t)\nonumber
\\&+&q^{n-3}t^3F_{n-9}^{(3)}(q,t).
\end{eqnarray}
The $F_n^{(r)}(q,t)$ have the following explicit formula.

\begin{theo}
For all $n \in \mathbb{N}$,
\begin{equation}\label{e2.8}
F_n^{(r)}(q,t) = \sum_{0 \leq k \leq \lfloor n/r \rfloor} q^{\binom{k+1}{2}} \binom{n - (r-1)k}{k}_{q}
t^k.
\end{equation}
\end{theo}

\begin{proof}[Proof.] It clearly suffices to show that
\begin{displaymath}
\sum_{c \in \mathcal{R}_{n,k}^{(r)}} q^{\pi(c)} = q^{\binom{k+1}{2}} \binom{n-(r-1)k}{k}_{q}.
\end{displaymath}

\noindent Each $c \in \mathcal{R}_{n,k}^{(r)}$ corresponds uniquely to a sequence
$(d_0,d_1,\dots,d_{k})$, where $d_0$ is the number of squares following the $k^{th}$ $r$-mino (counting
from left to right) in the covering $c$, $d_k$ is the number of squares preceding the first $r$-mino,
and, for $0 < i < k$, $d_{k-i}$ is the number of squares between the $i^{th}$ and $(i+1)^{st}$ $r$-mino.
Then $\pi(c) = (d_{k}+1) + (d_{k} + d_{k-1} + 2) + \cdots + (d_{k} + d_{k-1} + \cdots + d_1 + k) =
\binom{k+1}{2} + kd_k + (k-1)d_{k-1} + \cdots + 1d_1$ so that
\begin{eqnarray}
\nonumber \sum_{c \in \mathcal{R}_{n,k}^{(r)}} q^{\pi(c)} &=&
q^{\binom{k+1}{2}} \sum_{\substack{d_0+d_1+\cdots+d_{k}=n-rk\\
d_i\in\mathbb{N}}} q^{0d_0 + 1d_1 + \cdots + kd_{k}} \\
    \nonumber &=& q^{\binom{k+1}{2}} \binom{n-(r-1)k}{k}_{q},
\end{eqnarray}
\noindent by \eqref{e1.5}. \end{proof}

\begin{theo} The ordinary generating function of the sequence $(F_n^{(r)}(q,t))_{n \geq
0}$ is given by
\begin{equation}\label{e2.9}
\sum_{n \geq 0} F_n^{(r)}(q,t)x^n = \sum_{k \geq
0}\frac{q^{\binom{k+1}{2}}t^kx^{rk}}{(1-x)(1-qx)\cdots(1-q^{k}x)}.
\end{equation}
\end{theo}

\begin{proof} By \eqref{e2.8} and \eqref{e1.3},
\[\mbox{\hskip-1.5in}\sum_{n \geq 0}F_n^{(r)}(q,t)x^n=\sum_{n \geq 0}
    \left(\sum_{0 \leq k \leq \lfloor n/r \rfloor} q^{\binom{k+1}{2}}
    \binom{n - (r-1)k}{k}_{q} t^k\right)x^n\]
  \begin{eqnarray*}
&=&\sum_{k\geq 0}q^{\binom{k+1}{2}}t^kx^{(r-1)k}\sum_{n \geq kr}{\binom{n-(r-1)k}{k}}_qx^{n-(r-1)k}\\
&=&\sum_{k \geq 0}q^{\binom{k+1}{2}}t^kx^{(r-1)k}\cdot\frac{x^{k}}{(1-x)(1-qx)\cdots(1-q^{k}x)}.
\end{eqnarray*}
\end{proof}

Note that $F_n^{(r)}(1,1)=F_n^{(r)}$, whence \eqref{e2.9} generalizes \eqref{e2.4}. Setting $q=1$ and
$q=-1$ in \eqref{e2.9} yields

\vspace{.2 in} \noindent \textbf{Corollary} \textbf{2.2.1.}\hspace{.003in} \textit{The ordinary
generating function of the sequence} $(F_n^{(r)}(1,t))_{n \geq 0}$ \textit{is} \textit{given by}
\begin{equation}\label{e2.10}
\sum_{n \geq 0} F_n^{(r)}(1,t)x^n = \frac{1}{1-x-tx^r}.
\end{equation}
\noindent and

\vspace{.2 in} \noindent \textbf{Corollary} \textbf{2.2.2.} \textit{The ordinary generating function of
the sequence} $(F_n^{(r)}(-1,t))_{n \geq 0}$ \textit{is} \textit{given by}
\begin{equation}\label{e2.11}
\sum_{n \geq 0} F_n^{(r)}(-1,t)x^n = \frac{1+x-tx^r}{1-x^2+t^2x^{2r}}.
\end{equation}

\vspace{.2 in} When $r=2$ and $t=1$ in \eqref{e2.11}, we get
\begin{equation}\label{e2.12}
\sum_{n \geq 0} F_n^{(2)}(-1,1)x^n = \frac{1+x-x^2}{1-x^2+x^4} = \frac{(1+x+x^3-x^4)(1-x^6)}{1-x^{12}},
\end{equation}
which implies

\vspace{.2 in} \noindent \textbf{Corollary} \textbf{2.2.3.}\hspace{.003in}\textit{ The sequence}
$(F_n^{(2)}(-1,1))_{n \geq 0}$ \textit{is periodic with period $12$; namely, if} $a_n:=F_n^{(2)}(-1,1)$
\textit{for} ${n \geq 0}$, \textit{then} $a_0=1$, $a_1=1$, $a_2=0$, $a_3=1$,
$a_4=-1$, \textit{and} $a_5=0$ \textit{with} $a_{n+6}=-a_n$, $n\geq 0$.\\

\noindent(We call a sequence $(b_n)_{n\geq 0}$ \emph{periodic}
\emph{with} \emph{period} $d$ if $b_{n+d}=b_n$ for all $n\geq m$
for some $m\in\mathbb{N}$.)

\vspace{.2 in} \noindent\emph{Remark.}\hspace{.12in} Corollary 2.2.3 is the $q=-1$ case of the well
known formula
\begin{equation*}
\sum_{0 \leq k \leq \lfloor n/2 \rfloor}(-1)^kq^{\binom{k}{2}}{\binom{n-k}{k}}_q = \begin{cases}
{\displaystyle (-1)^{\lfloor n/3 \rfloor}q^{n(n-1)/6}}, &\text{\emph{if $n\equiv 0$, $1$}}\text{ (mod
3)};\\\\
{\displaystyle 0}, &\text{\emph{if $n\equiv 2$}} \text{ (mod 3)}.\end{cases}
\end{equation*}

\noindent See, e.g., Cigler \cite{cigler3}, Ekhad and Zeilberger \cite{Ekhad}, and Kupershmidt \cite{Kuper}.\\

We now show that the periodic behavior of $F_n^{(r)}(-1,1)$ seen when $r=2$ is restricted to that case.
The following lemma is established in \cite{shattuck2}. We include its proof here for completeness.

\begin{lem}
If $r\geq 3$, then $g_r(x):=1-x+x^r$ does not divide any polynomial of the form $1-x^m$, where
$m\in\mathbb{P}$.
\end{lem}

\begin{proof}
We first describe the roots of unity that are zeros of $g_r(x)$, where $r\geq 2$. If $z$ is such a root
of unity, let $y=z^{r-1}$. Since $z(1-z^{r-1})=1$ and $z$ is a root of unity, it follows that both $y$
and $1-y$ are roots of unity. In particular, $|y|=|1-y|=1$. Therefore, $1-2$Re$(y)+|y|^2=1$, so
Re$(y)=\frac{1}{2}$. This forces $y$, and hence $1-y$, to be primitive $6^{th}$ roots of unity. But
$1-y=\frac{1}{z}$, so $z$ is also a primitive $6^{th}$ root of unity.

This implies that the only possible roots of unity which are zeros of $g_r$ are the primitive $6^{th}$
roots of unity. Since the derivative of $g_r$ has no roots of unity as zeros, these $6^{th}$ roots of
unity can only be simple zeros of $g_r$. In particular, if every root of $g_r$ is a root of unity, then
$r=2$.
\end{proof}
\begin{theo}
The sequence $(F_n^{(r)}(-1,1))_{n\geq 0}$ is never periodic for $r\geq 3$.
\end{theo}


\begin{proof} By \eqref{e2.11} at $t=1$, we must show that $1-x^2+x^{2r}$
does not divide the product $(1-x^m)(1+x-x^r)$ for any  $m \in \mathbb{P}$ whenever  $r\geq 3$. First
note that the polynomials $1-x^2+x^{2r}$ and $1+x-x^r$ cannot share a zero; for if $t_0$ is a common
zero, then $t_0^2-1=t_0^{2r}=(t_0+1)^2$, i.e, $t_0=-1$, which isn't a zero of either polynomial. Observe
next that $1-x^2+x^{2r}=g_r(x^2)$, where $g_r(x)$ is as in Lemma 2.3, so that $1-x^2+x^{2r}$ fails to
divide $1-x^m$ for any $m\in \mathbb{P}$, since $g_r(x)$ fails to, which completes the proof.
\end{proof}

Iterating \eqref{e2.7} or \eqref{e2.8'} yields $F_{-i}^{(r)}(q,t)=0$ if  $1\leq i\leq r-1$, which we'll
take as a convention.

\begin{theo}
Let $m\in \mathbb{N}$. If $m$ and $r$ have the same parity, then
\begin{equation}\label{e2.13}
F_m^{(r)}(-1,t)=F_{\lfloor m/2 \rfloor}^{(r)}(1,-t^2)-tF_{(m-r)/2}^{(r)}(1,-t^2),
\end{equation}
and if $m$ and $r$ have different parity, then
\begin{equation}\label{e2.14}
F_m^{(r)}(-1,t)=F_{\lfloor m/2 \rfloor}^{(r)}(1,-t^2).
\end{equation}
\end{theo}

\begin{proof}
Taking the even and odd parts of both sides of \eqref{e2.11} followed by replacing $x$ with $x^{1/2}$
yields
\begin{equation*}
\sum_{n\geq 0}F_{2n}^{(r)}(-1,t)x^n=\frac{1-tx^{r/2}}{1-x+t^2x^r}
\end{equation*}
and
\begin{equation*} \sum_{n\geq 0}F_{2n+1}^{(r)}(-1,t)x^n=\frac{1}{1-x+t^2x^r},
\end{equation*}
when $r$ is even, and
\begin{equation*} \sum_{n\geq 0}F_{2n}^{(r)}(-1,t)x^n=\frac{1}{1-x+t^2x^r}
\end{equation*}
and
\begin{equation*} \sum_{n\geq 0}F_{2n+1}^{(r)}(-1,t)x^n=\frac{1-tx^{(r-1)/2}}{1-x+t^2x^r},
\end{equation*}
when $r$ is odd, from which \eqref{e2.13} and \eqref{e2.14} now follow from \eqref{e2.10} upon putting
together cases.

For a combinatorial proof of \eqref{e2.13} and \eqref{e2.14}, we
first assign to each $r$-mino arrange\-ment $c \in
\mathcal{R}_{m}^{(r)}$ the weight $w_c:=(-1)^{\pi(c)}t^{v(c)}$,
where $t$ is an indeterminate. Let $\mathcal{R}_{m}^{(r)'}$
consist of those $c=c_1c_2\cdots$ in $\mathcal{R}_{m}^{(r)}$
satisfying the conditions $c_{2i-1}=c_{2i}$, $i\geq 1$. Suppose
$c\in \mathcal{R}_{m}^{(r)}-\mathcal{R}_{m}^{(r)'}$, with $i_0$
being the smallest value of $i$ for which $c_{2i-1}\neq c_{2i}$.
Exchanging the positions of the $(2i_0-1)^{st}$ and $(2i_0)^{th}$
pieces within $c$ produces a $\pi$-parity changing involution of
$\mathcal{R}_{m}^{(r)}-\mathcal{R}_{m}^{(r)'}$ which preserves
$v$.

If $m$ and $r$ have the same parity, then
\begin{eqnarray*}
    F_{m}^{(r)}(-1,t)&=&\sum_{c\in\RN_{m}^{(r)}}w_c=\sum_{c\in\RN_{m}^{(r)'}}w_c=\sum_{\substack{
    c\in\RN_{m}^{(r)'}\\ v(c)\text{ even}}}w_c\hspace{.1in}+\sum_{\substack{
    c\in\RN_{m}^{(r)'}\\ v(c)\text{ odd}}}w_c\\
    &=&\sum_{\substack{c\in\RN_{m}^{(r)'}\\ v(c)\text{
    even}}}(-1)^{{v(c)}/{2}}t^{v(c)}\hspace{.1in}-t\sum_{\substack{c\in\RN_{m-r}^{(r)'}\\ v(c)\text{
    even}}}(-1)^{{v(c)}/{2}}t^{v(c)}\\
    &=&\sum_{z\in\RN_{\lfloor m/2
    \rfloor}^{(r)}}(-1)^{v(z)}t^{2v(z)}-t\sum_{z\in\RN^{(r)}_{{(m-r)}/{2}}}(-1)^{v(z)}t^{2v(z)}\\
    &=&F_{\lfloor m/2\rfloor}^{(r)}(1,-t^2)-tF^{(r)}_{{(m-r)}/{2}}(1,-t^2),
\end{eqnarray*}
which gives \eqref{e2.13}, since each pair of consecutive $r$-minos in $c\in \RN_m^{(r)'}$ contributes a
factor of $-1$ towards the sign $(-1)^{\pi(c)}$ and since members of $\RN_m^{(r)'}$ for which $v(c)$ is
odd end in a single $r$-mino. If $m$ and $r$ differ in parity, then
\begin{eqnarray*}
    F_{m}^{(r)}(-1,t)&=&\sum_{c\in\RN_{m}^{(r)}}w_c=\sum_{c\in\RN_{m}^{(r)'}}w_c
    =\sum_{z\in\RN_{\lfloor m/2
    \rfloor}^{(r)}}(-1)^{v(z)}t^{2v(z)}
    =F_{\lfloor m/2\rfloor}^{(r)}(1,-t^2),
\end{eqnarray*}
which gives \eqref{e2.14}, since members of $\RN_m^{(r)'}$ must contain an even number of $r$-minos.
\end{proof}

The involution of the previous theorem in the case $r=2$ can be extended to account for the periodicity
in Corollary 2.2.3 as follows. If $n\geq 6$, let $\RN_n^{(2)*}\subseteq \RN_n^{(2)'}$ consist of those
domino arrangements $c=c_1c_2\cdots$ that contain at least $4\lfloor n/6\rfloor$ pieces satisfying the
conditions
\begin{equation}\label{e2.15}
c_{4i-3}c_{4i-2}c_{4i-1}c_{4i}=ssdd,\qquad 1\leq i\leq \lfloor n/6\rfloor;
\end{equation}
if $0\leq n\leq 5$, then let $\RN_n^{(2)*}= \RN_n^{(2)'}$.

A $\pi$-parity changing involution of $\RN_n^{(2)'}- \RN_n^{(2)*}$ when $n\geq 6$ is given by the
pairing
$$(ssdd)^k ssssu\longleftrightarrow (ssdd)^k ddu,$$
where $k\geq 0$ and $u$ is some (non-empty) word in $\{d,s\}.$ If $n=6m+i,$ where $m\geq 1$ and $0\leq
i\leq 5,$ then
\begin{eqnarray*}
    F_{n}^{(2)}(-1,1)&=&\sum_{c\in\RN_{n}^{(2)}}(-1)^{\pi(c)}=\sum_{c\in\RN_{n}^{(2)'}}(-1)^{\pi(c)}
    =\sum_{c\in\RN_{n}^{(2)*}}(-1)^{\pi(c)}\\
    &=&(-1)^m\sum_{c\in\RN_{i}^{(2)*}}(-1)^{\pi(c)}=(-1)^mF_{i}^{(2)}(-1,1),
\end{eqnarray*}
which implies Corollary 2.2.3, upon checking directly the cases $0\leq n\leq 5,$ as each $ssdd$ unit in
$c\in\RN_n^{(2)*}$ contributes a factor of $-1$ towards the sign $(-1)^{\pi(c)}$.

\section{Circular $r$-Mino Arrangements}

If $n\in\mathbb{P}$ and $0\leq k\leq \lfloor n/r\rfloor$, let $\mathcal{C}_{n,k}^{(r)}$ denote the set
of coverings by $k$ $r$-minos and $n-rk$ squares of the numbers $1,2,\dots,n$ arranged clockwise around
a circle:

%%%%%%%%%%%%%%%%%% figure 1 here %%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
    \setlength{\unitlength}{1mm}
    \begin{picture}(40,40)
        \put(20,20){\bigcircle{30}}
        \put(37,20){\makebox(0,0)[l]{$\cdot$}}
        \put(32,32){\makebox(0,0)[lb]{$2$}}
        \put(20,37){\makebox(0,0)[b]{$1$}}
        \put(8,32){\makebox(0,0)[rb]{$n$}}
        \put(3,20){\makebox(0,0)[r]{$\cdot$}}
        \put(8,8){\makebox(0,0)[rt]{$\cdot$}}
        \put(20,3){\makebox(0,0)[t]{$\cdot$}}
        \put(32,8){\makebox(0,0)[lt]{$\cdot$}}
    \end{picture}
\end{center}



\noindent By the \emph{initial segment} of an $r$-mino occurring
in such a cover, we mean the segment first encountered as the
circle is traversed clockwise. Classifying members of
$\mathcal{C}_{n,k}^{(r)}$ according as (i) $1$ is covered by one
of $r$ segments of an $r$-mino or (ii) $1$ is covered by a square,
and applying \eqref{e2.1}, yields \setlength{\jot}{12pt}
\begin{eqnarray}\label{e3.1}
   \nonumber\left|\mathcal{C}_{n,k}^{(r)}\right|
   &=&r\binom{n-(r-1)k-1}{k-1}+\binom{n-(r-1)k-1}{k}\\
   &=&\frac{n}{n-(r-1)k}\binom{n-(r-1)k}{k},\qquad
    0\leq k\leq \lfloor n/r\rfloor.
\end{eqnarray}
Below we illustrate two members of $\mathcal{C}_{4,1}^{(3)}$: \setlength{\jot}{4.5pt}
%%%%%%%%%%%%%%%%%% figure 2 here %%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{center}
    \setlength{\unitlength}{0.8mm}
    (i)
    \parbox{40mm}{%
    \begin{picture}(50,50)
        \thicklines
    \put(25,25){\arc(-1.5,-17){190}}
    \put(25,25){\arc(-1.5,-8){200}}
    \drawline(23,8)(23,17)
    \drawline(23,33)(23,42)

    \drawline(6,20)(6,29)
    \drawline(14,20)(14,29)
    \drawline(6,29)(14,29)
    \drawline(6,20)(14,20)

    \put(25,38){\makebox(0,0){$1$}}
    \put(37,25){\makebox(0,0){$2$}}
    \put(25,12){\makebox(0,0){$3$}}
    \put(10,25){\makebox(0,0){$4$}}
    \end{picture}}
    \quad \quad \qquad (ii)
    \parbox{40mm}{%
    \begin{picture}(50,50)
        \thicklines
    \put(25,25){\arc(1,17){190}}
    \put(25,25){\arc(1,8){200}}
    \drawline(27,8.5)(27,17.5)
    \drawline(26,33)(26,42)

    \drawline(35,20)(35,29)
    \drawline(43,20)(43,29)
    \drawline(35,29)(43,29)
    \drawline(35,20)(43,20)

    \put(24,38){\makebox(0,0){$1$}}
    \put(39,25){\makebox(0,0){$2$}}
    \put(25,12){\makebox(0,0){$3$}}
    \put(12,25){\makebox(0,0){$4$}}
    \end{picture}}
\end{center}




\noindent In covering (i), the initial segment of the 3-mino covers 1, and in covering (ii), the initial
segment covers 3.

With
\begin{equation}\label{e3.2}
    \mathcal{C}_n^{(r)}:=\bigcup_{0\leq k\leq \lfloor
    n/r\rfloor}\mathcal{C}_{n,k}^{(r)}, \qquad n\in\mathbb{P},
\end{equation}
it follows that
\begin{equation}\label{e3.3}
    \left|\mathcal{C}_n^{(r)}\right|=\sum_{0\leq k\leq \lfloor
    n/r\rfloor}\frac{n}{n-(r-1)k}\binom{n-(r-1)k}{k}=L_n^{(r)},
\end{equation}
where $L_1^{(r)}=L_2^{(r)}=\cdots=L_{r-1}^{(r)}=1$, $L_r^{(r)}=r+1$, and
$L_n^{(r)}=L_{n-1}^{(r)}+L_{n-r}^{(r)}$ if $n\geq r+1$. Note that
\begin{equation}\label{e3.4}
    \sum_{n\geq 1}L_n^{(r)}x^n=\frac{x+rx^r}{1-x-x^r}.
\end{equation}


We'll associate to each $c\in\mathcal{C}_n^{(r)}$ a word $u_c=u_1u_2\cdots$ in the alphabet $\{r,s\}$,
where
\begin{equation*}
u_i:= \begin{cases} r, &\text{{if the $i^{th}$ piece of $c$ is an $r$-mino;}
}\\
s, &\text{{if the $i^{th}$ piece of $c$ is a square,} }\end{cases}
\end{equation*}
and one determines the $i^{th}$ piece of $c$ by starting with the piece covering 1 and proceeding
clockwise from that piece. Note that for each word starting with $r$, there are exactly $r$ associated
members of $\mathcal{C}_n^{(r)}$, while for each word starting with $s$, there is only one associated
member.

Given $c\in \mathcal{C}_n^{(r)}$ and its associated word $u_c=u_1u_2\cdots,$ let
\begin{equation}\label{e3.5}
\pi(c):=\sum_{i:u_i=r}i;
\end{equation}
note that $\pi(c)$ gives the sum of the numbers gotten by counting
the number of pieces preceding each $r$-mino, inclusive (counting
back each time counterclockwise to the piece covering 1).

Let
\begin{equation}\label{e3.6}
    L_n^{(r)}(q,t):=\sum_{c\in \mathcal{C}_n^{(r)}}q^{\pi(c)}t^{v(c)},\qquad
    n\in\mathbb{P},
\end{equation}
where $v(c):=$ the number of $r$-minos in the covering $c$.

Categorizing circular covers $c$ of $1,2,\dots, n$ according to whether the last letter in $u_c$ is an
$s$ or $r$ yields the recurrence relation

\begin{equation}\label{e3.7}
L_n^{(r)}(q,t)=L_{n-1}^{(r)}(q,t)+q^{n-r+1}tL_{n-r}^{(r)}(q,t/q^{r-1}),\quad n\geq r+1,
\end{equation}
with $L_i^{(r)}(q,t)=1$ if $1\leq i\leq r-1$ and $L_r^{(r)}(q,t)=1+rqt$, as seen upon removing the final
piece of $c$, sliding the remaining pieces together to form a circle, and renumbering (if necessary) so
that 1 corresponds to the same position as before. The $L_n^{(r)}(q,t),$ though, do not seem to satisfy
a recurrence like \eqref{e2.8'}. The following theorem gives an explicit formula for $L_n^{(r)}(q,t)$.

\begin{theo}
    For all $n\in\mathbb{P}$,

    \begin{equation}\label{e3.8}
L_n^{(r)}(q,t)= \sum_{0 \leq k \leq \lfloor n/r \rfloor} q^{\binom{k+1}{2}} \left[ \frac{(r-1)k_{q}
+(n-(r-1)k)_q}{(n-(r-1)k)_{q}} \right] \binom{n-(r-1)k}{k}_{q} t^k.
\end{equation}
\end{theo}

\begin{proof}
It suffices to show that

$$\sum_{c\in \mathcal{C}_{n,k}^{(r)}}q^{\pi(c)}=q^{\binom{k+1}{2}}\left[\frac{(r-1)k_{q}+(n-(r-1)k)_{q}}
{(n-(r-1)k)_{q}}\right]\binom{n-(r-1)k}{k}_{q}.$$ Partitioning $\mathcal{C}_{n,k}^{(r)}$ into the
categories employed above in deriving \eqref{e3.1}, and applying \eqref{e2.8}, yields

\begin{eqnarray}
 \nonumber\sum_{c\in
    \mathcal{C}_{n,k}^{(r)}}q^{\pi(c)}&=&\lefteqn{rq^{k-1+1}\cdot q^{\binom{k}{2}}\binom{n-(r-1)k-1}{k-1}_{q}}\\
    \label{e3.9}&\quad&+~ q^{k}\cdot q^{\binom{k+1}{2}}\binom{n-(r-1)k-1}{k}_{q}\\
    \nonumber &=& q^{\binom{k+1}{2}}\left[\frac{rk_{q}+q^k(n-rk)_q}{(n-(r-1)k)_{q}}\right]
    \binom{n-(r-1)k}{k}_{q}\\
    \nonumber &=& q^{\binom{k+1}{2}}\left[\frac{(r-1)k_{q}+(n-(r-1)k)_q}{(n-(r-1)k)_{q}}\right]
    \binom{n-(r-1)k}{k}_{q},\\\nonumber
    \end{eqnarray}
which completes the proof.
\end{proof}

Note that $L_n^{(r)}(1,1)=L_n^{(r)}$. By \eqref{e3.8} and \eqref{e2.8}, the $L_n^{(r)}(q,t)$ are related
to the $F^{(r)}_n (q,t)$ by the formula
\begin{equation}\label{e3.10}
L^{(r)}_n (q, t) = F^{(r)}_{n} (q, t) + (r-1)qt F^{(r)}_{n-r} (q, qt), \qquad n\geq 1,
\end{equation}
which reduces to
\begin{equation}\label{e3.11}
L_n^{(r)}=F_n^{(r)}+(r-1)F_{n-r}^{(r)},\qquad n \geq 1,
\end{equation}
when $q=t=1$. Formula (3.10) can also be realized by considering the way in which 1 is covered in
$c\in\mathcal{C}_n^{(r)}$, the first term representing those $c$ for which 1 is covered by a square or
an initial segment of an $r$-mino and the second term representing the remaining $r-1$ possibilities.


\begin{theo}
The ordinary generating function of the sequence
$(L_n^{(r)}(q,t))_{n\geq 1}$ is given by
\begin{equation}\label{e3.12}
    \sum_{n\geq
    1}L_n^{(r)}(q,t)x^n=\frac{x}{1-x}+\sum_{k\geq
    1}\frac{q^{\binom{k+1}{2}}t^kx^{rk}\left[r-(r-1)q^kx\right]}{(1-x)(1-qx)\cdots(1-q^kx)}.
\end{equation}
\end{theo}

\begin{proof}   From \eqref{e3.9},

\begin{eqnarray*}
     \sum_{n\geq 1}L_n^{(r)}(q,t)x^n&=&\sum_{n\geq 1}x^n\sum_{0 \leq k \leq \lfloor n/r
     \rfloor}\left(
     q^{k+\binom{k+1}{2}}t^k\binom{n-(r-1)k-1}{k}_q \right.\\
     &\quad& \left. +~rq^{\binom{k+1}{2}}t^k\binom{n-(r-1)k-1}{k-1}_q\right)\\
     &=&\frac{x}{1-x}+\sum_{k\geq 1}q^{k+\binom{k+1}{2}}t^k\sum_{n\geq
     rk+1}\binom{n-(r-1)k-1}{k}_qx^n\\&\quad&+~r\sum_{k\geq 1}q^{\binom{k+1}{2}}t^k\sum_{n\geq
     rk}\binom{n-(r-1)k-1}{k-1}_qx^n\\&=&\frac{x}{1-x}+\sum_{k\geq
     1}q^{k+\binom{k+1}{2}}t^kx^{(r-1)k+1}\cdot\frac{x^k}{(1-x)(1-qx)\cdots(1-q^kx)}\\&\quad&+~
     r\sum_{k\geq 1}q^{\binom{k+1}{2}}t^kx^{(r-1)k+1}\cdot\frac{x^{k-1}}{(1-x)(1-qx)\cdots(1-q^{k-1}x)}\\
     &=&\frac{x}{1-x}+\sum_{k\geq 1}q^{\binom{k+1}{2}}t^k\cdot\frac{x^{rk}\left[q^kx+r(1-q^kx)\right]}
     {(1-x)(1-qx)\cdots(1-q^{k}x)},\\
\end{eqnarray*}
by \eqref{e1.3}.
\end{proof}

Note that \eqref{e3.12} reduces to \eqref{e3.4} when $q=t=1$. Setting $q=1$ and $q=-1$ in \eqref{e3.12}
yields

\vspace{.2 in} \noindent \textbf{Corollary} \textbf{3.2.1.}\hspace{.003in} \textit{The ordinary
generating function of the sequence $( L^{(r)}_n  (1, t))_{n\geq 1}$ is given by}
\begin{equation}\label{e3.13}
\sum\limits_{n\geq 1} L^{(r)}_{n} (1, t)    x^n =\frac{x +rt x^r}{1-x-tx^r}.
\end{equation}
and

\vspace{.2 in} \noindent \textbf{Corollary} \textbf{3.2.2.}\hspace{.003in} \textit{The ordinary
generating function of the sequence $( L^{(r)}_n ( -1, t))_{n\geq 1}$ is given by}
\begin{equation}\label{e3.14}
\sum\limits_{n\geq 1} L^{(r)}_n (-1, t) x^n = \frac{x+x^2 -rt x^r -(r-1)tx^{r+1} -rt^2x^{2r}}{1-x^2 +
t^2 x^{2r}}.
\end{equation}\vspace{.1in}

When $r=2$ and $t=1$ in (3.14), we get
\begin{equation}\label{e3.15}
\sum\limits_{n\geq 1} L^{(2)}_n (-1, 1) x^n =\frac{x-x^2-x^3-2x^4}{1-x^2+x^4} = \frac{(x-x^2-3x^4 -x^5
-2x^6)(1-x^6)}{1-x^{12}},
\end{equation}
which implies

\vspace{.2 in} \noindent \textbf{Corollary}
\textbf{3.2.3.}\hspace{.003in} \textit{The sequence $( L^{(2)}_n (
-1, 1))_{n\geq 1}$ is periodic with period $12$; namely, if
$a_n:=L^{(2)}_n ( -1, 1)$ for ${n\geq 1},$ then $a_1=1,$ $a_2=-1,$
$a_3=0,$ $a_4=-3,$ $a_5=-1,$ and  $a_6=-2$ with $a_{n+6}=-a_n,$
$n\geq 1$.}\vspace{.1in}

\noindent This periodic behavior is again restricted to the case $r=2$.

\begin{theo}
The sequence $( L^{(r)}_n ( -1, 1))_{n\geq 1}$ is never periodic for $r\geq 3.$
\end{theo}

\begin{proof}
By \eqref{e3.14} at $t=1$, we must show that $f(x):=1-x^2+x^{2r}$ does not divide the product
$(1-x^m)h(x)$, where $h(x):=x+x^2-rx^r-(r-1)x^{r+1}-rx^{2r},$ for any $m\in\mathbb{P}$ whenever $r\geq
3$. By the proof of Theorem 2.4, it suffices to show that $f$ and $h$ are relatively prime. Suppose, to
the contrary, that $t_0$ is a common zero of $f$ and $h$ so that
$t_0(1+t_0)+r(1-t_0^2)=t_0(1+t_0)-rt_0^{2r}=t_0^r[r+(r-1)t_0]$. Squaring, substituting
$t_0^{2r}=t_0^2-1$, and noting $t_0\neq -1$ implies that $t_0$ must then be a root of the equation
$(x+1)\left[(r-1)x-r\right]^2=(x-1)[(r-1)x+r]^2,$ which reduces to $(r^2-1)x^2=r^2.$ But $t_0=\pm
\frac{r}{\sqrt{r^2-1}}$ is a zero of neither $f$ nor $h$ after all, which implies $f$ and $h$ are
relatively prime and completes the proof.
\end{proof}

Recall that $F_{-i}^{(r)}(q,t)=0$ if $1\leq i\leq r-1,$ by convention.

\begin{theo} Let $m\in \mathbb{P}$. If $r$ is even, then

\begin{equation}\label{e3.16}
L^{(r)}_{2m} (-1, t) =  L^{(r)}_m (1, -t^2)-rt F_{m-\frac{r}{2}}^{(r)}(1,-t^2)\\
\end{equation}
and
\begin{equation}\label{e3.17}
L^{(r)}_{2m-1} (-1, t) =  F^{(r)}_{m-1} (1, -t^2)-(r-1)t F_{m-\frac{r}{2}-1}^{(r)}(1,-t^2),\\
\end{equation}
and if $r$ is odd, then
\begin{equation}\label{e3.18}
L^{(r)}_{2m} (-1, t) =  L^{(r)}_m (1, -t^2)-(r-1)t F_{m-\left(\frac{r+1}{2}\right)}^{(r)}(1,-t^2)\\
\end{equation}
and
\begin{equation}\label{e3.19}
L^{(r)}_{2m-1} (-1, t) =  F^{(r)}_{m-1} (1, -t^2)-rt F_{m-\left(\frac{r+1}{2}\right)}^{(r)}(1,-t^2).\\
\end{equation}
\end{theo}




\begin{proof}
Taking the even and odd parts of both sides of \eqref{e3.14} followed by replacing $x$ with $x^{1/2}$
yields
\begin{equation*}
\sum\limits_{m\geq 1} L^{(r)}_{2m} (-1, t) x^m =\frac{x -rt x^{\frac{r}{2}}-rt^2 x^r}{1-x +t^2 x^r}
\end{equation*}
and
\begin{equation*}  \sum\limits_{m\geq 1} L^{(r)}_{2m-1} (-1, t) x^m = \frac{x-(r-1)tx^{\frac{r}{2}+1}}
{1-x+t^2x^r},
\end{equation*}
when $r$ is even, and
\begin{equation*}
\sum\limits_{m\geq 1} L^{(r)}_{2m} (-1, t) x^m =\frac{x -(r-1)t x^{\frac{(r+1)}{2}}-rt^2 x^r}{1-x +t^2
x^r}
\end{equation*}
and \begin{equation*}\sum\limits_{m\geq 1} L^{(r)}_{2m-1} (-1, t) x^m = \frac{x-rtx^{\frac{(r+1)}{2}}}
{1-x+t^2x^r},
\end{equation*}
when $r$ is odd, from which  \eqref{e3.16}$-$\eqref{e3.19} now follow from \eqref{e3.13} and
\eqref{e2.10}.

For a combinatorial proof of \eqref{e3.16}$-$\eqref{e3.19}, we first assign to each covering $c\in
\mathcal{C}^{(r)}_n$ the weight $w_c:= (-1)^{\pi(c)} t^{v(c)}$, where $t$ is an indeterminate. Let
$\mathcal{C}^{(r)^\prime}_n$ consist of those $c$ in $\mathcal{C}^{(r)}_n$ whose associated word
$u_c=u_1 u_2\cdots$ satisfies the conditions $u_{2i}=u_{2i+1,}$  $i\geq 1 $.  Suppose  $c\in
\mathcal{C}^{(r)}_n-\mathcal{C}^{(r)^\prime}_n$, with $i_0$ being the smallest value of $i$ for which
$u_{2i}\not= u_{2i+1}$. Exchanging the positions of the $(2i_0)^{th}$ and $(2i_0+1)^{st}$ pieces within
$c$ produces a $\pi$-parity changing, $v$-preserving involution of $\mathcal{C}^{(r)}_n
-\mathcal{C}^{(r)^\prime}_n$.

If $r$ is even and $n=2m$, then
\begin{eqnarray*}
L^{(r)}_{2m} (-1, t)
 &=&  \sum\limits_{c\in \mathcal{C}^{(r)}_{2m}} w_c =  \sum\limits_{c\in \mathcal{C}^{(r)^\prime}_{2m}} w_c
 =\sum\limits_{\substack{c\in \mathcal{C}^{(r)^\prime}_{2m}\\v(c) \text{ even}}} w_c
+ \sum\limits_{\substack{c\in \mathcal{C}^{(r)^\prime}_{2m}\\v(c) \text{ odd}}}w_c \\
&=&\sum\limits_{\substack{c\in \mathcal{C}^{(r)^\prime}_{2m}\\v(c) \text{ even}}} (-1)^{v(c)/2} t^{v(c)}
- rt
 \sum\limits_{\substack{c\in \mathcal{R}^{(r)^\prime}_{2m-r}\\v(c) \text{ even}}} (-1)^{v(c)/2} t^{v(c)} \\
&=&\sum\limits_{z\in \mathcal{C}^{(r)}_{m}} (-1)^{v(z)} t^{2v(z)} -rt
 \sum\limits_{z\in \mathcal{R}^{(r)}_{m-\frac{r}{2}}} (-1)^{v(z)} t^{2v(z)}\\
&=& L^{(r)}_{m} (1, -t^2) - rt F^{(r)}_{m- \frac{r}{2}} (1, -t^2),
\end{eqnarray*}
which gives \eqref{e3.16}, where $\mathcal{R}^{(r)^\prime}_n$ is as in the proof of Theorem 2.5, since
members of $\mathcal{C}^{(r)^\prime}_{2m}$ with $v(c)$ even must begin and end with the same type of
piece, while members with $v(c)$ odd must have $u_1=r$ in $u_c$ with $r$ possibilities for the position
of its initial segment. Similarly, if $r$ is odd and $n=2m-1$, then
\begin{eqnarray*}
L^{(r)}_{2m-1} (-1, t)
 &=& \sum\limits_{c\in \mathcal{C}^{(r)^\prime}_{2m-1}} w_c =
 \sum\limits_{\substack{c\in \mathcal{C}^{(r)^\prime}_{2m-1}\\u_1=s}} w_c
+ \sum\limits_{\substack{c\in \mathcal{C}^{(r)^\prime}_{2m-1}\\u_1=r}}w_c \\
&=& \sum\limits_{c\in \mathcal{R}^{(r)^\prime}_{2m-2}} w_c-rt
\sum\limits_{c\in \mathcal{R}^{(r)^\prime}_{2m-r-1}} w_c \\
&=&  F^{(r)}_{m-1} (1, -t^2) - rt F^{(r)}_{m-\left( \frac{r+1}{2}\right)} (1, -t^2),
\end{eqnarray*}
which gives \eqref{e3.19}.

For the cases that remain, let
$\mathcal{C}^{(r)^\ast}_{n}\subseteq\mathcal{C}^{(r)^\prime}_{n}$
such that
$\mathcal{C}^{(r)^\prime}_{n}-\mathcal{C}^{(r)^\ast}_{n}$
comprises those $c$ which satisfy the following additional
conditions:

\begin{enumerate}
\item[(i)] $c$ contains an even number of pieces in all;

\item[(ii)] $u_1\neq u_p$ in $u_c=u_1u_2\cdots u_p$;

\item[(iii)] if $u_1=r$, then 1 corresponds to the initial segment of the $r$-mino covering it.\\

\end{enumerate}
\noindent Pair members of $\mathcal{C}^{(r)^\prime}_{n}-\mathcal{C}^{(r)^\ast}_{n}$ of opposite
$\pi$-parity as follows: given $c\in\mathcal{C}^{(r)^\prime}_{n}-\mathcal{C}^{(r)^\ast}_{n}$, let $c'$
be the covering resulting when $u_c=u_1u_2\cdots u_p$ is read backwards.

If $r$ is even and $n=2m-1$, then

\begin{eqnarray*}
L^{(r)}_{2m-1} (-1, t)
 &=& \sum\limits_{c\in \mathcal{C}^{(r)}_{2m-1}} w_c =
 \sum\limits_{c\in \mathcal{C}^{(r)^\ast}_{2m-1}} w_c=
 \sum\limits_{\substack{c\in \mathcal{C}^{(r)^\ast}_{2m-1}\\u_1=s}} w_c
+ \sum\limits_{\substack{c\in \mathcal{C}^{(r)^\ast}_{2m-1}\\u_1=r}}w_c \\
&=& \sum\limits_{\substack{c\in \mathcal{R}^{(r)^\prime}_{2m-2}\\v(c) \text{ even}}} w_c-(r-1)t
\sum\limits_{\substack{c\in \mathcal{R}^{(r)^\prime}_{2m-r-2}\\v(c) \text{ even}}} w_c \\
&=&  F^{(r)}_{m-1} (1, -t^2) - (r-1)t F^{(r)}_{m-\frac{r}{2}-1} (1, -t^2),
\end{eqnarray*}
which gives \eqref{e3.17}, since members of $\mathcal{C}^{(r)^\ast}_{2m-1}$ with $u_1=s$ must end in a
double letter, while those with $u_1=r$ must end in a single $s$ with 1 not corresponding to the initial
segment of the $r$-mino covering it. Similarly, if $r$ is odd and $n=2m$, then
\begin{eqnarray*}
L^{(r)}_{2m} (-1, t)
 &=&  \sum\limits_{c\in \mathcal{C}^{(r)^\ast}_{2m}} w_c
 =\sum\limits_{\substack{c\in \mathcal{C}^{(r)^\ast}_{2m}\\u_1=u_p}} w_c
+ \sum\limits_{\substack{c\in \mathcal{C}^{(r)^\ast}_{2m}\\u_1\neq u_p}}w_c \\
&=&\sum\limits_{\substack{c\in \mathcal{C}^{(r)^\ast}_{2m}\\u_1=u_p}} (-1)^{v(c)/2} t^{v(c)} - (r-1)t
 \sum\limits_{\substack{c\in \mathcal{R}^{(r)^\prime}_{2m-r-1}}} (-1)^{v(c)/2} t^{v(c)} \\
&=&\sum\limits_{z\in \mathcal{C}^{(r)}_{m}} (-1)^{v(z)} t^{2v(z)} -(r-1)t
 \sum\limits_{z\in \mathcal{R}^{(r)}_{m-\left(\frac{r+1}{2}\right)}} (-1)^{v(z)} t^{2v(z)}\\
&=& L^{(r)}_{m} (1, -t^2) - (r-1)t F^{(r)}_{m- \left(\frac{r+1}{2}\right)} (1, -t^2),
\end{eqnarray*}
which gives \eqref{e3.18}.
\end{proof}

\section{Variants of the $\pi$ Statistic}

Modifying the $\pi$ statistic of the previous section in different ways yields additional polynomial
generalizations of $L_n^{(r)}$. In this section, we look at some specific variants of the $\pi$
statistic on circular $r$-mino arrangements, taking $r=2$ for simplicity. We'll use the notation
$\mathcal{C}_n=\mathcal{C}_n^{(2)}$, $\mathcal{C}_{n,k}=\mathcal{C}_{n,k}^{(2)}$, and
$F_n(q,t)={F}_n^{(2)}(q,t).$

We first partition $\mathcal{C}_n$ as follows: let $\overrightarrow{\mathcal{C}}_n$ comprise those
coverings in which 1 is covered by a square or by an initial segment of a domino and let
$\overleftarrow{\mathcal{C}}_n$ comprise those coverings in which 1 is covered by the second segment of
a domino.

Define the statistic $\pi_1$ on $\mathcal{C}_n$ by

\begin{equation}\label{e4.1}
\pi_1(c)= \begin{cases} \pi(c), &\text{\emph{if} $c\in\overrightarrow{\mathcal{C}}_n$;}\\
\pi(c)-2v(c)+n, &\text{\emph{if} $c\in\overleftarrow{\mathcal{C}}_n$.}\end{cases}
\end{equation}
Note that $\pi_1(c)$ gives the sum of the numbers obtained by
counting back counterclockwise the pieces from each domino to the
piece covering 2 whenever $c\in\overleftarrow{\mathcal{C}}_n$.

\begin{theo}
For all $n\in\mathbb{P},$
\begin{equation}\label{e4.2}
\sum_{c\in\mathcal{C}_n}q^{\pi_1(c)}t^{v(c)}=\sum_{0\leq k\leq \lfloor
    n/2\rfloor}q^{\binom{k+1}{2}}\left[\frac{(n-k)_q+q^{n-2k}k_q}{(n-k)_q}\right]\binom{n-k}{k}_qt^k.
\end{equation}
\end{theo}

\begin{proof}
By \eqref{e2.8} when $r=2$,
\begin{eqnarray*}
\sum_{c\in\mathcal{C}_{n,k}}q^{\pi_1(c)}&=&q^{\binom{k+1}{2}}\binom{n-k}{k}_q+q^{\binom{k}{2}+k+(n-2k)}\binom{n-k-1}{k-1}_q\\
&=&q^{\binom{k+1}{2}}\left[\binom{n-k}{k}_q+q^{n-2k}\frac{k_q}{(n-k)_q}\binom{n-k}{k}_q\right]\\
&=&q^{\binom{k+1}{2}}\left[\frac{{(n-k)}_q+q^{n-2k}k_q}{(n-k)_q}\right]\binom{n-k}{k}_q.\\
\end{eqnarray*}
\end{proof}

If $\hat{L}_n(q,t)$ denotes the distribution polynomial in \eqref{e4.2}, then
\begin{equation}\label{e4.3}
\hat{L}_n(q,t)=F_n(q,t)+q^{n-1}tF_{n-2}(q,t/q),\quad n\geq 1,
\end{equation}
by \eqref{e4.2} and \eqref{e2.8}, or by considering whether or not
$c$ belongs to $\overrightarrow{\mathcal{C}}_n$.  The
$\hat{L}_n(q,t)$ satisfy the nice recurrence
\begin{equation}\label{e4.4}
\hat{L}_n(q,t)=\hat{L}_{n-1}(q,qt)+qt\hat{L}_{n-2}(q,qt),\quad n\geq 3,
\end{equation}
with $\hat{L}_1(q,t)=1$ and $\hat{L}_2(q,t)=1+2qt$, the first term of \eqref{e4.4} accounting for those
$c\in\overrightarrow{\mathcal{C}}_n$ where 1 is covered by a square as well as those
$c\in\overleftarrow{\mathcal{C}}_n$ where 2 is covered by a square and the second term accounting for
the cases that remain.

Next define $\pi_2$ on $\mathcal{C}_n$ by
\begin{equation}\label{e4.5}
\pi_2(c)= \begin{cases} \pi(c), &\text{\emph{if} $c\in\overrightarrow{\mathcal{C}}_n$;}\\
\pi(c)-v(c), &\text{\emph{if} $c\in\overleftarrow{\mathcal{C}}_n$.}\end{cases}
\end{equation}

\begin{theo}
For all $n\in\mathbb{P},$
\begin{equation}\label{e4.6}
\sum_{c\in\mathcal{C}_n}q^{\pi_2(c)}t^{v(c)}=\sum_{0\leq k\leq \lfloor
    n/2\rfloor}q^{\binom{k}{2}}\frac{n_q}{(n-k)_q}\binom{n-k}{k}_qt^k.
\end{equation}
\end{theo}

\begin{proof}
By \eqref{e2.8} when $r=2$,
\begin{eqnarray*}
\sum_{c\in\mathcal{C}_{n,k}}q^{\pi_2(c)}&=&q^{\binom{k+1}{2}}\binom{n-k}{k}_q+q^{\binom{k}{2}+k-k}\binom{n-k-1}{k-1}_q\\
&=&q^{\binom{k}{2}}\left[\frac{q^k{(n-k)}_q+k_q}{(n-k)_q}\right]\binom{n-k}{k}_q\\
&=&q^{\binom{k}{2}}\frac{{n}_q}{(n-k)_q}\binom{n-k}{k}_q.
\end{eqnarray*}
\end{proof}

Theorem 4.2 provides a combinatorial interpretation of the generalized Lucas polynomials
\begin{equation}\label{e4.7}
{Luc}_n(x,t):=\sum_{0\leq k\leq \lfloor
    n/2\rfloor}q^{\binom{k}{2}}\frac{n_q}{(n-k)_q}\binom{n-k}{k}_qx^{n-2k}t^k,
\end{equation}
studied by Cigler \cite{cigler0,cigler1}. Note that the joint distribution of $\pi_2$ and $v$ on $\mathcal{C}_n$ is
${Luc}_n(1,t)$, with the $x$ variable of ${Luc}_n(x,t)$ recording the number of squares in $c\in
\mathcal{C}_n$. Considering whether or not $c$ belongs to $\overrightarrow{\mathcal{C}}_n$ leads
directly to the relation (cf.\ \cite{cigler1})
\begin{equation}\label{e4.8}
{Luc}_n(1,t)=F_n(q,t)+tF_{n-2}(q,t),\quad n\geq 1.
\end{equation}
The ${Luc}_n(1,t)$ do not seem to satisfy a two-term recurrence like (\ref{e3.7}) or (\ref{e4.4}).

 Similar reasoning shows that ${Luc}_n(1,t)$ is also the joint distribution of the statistics $\pi_3$
and $v$ on $\mathcal{C}_n$, where
\begin{equation}\label{e4.9}
\pi_3(c)= \begin{cases} \pi(c)-v(c), &\text{\emph{if} $c\in\overrightarrow{\mathcal{C}}_n$;}\\
\pi(c)-2v(c)+n, &\text{\emph{if} $c\in\overleftarrow{\mathcal{C}}_n$,}\end{cases}
\end{equation}
which yields the relation
\begin{equation}\label{e4.10}
Luc_n(1,t)=F_n(q,t/q)+q^{n-1}tF_{n-2}(q,t/q),\quad n\geq 1.
\end{equation}

The $\pi_2$ statistic on $\mathcal{C}_n$ can be generalized to $\mathcal{C}_n^{(r)}$ by letting
$\pi_2(c)=\pi(c),$ if the number 1 is covered by a square or an initial segment of an $r$-mino, and
letting $\pi_2(c)=\pi(c)-v(c),$ otherwise. Reasoning as in Theorem 4.2 with $\pi_2$ on
$\mathcal{C}_n^{(r)}$ leads to
\begin{equation}\label{e4.11}
Luc_n^{(r)}(x,t):=\sum_{0\leqslant k\leqslant\lfloor n/r\rfloor}q^{\binom{k}{2}}
\left[\frac{(r-2)k_q+(n-(r-2)k)_q}{(n-(r-1)k)_q}\right]\binom{n-(r-1)k}{k}_q x^{n-rk}t^k,
\end{equation}

\vspace{0.5cm}

\noindent which generalizes $ Luc_n(x,t).$ The $Luc_n^{(r)}(x,t)$ are connected with the $F^{(r)}_n
(q,t)$ by the simple relation
\begin{equation}\label{e4.12}
Luc_n^{(r)}(1,t)=F^{(r)}_n (q,t)+(r-1)tF^{(r)}_{n-r} (q,t),\qquad n\geqslant 1,
\end{equation}
which generalizes \eqref{e4.8}.

\section*{Acknowledgment}
The authors would like to thank the anonymous referee for formulas \eqref{e2.8'}, \eqref{e2.9'},
\eqref{e4.11}, and \eqref{e4.12}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{thebibliography}{99}

%1
\bibitem{carlitz}
        L. Carlitz, Fibonacci notes 3: $q$-Fibonacci polynomials, {\em
        Fibonacci Quart.} {\bf 12} (1974), 317--322.

%2
\bibitem{cigler0}
        J. Cigler, Einige $q$-Analoga der Lucas- and Fibonacci-Polynome, {\em 
\"Osterreich.\ Akad.\ Wiss.\ Math.-Natur.\ Kl.\ Sitzungsber.\ II}
        {\bf 211} (2002), 3--20.

%3
\bibitem{cigler1}
        J. Cigler, A new class of $q$-Fibonacci polynomials, \href{http://www.combinatorics.org/Volume_10/Abstracts/v10i1r19.html}{\em Electron.  J. Combin.}
	{\bf 10} (2003), \#R19.

%4
\bibitem{cigler2}
        J. Cigler, Some algebraic aspects of Morse code sequences,
        {\em Discrete Math. Theor. Comput. Sci.}
        {\bf 6} (2003), 55--68.

%5
\bibitem{cigler3}
        J. Cigler, $q$-Fibonacci polynomials and the Rogers-Ramanujan
        identities, {\em Ann. Combin.} {\bf 8} (2004), 269--285.

%6
\bibitem{Ekhad}
        S. Ekhad and D. Zeilberger, \href{http://www.combinatorics.org/Volume_3/Abstracts/v3i1r2.html}{The number of solutions of $X^2=0$ in triangular matrices over GF($q$)}, {\em Electron.
        J. Combin.} {\bf 3} (1) (1996), \#R2.
%7
\bibitem{Kuper}
        B. Kupershmidt, $q$-Analogues of classical 6-periodicity, {\em J. Nonlinear Math. Physics}
        {\bf 10} (2003), 318--339.

%8
\bibitem{shattuck1}
M. Shattuck and C. Wagner, \href{http://www.combinatorics.org/Volume_12/Abstracts/v12i1n10.html}{Parity theorems for statistics on domino arrangements}, {\em Electron. J.
Combin.} {\bf 12} (2005), \#N10.

%9
\bibitem{shattuck2}
M. Shattuck and C. Wagner, \href{http://www.combinatorics.org/Volume_13/Abstracts/v13i1r42.html}{A new statistic on linear and circular $r$-mino arrangements}, {\em Electron.
J. Combin.} {\bf 13} (1) (2006), \#R42.

%10
\bibitem{stanley1} R. Stanley, {\em Enumerative Combinatorics, Vol.} {\em I},
        Wadsworth and Brooks/Cole, 1986.

%11
\bibitem{wagner1} C. Wagner, Generalized Stirling and Lah numbers,
        {\em Discrete Math.} {\bf 160} (1996), 199--218.

%12
\bibitem{wilf1} H. Wilf, {\em generatingfunctionology}, Academic Press,
        1990.

\end{thebibliography}

\bigskip
\hrule
\bigskip

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

\noindent {\em Keywords:} $r$-mino arrangement, polynomial
generalization, Fibonacci numbers, Lucas numbers.

\bigskip
\hrule
\bigskip


\noindent (Concerned with sequences
\seqnum{A000045} and \seqnum{A000204}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 4 2006;
revised version received August 17 2006.
Published in {\it Journal of Integer Sequences}, August 18 2006.

\bigskip
\hrule
\bigskip

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


\end{document}