Periodicity and Parity Theorems for a Statistic on r-Mino Arrangements

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

                     shattuck@math.utk.edu
                      wagner@math.utk.edu

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.

1 Introduction

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 [12], 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 [1], lattice paths [5], and linear and circular domino arrangements [8]. Generalizations of F_{n}^{(r)} and/or L_{n}^{(r)} have arisen similarly in connection with statistics on Morse code sequences [4] as well as on linear and circular r-mino arrangements [9].

Cigler [3] 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 π, applied more generally to linear r-mino arrangements, leads to the polynomial generalization

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

of F_{n}^{(r)}. A natural extension of this π statistic to circular r-mino arrangements leads to the new polynomial generalization

L_{n}^{(r)}(q, t) := ∑_{0⩽k⩽⌊n/r⌋} q^{\binom{k+1}{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}  (1.2)

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 [11, pp. 201–202]

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

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 π statistic on circular domino arrangements which lead to additional polynomial generalizations of the Lucas sequence.

In what follows, ℕ and ℙ 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 + ⋯ + 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.4)

A useful variation of (1.4) is the well known formula [10, p. 29]

\binom{n}{k}_{q} = ∑_{\begin{matrix}d_{0}+d_{1}+···+d_{k}=n−k \\ d_{i}∈ℕ \end{matrix}}q^{0d_{0}+1d_{1}+···+kd_{k}} = ∑_{t⩾0}p(k, n − k, t)q^{t},  (1.5)

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.

2 Linear 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 a covering c = c_{1}c_{2} ⋯, let

π(c) := ∑_{i:c_{i}=r} i;  (2.5)

note that π(c) gives the total resulting when one counts the number of pieces preceding each r-mino, inclusive, and adds up these numbers.

Let

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

where v(c) := the number of r-minos in the covering c.

Categorizing linear covers of 1, 2, …, n according to whether the piece covering n is a square or r-mino yields the recurrence relation

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

with F_{i}^{(r)}(q, t) = 1 if 0 ⩽ i ⩽ r − 1, since the total number of pieces in c ∈ 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

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

By combining relations (2.7) and (2.8), one gets a recurrence for F_{n}^{(r)}(q, t) for each number q and t. For example when r = 3, this is

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^{2}F_{n−7}^{(3)}(q, t)
+ q^{n−3}t^{3}F_{n−9}^{(3)}(q, t).  (2.9)

The F_{n}^{(r)}(q, t) have the following explicit formula.

Theorem 2.1. For all n ∈ ℕ,

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

Proof. It clearly suffices to show that

∑_{c∈R_{n,k}^{(r)}} q^{π(c)} = q^{\binom{k+1}{2}}\binom{n − (r − 1)k}{k}_{q}.

Each c ∈ R_{n,k}^{(r)} corresponds uniquely to a sequence (d_{0}, d_{1}, …, 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 π(c) = (d_{k} + 1) + (d_{k} + d_{k−1} + 2) + ⋯ + (d_{k} + d_{k−1} + ⋯ + d_{1} + k) = \binom{k+1}{2} + kd_{k} + (k − 1)d_{k−1} + ⋯ + 1d_{1} so that

∑_{c∈R_{n,k}^{(r)}} q^{π(c)} = q^{\binom{k+1}{2}} ∑_{\begin{matrix}d_{0}+d_{1}+···+d_{k}=n−rk \\ d_{i}∈ℕ \end{matrix}}q^{0d_{0}+1d_{1}+···+kd_{k}}

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

by (1.5).

Theorem 2.2. The ordinary generating function of the sequence (F_{n}^{(r)}(q, t))_{n⩾0} is given by

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

Proof. By (2.10) and (1.3),

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

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

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

Note that F_{n}^{(r)}(1, 1) = F_{n}^{(r)}, whence (2.11) generalizes (2.4). Setting q = 1 and q = −1 in (2.11) yields

Corollary 2.2.1. The ordinary generating function of the sequence (F_{n}^{(r)}(1, t))_{n⩾0} is given by

∑_{n⩾0}F_{n}^{(r)}(1, t)x^{n} = \frac{1}{1 − x − tx^{r}} .  (2.12)

and

Corollary 2.2.2. The ordinary generating function of the sequence (F_{n}^{(r)}(−1, t))_{n⩾0} is given by

∑_{n⩾0}F_{n}^{(r)}(−1, t)x^{n} = \frac{1 + x − tx^{r}}{1 − x^{2} + t^{2}x^{2r}} .  (2.13)

When r = 2 and t = 1 in (2.13), we get

∑_{n⩾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}},  (2.14)

