Combinatorial Interpretations of Lucas Analogues of Binomial Coefficients and Catalan Numbers
- PDF / 737,990 Bytes
- 28 Pages / 439.37 x 666.142 pts Page_size
- 109 Downloads / 186 Views
Annals of Combinatorics
Combinatorial Interpretations of Lucas Analogues of Binomial Coefficients and Catalan Numbers Curtis Bennett, Juan Carrillo, John Machacek and Bruce E. Sagan Abstract. The Lucas sequence is a sequence of polynomials in s, t defined recursively by {0} = 0, {1} = 1, and {n} = s{n − 1} + t{n − 2} for n ≥ 2. On specialization of s and t one can recover the Fibonacci numbers, the nonnegative integers, and the q-integers [n]q . Given a quantity which is expressed in terms of products and quotients of nonnegative integers, one obtains a Lucas analogue by replacing each factor of n in the expression with {n}. It is then natural to ask if the resulting rational function is actually a polynomial in s, t with nonnegative integer coefficients and, if so, what it counts. The first simple combinatorial interpretation for this polynomial analogue of the binomial coefficients was given by Sagan and Savage, although their model resisted being used to prove identities for these Lucasnomials or extending their ideas to other combinatorial sequences. The purpose of this paper is to give a new, even more natural model for these Lucasnomials using lattice paths which can be used to prove various equalities as well as extending to Catalan numbers and their relatives, such as those for finite Coxeter groups. Mathematics Subject Classification. Primary 05A10; Secondary 05A15, 05A19, 11B39. Keywords. Binomial coefficient, Catalan number, Combinatorial interpretation, Coxeter group, Generating function, Integer partition, Lattice path, Lucas sequence, Tiling.
1. Introduction Let s and t be two variables. The corresponding Lucas sequence is defined inductively by letting {0} = 0, {1} = 1, and {n} = s{n − 1} + t{n − 2} 0123456789().: V,-vol
C. Bennett et al.
Figure 1. The tilings in T (3) for n ≥ 2. For example {2} = s, {3} = s2 + t, {4} = s3 + 2st, and so forth. Clearly when s = t = 1 one recovers the Fibonacci sequence. When s = 2 and t = −1 we have {n} = n. Furthermore if s = 1 + q and t = −q then {n} = [n]q where [n]q = 1 + q + · · · + q n−1 is the usual q-analogue of n. So when proving theorems about the Lucas sequence, one gets results about the Fibonacci numbers, the nonnegative integers, and q-analogues for free. It is easy to give a combinatorial interpretation to {n} in terms of tilings. Given a row of n squares, let T (n) denote the set of tilings T of this strip by monominoes which cover one square and dominoes which cover two adjacent squares. Figure 1 shows the tilings in T (3). Given any configuration of tiles T we define its weight to be wt T = snumber of monominoes in T tnumber of dominoes in T . Similarly, given any set of tilings T we define its weight to be wt T = wt T. T ∈T
To illustrate wt(T (3)) = s3 + 2st = {4}. This presages the next result which follows quickly by induction and is well known so we omit the proof. Proposition 1.1. For all n ≥ 1 we have {n} = wt(T (n − 1)).
Given any quantity which is defined using products and quotients of integers, we can replace each occurrence of n in the expressi
Data Loading...
