\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, rotating}
%\usepackage{amsfonts}
%\usepackage{amssymb}
\usepackage{mathrsfs}
\usepackage{epic}
\usepackage{curves}
%\usepackage{amsthm}

\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 
Some Generalized Fibonacci Polynomials}
\vskip 1cm
\large
Mark A. Shattuck\\
Mathematics Department\\
University of Tennessee\\
Knoxville, TN 37996-1300\\
USA\\
\href{mailto:shattuck@math.utk.edu}{\tt shattuck@math.utk.edu} \\

\bigskip

Carl G. Wagner\\
Mathematics Department\\
University of Tennessee\\
Knoxville, TN 37996-1300\\
USA\\
\href{mailto:wagner@math.utk.edu}{\tt wagner@math.utk.edu}

\end{center}

\vskip .2 in

\begin{abstract}
We introduce polynomial generalizations of the $r$-Fibonacci,
$r$-Gibonacci, and $r$-Lucas sequences
which arise in connection with two statistics defined,
respectively, on linear, phased, and circular
$r$-mino arrangements.
\end{abstract}


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


\newcommand{\sqbinom}[2]{\begin{bmatrix}#1\\#2\end{bmatrix}}
\numberwithin{equation}{section}

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

\section{Introduction}
In what follows, $\mathbb{Z}$, $\mathbb{N}$, and $\mathbb{P}$ denote, respectively, the integers, the
nonnegative integers, and the 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.1}
\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}
The $\binom{n}{k}_q$ are also given, equivalently,
by  the column generating function \cite[pp.\ 201--202]{wagner1}
\begin{equation}\label{e1.2}
\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}

 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 distribution polynomials for statistics
on binary words \cite{carlitz1}, lattice paths \cite{cigler4},
Morse code sequences \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{cigler3} as well as on linear and circular $r$-mino
arrangements \cite{shattuck2,shattuck3}.

