×

Counting on Chebyshev polynomials. (English) Zbl 1223.33013

Summary: Chebyshev polynomials have several elegant combinatorial interpretations. Specifically, the Chebyshev polynomials of the first kind are defined by \(T_{0}(x) = 1, T_{1}(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_{1}(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.

MSC:

33C45 Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.)
11B39 Fibonacci and Lucas numbers and polynomials and generalizations
97K20 Combinatorics (educational aspects)