The generalized lucky ticket problem, perfect matchings, and closure relations satisfied by the Chebyshev and \(q\) -Hermite polynomials

详细信息    查看全文

• 作者：Joseph P. Brennan ; Robert A. Van Gorder
• 关键词：Lucky tickets ; Perfect matching ; Chebyshev polynomials ; $$q$$ q ; Hermite polynomials ; Contour integration methods ; Primary 05C70 ; 33D45 ; Secondary 05A15
• 刊名：The Ramanujan Journal
• 出版年：2015
• 出版时间：June 2015
• 年：2015
• 卷：37
• 期：2
• 页码：269-289
• 全文大小：484 KB
• 参考文献：1.Aliashvili, T.: Geometry and topology of proper polynomial mappings. J. Math. Sci. 160, 679鈥?92 (2009)View Article MATH MathSciNet
  2.Askey, R.: Linearization of the product of orthogonal polynomials. In: Gunning R.C. (ed.) Problems in Analysis, A Symposium in Honor of Salomon Bochner, Princeton University Press, Princeton, NJ, 1970, pp. 131鈥?38. CBMS Regional Conference Series in Applied Mathematics, vol. 21, SIAM, Philadelphia (1975)
  3.Askey, R.: Orthogonal Polynomials and Special Functions. In: CBMS Regional Conference Series in Applied Mathematics, vol. 21. SIAM, Philadelphia (1975)
  4.Askey, R., Ismail, M.E.H.: A generalization of ultraspherical polynomials. In: Erd枚s, P. (ed.) Studies in Pure Mathematics. Birkhauser, Basel (1983)
  5.De M茅dicis, A., Stanton, D., White, D.: The combinatorics of q-Charlier polynomials. J. Combin. Theory Ser. A 69(1), 87鈥?14 (1995)View Article MATH MathSciNet
  6.De Sainte-Catherine, M. , Viennot, X.G.: Combinatorial Interpretation of Integrals of Products of Hermite, Laguerre and Tchebycheff Polynomials. In: Lecture Notes in Mathematics, vol. 1171, pp. 120鈥?28. Springer, New York (1985)
  7.Foata, D., Zeilberger, D.: Laguerre polynomials, weighted derangements and positivity. SIAM J. Discret. Math. 1, 425鈥?33 (1988)View Article MATH MathSciNet
  8.Fulmek, M.: Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three. Adv. Appl. Math. 30, 607鈥?32 (2003)View Article MATH MathSciNet
  9.Gessel, I.: Generalized rook polynomials and orthogonal polynomials. In: q-Series and Partitions, Minneapolis, MN, 1988. IMA Volumes in Mathematics and Applications, vol. 18, pp. 159鈥?76. Springer, New York (1989)
  10.Ismail, M.E.H., Kasraoui, A., Zeng, J.: Separation of variables and combinatorics of linearization coefficients of orthogonal polynomials. J. Comb. Theory Ser. A 120, 561鈥?99 (2013)View Article MATH MathSciNet
  11.Ismail, M.E.H., Stanton, D., Viennot, G.: The combinatoric of \(q\) -Hermite polynomials and the Askey鈥揥ilson integral. Eur. J. Comb. 8, 379鈥?92 (1987)View Article MATH MathSciNet
  12.Ismail, M., Tamhankar, M.: A combinatorial approach to some positivity problems. SIAM J. Math. Anal. 10, 478鈥?85 (1979)View Article MATH MathSciNet
  13.Ismail M.: Personal communication (2013)
  14.Khovansky, A.: Fewnomials. AMS, Providence (1997)
  15.Kim, D., Zeng, J.: A combinatorial formula for the linearization coefficients of general Sheffer polynomials. Eur. J. Comb. 22, 313鈥?32 (2001)View Article MATH MathSciNet
  16.Kim, D., Zeng, J.: Combinatorics of generalized Tchebycheff polynomials. Eur. J. Comb. 24, 499鈥?09 (2003)View Article MATH MathSciNet
  17.Lando, S.K.: Lectures on Generating Functions. AMS, Providence (2003)View Article MATH
  18.Mansour, T., Vainshtein, A.: Layered restrictions and Chebyshev polynomials. Ann. Comb. 5, 451鈥?58 (2001)View Article MATH MathSciNet
  19.Mansour, T., Vainshtein, A.: Restricted permutations and Chebyshev polynomials. S茅minaire Lotharingien de Combinatoire 47 (2002). Article B47c
  20.Guibert, O., Mansour, T.: Restricted 132-involutions and Chebyshev polynomials. S茅minaire Lotharingien de Combinatoire 48 (2002). Article B48a
  21.Mansour, T.: Restricted 132-alternating permutations and Chebyshev polynomials. Ann. Comb. 7, 201鈥?27 (2003)View Article MATH MathSciNet
  22.Mihailovs, A.: Lucky tickets and the Petrovsky numbers. Bachelor鈥檚 thesis, University of Latvia (1995)
  23.Petrovsky, I., Oleynik, O.: On the topology of real algebraic curves. Izv. Akad. Nauk SSSR 13, 389鈥?02 (1949)
  24.Simion, R., Stanton, D.: Octabasic Laguerre polynomials and permutation statistics. J. Comput. Appl. Math. 68(1鈥?), 297鈥?29 (1996)View Article MATH MathSciNet
  25.Slater, L.J.: Generalized Hypergeometric Functions. Cambridge University Press, Cambridge (1966)MATH
  
• 作者单位：Joseph P. Brennan (1)
  Robert A. Van Gorder (1)
  
  1. Department of Mathematics, University of Central Florida, Orlando, FL聽, 32816-1364, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Number Theory
  Field Theory and Polynomials
  Combinatorics
  Fourier Analysis
  Functions of a Complex Variable
  
• 出版者：Springer U.S.
• ISSN：1572-9303

文摘

Consideration is given to an asymmetric ticket of length \(m+n\) in base \(\ell \). Such a ticket is said to be \((m,n)\)-lucky if the sum of the first \(m\) digits is equal to that of the last \(n\) digits. In other words, a \((m,n)\)-lucky ticket is a \(m+n\) digit number (in base \(\ell \)) of the form \(a_1a_2\cdots a_mb_1b_2\cdots b_n\) where \(a_i,b_j \in \left\{ 0,1,2,\dots ,\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 \((m,n)\)-lucky 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 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 \(q\)-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 \(q=0\) 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.