Some Generalized Fibonacci Polynomials

Mark A. Shattuck Mathematics Department University of Tennessee Knoxville, TN 37996-1300 USA

                     shattuck@math.utk.edu

Carl G. Wagner Mathematics Department University of Tennessee Knoxville, TN 37996-1300 USA

                      wagner@math.utk.edu

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.

1 Introduction

In what follows, ℤ, ℕ, and ℙ 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 + ⋯ + q^{n−1} for n ∈ ℙ, 0!_{q} := 1,

n!_{q} := 1_{q}2_{q} ⋯ n_{q} for n ∈ ℙ, and

\binom{n}{k}_{q} := \begin{cases}\frac{n!_{q}}{k!_{q}(n−k)!_{q}} , & if 0 ⩽ k ⩽ n; \\ 0, & if k < 0 or 0 ⩽ n < k. \end{cases}  (1.1)

The \binom{n}{k}_{q} are also given, equivalently, by the column generating function [12, pp. 201–202]

∑_{n⩾0} \binom{n}{k}_{q}x^{n} = \frac{x^{k}}{(1 − x)(1 − qx) ⋯ (1 − q^{k}x)},  k ∈ ℕ.  (1.2)

If r ⩾ 2, the r-Fibonacci numbers F_{n}^{(r)} are defined by F_{0}^{(r)} = F_{1}^{(r)} = ⋯ = F_{r−1}^{(r)} = 1, with F_{n}^{(r)} = F_{n−1}^{(r)} + F_{n−r}^{(r)} if n ⩾ r. The r-Lucas numbers L_{n}^{(r)} are defined by L_{1}^{(r)} = L_{2}^{(r)} = ⋯ = 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 ⩾ 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 [13] 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 [3], lattice paths [8], Morse code sequences [7], and linear and circular domino arrangements [9]. Generalizations of F_{n}^{(r)} and/or L_{n}^{(r)} have arisen similarly in connection with statistics on Morse code sequences [7] as well as on linear and circular r-mino arrangements [10, 11].

In the next section, we consider the q-generalization

F_{n}^{(r)}(q, t) := ∑_{0⩽k⩽⌊n/r⌋} q^{k+r\binom{k}{2}}\binom{n − (r − 1)k}{k}_{q}t^{k}  (1.3)

