The Generalized Lucky Ticket Problem, Perfect Matchings, And Closure Relations Satisfied By The Chebyshev And (Formula Presented.)-Hermite Polynomials

Keywords

(Formula presented.)-Hermite polynomials; Chebyshev polynomials; Contour integration methods; Lucky tickets; Perfect matching

Abstract

Consideration is given to an asymmetric ticket of length (Formula presented.) in base (Formula presented.). Such a ticket is said to be (Formula presented.)-lucky if the sum of the first (Formula presented.) digits is equal to that of the last (Formula presented.) digits. In other words, a (Formula presented.)-lucky ticket is a (Formula presented.)m+n digit number (in base (Formula presented.)) of the form (Formula presented.). Applying both analytical (contour integral) and combinatorial methods, we arrive at two representations for the number of (Formula presented.)-lucky tickets in base (Formula presented.). Our results reduce to those in the literature, when (Formula presented.) and (Formula presented.). Furthermore, through the contour integral approach, we arrive at a non-obvious closure relation satisfied by the Chebyshev polynomials. The weighted ticket problem is also considered, and analogous results are obtained. As addressed by Ismail, Stanton, and Viennot, the generating function of the crossing numbers over perfect matchings is related to closure relations of (Formula presented.)-Hermite polynomials. In the second part of this paper, we give corresponding contour integral representations for these closure relations, which permit us to give an alternate representation of the number of perfect matchings between sets. In the (Formula presented.) limit, we obtain a representation equivalent to that of De Sainte-Catherine and Viennot for the number of Dyck words of a fixed length satisfying a set of algebraic restrictions. In order to relate the two combinatorial problems, we find an explicit correspondence between our contour formulations for each problem.

Publication Date

6-1-2015

Publication Title

Ramanujan Journal

Volume

37

Issue

2

Number of Pages

269-289

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1007/s11139-014-9564-9

Socpus ID

84928893330 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84928893330

This document is currently not available here.

Share

COinS