which implies

Corollary 2.2.3. The sequence (F_{n}^{(2)}(−1, 1))_{n⩾0} is periodic with period 12; namely, if a_{n} := F_{n}^{(2)}(−1, 1) for n ⩾ 0, then a_{0} = 1, a_{1} = 1, a_{2} = 0, a_{3} = 1, a_{4} = −1, and a_{5} = 0 with a_{n+6} = −a_{n}, n ⩾ 0.

(We call a sequence (b_{n})_{n⩾0} periodic with period d if b_{n+d} = b_{n} for all n ⩾ m for some m ∈ ℕ.)

Remark. Corollary 2.2.3 is the q = −1 case of the well known formula

∑_{0⩽k⩽⌊n/2⌋}(−1)^{k}q^{\binom{k}{2}}\binom{n − k}{k}_{q} = \begin{cases}(−1)^{⌊n/3⌋}q^{n(n−1)/6}, & if n ≡ 0, 1 (mod 3); \\ 0, & if n ≡ 2 (mod 3). \end{cases}

See, e.g., Cigler [5], Ekhad and Zeilberger [6], and Kupershmidt [7].

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 [9]. We include its proof here for completeness.

Lemma 2.3. If r ⩾ 3, then g_{r}(x) := 1 − x + x^{r} does not divide any polynomial of the form 1 − x^{m}, where m ∈ ℙ.

Proof. We first describe the roots of unity that are zeros of g_{r}(x), where r ⩾ 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−2Re(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.

Theorem 2.4. The sequence (F_{n}^{(r)}(−1, 1))_{n⩾0} is never periodic for r ⩾ 3.

Proof. By (2.13) 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 ∈ ℙ whenever r ⩾ 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 ∈ ℙ, since g_{r}(x) fails to, which completes the proof.

Iterating (2.7) or (2.8) yields F_{−i}^{(r)}(q, t) = 0 if 1 ⩽ i ⩽ r − 1, which we’ll take as a convention.

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

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

and if m and r have different parity, then

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

Proof. Taking the even and odd parts of both sides of (2.13) followed by replacing x with x^{1/2} yields

∑_{n⩾0}F_{2n}^{(r)}(−1, t)x^{n} = \frac{1 − tx^{r/2}}{1 − x + t^{2}x^{r}}

and

∑_{n⩾0}F_{2n+1}^{(r)}(−1, t)x^{n} = \frac{1}{1 − x + t^{2}x^{r}} ,

when r is even, and

∑_{n⩾0}F_{2n}^{(r)}(−1, t)x^{n} = \frac{1}{1 − x + t^{2}x^{r}}

and

∑_{n⩾0}F_{2n+1}^{(r)}(−1, t)x^{n} = \frac{1 − tx^{(r−1)/2}}{1 − x + t^{2}x^{r}} ,

when r is odd, from which (2.15) and (2.16) now follow from (2.12) upon putting together cases.

For a combinatorial proof of (2.15) and (2.16), we first assign to each r-mino arrangement c ∈ R_{m}^{(r)} the weight w_{c} := (−1)^{π(c)}t^{v(c)}, where t is an indeterminate. Let R_{m}^{(r)′} consist of those c = c_{1}c_{2} ⋯ in R_{m}^{(r)} satisfying the conditions c_{2i−1} = c_{2i}, i ⩾ 1. Suppose c ∈ R_{m}^{(r)} − R_{m}^{(r)′}, with i_{0} being the smallest value of i for which c_{2i−1} ≠ c_{2i}. Exchanging the positions of the (2i_{0} − 1)^{st} and (2i_{0})^{th} pieces within c produces a π-parity changing involution of R_{m}^{(r)} − R_{m}^{(r)′} which preserves v.

If m and r have the same parity, then

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

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

= ∑_{z∈R_{⌊m/2⌋}^{(r)}}(−1)^{v(z)}t^{2v(z)} − t ∑_{z∈R_{(m−r)/2}^{(r)}}(−1)^{v(z)}t^{2v(z)}

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

which gives (2.15), since each pair of consecutive r-minos in c ∈ R_{m}^{(r)′} contributes a factor of −1 towards the sign (−1)^{π(c)} and since members of R_{m}^{(r)′} for which v(c) is odd end in a single r-mino. If m and r differ in parity, then

F_{m}^{(r)}(−1, t) = ∑_{c∈R_{m}^{(r)}} w_{c} = ∑_{c∈R_{m}^{(r)′}} w_{c} = ∑_{z∈R_{⌊m/2⌋}^{(r)}}(−1)^{v(z)}t^{2v(z)} = F_{⌊m/2⌋}^{(r)}(1, −t^{2}),

which gives (2.16), since members of R_{m}^{(r)′} must contain an even number of r-minos.

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 ⩾ 6, let R_{n}^{(2)∗} ⊆ R_{n}^{(2)′} consist of those domino arrangements c = c_{1}c_{2} ⋯ that contain at least 4⌊n/6⌋ pieces satisfying the conditions

c_{4i−3}c_{4i−2}c_{4i−1}c_{4i} = ssdd,  1 ⩽ i ⩽ ⌊n/6⌋;  (2.17)

if 0 ⩽ n ⩽ 5, then let R_{n}^{(2)∗} = R_{n}^{(2)′}.

A π-parity changing involution of R_{n}^{(2)′} − R_{n}^{(2)∗} when n ⩾ 6 is given by the pairing

(ssdd)^{k}ssssu ⟷ (ssdd)^{k}ddu,

where k ⩾ 0 and u is some (non-empty) word in {d, s}. If n = 6m + i, where m ⩾ 1 and 0 ⩽ i ⩽ 5, then

F_{n}^{(2)}(−1, 1) = ∑_{c∈R_{n}^{(2)}}(−1)^{π(c)} = ∑_{c∈R_{n}^{(2)′}}(−1)^{π(c)} = ∑_{c∈R_{n}^{(2)∗}}(−1)^{π(c)}

= (−1)^{m} ∑_{c∈R_{i}^{(2)∗}}(−1)^{π(c)} = (−1)^{m}F_{i}^{(2)}(−1, 1),

which implies Corollary 2.2.3, upon checking directly the cases 0 ⩽ n ⩽ 5, as each ssdd unit in c ∈ R_{n}^{(2)∗} contributes a factor of −1 towards the sign (−1)^{π(c)}.

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_{4,1}^{(3)}:

(i)  ^{...........................................................................................................................................................................................................................................................................................................................................................................................}^{..............................................................................................................................................................................................} 1 2 3 4  (ii) ^{...........................................................................................................................................................................................................................................................................................................................................................................................}^{..............................................................................................................................................................................................} 1  2 3 4

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

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)

