On Vince Vatter's Brilliant Extension of Doron Zeilberger's Enumeration Schemes for Counting Herb Wilf's Classes

By Doron Zeilberger

.pdf   .ps   .tex  
Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger
First Written: Dec. 29, 2006.

This version (of this webpage NOT of the article): March 18, 2013.
[It adds links to the Maple package ARV and its output files, corroborating an amazing result of M. Albert, N. Ruksuc, and V. Vatter. See the bottom of this webpage.]

Previous Version: March 26, 2007 (incorporating referee Lara Pudwell's comments.) March 28, 2007 (incorporating some of referee Vince Vatter's comments.)

This is a modest improvement on Vince Vatter's major improvement of my original enumeration schemes paper

My brilliant current student, Lara Pudwell, is currently extending this to words (a.k.a. multiset permutations).

added March 26, 2007: Thoroughly refereed by Lara Pudwell. Read Lara Pudwell's report and my response .

added March 28, 2007: Also thoroughly refereed by Vince Vatter. Read Vince Vatter's report and my response .

Important: This article is accompanied by Maple package VATTER that tries to find Vatter-Zeilberger-type enumeration schemes for any set of patterns.

Sample Input and Output for VATTER

  • In order to find enumeration schemes for single patterns of length 3 the input would yield the output
  • In order to find enumeration schemes for a set of two patterns, both of length 3, the input would yield the output
  • In order to find enumeration schemes for a set three patterns, each of length 3 the input would yield the output
  • In order to find enumeration schemes for sets of four patterns of each length 3 the input would yield the output
  • In order to find enumeration schemes for single patterns of length 4 the input would yield the output
  • In order to find enumeration schemes for sets of two patterns one of length 3 and the other of length 4, the input would yield the output
  • In order to find enumeration schemes for sets of two patterns both of length 4, the input would yield the output
  • In order to find enumeration schemes for sets of two patterns , one of length 3 and the other of length 5, the input would yield the output
  • In order to find enumeration schemes for sets of three patterns , one of length 3 and the other two of length 4, the input would yield the output
  • In order to find enumeration schemes for sets of three patterns , one of length 4 and the other two of length 3, the input would yield the output
  • In order to find enumeration schemes for sets of three patterns , all of length 4 , the input would yield the output

Added March 18, 2013: On March 7, 2013, Vince Vatter gave a brilliant talk [part 1, part 2] where he talked about, the still unwritten-up amazing result (joint with Michael Albert and Nik Ruskuc), that the pattern 321 is "barely" algebraic, i.e., while it is true that its enumerating generating function is algebraic (being counted by the famous Catalan numbers), if you add any pattern(s), you would get rational generating functions. Since I don't (completely) trust human reasoning, I adapted the package VATTER, and wrote a new Maple package

that tested this empirically.

Sample Input and Output for ARV for the pattern 321

  • In order to find generating functions for the sequences enumerating permutations that avoid the pattern 321 AND any ONE other pattern of length 4 (NOT containing it of course)
    the input would yield the output

  • In order to find generating functions for the sequences enumerating permutations that avoid the pattern 321 AND any ONE other pattern of length 5 (NOT containing it of course)
    the input would yield the output

  • In order to find generating functions for the sequences enumerating permutations that avoid the pattern 321 AND any TWO other patterns of length 4 (NOT containing it of course)
    the input would yield the output

  • In order to find generating functions for the sequences enumerating permutations that avoid the pattern 321 AND any TWO other patterns of length 5 (NOT containing it of course)
    the input would yield the output

Vince Vatter also mentioned that the analogous result for the pattern 312 is already known, and can be found (Example 2 on Page 12) of this beautiful article of Michael Albert and Mike Atkninson entitled "Simple permutations and pattern restricted permutations", officially published in Discrete Mathematics v. 300 (2005), 1-15.

Here is the empirical evidence for it.

Sample Input and Output for ARV for the pattern 312

  • In order to find generating functions for the sequences enumerating permutations that avoid the pattern 312 AND any ONE other pattern of length 4 (NOT containing it of course)
    the input would yield the output

  • In order to find generating functions for the sequences enumerating permutations that avoid the pattern 312 AND any ONE other pattern of length 5 (NOT containing it of course)
    the input would yield the output

  • In order to find generating functions for the sequences enumerating permutations that avoid the pattern 312 AND any TWO other patterns of length 4 (NOT containing it of course)
    the input would yield the output

  • In order to find generating functions for the sequences enumerating permutations that avoid the pattern 312 AND any TWO other patterns of length 5 (NOT containing it of course)
    the input would yield the output
    [It ran out of memory in the middle, sorry!]

Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

Doron Zeilberger's Home Page