Counting on Chebyshev Polynomials

Authors

Arthur T. Benjamin, Harvey Mudd CollegeFollow
Daniel Walton '07, Harvey Mudd CollegeFollow

Student Co-author

HMC Undergraduate

Document Type

Article

Department

Mathematics (HMC)

Publication Date

4-2009

Abstract

Chebyshev polynomials have several elegant combinatorial interpretations. Specificially, the Chebyshev polynomials of the first kind are defined by T₀(x) = 1, T₁(x) = x, and T_n(x) = 2x T_n-1(x) - T_n-2(x). Chebyshev polynomials of the second kind U_n(x) are defined the same way, except U₁(x) = 2x. T_n and U_n are shown to count tilings of length n strips with squares and dominoes, where the tiles are given weights and sometimes color. Using these interpretations, many identities satisfied by Chebyshev polynomials can be given combinatorial proofs.

Comments

First published in Mathematics Magazine, vol. 82, no. 2 (April 2009), by the Mathematical Association of America.

Rights Information

© 2009 Mathematical Association of America

Terms of Use & License Information

Terms of Use for work posted in Scholarship@Claremont.

Recommended Citation

Benjamin, A.T., & Walton, D. (2009). Counting on Chebyshev Polynomials. Mathematics Magazine, 82(2): 117-126.