of F_{n}^{(r)}. The r = 2 case of (1.3) or close variants thereof have appeared several times in the literature starting with Carlitz (see, e.g., [3, 4, 5, 8, 9]. 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

L_{n}^{(r)}(q, t) := ∑_{0⩽k⩽⌊n/r⌋} q^{k+r\binom{k}{2}} [\frac{n_{q}}{(n − (r − 1)k)_{q}} ] \binom{n − (r − 1)k}{k}_{q}t^{k}  (1.4)

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 (1.4) was introduced by Carlitz [3] and has been subsequently studied (see, e.g., [9]).

2 Linear and Phased r-Mino Arrangements

Let R_{n,k}^{(r)} denote the set of coverings of the numbers 1, 2, …, n arranged in a row by k indistinguishable r-minos and n − rk indistinguishable squares, where pieces do not overlap, an r-mino, r ⩾ 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

|R_{n,k}^{(r)}| = \binom{n − (r − 1)k}{k},  0 ⩽ k ⩽ ⌊n/r⌋,  (2.1)

for all n ∈ ℙ. (If we set R_{0,0}^{(r)} = {∅}, the “empty covering,” then (2.1) holds for n = 0 as well.) In what follows, we will identify coverings c with such words c_{1}c_{2} ⋯ in {r, s}. With

R_{n}^{(r)} := ⋃_{0⩽k⩽⌊n/r⌋} R_{n,k}^{(r)},  n ∈ ℕ,  (2.2)

it follows that

|R_{n}^{(r)}| = ∑_{0⩽k⩽⌊n/r⌋} \binom{n − (r − 1)k}{k} = F_{n}^{(r)},  (2.3)

where F_{0}^{(r)} = F_{1}^{(r)} = ⋯ = F_{r−1}^{(r)} = 1, with F_{n}^{(r)} = F_{n−1}^{(r)} + F_{n−r}^{(r)} if n ⩾ r. Note that

∑_{n⩾0} F_{n}^{(r)}x^{n} = \frac{1}{1 − x − x^{r}} .  (2.4)

Given c ∈ R_{n}^{(r)}, let v(c) := the number of r-minos in the covering c, let σ(c) := the sum of the numbers covered by the leftmost segments of each of these r-minos, and let

F_{n}^{(r)}(q, t) := ∑_{c∈R_{n}^{(r)}} q^{σ(c)}t^{v(c)},  n ∈ ℕ.  (2.5)

Categorizing linear covers of 1, 2, …, n according to the final and initial pieces, respectively, yields the recurrences

F_{n}^{(r)}(q, t) = F_{n−1}^{(r)}(q, t) + q^{n−r+1}tF_{n−r}^{(r)} (q, t) ,  n ⩾ r,  (2.6)

and

F_{n}^{(r)}(q, t) = F_{n−1}^{(r)}(q, qt) + qtF_{n−r}^{(r)}(q, q^{r}t),  n ⩾ r,  (2.7)

where F_{0}^{(r)}(q, t) = F_{1}^{(r)}(q, t) = ⋯ = F_{r−1}^{(r)}(q, t) = 1. Iterating (2.6) or (2.7) gives F_{−i}^{(r)}(q, t) = 0 if 1 ⩽ i ⩽ 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

Φ^{(r)}(x, q, t) := ∑_{n⩾0} F_{n}^{(r)}(q, t)x^{n},  (2.8)

recurrence (2.6) is equivalent to the identity

Φ^{(r)}(x, q, t) = 1 + xΦ^{(r)}(x, q, t) + qtx^{r}Φ^{(r)}(qx, q, t),  (2.9)

which may be rewritten, with the operator εf(x) := f(qx), as

(1 − x − qtx^{r}ε)Φ^{(r)}(x, q, t) = 1,

or

(1 − \frac{qtx^{r}}{1 − x}ε) Φ^{(r)}(x, q, t) = \frac{1}{1 − x}.  (2.10)

From (2.10), we immediately get

Φ^{(r)}(x, q, t) = ∑_{k⩾0} (\frac{qtx^{r}}{1 − x}ε)^{k} \frac{1}{1 − x},

which implies

Theorem 2.1.

Φ^{(r)}(x, q, t) = ∑_{k⩾0} \frac{q^{k+r\binom{k}{2}}t^{k}x^{rk}}{(1 − x)(1 − qx) ⋯ (1 − q^{k}x)}.  (2.11)

By (2.11) and (1.2),

Φ^{(r)}(x, q, t) = ∑_{k⩾0} q^{k+r\binom{k}{2}}t^{k}x^{(r−1)k} · \frac{x^{k}}{(1 − x)(1 − qx) ⋯ (1 − q^{k}x)}

= ∑_{k⩾0} q^{k+r\binom{k}{2}}t^{k}x^{(r−1)k} ∑_{n⩾rk} \binom{n − (r − 1)k}{k}_{q}x^{n−(r−1)k}

= ∑_{n⩾0} ( ∑_{0⩽k⩽⌊n/r⌋} q^{k+r\binom{k}{2}}\binom{n − (r − 1)k}{k}_{q}t^{k}) x^{n},

which establishes the explicit formula:

Theorem 2.2. For all n ∈ ℕ,

F_{n}^{(r)}(q, t) = ∑_{0⩽k⩽⌊n/r⌋} q^{k+r\binom{k}{2}}\binom{n − (r − 1)k}{k}_{q}t^{k}.  (2.12)

Remark: Cigler [7] has studied algebraically the polynomials

F_{n}(j, x, s, q) := ∑_{0⩽jk⩽n−j+1} q^{j\binom{k}{2}}\binom{n − (j − 1)(k + 1)}{k}_{q}s^{k}x^{n−j(k+1)+1}, n ⩾ 0,

which, by (2.12), are related to the F_{n}^{(r)}(q, t) by

F_{n}(j, x, s, q) = x^{n−j+1}F_{n−j+1}^{(j)} (q, \frac{s}{qx^{j}} ) , n ⩾ 0.  (2.13)

From (2.5) and (2.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 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 (2.11) and (2.12) reduce, respectively, to (2.4) and (2.3) when q = t = 1. Setting q = 1 and q = −1 in (2.11) gives Corollary 2.3.

Φ^{(r)}(x, 1, t) = \frac{1}{1 − x − tx^{r}} .  (2.14)

and

Corollary 2.4.

Φ^{(r)}(x, −1, t) = \frac{1 + x − tx^{r}}{1 − x^{2} + (−1)^{r+1}t^{2}x^{2r}} .  (2.15)

Taking the even and odd parts of both sides of (2.15), replacing x with x^{1/2}, and applying (2.14) yields

Theorem 2.5. Let m ∈ ℕ. If m and r have the same parity, then

F_{m}^{(r)}(−1, t) = F_{⌊m/2⌋}^{(r)}(1, (−1)^{r}t^{2}) − tF_{(m−r)/2}^{(r)}(1, (−1)^{r}t^{2}),  (2.16)

and if m and r have different parity, then

F_{m}^{(r)}(−1, t) = F_{⌊m/2⌋}^{(r)}(1, (−1)^{r}t^{2}).  (2.17)

One can provide combinatorial proofs of (2.16) and (2.17) similar to those in [10, 11] given for comparable formulas involving other q-Fibonacci polynomials.

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

If r ⩾ 2 and a, b ∈ ℙ, then define the sequence (G_{n}^{(r)})_{n∈ℤ} by the recurrence G_{n}^{(r)} = G_{n−1}^{(r)} + G_{n−r}^{(r)} for all n ∈ ℤ with the initial conditions G_{−(r−2)}^{(r)} = ⋯ = G_{−1}^{(r)} = 0, G_{0}^{(r)} = a,

and G_{1}^{(r)} = b. When r = 2, these are the Gibonacci numbers G_{n} (shorthand for generalized Fibonacci numbers) occurring in Benjamin and Quinn [2, p. 17]. 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)} r-Gibonacci numbers.

