The generalized lucky ticket problem perfect matc

Authors: Joseph P Brennan Robert A Van Gorder

Publish Date: 2014/05/17

Volume: 37, Issue: 2, Pages: 269-289

PDF Link

Abstract

Consideration is given to an asymmetric ticket of length m+n in base ell Such a ticket is said to be mnlucky if the sum of the first m digits is equal to that of the last n digits In other words a mnlucky ticket is a m+n digit number in base ell of the form a 1a 2cdots a mb 1b 2cdots b n where a ib j in left 012dots ell 1 right and a 1 + a 2 + cdots + a m = b 1 + b 2 + cdots + b n Applying both analytical contour integral and combinatorial methods we arrive at two representations for the number of mnlucky tickets in base ell Our results reduce to those in the literature when m=n and ell =10 Furthermore through the contour integral approach we arrive at a nonobvious 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 qHermite 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 q=0 limit we obtain a representation equivalent to that of De SainteCatherine 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

Keywords: