Combinatorial interpretations of Lucas analogues of binomial coefficients and Catalan numbers.

*(English)*Zbl 1451.05009Summary: 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\ge 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 B. E. Sagan and C. D. Savage [Integers 10, No. 6, 697–703, A52 (2010; Zbl 1227.11041)], 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.

##### MSC:

05A10 | Factorials, binomial coefficients, combinatorial functions |

05A15 | Exact enumeration problems, generating functions |

05A19 | Combinatorial identities, bijective combinatorics |

11B39 | Fibonacci and Lucas numbers and polynomials and generalizations |

##### Keywords:

binomial coefficient; Catalan number; combinatorial interpretation; Coxeter group; generating function; integer partition; lattice path; Lucas sequence; tiling
Full Text:
DOI

##### References:

[1] | Farid Aliniaeifard, Nantel Bergeron, Cesar Ceballos, Tom Denton, and Shu Xiao Li. Algebraic Combinatorics Seminar, Fields Institute. 2013-2015. |

[2] | Drew Armstrong. Generalized noncrossing partitions and combinatorics of Coxeter groups. Mem. Amer. Math. Soc., 202(949):x+159, 2009. · Zbl 1191.05095 |

[3] | Arthur T. Benjamin and Sean S. Plott. A combinatorial approach to Fibonomial coefficients. Fibonacci Quart., 46/47(1):7-9, 2008/09. · Zbl 1222.11019 |

[4] | Nantel Bergeron, Cesar Ceballos, and josef Küstner. Elliptic and \(q\)-analogues of the Fibonomial numbers. Preprint arXiv:1911.12785. · Zbl 1447.05037 |

[5] | Brändén, Petter, \(q\)-Narayana numbers and the flag \(h\)-vector of \(J({ 2}\times{ n})\), Discrete Math., 281, 1-3, 67-81 (2004) · Zbl 1042.05001 |

[6] | Francesco Brenti. Log-concave and unimodal sequences in algebra, combinatorics, and geometry: an update. In Jerusalem combinatorics ’93, volume 178 of Contemp. Math., pages 71-89. Amer. Math. Soc., Providence, RI, 1994. · Zbl 0813.05007 |

[7] | Shalosh B. Ekhad. The Sagan-Savage Lucas-Catalan polynomials have positive coefficients. Preprint arXiv:1101.4060. · Zbl 0933.05007 |

[8] | Gessel, Ira; Viennot, Gérard, Binomial determinants, paths, and hook length formulae, Adv. in Math., 58, 3, 300-321 (1985) · Zbl 0579.05004 |

[9] | Verner E. Hoggatt, Jr. and Calvin T. Long. Divisibility properties of generalized Fibonacci polynomials. Fibonacci Quart., 12:113-120, 1974. · Zbl 0284.10003 |

[10] | Sagan, Bruce E.; Savage, Carla D., Combinatorial interpretations of binomial coefficient analogues related to Lucas sequences, Integers, 10, A52, 697-703 (2010) · Zbl 1227.11041 |

[11] | Richard P. Stanley. Log-concave and unimodal sequences in algebra, combinatorics, and geometry. In Graph theory and its applications: East and West (Jinan, 1986), volume 576 of Ann. New York Acad. Sci., pages 500-535. New York Acad. Sci., New York, 1989. · Zbl 0792.05008 |

[12] | Bruce E Sagan and Jordan Tirrell. Lucas atoms. Preprint arXiv:1909.02593. |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.