From the initial conditions and recurrence, one sees that the G_{n}^{(r)}, when n ⩾ 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 phased r-mino tilings (of length n), in accordance with Benjamin and Quinn [1, 2] in the case r = 2. Let R̂_{n}^{(r)} be the set consisting of these phased tilings and let

G_{n}^{(r)}(q, t) := ∑_{c∈R̂_{n}^{(r)}} q^{σ(c)}t^{v(c)}, n ⩾ 1,  (2.18)

where the σ and v statistics on 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 respective recurrences

G_{n}^{(r)}(q, t) = G_{n−1}^{(r)}(q, t) + q^{n−r+1}tG_{n−r}^{(r)}(q, t), n ⩾ r + 1,  (2.19)

and

G_{n}^{(r)}(q, t) = bF_{n−1}^{(r)}(q, qt) + aqtF_{n−r}^{(r)}(q, q^{r}t), n ⩾ r + 1,  (2.20)

with G_{1}^{(r)}(q, t) = ⋯ = G_{r−1}^{(r)}(q, t) = b and G_{r}^{(r)}(q, t) = b + aqt. From (2.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 (2.20), and applying (2.12), yields

L̂_{n}^{(r)}(q, t) := ∑_{0⩽k⩽⌊n/r⌋} q^{k+r\binom{k}{2}} [\frac{(r − 1)k_{q} + (n − (r − 1)k)_{q}}{(n − (r − 1)k)_{q}} ] \binom{n − (r − 1)k}{k}_{q}t^{k}, (2.21)

a q-generalization of the r-Lucas numbers.

3 Circular r-Mino Arrangements

If n ∈ ℙ and 0 ⩽ k ⩽ ⌊n/r⌋, let C_{n,k}^{(r)} denote the set of coverings by k r-minos and n − rk squares of the numbers 1, 2, …, n arranged clockwise around a circle:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .^{.................}^{..................}^{..................}^{..................}^{.................}^{................}^{................}^{.................}^{..................}^{..................}^{..................}^{.................}^{.................}^{..................}^{..................}^{..................}^{.................}^{................}^{................}^{.................}^{..................}^{..................}^{..................}^{.................} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . · 2 1 n · ·  ·  ·

By the 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 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 (2.1), yields

|C_{n,k}^{(r)}| = 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},  0 ⩽ k ⩽ ⌊n/r⌋.  (3.1)

Below we illustrate two members of C_{5,1}^{(4)}:

