The Enumeration of Permutations with a prescribed number of `forbidden' patterns
(with John Noonan)[Adv. Appl. Math. 17(1996), 381-407]
Stack-Permutations are those that avoid the pattern acb. Wilf asked,
and Julian West and several others considered, the problem of enumerating
permutations that avoid other, longer, patterns. Here we go yet one
step beyond, by tackling the problem of enumerating permutations
that contain the `forbidden' patterns exactly r times.
(Plain) .tex version
.dvi (for previewing)
.ps version
.pdf version
Added Dec. 10, 1996:
Mireille Bousquet-Melou and Ira Gessel made some
interesting comments
Added May 30, 2015: Scott Garrabrant and Igor Pak, in a beautiful
tour de force, disproved the Noonan-Zeilberger conjecture.
DZ donated $100 to the OEIS in their honor.
Back to
Doron Zeilberger's List of Papers
Back to
Doron Zeilberger's Home Page