Automatic Generation of Theorems and Proofs on Enumerating Consecutive-Wilf classes

By Andrew Baxter, Brian Nakamura, and Doron Zeilberger

.pdf   .ps   .tex  
[Appeared in "Advances in Combinatorics: Waterloo Workshop in Computer Algebra, W80, May 26-29, 2011", (edited by Ilias Kotsireas and Eugene Zima), 121-138].
Written: Jan. 20, 2011.
To W from Z (et. al.), a gift for his (2/3)|S5|-th birthday
This article, describes two complementary approaches to enumeration, the positive and the negative, each with its advantages and disadvantages. Both approaches are amenable to automation, and when applied to the currently active subarea, initiated in 2003 by Sergi Elizalde and Marc Noy, of enumerating consecutive-Wilf classes (i.e. consecutive pattern-avoidance )in permutations, were successfully pursued by DZ's two current PhD students, Andrew Baxter and Brian Nakamura. The Maple packages SERGI and ELIZALDE, implementing the algorithms enable the computer to "do research" by deriving, "all by itself", functional equations for the generating functions that enable polynomial-time enumeration for any set of patterns. In the case of ELIZALDE (the "negative" approach), these functional equations can be sometimes (automatically!) simplified, and imply "explicit" formulas, that previously were derived by humans using ad-hoc methods. We also get lots of new "explicit" results, beyond the scope of humans, but we have to admit, that we still need humans to handle "infinite families" of patterns, but this too, no doubt will soon be automatable, and we leave it as a challenge to the (human and/or computer) reader.

Maple Packages

Important: This article is accompanied by Maple packages
  • ELIZALDE , for automatic generation of theorems, proofs, and sequences concerning the enumeration of permutations avoiding consecutive patterns, using an automation of an extension of the cluster method.
  • SERGI, that does the same thing but using the Umbral Transfer Method (automated, of course) directly. It is based on the work of Andrew Baxter, and is here mainly for comparison and for checking.

Sample Input and Output for the Maple package ELIZALDE: Number-Crunching

  • If you want to see the first 200 terms of the enumerating sequences for permutations that avoid a single pattern of length 3, for all possible patterns, as well as their asympototic formulas, ordered from smallest-to-largest,
    the input gives the output.

  • If you want to see the first 60 terms of the enumerating sequences for permutations that avoid a single pattern of length 4, for all possible patterns, as well as their asympototic formulas, ordered from smallest-to-largest,
    the input gives the output.

  • If you want to see the first 40 terms of the enumerating sequences for permutations that avoid a single pattern of length 5, for all possible patterns, as well as their asympototic formulas, ordered from smallest-to-largest,
    the input gives the output.

  • If you want to see the first 30 terms of the enumerating sequences for permutations that avoid a single pattern of length 6, for all possible patterns, as well as their asympototic formulas, ordered from smallest-to-largest,
    the input gives the output.

Sample Input and Output for the Maple package ELIZALDE: Automatic Generation of Theorems and Proofs

  • If you want to see all the theorems (but no proofs) about enumerating sequences for permutations that avoid a single pattern of length 3, for all possible patterns,
    the input gives the output.

  • If you want to see all the theorems (but no proofs) about enumerating sequences for permutations that avoid a single pattern of length 4, for all possible patterns,
    the input gives the output.

  • If you want to see all the theorems (but no proofs) about enumerating sequences for permutations that avoid a single pattern of length 5, for all possible patterns,
    the input gives the output.

  • If you want to see all the theorems (but no proofs) about enumerating sequences for permutations that avoid a single pattern of length 6, for all possible patterns,
    the input gives the output.
    [As you can see most of these theorems become very complicated for human eyes].

  • If you want to see all the theorems (and full proofs!) about enumerating sequences for permutations that avoid a single pattern of length 3, for all possible patterns,
    the input gives the output.

  • If you want to see all the theorems (and full proofs!) about enumerating sequences for permutations that avoid a single pattern of length 4, for all possible patterns,
    the input gives the output.

  • If you want to see all the theorems (and full proofs) about enumerating sequences for permutations that avoid a single pattern of length 5, for all possible patterns,
    the input gives the output.

Sample Input and Output for the Maple package SERGI: Number Crunching

  • Length-3 patterns:

    • If you want to see a ranked list of single patterns of length 3 according to the number of permutations that they avoid, followed by the first 100 terms of the (called P31 in the file)
      the input gives the output.

    • If you want to see a ranked list of sets of two patterns each of length 3 according to the number of permutations that they avoid, followed by the first 50 terms of the (called P32 in the file)
      the input gives the output.

    • If you want to see a ranked list of sets of three patterns each of length 3 according to the number of permutations that they avoid, followed by the first 50 terms of the (called P33 in the file)
      the input gives the output.

    • If you want to see a ranked list of sets of four patterns each of length 3 according to the number of permutations that they avoid, followed by the first 50 terms of the (called P34 in the file)
      the input gives the output.

    • If you want to see a ranked list of sets of five patterns each of length 3 according to the number of permutations that they avoid, followed by the first 50 terms of the (called P35 in the file)
      the input gives the output.

    • If you want to see a ranked list of sets of six patterns each of length 3 (there is only one such set obviously!, and you don't need a computer for this one!) according to the number of permutations that they avoid, followed by the first 50 terms of the (called P36 in the file)
      the input gives the output.

  • Length-4 patterns:

    • If you want to see a ranked list of single patterns of length 4 according to the number of permutations that they avoid, followed by the first 40 terms of the (called P41 in the file)
      the input gives the output.

    • If you want to see a ranked list of sets of two patterns each of length 4 according to the number of permutations that they avoid, followed by the first 40 terms of the (called P42 in the file)
      the input gives the output.

    • If you want to see a ranked list of sets of three patterns each of length 4 according to the number of permutations that they avoid, followed by the first 40 terms of the (called P43 in the file)
      the input gives the output.

  • Length-5 patterns:

    • If you want to see a ranked list of single patterns of length 5 according to the number of permutations that they avoid, followed by the first 30 terms of the (called P51 in the file)
      the input gives the output.

    • If you want to see a ranked list of sets of two patterns each of length 5 according to the number of permutations that they avoid, followed by the first 30 terms of the (called P52 in the file)
      the input gives the output

Sample Input and Output for the Maple package SERGI: Auotomatic Generation of Theorems

  • If you want to see the theorem that produces the system of functional equations for the weight-enumeration according to pattern pf length 2,
    the input gives the output

  • If you want to see the theorem that produces the system of functional equations for the weight-enumeration according to pattern pf length 3,
    the input gives the output

  • If you want to see the theorem that produces the system of functional equations for the weight-enumeration according to pattern pf length 4,
    the input gives the output

  • If you want to see the theorem that produces the system of functional equations for the weight-enumeration of permutations avoiding the consecutive pattern [1,2,3]
    the input gives the output

  • If you want to see the theorem that produces the system of functional equations for the weight-enumeration of permutations avoiding the consecutive patterns [1,2,3] and [1,3,2],
    the input gives the output

  • If you want to see the theorem that produces the system of functional equations for the weight-enumeration of permutations avoiding the consecutive patterns [1,2,3,4] and [1,3,2,4],
    the input gives the output

Doron Zeilberger's List of Papers

Doron Zeilberger's Home Page