##
**Forbidden subsequences and Chebyshev polynomials.**
*(English)*
Zbl 0932.05007

Summary: In J. West [Discrete Math. 157, No. 1-3, 363-374 (1996; Zbl 0877.05002)] it was shown using transfer matrices that the number \(|S_n(123;3214)|\) of permutations avoiding the patterns 123 and 3214 is the Fibonacci number \(F_{2n}\) (as are also \(|S_n(213; 1234)|\) and \(|S_n(213;4123)|)\). We now find the transfer matrix for \(\bigl|S_n(123;r,r-1, \dots, 2,1,r+1) \bigr|\), \(\bigl|S_n(213;1,2, \dots,r,r+1) \bigr|\), and \(\bigl |S_n(213; r+1,1,2, \dots,r) \bigr |\), determine its characteristic polynomial in terms of the Chebyshev polynomials, and go on to determine the generating function as a quotient of modified Chebyshev polynomials. This leads to an asymptotic result for each \(r\) which collapses to the exact results \(2^n\) when \(r=2\) and \(F_{2n}\) when \(r=3\) and to the Catalan number \(c_n\) as \(r\to\infty\). We observe that our generating function also enumerates certain lattice paths, plane trees, and directed animals, giving hope that these areas of combinatorics can be applied to enumerating permutations with excluded subsequences.

### Keywords:

permutations; Fibonacci number; Chebyshev polynomials; generating function; Catalan number; lattice paths; plane trees; directed animals; excluded subsequences### Citations:

Zbl 0877.05002
PDF
BibTeX
XML
Cite

\textit{T. Chow} and \textit{J. West}, Discrete Math. 204, No. 1--3, 119--128 (1999; Zbl 0932.05007)

Full Text:
DOI

### References:

[1] | Chung, F.R.K.; Graham, R.L.; Hoggatt, V.E.; Kleiman, M., The number of Baxter permutations, J. combin. theory ser. A, 24, 382-394, (1978) · Zbl 0398.05003 |

[2] | Simion, R.; Schmidt, F.W., Restricted permutations, European J. combin., 6, 383-406, (1985) · Zbl 0615.05002 |

[3] | Stanley, R.P., () |

[4] | West, J., Generating trees and the Catalan and schroder numbers, Discrete math., 146, 247-262, (1995) · Zbl 0841.05002 |

[5] | West, J., Generating trees and forbidden subsequences, Discrete math., 157, 363-374, (1996) · Zbl 0877.05002 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.