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