(i)  [figure: . . . . . . . . . . . . . . . .^{...............}^{................}^{................}^{................}^{...............}^{...............}^{...............}^{...............}^{................}^{................}^{................}^{...............}^{...............}^{................}^{................}^{................}^{...............}^{...............}^{...............}^{...............}^{................}^{................}^{................}^{................} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .; .. . . . . . . . . . .^{...........}^{...........}^{...........}^{..........}^{..........}^{...........}^{...........}^{...........}^{..........}^{...........}^{...........}^{...........}^{..........}^{..........}^{...........}^{...........}^{...........} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .; 1; 2; 3; 4; 5]  (ii) [figure: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .^{...............}^{................}^{................}^{................}^{...............}^{...............}^{...............}^{...............}^{................}; . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . .^{...........}^{............}^{...........}^{...........}^{...........}^{...........}^{............}; 1; 2; 4; 3; 5]

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

With

C_{n}^{(r)} := ⋃_{0⩽k⩽⌊n/r⌋} C_{n,k}^{(r)},  n ∈ ℙ,  (3.2)

it follows that

|C_{n}^{(r)}| = ∑_{0⩽k⩽⌊n/r⌋} \frac{n}{n − (r − 1)k} \binom{n − (r − 1)k}{k} = L_{n}^{(r)},  (3.3)

where L_{1}^{(r)} = L_{2}^{(r)} = ⋯ = L_{r−1}^{(r)} = 1, L_{r}^{(r)} = r + 1, and L_{n}^{(r)} = L_{n−1}^{(r)} + L_{n−r}^{(r)} if n ⩾ r + 1. Note that

∑_{n⩾1} L_{n}^{(r)}x^{n} = \frac{x + rx^{r}}{1 − x − x^{r}}  (3.4)

and that

L_{n}^{(r)} = F_{n}^{(r)} + (r − 1)F_{n−r}^{(r)}, n ⩾ 1.  (3.5)

Given c ∈ C_{n}^{(r)}, let v(c) := the number of r-minos in the covering c, let σ(c) := the sum of the numbers covered by the initial segments of each of these r-minos, and let

L_{n}^{(r)}(q, t) := ∑_{c∈C_{n}^{(r)}} q^{σ(c)}t^{v(c)}.  (3.6)

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 ⩽ i ⩽ r − 1, yields the formula

L_{n}^{(r)}(q, t) = F_{n}^{(r)}(q, t) + q^{n−r+1}t ∑_{i=1}^{r−1} q^{i}F_{n−r}^{(r)}(q, q^{i}t), n ⩾ 1,  (3.7)

which reduces to the well known formula (see, e.g., [10])

L_{n}^{(r)}(1, t) = F_{n}^{(r)}(1, t) + (r − 1)tF_{n−r}^{(r)}(1, t), n ⩾ 1,  (3.8)

when q = 1. The L_{n}^{(r)}(q, t), though, do not appear to satisfy a simple recurrence like (2.6) or (2.7).

With the ordinary generating function

λ^{(r)}(x, q, t) := ∑_{n⩾1} L_{n}^{(r)}(q, t)x^{n},  (3.9)

one sees that (3.7) is equivalent to

λ^{(r)}(x, q, t) = −1 + Φ^{(r)}(x, q, t) + qtx^{r} ∑_{i=1}^{r−1} q^{i}Φ^{(r)}(qx, q, q^{i}t).  (3.10)

By (2.11), identity (3.10) is equivalent to Theorem 3.1.

λ^{(r)}(x, q, t) = \frac{x}{1 − x} + ∑_{k⩾1} \frac{q^{k+r\binom{k}{2}}t^{k}x^{rk} [1 + (1 − x) ∑_{i=1}^{r−1} q^{ki}]}{(1 − x)(1 − qx) ⋯ (1 − q^{k}x)}.  (3.11)

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

Theorem 3.2. For all n ∈ ℙ,

L_{n}^{(r)}(q, t) = ∑_{0⩽k⩽⌊n/r⌋} q^{k+r\binom{k}{2}} [\frac{n_{q}}{(n − (r − 1)k)_{q}} ] \binom{n − (r − 1)k}{k}_{q}t^{k}.  (3.12)

Proof. It suffices to show

∑_{c∈C_{n,k}^{(r)}} q^{σ(c)} = q^{k+r\binom{k}{2}} [\frac{n_{q}}{(n − (r − 1)k)_{q}} ] \binom{n − (r − 1)k}{k}_{q}.

Partitioning 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 ⩽ i ⩽ r − 1, or (iii) 1 is covered by a square, and applying (2.12) to each class, yields