We’ll associate to each c ∈ C_{n}^{(r)} a word u_{c} = u_{1}u_{2} ⋯ in the alphabet {r, s}, where

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

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.

Given c ∈ C_{n}^{(r)} and its associated word u_{c} = u_{1}u_{2} ⋯, let

π(c) := ∑_{i:u_{i}=r} i;  (3.5)

note that π(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

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

where v(c) := the number of r-minos in the covering c.

Categorizing circular covers c of 1, 2, …, n according to whether the last letter in u_{c} is an s or r yields the recurrence relation

L_{n}^{(r)}(q, t) = L_{n−1}^{(r)}(q, t) + q^{n−r+1}tL_{n−r}^{(r)}(q, t/q^{r−1}), n ⩾ r + 1,  (3.7)

with L_{i}^{(r)}(q, t) = 1 if 1 ⩽ i ⩽ 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 (2.8). The following theorem gives an explicit formula for L_{n}^{(r)}(q, t).

Theorem 3.1. For all n ∈ ℙ,

L_{n}^{(r)}(q, t) = ∑_{0⩽k⩽⌊n/r⌋} q^{\binom{k+1}{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}.  (3.8)

Proof. It suffices to show that

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

Partitioning C_{n,k}^{(r)} into the categories employed above in deriving (3.1), and applying (2.10), yields

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

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

= q^{\binom{k+1}{2}} [\frac{rk_{q} + q^{k}(n − rk)_{q}}{(n − (r − 1)k)_{q}} ] \binom{n − (r − 1)k}{k}_{q}

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

which completes the proof.

Note that L_{n}^{(r)}(1, 1) = L_{n}^{(r)}. By (3.8) and (2.10), the L_{n}^{(r)}(q, t) are related to the F_{n}^{(r)}(q, t) by the formula

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

which reduces to

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

when q = t = 1. Formula (3.10) can also be realized by considering the way in which 1 is covered in c ∈ 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.

Theorem 3.2. The ordinary generating function of the sequence (L_{n}^{(r)}(q, t))_{n⩾1} is given by

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

Proof. From (3.9),

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

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

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

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

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

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

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

by (1.3).

Note that (3.12) reduces to (3.4) when q = t = 1. Setting q = 1 and q = −1 in (3.12) yields

Corollary 3.2.1. The ordinary generating function of the sequence (L_{n}^{(r)}(1, t))_{n⩾1} is given by

∑_{n⩾1}L_{n}^{(r)}(1, t)x^{n} = \frac{x + rtx^{r}}{1 − x − tx^{r}} .  (3.13)

and

Corollary 3.2.2. The ordinary generating function of the sequence (L_{n}^{(r)}(−1, t))_{n⩾1} is given by

∑_{n⩾1}L_{n}^{(r)}(−1, t)x^{n} = \frac{x + x^{2} − rtx^{r} − (r − 1)tx^{r+1} − rt^{2}x^{2r}}{1 − x^{2} + t^{2}x^{2r}} .  (3.14)

When r = 2 and t = 1 in (3.14), we get

∑_{n⩾1}L_{n}^{(2)}(−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}},  (3.15)

which implies Corollary 3.2.3. The sequence (L_{n}^{(2)}(−1, 1))_{n⩾1} is periodic with period 12; namely, if a_{n} := L_{n}^{(2)}(−1, 1) for n ⩾ 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 ⩾ 1.

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

Theorem 3.3. The sequence (L_{n}^{(r)}(−1, 1))_{n⩾1} is never periodic for r ⩾ 3.

Proof. By (3.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 ∈ ℙ whenever r ⩾ 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} ≠ −1 implies that t_{0} must then be a root of the equation (x + 1) [(r − 1)x − r]^{2} = (x − 1)[(r − 1)x + r]^{2}, which reduces to (r^{2} − 1)x^{2} = r^{2}. But t_{0} = ±\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.

Recall that F_{−i}^{(r)}(q, t) = 0 if 1 ⩽ i ⩽ r − 1, by convention.

Theorem 3.4. Let m ∈ ℙ. If r is even, then

L_{2m}^{(r)}(−1, t) = L_{m}^{(r)}(1, −t^{2}) − rtF_{m− \frac{r}{2}}^{(r)} (1, −t^{2})  (3.16)

and

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

and if r is odd, then

L_{2m}^{(r)}(−1, t) = L_{m}^{(r)}(1, −t^{2}) − (r − 1)tF_{m−(\frac{r+1}{2})}^{(r)}(1, −t^{2})  (3.18)

and

L_{2m−1}^{(r)}(−1, t) = F_{m−1}^{(r)}(1, −t^{2}) − rtF_{m−(\frac{r+1}{2})}^{(r)}(1, −t^{2}).  (3.19)

Proof. Taking the even and odd parts of both sides of (3.14) followed by replacing x with x^{1/2} yields

∑_{m⩾1}L_{2m}^{(r)}(−1, t)x^{m} = \frac{x − rtx^{\frac{r}{2}} − rt^{2}x^{r}}{1 − x + t^{2}x^{r}}

and

∑_{m⩾1}L_{2m−1}^{(r)}(−1, t)x^{m} = \frac{x − (r − 1)tx^{\frac{r}{2} +1}}{1 − x + t^{2}x^{r}} ,

when r is even, and

∑_{m⩾1}L_{2m}^{(r)}(−1, t)x^{m} = \frac{x − (r − 1)tx^{\frac{(r+1)}{2}} − rt^{2}x^{r}}{1 − x + t^{2}x^{r}}

and

∑_{m⩾1}L_{2m−1}^{(r)}(−1, t)x^{m} = \frac{x − rtx^{\frac{(r+1)}{2}}}{1 − x + t^{2}x^{r}} ,

when r is odd, from which (3.16)−(3.19) now follow from (3.13) and (2.12).

For a combinatorial proof of (3.16)−(3.19), we first 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 word u_{c} = u_{1}u_{2} ⋯ satisfies 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)′}.