In the next section, we consider the $q$-generalization
\begin{equation}\label{e1.3}
F_n^{(r)}(q,t):=\sum_{0 \leq k \leq \lfloor n/r \rfloor} q^{k+r\binom{k}{2}}\binom{n-(r-1)k}{k}_qt^k
\end{equation}
of $F_n^{(r)}$. The $r=2$ case of \eqref{e1.3} or close variants thereof have appeared  several times in
the literature starting with Carlitz  
(see, e.g., \cite{carlitz1,carlitz2,cigler1,cigler4,shattuck1}.
The $F_n^{(r)}(q,t)$ arise
as joint distribution polynomials for two statistics on linear $r$-mino arrangements which naturally
extend well known statistics on domino arrangements. When defined, more broadly, on phased $r$-mino
arrangements, these statistics lead to a further generalization of the $F_n^{(r)}(q,t)$ which we denote
by $G_n^{(r)}(q,t)$. In the third section, we consider the $q$-generalization
\begin{equation}\label{e1.4}
L_n^{(r)}(q,t):=\sum_{0 \leq k \leq \lfloor n/r \rfloor}
q^{k+r\binom{k}{2}}\left[\frac{n_q}{(n-(r-1)k)_q}\right]\binom{n-(r-1)k}{k}_qt^k
\end{equation}
of $L_n^{(r)}$, which arises as the joint distribution polynomial for the same two statistics, now
defined on circular $r$-mino arrangements. The $r=2$ case of \eqref{e1.4} was introduced by Carlitz \cite{carlitz1}
and has been subsequently studied (see, e.g., \cite{shattuck1}).



\section{Linear and Phased $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 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 $c\in \mathcal{R}_n^{(r)},$ let $v(c):=$ the number of $r$-minos in the covering $c$, let
$\sigma(c):=$ the sum of the numbers covered by the leftmost segments of each of these $r$-minos, and
let
\begin{equation}\label{e2.5}
F_n^{(r)}(q,t) := \sum_{c \in \mathcal{R}_n^{(r)}} q^{\sigma(c)} t^{v(c)}, \qquad n \in \mathbb{N}.
\end{equation}
Categorizing linear covers of $1,2,\dots,n$ according to the final and initial pieces, respec\-tively,
yields the recurrences
\begin{equation}\label{e2.6}
F_n^{(r)}(q,t) = F_{n-1}^{(r)}(q,t) + q^{n-r+1}tF_{n-r}^{(r)}\left(q,t\right), \qquad n \geq r,
\end{equation}
\noindent and
\begin{equation}\label{e2.7}
F_n^{(r)}(q,t)=F_{n-1}^{(r)}(q,qt)+qtF_{n-r}^{(r)}(q,q^rt), \qquad n\geqslant r,
\end{equation}
\\
\noindent where $F_0^{(r)}(q,t)=F_1^{(r)}(q,t)=\cdots=F_{r-1}^{(r)}(q,t)=1$. Iterating \eqref{e2.6} or
\eqref{e2.7} gives $F_{-i}^{(r)}(q,t)=0$ if $1\leqslant i\leqslant r-1$ with
$F_{-r}^{(r)}(q,t)=q^{r-1}t^{-1},$ which we'll take as a convention.

With the ordinary generating function
\begin{equation}\label{e2.8}
\Phi^{(r)}(x,q,t):=\sum_{n\geqslant 0}F_n^{(r)}(q,t)x^n,
\end{equation}
recurrence (\ref{e2.6}) is equivalent to the identity
\begin{equation}\label{e2.9}
\Phi^{(r)}(x,q,t)=1+x\Phi^{(r)}(x,q,t)+qtx^r\Phi^{(r)}(qx,q,t),
\end{equation}
which may be rewritten, with the operator $\varepsilon f(x):=f(qx)$, as
\begin{equation*}
(1-x-qtx^r\varepsilon)\Phi^{(r)}(x,q,t)=1,\nonumber
\end{equation*}
or
\begin{equation}\label{e2.10}
 \left(1-\frac{qtx^r}{1-x}\varepsilon\right)\Phi^{(r)}(x,q,t)=\frac{1}{1-x}.
\end{equation}
From (\ref{e2.10}), we immediately get
$$\Phi^{(r)}(x,q,t)=\sum_{k\geqslant0}\left(\frac{qtx^r}{1-x}\varepsilon\right)^k \frac{1}{1-x},$$
which implies
\begin{theo}
\begin{eqnarray}\label{e2.11}
\Phi^{(r)}(x,q,t)=\sum_{k\geqslant0}\frac{q^{k+r\binom{k}{2}}t^kx^{rk}}{(1-x)(1-qx)\cdot\cdot\cdot(1-q^kx)}.
\end{eqnarray}
\end{theo}
By (\ref{e2.11}) and (\ref{e1.2}),
\begin{eqnarray*}
\Phi^{(r)}(x,q,t)&=&\sum_{k\geqslant0}q^{k+r\binom{k}{2}}t^kx^{(r-1)k}\cdot\frac{x^k}{(1-x)(1-qx)\cdot\cdot\cdot(1-q^kx)}\\
&=&\sum_{k\geqslant0}q^{k+r\binom{k}{2}}t^kx^{(r-1)k}\sum_{n\geqslant
rk}\binom{n-(r-1)k}{k}_qx^{n-(r-1)k}\\
&=&\sum_{n\geqslant0}\left(\sum_{0\leqslant k\leqslant \lfloor
n/r\rfloor}q^{k+r\binom{k}{2}}\binom{n-(r-1)k}{k}_qt^k\right)x^{n},
\end{eqnarray*}
which establishes the explicit formula:
\begin{theo}
For all $n \in \mathbb{N}$,
\begin{equation}\label{e2.12}
F_n^{(r)}(q,t) = \sum_{0 \leq k \leq \lfloor n/r \rfloor} q^{k+r\binom{k}{2}} \binom{n - (r-1)k}{k}_{q}
t^k.
\end{equation}
\end{theo}

\ \

\ \

\noindent{\it Remark:} Cigler \cite{cigler3} has studied algebraically the polynomials
$$F_n(j,x,s,q):=\sum_{0\leqslant jk\leqslant n-j+1}q^{j\binom{k}{2}}\binom{n-(j-1)(k+1)}{k}_q
s^kx^{n-j(k+1)+1}, \quad n\geqslant 0,$$ which, by \eqref{e2.12}, are related to the $F_n^{(r)}(q,t)$ by
\begin{equation}\label{e2.13}
F_n(j,x,s,q)= x^{n-j+1}F_{n-j+1}^{(j)}\left(q, \frac{s}{qx^j}\right), \quad n \geqslant 0.
\end{equation}
From \eqref{e2.5} and \eqref{e2.13}, one gets a combinatorial interpretation for the $F_n(j,x,s,q)$ in
terms of $j$-mino arrangements; viz., $F_n(j,x,s,q)$ is the joint distribution polynomial for the
statistics on $\mathcal{R}_{n-j+1}^{(j)}$ recording the number of squares, the number of $j$-minos, and
the sum of the numbers directly preceding leftmost segments of $j$-minos.

\ \

\ \

Note that (\ref{e2.11}) and (\ref{e2.12}) reduce, respectively, to (\ref{e2.4}) and (\ref{e2.3}) when
$q=t=1$. Setting $q=1$ and $q=-1$ in (\ref{e2.11}) gives
\begin{cor}\label{c2.3}
\begin{equation}\label{e2.14}
\Phi^{(r)}(x,1,t)=\frac{1}{1-x-tx^r}.
\end{equation}
\end{cor}
\noindent and
\begin{cor}
\begin{equation}\label{e2.15}
\Phi^{(r)}(x,-1,t)=\frac{1+x-tx^r}{1-x^2+(-1)^{r+1}t^2x^{2r}}.
\end{equation}
\end{cor}

Taking the even and odd parts of both sides of \eqref{e2.15}, replacing $x$ with $x^{1/2},$ and applying
\eqref{e2.14} yields

\vspace{0.25cm}

\begin{theo}\label{teo2.3}
Let $m\in \mathbb{N}$. If $m$ and $r$ have the same parity, then
\begin{equation}\label{e2.16}
F_m^{(r)}(-1,t)=F_{\lfloor m/2 \rfloor}^{(r)}(1,(-1)^rt^2)-tF_{(m-r)/2}^{(r)}(1,(-1)^rt^2),
\end{equation}
and if $m$ and $r$ have different parity, then
\begin{equation}\label{e2.17}
F_m^{(r)}(-1,t)=F_{\lfloor m/2 \rfloor}^{(r)}(1,(-1)^rt^2).
\end{equation}
\end{theo}
\vspace{0.25cm} \noindent One can provide combinatorial proofs of (\ref{e2.16}) and (\ref{e2.17})
similar to those in \cite{shattuck2,shattuck3} given for comparable formulas involving other $q$-Fibonacci
polynomials.

\vspace{0.25cm}

The $F_n^{(r)}(q,t)$ may be generalized as follows:

If $r\geqslant 2$ and $a,b\in\mathbb{P},$ then define the sequence $(G_n^{(r)})_{n\in\mathbb{Z}}$ by the
recurrence $G_n^{(r)}=G_{n-1}^{(r)}+G_{n-r}^{(r)}$ for all $n\in\mathbb{Z}$ with the initial conditions
$G_{-(r-2)}^{(r)}=\cdots= G_{-1}^{(r)}=0,$ $G_0^{(r)}=a,$ and $G_1^{(r)}=b.$ When $r=2,$ these are the
{\it Gibonacci numbers} $G_n$ (shorthand for {\it generalized Fibonacci numbers}) occurring in Benjamin
and Quinn \cite[p.\ 17]{benjamin2}. When $a=b=1$ and $a=r,$ $b=1,$ the $G_n^{(r)}$ reduce to the $r$-Fibonacci and
$r$-Lucas numbers, respectively. We'll call the $G_n^{(r)}$ {\it $r$-Gibonacci numbers.}

From the initial conditions and recurrence, one sees that the $G_n^{(r)}$, when $n\geqslant 1$, count
linear $r$-mino coverings of length $n$ in which an initial $r$-mino is assigned one of $a$ phases and
an initial square is assigned one of $b$ phases. We'll call such coverings {\it phased r-mino tilings}
({\it of length} $n$), in accordance with Benjamin and Quinn 
\cite{benjamin1,benjamin2} in the case $r=2$. Let
$\widehat{\mathcal{R}}_{n}^{(r)}$ be the set consisting of these phased tilings and let
\begin{eqnarray}\label{e2.18}
    G_{n}^{(r)}(q,t):=\sum_{c\in\widehat{\mathcal{R}}_{n}^{(r)}}q^{\sigma(c)}t^{v(c)}, \quad n\geqslant
    1,
\end{eqnarray}
where the $\sigma$ and $v$ statistics on $\widehat{\mathcal{R}}_{n}^{(r)}$ are defined as above. When
$a=b=1,$ the $G_n^{(r)}(q,t)$ reduce to the $F_n^{(r)}(q,t)$.

Conditioning on the final and initial pieces of a phased $r$-mino tiling yields the re\-spective
recurrences
\begin{eqnarray}\label{e2.19}
    G_{n}^{(r)}(q,t)=G_{n-1}^{(r)}(q,t)+q^{n-r+1}t G_{n-r}^{(r)}(q,t), \quad n\geqslant r+1,
\end{eqnarray}
and
\begin{eqnarray}\label{e2.20}
    G_{n}^{(r)}(q,t)=bF_{n-1}^{(r)}(q,qt)+aqtF_{n-r}^{(r)}(q,q^r t), \quad n\geqslant r+1,
\end{eqnarray}
with $G_1^{(r)}(q,t)=\cdots=G_{r-1}^{(r)}(q,t)=b$ and $G_{r}^{(r)}(q,t)=b+aqt.$ From \eqref{e2.20},
 one gets formulas for $G_n^{(r)}(q,t)$ similar to those for
 $F_n^{(r)}(q,t).$ For example, taking $a=r$, $b=1$ in \eqref{e2.20}, and applying \eqref{e2.12}, yields

\begin{eqnarray}\label{e2.21}
    \widehat{L}_{n}^{(r)}(q,t):=\sum_{0\leqslant k\leqslant\lfloor n/r\rfloor}q^{k+r\binom{k}{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{eqnarray}
a $q$-generalization of the $r$-Lucas numbers.

\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}_{5,1}^{(4)}$: \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){-220}}
    \put(25,25){\arc(-1.5,8){-230}}
    \drawline(15,11)(19.5,18.5)
    \drawline(23,33)(23,42)

    \drawline(7,22)(7,31)
    \drawline(15,22)(15,31)
    \drawline(7,31)(15,31)
    \drawline(7,22)(15,22)

    \put(25,38){\makebox(0,0){$1$}}
    \put(36,31){\makebox(0,0){$2$}}
    \put(35,18){\makebox(0,0){$3$}}
    \put(20,13){\makebox(0,0){$4$}}
    \put(11,27){\makebox(0,0){$5$}}
    \end{picture}}
    \quad \quad \qquad (ii)
    \parbox{40mm}{%
    \begin{picture}(50,50)

        \thicklines
    \put(25,25){\arc(-2,-17){-240}}
    \put(25,25){\arc(-2,-8){-240}}
    \drawline(23,8.1)(23,17.1)
    \drawline(33,27)(40.5,31.5)

    \drawline(32,13)(32,22)
    \drawline(32,13)(40,13)
    \drawline(32,22)(40,22)
    \drawline(40,22)(40,13)

    \put(24,38){\makebox(0,0){$1$}}
    \put(35.5,32.5){\makebox(0,0){$2$}}
    \put(20,13){\makebox(0,0){$4$}}
    \put(36,17){\makebox(0,0){$3$}}
    \put(13,27){\makebox(0,0){$5$}}
    \end{picture}}