∑_{c∈C_{n,k}^{(r)}} q^{σ(c)} = q^{(k−1)+r\binom{k−1}{2}}\binom{n − (r − 1)k − 1}{k − 1}_{q} (q^{r(k−1)+1} + ∑_{i=1}^{r−1} q^{(k−1)i+(n−r+1+i)})

+ q^{k+r\binom{k}{2}}\binom{n − (r − 1)k − 1}{k}_{q} · q^{k}

= q^{k+r\binom{k}{2}}\binom{n − (r − 1)k − 1}{k − 1}_{q} (1 + ∑_{i=1}^{r−1} q^{n−(r−i)k}) + q^{2k+r\binom{k}{2}}\binom{n − (r − 1)k − 1}{k}_{q}

= q^{k+r\binom{k}{2}} [\binom{n − (r − 1)k − 1}{k − 1}_{q} (1 + ∑_{i=1}^{r−1} q^{n−ki}) + q^{k}\binom{n − (r − 1)k − 1}{k}_{q}]

= \frac{q^{k+r\binom{k}{2}}}{(n − (r − 1)k)_{q}} \binom{n − (r − 1)k}{k}_{q} [k_{q} (1 + ∑_{i=1}^{r−1} q^{n−ki}) + q^{k}(n − rk)_{q}] ,

from which (3.12) now follows from the easily verified identity

n_{q} = k_{q} (1 + ∑_{i=1}^{r−1} q^{n−ki}) + q^{k}(n − rk)_{q}.

Note that (3.11) and (3.12) reduce, respectively, to (3.4) and (3.3) when q = t = 1. Setting q = 1 and q = −1 in (3.11) gives Corollary 3.3.

λ^{(r)}(x, 1, t) = \frac{x + rtx^{r}}{1 − x − tx^{r}} .  (3.13)

and

Corollary 3.4.

λ^{(r)}(x, −1, t) = \frac{x + x^{2} − tx^{2⌊\frac{r}{2}⌋+1} + r(−1)^{r}t^{2}x^{2r}}{1 − x^{2} + (−1)^{r+1}t^{2}x^{2r}} .  (3.14)

Either setting q = −1 in (3.7) and applying (2.16), (2.17), and (3.8) or taking the even and odd parts of both sides of (3.14), replacing x with x^{1/2}, and applying (3.13) and (2.14) yields

Theorem 3.5. If m ∈ ℙ, then

L_{2m}^{(r)}(−1, t) = L_{m}^{(r)}(1, (−1)^{r}t^{2})  (3.15)

and

L_{2m−1}^{(r)}(−1, t) = F_{m−1}^{(r)}(1, (−1)^{r}t^{2}) − tF_{m−⌊ \frac{r}{2} ⌋−1}^{(r)}(1, (−1)^{r}t^{2}).  (3.16)

For a combinatorial proof of (3.15) and (3.16), we first associate to each c ∈ C_{n}^{(r)} a word u_{c} = u_{1}u_{2} ⋯ in the alphabet {r, s}, where