If r is even and n = 2m, then

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

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

= ∑_{z∈C_{m}^{(r)}}(−1)^{v(z)}t^{2v(z)} − rt ∑_{z∈R_{m− \frac{r}{2}}^{(r)}} (−1)^{v(z)}t^{2v(z)}

= L_{m}^{(r)}(1, −t^{2}) − rtF_{m− \frac{r}{2}}^{(r)} (1, −t^{2}),

which gives (3.16), where R_{n}^{(r)′} is as in the proof of Theorem 2.5, since members of C_{2m}^{(r)′} 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

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

= ∑_{c∈R_{2m−2}^{(r)′}} w_{c} − rt ∑_{c∈R_{2m−r−1}^{(r)′}} w_{c}

= F_{m−1}^{(r)}(1, −t^{2}) − rtF_{m−(\frac{r+1}{2})}^{(r)}(1, −t^{2}),

which gives (3.19).

For the cases that remain, let C_{n}^{(r)^{∗}} ⊆ C_{n}^{(r)′} such that C_{n}^{(r)′} − C_{n}^{(r)^{∗}} comprises those c which satisfy the following additional conditions:

(i) c contains an even number of pieces in all;

(ii) u_{1} ≠ u_{p} in u_{c} = u_{1}u_{2} ⋯ u_{p}; (iii) if u_{1} = r, then 1 corresponds to the initial segment of the r-mino covering it.