\end{center}




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

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}
and that
\begin{equation}\label{e3.5}
    L_n^{(r)}=F_n^{(r)}+(r-1)F_{n-r}^{(r)}, \quad n\geq 1.
\end{equation}

Given $c\in \mathcal{C}_n^{(r)}$, let $v(c):=$ the number of $r$-minos in the covering $c$, let
$\sigma(c):=$ the sum of the numbers covered by the initial segments of each of these $r$-minos, and let
\begin{equation}\label{e3.6}
    L_n^{(r)}(q,t):=\sum_{c\in \mathcal{C}_n^{(r)}}q^{\sigma(c)}t^{v(c)}.
\end{equation}
Conditioning on whether the number 1 is covered by a square or by an initial segment of an $r$-mino or
by an $r$-mino with initial segment $n-(r-1-i)$ for some $i$, $1\leqslant i \leqslant r-1,$ yields the
formula
\begin{equation}\label{e3.7}
L_n^{(r)}(q,t)=F_n^{(r)}(q,t)+q^{n-r+1}t\sum_{i=1}^{r-1}q^iF_{n-r}^{(r)}(q,q^it),\quad n\geqslant1,
\end{equation}
which reduces to the well known formula (see, e.g., \cite{shattuck2})
\begin{equation}\label{e3.8}
L_n^{(r)}(1,t)=F_n^{(r)}(1,t)+(r-1)tF_{n-r}^{(r)}(1,t),\quad n\geqslant1,
\end{equation}
when $q=1$. The $L_n^{(r)}(q,t)$, though, do not appear to satisfy  a simple recurrence like
(\ref{e2.6}) or (\ref{e2.7}).