u_{i} := \{ \begin{matrix}r, & if the i^{th} piece of c is an r -mino; \\ s, & if the i^{th} piece of c is a square, \end{matrix}

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 C_{n}^{(r)}, while for each word starting with s, there is only one associated member.

Assign to each covering c ∈ C_{n}^{(r)} the weight w_{c} := (−1)^{σ(c)}t^{v(c)}, where t is an indeterminate. Let C_{n}^{(r)′} consist of those c in C_{n}^{(r)} whose associated words u_{c} = u_{1}u_{2} ⋯ satisfy the conditions u_{2i} = u_{2i+1}, i ⩾ 1. Suppose c ∈ C_{n}^{(r)} − C_{n}^{(r)′}, with i_{0} being the smallest value of i for which u_{2i} ≠ u_{2i+1}. Exchanging the positions of the (2i_{0})^{th} and (2i_{0} + 1)^{st} pieces within c produces a σ-parity changing, v-preserving involution of C_{n}^{(r)} − C_{n}^{(r)′}.

First assume n = 2m and let C_{2m}^{(r)∗} ⊆ 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 C_{2m}^{(r)} − C_{2m}^{(r)′} above to C_{2m}^{(r)′} − C_{2m}^{(r)∗} as follows. Let c ∈ C_{2m}^{(r)′} − 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_{1}u_{2} ⋯ backwards. Thus,

L_{2m}^{(r)}(−1, t) = ∑_{c∈C_{2m}^{(r)}} w_{c} = ∑_{c∈C_{2m}^{(r)∗}} w_{c} = ∑_{c∈C_{2m}^{(r)∗}}(−1)^{rv(c)/2}t^{v(c)}

= ∑_{c∈C_{m}^{(r)}}(−1)^{rv(c)}t^{2v(c)} = L_{m}^{(r)}(1, (−1)^{r}t^{2}),

which gives (3.15).

Next, assume n = 2m − 1 and let C_{2m−1}^{(r)∗} ⊆ 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 C_{2m−1}^{(r)′} − C_{2m−1}^{(r)∗} as follows. If r is odd, then use the mapping defined above for C_{2m}^{(r)′} − C_{2m}^{(r)∗} when r was even. If r is even, then slightly modify the mapping defined above for C_{2m}^{(r)′} − C_{2m}^{(r)∗} when r was odd (i.e., replace the word “initial” with “second” in a couple of places). Thus,

L_{2m−1}^{(r)}(−1, t) = ∑_{c∈C_{2m−1}^{(r)∗}} w_{c} = ∑_{\begin{matrix}c∈C_{2m−1}^{(r)∗} \\ u_{1}=s in u_{c} \end{matrix}} w_{c} + ∑_{\begin{matrix}c∈C_{2m−1}^{(r)∗} \\ u_{1}=r in u_{c} \end{matrix}} w_{c}

= ∑_{\begin{matrix}c∈R_{2m−2}^{(r)′} \\ v(c) even \end{matrix}} w_{c} − t ∑_{c∈R_{2m−r−1}^{(r)′}} w_{c}

= F_{m−1}^{(r)}(1, (−1)^{r}t^{2}) − tF_{m−⌊ \frac{r}{2} ⌋−1}^{(r)}(1, (−1)^{r}t^{2}),

which gives (3.16), where R_{n}^{(r)′} ⊆ R_{n}^{(r)} consists of those c = c_{1}c_{2} ⋯ such that c_{2i−1} = c_{2i}, i ⩾ 1.

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 (2.9), (2.10), (3.7), and (3.10).

References

[1] A. Benjamin, J. Quinn, and F. Su, Phased tilings and generalized Fibonacci identities, Fibonacci Quart. 38 (2000), 282–288.

[2] A. Benjamin and J. Quinn, Proofs that Really Count: The Art of Combinatorial Proof, The Dolciani Mathematical Expositions, 27, Mathematical Association of America, 2003.

[3] L. Carlitz, Fibonacci notes 3: q-Fibonacci numbers, Fibonacci Quart. 12 (1974), 317– 322.

[4] L. Carlitz, Fibonacci notes 4: q-Fibonacci polynomials, Fibonacci Quart. 13 (1975), 97–102.

[5] J. Cigler, q-Fibonacci polynomials, Fibonacci Quart. 41 (2003), 31–40.

[6] J. Cigler, A new class of q-Fibonacci polynomials, Electron. J. Combin. 10 (2003), #R19.

[7] J. Cigler, Some algebraic aspects of Morse code sequences, Discrete Math. Theor. Comput. Sci. 6 (2003), 55–68.

[8] J. Cigler, q-Fibonacci polynomials and the Rogers-Ramanujan identities, Ann. Combin. 8 (2004), 269–285.

[9] M. Shattuck and C. Wagner, Parity theorems for statistics on domino arrangements, Electron. J. Combin. 12 (2005), #N10.

[10] M. Shattuck and C. Wagner, A new statistic on linear and circular r-mino arrangements, Electron. J. Combin. 13 (2006), #R42.

[11] M. Shattuck and C. Wagner, Periodicity and parity theorems for a statistic on r-mino arrangements, J. Integer Seq. 9 (2006), Art. 6.3.6.

[12] C. Wagner, Generalized Stirling and Lah numbers, Discrete Math. 160 (1996), 199–218.

[13] H. Wilf, generatingfunctionology, Academic Press, 1990.

2000 Mathematics Subject Classification: Primary 11B39; Secondary 05A15. Keywords: r-mino arrangement, polynomial generalization, Fibonacci numbers, Lucas numbers, Gibonacci numbers.

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

Received February 20 2007; revised version received May 7 2007. Published in Journal of Integer Sequences, May 7 2007.

Return to Journal of Integer Sequences home page.