Pair members of C_{n}^{(r)′} − C_{n}^{(r)^{∗}} of opposite π-parity as follows: given c ∈ C_{n}^{(r)′} − C_{n}^{(r)^{∗}}, let c′ be the covering resulting when u_{c} = u_{1}u_{2} ⋯ u_{p} is read backwards.

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

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

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

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

which gives (3.17), since members of C_{2m−1}^{(r)^{∗}} 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

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

= ∑_{\begin{matrix}c∈C_{2m}^{(r)^{∗}} \\ u_{1}=u_{p} \end{matrix}}(−1)^{v(c)/2}t^{v(c)} − (r − 1)t ∑_{c∈R_{2m−r−1}^{(r)′}}(−1)^{v(c)/2}t^{v(c)}

= ∑_{z∈C_{m}^{(r)}}(−1)^{v(z)}t^{2v(z)} − (r − 1)t ∑_{z∈R_{m−(\frac{r+1}{2})}^{(r)}}(−1)^{v(z)}t^{2v(z)}

= L_{m}^{(r)}(1, −t^{2}) − (r − 1)tF_{m−(\frac{r+1}{2})}^{(r)}(1, −t^{2}),

which gives (3.18).

4 Variants of the π Statistic

Modifying the π 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 π statistic on circular r-mino arrangements, taking r = 2 for simplicity. We’ll use the notation C_{n} = C_{n}^{(2)}, C_{n,k} = C_{n,k}^{(2)}, and F_{n}(q, t) = F_{n}^{(2)}(q, t).

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

Define the statistic π_{1} on C_{n} by

π_{1}(c) = \begin{cases}π(c), & if c ∈ \overrightarrow{C}_{n}; \\ π(c) − 2v(c) + n, & if c ∈ \overleftarrow{C}_{n}. \end{cases}  (4.1)

