AUTOMATIC GENERATION of THEOREMS and PROOFS On Enumerating Permutations that Avoid Consecutive Patterns

Brian NAKAMURA and Doron ZEILBERGER^{1}

Preface

The present article is a case study in automated generation of theorems and proofs in mathematics, and its main goal is to present by example a research methodology, extensively pursued by Zeilberger and his students, of “teaching” the computer to do research in mathematics. Hence, we will focus on the meta-level and expect the reader to look up, for human approaches, the pioneering work of Elizalde and Noy [EN], and the subsequent exciting work of, Anders Claesson, Toufik Mansour, Sergey Kitaev, Anthony Mendes, Jeff Remmel, and the more recent work of Vladimir Dotsenko and Anton Khoroshkin and Boris Shapiro, and the beautiful resolution of the Warlimont conjecture by Richard Ehrenborg, Sergey Kitaev, and Peter Perry [EKP]. This paper also contains extensive references. We will also assume that the reader is familiar with Zeilberger’s Umbral Transfer Matrix method [Z1]. See [EZ][Z1][Z2][Z3][Z4] for previous, computer-generated, appilcations.

The present article, and especially the accompanying Maple package ELIZALDE downloadable

References

[EKP] Richard Ehrenborg, Sergey Kitaev, and Peter Perry, A Spectral Approach to Consecutive Pattern-Avoiding Permutations, arXiv: 1009.2119v1 [math.CO] 10 Sep 2010

[EN] S. Elizalde and M. Noy, Consecutive patterns in permutations, Advances in Applied Mathematics 30 (2003), 110-125.

[EZ] Shalosh B. Ekhad, and D. Zeilberger, Using Rota’s Umbral Calculus to Enumerate Stanley’s P-Partitions, Advances in Applied Mathematics 41 (2008), 206-217.

[Z1] D. Zeilbeger, The Umbral Transfer-Matrix Method I. Foundations, J. Comb. Theory, Ser. A 91 (2000), 451-463 .

[Z2] D. Zeilbeger, The Umbral Transfer-Matrix Method. III. Counting Animals, New Journal of Mathematics 7(2001), 223-231 .

1 Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen

Rd., Piscataway, NJ 08854-8019, USA. [bnaka, zeilberg] at math dot rutgers dot edu , http://www.math.rutgers.edu/~bnaka/ , http://www.math.rutgers.edu/~zeilberg/ . First version: Jan. 1, 2011. Accompanied by Maple packages ELIZALDE and SERGI downloadable from the webpage of this article:

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/agt.html, where the reader can find lots of sample input and output.

The second author was supported in part by the NSF.

Exclusively published in the Personal Journal of S.B. Ekhad and Doron Zeilberger http://www.math.rutgers.edu/~zeilberg/pj.html and arxiv.org.

[Z3] D. Zeilbeger, The Umbral Transfer-Matrix Method V. The Goulden-Jackson Cluster Method for Infinitely Many Mistakes, Integers 2 (2002), A5.

[Z4] D. Zeilbeger, In How Many Ways Can You Reassemble Several Russian Dolls?, Personal

Journal of S.B. Ekhad and D. Zeilberger, http://www.math.rutgers.edu/~zeilberg/pj.html, Sept. 16,

2009.