With the ordinary generating function
\begin{equation}\label{e3.9}
\lambda^{(r)}(x,q,t):=\sum_{n\geqslant 1}L_n^{(r)}(q,t)x^n,
\end{equation}
one sees that (\ref{e3.7}) is equivalent to
\begin{equation}\label{e3.10}
\lambda^{(r)}(x,q,t)=-1+\Phi^{(r)}(x,q,t)+qtx^r\sum_{i=1}^{r-1}q^i\Phi^{(r)}(qx,q,q^it).
\end{equation}
By (\ref{e2.11}), identity (\ref{e3.10}) is equivalent to

\begin{theo}
\begin{equation}\label{e3.11}
\lambda^{(r)}(x,q,t)=
    \frac{x}{1-x}+\sum_{k\geq
    1}\frac{q^{k+r\binom{k}{2}}t^kx^{rk}\left[1+(1-x)\sum_{i=1}^{r-1}q^{ki}\right]}
    {(1-x)(1-qx)\cdots(1-q^kx)}.
\end{equation}
\end{theo}

The following theorem gives an explicit formula for the $L_n^{(r)}(q,t)$:

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

    \begin{equation}\label{e3.12}
L_n^{(r)}(q,t)= \sum_{0 \leq k \leq \lfloor n/r \rfloor} q^{k+r\binom{k}{2}} \left[
\frac{n_{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

$$\sum_{c\in \mathcal{C}_{n,k}^{(r)}}q^{\sigma(c)}=q^{k+r\binom{k}{2}}\left[\frac{n_{q}}
{(n-(r-1)k)_{q}}\right]\binom{n-(r-1)k}{k}_{q}.$$ Partitioning $\mathcal{C}_{n,k}^{(r)}$ into three
classes according to whether (i) 1 is covered by an initial segment of an $r$-mino, (ii) 1 is covered by
an $r$-mino with initial segment $n-(r-1-i)$ for some $i$, $1\leqslant i\leqslant r - 1$, or (iii) 1 is
covered by a square, and applying \eqref{e2.12} to each class, yields

\begin{eqnarray}
 \nonumber\sum_{c\in
    \mathcal{C}_{n,k}^{(r)}}q^{\sigma(c)}&=&q^{(k-1)+r\binom{k-1}{2}}\binom{n-(r-1)k-1}{k-1}_q
    \left(q^{r(k-1)+1}+\sum_{i=1}^{r-1}q^{(k-1)i+(n-r+1+i)}
    \right)\\
    \nonumber &&\hspace{-1.75cm}+ \;\;q^{k+r\binom{k}{2}}\binom{n-(r-1)k-1}{k}_{q}
    \cdot q^{k}\\
    \nonumber &&\hspace{-1.75cm}= \;\;q^{k+r\binom{k}{2}}\binom{n-(r-1)k-1}{k-1}_q
    \left(1+\sum_{i=1}^{r-1}q^{n-(r-i)k}\right)+q^{2k+r\binom{k}{2}}\binom{n-(r-1)k-1}{k}_{q}
    \\
    \nonumber&&\hspace{-1.75cm}= \;\;q^{k+r\binom{k}{2}}\left[\binom{n-(r-1)k-1}{k-1}_q
    \left(1+\sum_{i=1}^{r-1}q^{n-ki}\right)+q^{k}\binom{n-(r-1)k-1}{k}_{q}\right]
    \\
    \nonumber&&\hspace{-1.75cm}= \;\;\frac{q^{k+r\binom{k}{2}}}{(n-(r-1)k)_q}\binom{n-(r-1)k}{k}_q
    \left[k_q\left(1+\sum_{i=1}^{r-1}q^{n-ki}\right)+q^{k}(n-rk)_q\right],
    \\\nonumber
    \end{eqnarray}
from which \eqref{e3.12} now follows from the easily verified identity
$$n_q=k_q\left(1+\sum_{i=1}^{r-1}q^{n-ki}\right)+q^k(n-rk)_q.$$
\end{proof}
Note that \eqref{e3.11} and \eqref{e3.12} reduce, respectively, to \eqref{e3.4} and \eqref{e3.3} when
$q=t=1.$ Setting $q=1$ and $q=-1$ in \eqref{e3.11} gives
\begin{cor}
\begin{equation}\label{e3.13}
\lambda^{(r)}(x,1,t)=\frac{x+rtx^r}{1-x-tx^r}.
\end{equation}
\end{cor}
\noindent and
\begin{cor}
\begin{equation}\label{e3.14}
\lambda^{(r)}(x,-1,t)=\frac{x+x^2-tx^{2\left\lfloor
\frac{r}{2}\right\rfloor+1}+r(-1)^rt^2x^{2r}}{1-x^2+(-1)^{r+1}t^2x^{2r}}.
\end{equation}
\end{cor}

Either setting $q=-1$ in \eqref{e3.7} and applying \eqref{e2.16}, \eqref{e2.17}, and \eqref{e3.8} or
taking the even and odd parts of both sides of \eqref{e3.14}, replacing $x$ with $x^{1/2}$, and applying
\eqref{e3.13} and \eqref{e2.14} yields
\begin{theo}\label{teo3.3}
If $m\in\mathbb{P}$, then

\begin{equation}\label{e3.15}
L^{(r)}_{2m} ( -1, t)= L^{(r)}_m ( 1, (-1)^rt^2)
\end{equation}
 and
\begin{equation}\label{e3.16}
L^{(r)}_{2m-1} ( -1, t)= F^{(r)}_{m-1} ( 1, (-1)^rt^2)-tF^{(r)}_{m-\lfloor\frac{r}{2}\rfloor-1} ( 1,
(-1)^rt^2).
\end{equation}
\end{theo}

For a combinatorial proof of (\ref{e3.15}) and (\ref{e3.16}), we first associate to each $c\in
\mathcal{C}_n^{(r)}$ a word $u_c=u_1u_2\cdots$ in the alphabet $\{r,s\}$, where $$u_i:=\left\{%
\begin{array}{ll}
    r, & \hbox{if the } i^{th}\hbox{ piece of } c \hbox{ is an }\text{{\it r}\,-mino}; \\
    s, & \hbox{if the } i^{th}\hbox{ piece of } c \hbox{ is a square,} \\
\end{array}%
\right.$$ 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.

Assign to each covering $c\in \mathcal{C}_n^{(r)}$ the weight $w_c:=(-1)^{\sigma(c)}t^{v(c)}$, where $t$
is an indeterminate. Let $\mathcal{C}_n^{(r)'}$ consist of those $c$ in $\mathcal{C}_n^{(r)}$ whose
associated words $u_c=u_1u_2\cdots$ satisfy the conditions $u_{2i}=u_{2i+1}$, $i\geq 1$. Suppose $c\in
\mathcal{C}_n^{(r)}-\mathcal{C}_n^{(r)'}$, with $i_0$ being the smallest value of $i$ for which
$u_{2i}\neq u_{2i+1}$. Exchanging the positions of the $(2i_0)^{th}$ and $(2i_0+1)^{st}$ pieces within
$c$ produces a $\sigma$-parity changing, $v$-preserving involution of
$\mathcal{C}_n^{(r)}-\mathcal{C}_n^{(r)'}$.

First assume $n=2m$ and let $\mathcal{C}_{2m}^{(r)*}\subseteq \mathcal{C}_{2m}^{(r)'}$ comprise those
$c$ whose first and last pieces are the same and containing an even number of pieces in all. We extend
the involution of $\mathcal{C}_{2m}^{(r)}-\mathcal{C}_{2m}^{(r)'}$ above to
$\mathcal{C}_{2m}^{(r)'}-\mathcal{C}_{2m}^{(r)*}$ as follows. Let
$c\in\mathcal{C}_{2m}^{(r)'}-\mathcal{C}_{2m}^{(r)*}$, first assuming $r$ is even. If the initial
segment of the $r$-mino covering 1 in $c$ lies on an odd (resp., even) number, then rotate the entire
arrangement counterclockwise (resp., clockwise) one position, moving the pieces but keeping the numbered
positions fixed.

Now assume $r$ is odd. If 1 is covered by a segment of an $r$-mino which isn't initial, the rotate the
entire arrangement clockwise or counterclockwise depending on whether the initial segment of this
$r$-mino covers an odd or an even number. If 1 is covered by a square or by an initial segment of an
$r$-mino, then pair $c$ with the covering obtained by reading $u_c=u_1u_2\cdots$ backwards. Thus,

\begin{eqnarray*}
L_{2m}^{(r)}(-1,t)&=&\sum_{c\in \mathcal{C}_{2m}^{(r)}} w_c=\sum_{c\in \mathcal{C}_{2m}^{(r)*}}
w_c=\sum_{c\in \mathcal{C}_{2m}^{(r)*}}
(-1)^{rv(c)/2}t^{v(c)}\\
&=&\sum_{c\in \mathcal{C}_{m}^{(r)}} (-1)^{rv(c)}t^{2v(c)}=L_m^{(r)}(1,(-1)^rt^2),
\end{eqnarray*}
which gives (\ref{e3.15}).

Next, assume $n=2m-1$ and let $\mathcal{C}_{2m-1}^{(r)*}\subseteq \mathcal{C}_{2m-1}^{(r)'}$ comprise
those $c$ in which 1 is covered by a square or by an initial segment of an $r$-mino and containing an
odd number of pieces in all if 1 is covered by a square. Define an involution of
$\mathcal{C}_{2m-1}^{(r)'}-\mathcal{C}_{2m-1}^{(r)*}$ as follows. If $r$ is odd, then use the mapping
defined above for $\mathcal{C}_{2m}^{(r)'}-\mathcal{C}_{2m}^{(r)*}$ when $r$ was even. If $r$ is even,
then slightly modify the mapping defined above for $\mathcal{C}_{2m}^{(r)'}-\mathcal{C}_{2m}^{(r)*}$
when $r$ was odd (i.e., replace the word ``initial'' with ``second'' in a couple of places). Thus,
\begin{eqnarray*}
L_{2m-1}^{(r)}(-1,t)&=&\sum_{c\in \mathcal{C}_{2m-1}^{(r)*}} w_c=\sum\limits_{\substack{c\in \mathcal{C}_{2m-1}^{(r)*}\\
u_1=s \hbox{\scriptsize{ in }}u_c}}
w_c+\sum\limits_{\substack{c\in \mathcal{C}_{2m-1}^{(r)*}\\ u_1=r \hbox{\scriptsize{ in }} u_c}}w_c\\
&=& \sum\limits_{\substack{c\in \mathcal{R}_{2m-2}^{(r)'}\\ v(c)\hbox{\scriptsize{ even }}}} w_c - t\sum_{c\in \mathcal{R}_{2m-r-1}^{(r)'}}w_c\\
&=& F_{m-1}^{(r)}(1,(-1)^rt^2)-tF_{m-\lfloor\frac{r}{2}\rfloor-1}^{(r)}(1,(-1)^rt^2),
\end{eqnarray*}
which gives (\ref{e3.16}), where $\mathcal{R}_n^{(r)'}\subseteq \mathcal{R}_n^{(r)}$ consists of those
$c=c_1c_2\cdots$ such that $c_{2i-1}=c_{2i},$  $i\geqslant1.$

\section*{Acknowledgment}
The authors would like to thank the anonymous referee for a prompt, thorough reading of this
paper and for many excellent suggestions which improved it. We are indebted to the referee for formulas
\eqref{e2.9}, \eqref{e2.10}, \eqref{e3.7}, and \eqref{e3.10}.



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


\begin{thebibliography}{99}
\bibitem{benjamin1}
        A. Benjamin, J. Quinn, and F. Su, Phased tilings and generalized Fibonacci identities, {\em
        Fibonacci Quart.} {\bf 38} (2000), 282--288.

\bibitem{benjamin2}
        A. Benjamin and J. Quinn, {\em Proofs that Really Count: The Art of Combinatorial Proof,} The Dolciani Mathematical Expositions, 27,
        Mathematical Association of America, 2003.


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


\bibitem{carlitz2}
        L. Carlitz, Fibonacci notes 4: $q$-Fibonacci polynomials, {\em
        Fibonacci Quart.} {\bf 13} (1975), 97--102.


\bibitem{cigler1}
        J. Cigler, $q$-Fibonacci polynomials, {\em
        Fibonacci Quart.} {\bf 41} (2003), 31--40.

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

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

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

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

\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} (2006), \#R42.

\bibitem{shattuck3}
M. Shattuck and C. Wagner,\\
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL9/Shattuck/shattuck56.html}{Periodicity and parity theorems for a statistic on $r$-mino arrangements},
{\em J. Integer Seq.} {\bf 9} (2006), Art. 6.3.6.

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

\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, Gibonacci numbers.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received February 20 2007;
revised version received  May 7 2007.
Published in {\it Journal of Integer Sequences}, May 7 2007.

\bigskip
\hrule
\bigskip

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


\end{document}