Note that π_{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 ∈ \overleftarrow{C}_{n}.

Theorem 4.1. For all n ∈ ℙ,

∑_{c∈C_{n}} q^{π_{1}(c)}t^{v(c)} = ∑_{0⩽k⩽⌊n/2⌋} q^{\binom{k+1}{2}} [\frac{(n − k)_{q} + q^{n−2k}k_{q}}{(n − k)_{q}} ] \binom{n − k}{k}_{q}t^{k}.  (4.2)

Proof. By (2.10) when r = 2,

∑_{c∈C_{n,k}} q^{π_{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}} [\binom{n − k}{k}_{q} + q^{n−2k} \frac{k_{q}}{(n − k)_{q}} \binom{n − k}{k}_{q}]

= q^{\binom{k+1}{2}} [\frac{(n − k)_{q} + q^{n−2k}k_{q}}{(n − k)_{q}} ] \binom{n − k}{k}_{q}.

If L̂_{n}(q, t) denotes the distribution polynomial in (4.2), then

L̂_{n}(q, t) = F_{n}(q, t) + q^{n−1}tF_{n−2}(q, t/q), n ⩾ 1,  (4.3)

by (4.2) and (2.10), or by considering whether or not c belongs to \overrightarrow{C}_{n}. The L̂_{n}(q, t) satisfy the nice recurrence

L̂_{n}(q, t) = L̂_{n−1}(q, qt) + qtL̂_{n−2}(q, qt), n ⩾ 3,  (4.4)

with L̂_{1}(q, t) = 1 and L̂_{2}(q, t) = 1 + 2qt, the first term of (4.4) accounting for those c ∈ \overrightarrow{C}_{n} where 1 is covered by a square as well as those c ∈ \overleftarrow{C}_{n} where 2 is covered by a square and the second term accounting for the cases that remain.

Next define π_{2} on C_{n} by

π_{2}(c) = \begin{cases}π(c), & if c ∈ \overrightarrow{C}_{n}; \\ π(c) − v(c), & if c ∈ \overleftarrow{C}_{n}. \end{cases}  (4.5)

Theorem 4.2. For all n ∈ ℙ,

∑_{c∈C_{n}} q^{π_{2}(c)}t^{v(c)} = ∑_{0⩽k⩽⌊n/2⌋} q^{\binom{k}{2}} \frac{n_{q}}{(n − k)_{q}} \binom{n − k}{k}_{q}t^{k}.  (4.6)

Proof. By (2.10) when r = 2,

∑_{c∈C_{n,k}} q^{π_{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}} [\frac{q^{k}(n − k)_{q} + k_{q}}{(n − k)_{q}} ] \binom{n − k}{k}_{q}

= q^{\binom{k}{2}} \frac{n_{q}}{(n − k)_{q}} \binom{n − k}{k}_{q}.

Theorem 4.2 provides a combinatorial interpretation of the generalized Lucas polynomials

Luc_{n}(x, t) := ∑_{0⩽k⩽⌊n/2⌋} q^{\binom{k}{2}} \frac{n_{q}}{(n − k)_{q}} \binom{n − k}{k}_{q}x^{n−2k}t^{k},  (4.7)

studied by Cigler [2, 3]. Note that the joint distribution of π_{2} and v on C_{n} is Luc_{n}(1, t), with the x variable of Luc_{n}(x, t) recording the number of squares in c ∈ C_{n}. Considering whether or not c belongs to \overrightarrow{C}_{n} leads directly to the relation (cf. [3])

Luc_{n}(1, t) = F_{n}(q, t) + tF_{n−2}(q, t), n ⩾ 1.  (4.8)

The Luc_{n}(1, t) do not seem to satisfy a two-term recurrence like (3.7) or (4.4).

Similar reasoning shows that Luc_{n}(1, t) is also the joint distribution of the statistics π_{3} and v on C_{n}, where

π_{3}(c) = \begin{cases}π(c) − v(c), & if c ∈ \overrightarrow{C}_{n}; \\ π(c) − 2v(c) + n, & if c ∈ \overleftarrow{C}_{n}, \end{cases}  (4.9)

which yields the relation

Luc_{n}(1, t) = F_{n}(q, t/q) + q^{n−1}tF_{n−2}(q, t/q), n ⩾ 1.  (4.10)

The π_{2} statistic on C_{n} can be generalized to C_{n}^{(r)} by letting π_{2}(c) = π(c), if the number 1 is covered by a square or an initial segment of an r-mino, and letting π_{2}(c) = π(c) − v(c), otherwise. Reasoning as in Theorem 4.2 with π_{2} on C_{n}^{(r)} leads to

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

which generalizes Luc_{n}(x, t). The Luc_{n}^{(r)}(x, t) are connected with the F_{n}^{(r)}(q, t) by the simple relation

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

which generalizes (4.8).

Acknowledgment

The authors would like to thank the anonymous referee for formulas (2.8), (2.9), (4.11), and (4.12).

References

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

[2] J. Cigler, Einige q-Analoga der Lucas- and Fibonacci-Polynome, Österreich. Akad. Wiss. Math.-Natur. Kl. Sitzungsber. II 211 (2002), 3–20.

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

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

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

[6] S. Ekhad and D. Zeilberger, The number of solutions of X^{2} = 0 in triangular matrices over GF(q), Electron. J. Combin. 3 (1) (1996), #R2.

[7] B. Kupershmidt, q-Analogues of classical 6-periodicity, J. Nonlinear Math. Physics 10 (2003), 318–339.

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

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

[10] R. Stanley, Enumerative Combinatorics, Vol. I, Wadsworth and Brooks/Cole, 1986.

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

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

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

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

Received April 4 2006; revised version received August 17 2006. Published in Journal of Integer Sequences, August 18 2006.

Return to Journal of Integer Sequences home page.