BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Doron Zeilberger appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
This is a symbolic-computational redux, and extension, of a beautiful paper, by Harry Dym and Eugene Luks, published in 1966 (but written in 1964) about a certain game with balls and cells.
We state and prove an explicit evaluation of a certain multi-variate integral and use it to furnish a new, and shorter, proof of an elegant determinant identity of Michael Dougherty and Jon McCammond that came up in their study of critical values.
Inspired by a recent beautiful construction of Armin Straub and Wadim Zudilin, that 'tweaked' the sum of the $s^{th}$ powers of the $n$-th row of Pascal's triangle, getting instead of sequences of numbers, sequences of rational functions, we do the same for general binomial coefficients sums, getting a practically unlimited supply of Apéry limits. While getting what we call "major Apéry miracles", proving irrationality of the associated constants (i.e. the so-called Apéry limits) is very rare, we do get, every time, at least a "minor Apéry miracle" where an explicit constant, defined as an (extremely slowly-converging) limit of some explicit sequence, is expressed as an Apéry limit of some recurrence, with some initial conditions, thus enabling a very fast computation of that constant, with exponentially decaying error.
How many ways, exactly, can a Chess King, always moving forward (i.e. with steps [1,0],[0,1],[1,1]) walk to [100000,200000]? Thanks to the amazing Apagodu-Zeilberger extension of the Almkvist-Zeilberger algorithm, adapted in this article for combinatorial applications, this 104492-digit number, can be computed in less than 33 seconds. But not just this particular number. Many other numbers that come up in enumerative combinatorics, can be computed just as efficiently
In this memorial tribute to Joe Gillis, who taught us that Special Functions count, we show how the seminal Even-Gillis integral formula for the number of derangements of a multiset, in terms of Laguerre polynomials, can be used to efficiently compute not only the number of the title, but much harder ones, when it is interfaced with Wilf-Zeilberger algorithmic proof theory.
There are only aleph-zero rational numbers, while there are 2 to the power aleph-zero real numbers. Hence the probability that a randomly chosen real number would be rational is 0. Yet proving rigorously that any specific, natural, real constant, is irrational is usually very hard, witness that there are still no proofs of the irrationality of the Euler-Mascheroni constant, the Catalan constant, or Zeta(5). Inspired by Frits Beukers' elegant rendition of Apery's seminal proofs of the irrationality of Zeta(2) and Zeta(3), and heavily using algorithmic proof theory, we systematically searched for other similar integrals, that lead to irrationality proofs. We found quite a few candidates for such proofs, including the square-root of Pi times Gamma(7/3)/Gamma(-1/6) and Gamma(19/6)/Gamma(8/3) divided by the square-root of Pi.
We use the data of tenured and tenure-track faculty at ten public and private math departments of various tiered rankings in the United States, as a case study to demonstrate the statistical and mathematical relationships among several variables, e.g., the number of publications and citations, the rank of professorship and AMS fellow status. At first we do an exploratory data analysis of the math departments. Then various statistical tools, including regression, artificial neural network, and unsupervised learning, are applied and the results obtained from different methods are compared. We conclude that with more advanced models, it may be possible to design an automatic promotion algorithm that has the potential to be fairer, more efficient and more consistent than human approach.
Inspired by the recent pioneering work, dubbed "The Ramanujan Machine" by Raayoni et al. (arXiv:1907.00205), we (automatically) [rigorously] prove some of their conjectures regarding the exact values of some specific infinite continued fractions, and generalize them to evaluate infinite families (naturally generalizing theirs). Our work complements their beautiful approach, since we use symbolic rather than numeric computations, and we instruct the computer to not only discover such evaluations, but at the same time prove them rigorously.
Dyck paths are one of the most important objects in enumerative combinatorics, and there are many papers devoted to counting selected families of Dyck paths. Here we present two approaches for the automatic counting of many such families, using both a "dumb" approach (driven by numeric dynamic programming) that often works in practice, and a "clever" approach, needed for larger problems, driven by "symbolic" dynamic programming. Both approaches are fully automated and implemented in Maple.
In Ramanujan's Lost Notebook there is an amazing identity that furnishes infinitely many "almost counterexamples" to the cubic Fermat's Last Theorem, with no indication whatsoever how he discovered it. In 1995, Michael Hirschhorn explained, in a brilliant way, how Ramanujan may have done it, based on a certain polynomial identity for a sum of four cubes. Much earlier, Eri Jabotinsky, in an article published in 1946 (in a mathematics journal for teenagers) explained how Ramanujan may have discovered these polynomial identities needed for Hirschhorn's approach. Here we combine these two brilliant ideas (that may or may not have been how Ramanujan did it), automate it, and generalize, by developing an algorithm to solve a large class of cubic diophantine equations. Our interest in this problem was rekindled after reading Amy Alznauer's (b. Andrews) delightful children book "The Boy Who Dreamed of Infinity" (Candlewick Press), 2020, where Ramanujan's identity appears in one of the illustrations.
The number of Young Tableaux whose shape is a k by n rectangle is famously (nk)! 0! ... (k-1)!/((n+k-1)!(n+k-2)!... n!) implying that for each specific k, that sequence satisfies a linear recurrence equation with polynomial coefficients of the first order. But what about counting Young tableaux where certain "run lengths" are forbidden? Then things seem to get much more complicated. We conclude with four conjectures and pledge donations to the OEIS in honor of the first provers.
In a delightful article that recently appeared in the American Mathematics Monthly, Norbert Henze and Guenter Last discuss the "Absent-Minded Passengers" Problem, but left open finding an explicit expression for the probability generating function, of the random variable "Number of passengers occupying a wrong seat", when the number of absent-minded passengers is larger than one. This is accomplished in this note, using experimental mathematics and symbolic computation. We also derive explicit expressions for the first 8 moments of the original case of one absent-minded passenger, and indicate how to extend it to the general case
Inspired by the Croot-Lev-Pach breakthrough, Jordan Ellenberg and Dion Gijswijt have recently amazed the combinatorial world by proving that the largest size of a subset of $F_3^n$ with no 3-term arithmetic progressions is exponentially less than the size, $3^n$ of $F_3^n$ (and, more generally, $q^n$ for $F_q^n$). Here we give a motivated, top-down, rendition of their beautiful proof, that aims to make it appreciated by a wider audience.
Pisot sequences (sequences $a_n$ with initial terms $a_0=x, a_1=y$, and defined for $n>1$ by $a_n= \lfloor a_{n-1}^2/a_{n-2} + \frac{1}{2} \rfloor$) often satisfy linear recurrences with constant coefficients that are valid for all $n \geq 0$, but there are also cautionary examples where there is a linear recurrence that is valid for an initial range of values of $n$ but fails to be satisfied beyond that point, providing further illustrations of Richard Guy's celebrated "Strong Law of Small Numbers". In this paper we present a decision algorithm, fully implemented in an accompanying Maple program ({\tt Pisot.txt}), that first searches for a putative linear recurrence and then decides whether or not it holds for all values of $n$. We also explain why the failures happen (in some cases the `fake' linear recurrence may be valid for thousands of terms). We conclude by defining, and studying, higher-order analogs of Pisot sequences, and point out that similar phenomena occur there, albeit far less frequently. This article is dedicated to Richard K. Guy (b. Sept. 30, 1916) on his 100th birthday.
Doron Gepner's word statistics, that came up in his research in conformal field theory, is studied and it is conjectured that its scaled limiting distribution is the Logistic distribution. We support this by proving rigorously that the scaled limits of the first twelve moments do indeed converge to those of the Logistic distribution. This is surprising, since Gepner's statistics is a natural analog of the classical statistics called the number of inversion, that is known to be asymptotically normal.
We discuss how to decide whether a given C-finite sequence can be written nontrivially as a product of two other C-finite sequences.
In this tribute to Neil Sloane, we revisit the first sequence in the On-Line Encyclopedia of Integer Sequences, sequence A435 (1, 8, 78, 944, 13800, 237432, 4708144, 105822432, ...), that he encountered when he was a graduate student, and when normalized gives the average total height of rooted labeled trees. We state rigorously-computed explicit expressions for the first twelve moments of the random variable `total height' on rooted labeled trees, and pledge to donate to the OEIS 100 dollars in honor of the first to find an explicit expression for the probability density function of the limiting scaled probability distribution, as n goes to infinity.
Continuing pioneering work of Christophe Doche and Laurent Habsieger from 2004, we develop computer algebra algorithms, implemented in Maple, for finding the (necessarily rational) generating function for any integral of products, and in particular, moments, of Rudin-Shapiro polynomials. We generate a lot of output, and confirm again a conjecture of Saffari for the asymptotics for small (and not so small) powers. We also confirm, for small powers, a related, more general, conjecture, of Hugh Montgomery. Finally, we outline a proof of Saffari's full conjecture, that we believe can be turned into a full proof. [In this version we report that Brad Rodgers has independently found a (complete!) proof of Saffari's conjecture here http://arxiv.org/abs/1606.01637] .
Shmuel Friedland and Giorgio Ottaviani's beautiful constant term expression for the number of singular vector tuples of generic tensors is used to derive a rational generating function for these numbers, that in turn, is used to obtain an asymptotic formula for the number of such tuples for n by n by n three-dimensional tensors, and to conjecture an asymptotic formula for the general d-dimensional case. A donation of 100 dollars, in honor of the first prover, will be made to the On-line Encyclopedia of Integer Sequences.
In a recent beautiful but technical article, William Y.C. Chen, Qing-Hu Hou, and Doron Zeilberger developed an algorithm for finding and proving congruence identities (modulo primes) of indefinite sums of many combinatorial sequences, namely those (like the Catalan and Motzkin sequences) that are expressible in terms of constant terms of powers of Laurent polynomials. We first give a leisurely exposition of their elementary but brilliant approach, and then extend it in two directions. The Laurent polynomials may be of several variables, and instead of single sums we have multiple sums. In fact we even combine these two generalizations! We conclude with some super-challenges. In this version we report that Roberto Tauraso pointed out that all our conjectured super-congruences, at the end of our article are already known, except one, for which he supplied a beautiful proof that can be found here: arXiv:1606.05543.
We develop a meta-algorithm that, given a polynomial (in one or more variables), and a prime p, produces a fast (logarithmic time) algorithm that takes a positive integer n and outputs the number of times each residue class modulo p appears as a coefficient when the polynomial is raised to the power n and the coefficients are read modulo p.
A very short, bijective proof, of Touchard's Catalan identity is given, using Dyck paths.
Many combinatorial sequences (for example, the Catalan and Motzkin numbers) may be expressed as the constant term of $P(x)^k Q(x)$, for some Laurent polynomials $P(x)$ and $Q(x)$ in the variable $x$ with integer coefficients. Denoting such a sequence by $a_k$, we obtain a general formula that determines the congruence class, modulo $p$, of the indefinite sum $\sum_{k=0}^{rp -1} a_k$, for {\it any} prime $p$, and any positive integer $r$, as a linear combination of sequences that satisfy linear recurrence (alias difference) equations with constant coefficients. This enables us (or rather, our computers) to automatically discover and prove congruence theorems for such partial sums. Moreover, we show that in many cases, the set of the residues is finite, regardless of the prime $p$.
In this short article, two recent beautiful proofs of George Andrews, Aviezri Fraenkel, and James Sellers, about the mod m characterization of the number of m-ary partitions are simplified and streamlined, and then generalized to handle many more cases, and prove much deeper theorems, with the help of computers, of course.
Jaclyn Anderson proved that if s and t are relatively prime positive integers, then there are exactly (s+t-1)!/(s!t!) partitions whose set of hook-lengths is disjoint from the set {s,t}. Drew Armstrong conjectured (and Paul Johnson, and a bit later, Victor Wang, proved) a beautiful expression for the average size, namely (s-1)(t-1)(s+t+1)/24 . In the present article, we go far beyond the average, and state absolutely certain expressions (but "officially" still conjectures) for the variance (showing in particular that it is rather large, and there is no "concentration about the mean"), and the third through the sixth moments. For the special case of (s,s+1)-core partitions, we go all the way to the 9th moment. We pose two challenges, and will be glad to donate 100 dollars each, to the OEIS foundation in honor of the first provers, regarding a "soft" and "global", yet rigorous, justification of our empirical approach, and for proving an intriguing conjecture about the limiting distribution. This version reports (thanks to Marko Thiel and Nathan Williams) that the second challenge mentioned above has been done by Paul Johnson (but not in two pages). A donation to the OEIS was made. The first challenge is still wide open.
In the classic "Concrete Math", by Graham, Patashnik and Knuth, it is stated that "The numbers in Pascal's triangle satisfy, practically speaking, infinitely many identities, so it is not too surprising that we can find some surprising relationships by looking closely." The aim of this note is to indicate that a similar statement seems to hold for the character tables of the symmetric groups $S_n$. Just as important, it is a case-study in using a computer algebra system to prove deep identities, way beyond the ability of mere humans. This article is accomanied by a Maple pacgage, Sn, and ample output, avaialble from the webpage http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/sn.html .
An "odd-rule" cellular automaton (CA) is defined by specifying a neighborhood for each cell, with the rule that a cell turns ON if it is in the neighborhood of an odd number of ON cells at the previous generation, and otherwise turns OFF. We classify all the odd-rule CAs defined by neighborhoods which are subsets of a 3 X 3 grid of square cells. There are 86 different CAs modulo trivial symmetries. When we consider only the different sequences giving the number of ON cells after n generations, the number drops to 48, two of which are the Moore and von Neumann CAs. This classification is carried out by using the "meta-algorithm" described in an earlier paper to derive the generating functions for the 86 sequences, and then removing duplicates. The fastest-growing of these CAs is neither the Fredkin nor von Neumann neighborhood, but instead is one defined by "Odd-rule" 365, which turns ON almost 75% of all possible cells.
A set of arithmetical sequences $$ a_1\, (\bmod{ \,\, m_1}) \quad, \quad a_2 \, (\bmod{\,\, m_2}) \quad, \quad \dots \quad , \quad a_k \, (\bmod{\,\,m_k}) \quad \quad , $$ with $$ m_1 \leq m_2 \leq \dots \leq m_k \quad \quad , $$ is called a {\it disjoint covering system} (alias {\it exact covering system}) if every positive integer belongs to {\bf exactly} one of the sequences. Mirski, Newman, Davenport and Rado famously proved that the moduli can't all be distinct. In fact the two largest moduli must be equal, i.e. $m_{k-1}=m_k$ This raises the natural question:"How close can you get to getting distinct moduli?", in other words, can you find all such systems where all the moduli are distinct except the largest, that is repeated $r$ times, for any, specific given $r$? It turns out (conjecturally, but almost certainly) that excluding the trivial case where the smallest modulus is 2, for any number of repeats $r$, there are only finitely many such systems. Marc Berger, Alexander Felzenbaum and Aviezri Fraenkel found them all for $r$ up to $9$, and Mekmamu Zeleke and Jamie Simpson extended the list for systems up to $12$ repeats. In the present article we continue the list up to $r=32$. All our systems are correct, but we did not bother to formally prove completeness, but we know for sure that the lists are complete if the largest modulus is $\leq 600$, and we are pretty sure that they are complete.
In a recent article (arXiv:1507.03499) (joint with Alon Regev) we studied sums of squares of characters Chi(L,M) of the Symmetric Group over shapes L that are two-rowed, and shapes L that are hook shapes, and M is an arbitrary shape that mostly consists of ones, and designed algorithms for closed-form evaluations of each of these. We noted (and proved) that when M is the shape with n cells consisting of 3 followed by n-3 ones, the former sum equals one half time the analogous sum over hook shapes with n+2 cells and M is the partition consisting of 3,2, followed by n-3 ones. Here we show that this is just a tip of an iceberg, and prove (alas, by purely human means) that the former sum with M consisting of all odd parts, and (possibly) a consecutive string of powers of 2, starting at 2, equals one half of the latter sum where M is replaced by a partition where all the odd parts are retained but the consecutive string of powers of 2: 2,4, ..., $2^{t-1}$ is replaced by $2^t$.
The problems of enumerating lattice walks, with an arbitrary finite set of allowed steps, both in one and two dimensions, where one must always stay in the non-negative half-line and quarter-plane respectively, are used, as case studies, to illustrate the `naive' methodology of guess-and-check, where rigorous proofs are possible, but not worth the trouble. We argue that this is a metaphor for future math.
We use the Robinson-Schensted correspondence, followed by symbol-crunching, in order to derive explicit expressions for the quantities mentioned in the title. We follow it by number crunching, in order to compute the first terms of these sequences. As an encore, we cleverly implement Ira Gessel's celebrated determinant formula for the generating functions of these sequences, to crank out many terms. This modest tribute is dedicated to one of the greatest enumerators alive today (and definitely the most modest one!), Ira Martin Gessel, who is turning 64 years-old today
We give yet-another illustration of using Herb Wilf's Snake Oil Method, by proving a certain identity between the entries of the so-called Motzkin Triangle, that arose in a recent study of enumeration of certain classes of integer partitions. We also briefly illustrate how this method can be applied to general `triangles'.
Once upon a time there was an esoteric and specialized notion, called "size of the Durfee square", of interest to at most 100 specialists in the whole world. Then it was kissed by a prince called Jorge Hirsch, and became the famous (and to quite a few people, infamous) h-index, of interest to every scientist, and scholar, since it tells you how productive a scientist (or scholar) you are! When Rodney Canfield, Sylvie Corteel, and Carla Savage wrote their beautiful 1998 article proving, rigorously, by a very deep and intricate analysis, the asymptotic normality of the random variable "size of Durfee square" defined on integer-partitions of n (as n goes to infinity), with precise asymptotics for the mean and variance, they did not dream that one day their result should be of interest to everyone who has ever published a paper. However Canfield et. al. had to work really hard to prove their deep result. Here we take an "empirical" shortcut, that proves the same thing much faster (modulo routine number- and symbol- crunching). More importantly, the empirical methodology should be useful in many other cases where rigorous proofs are either too hard, or not worth the trouble!
We present an empirical-yet-rigorous approach for solving a wide class of functional equations, thereby automating many results that previously required considerable human ingenuity and human labor.
I conjecture a certain explicit determinant evaluation, whose proof would imply the solution of certain enumeration problem that I have been working on, and that I find interesting. I am pledging \$500 to the OEIS Foundation (in honor of the prover!) for a proof, and \$50 (in honor of the disprover)
I describe an empirical-yet-rigorous, algorithm, based on Riordan's rook polynomials and the so-called C-finite ansatz, fully implemented in the accompanying Maple package (http://www.math.rutgers.edu/~zeilberg/tokhniot/MENAGES ), MENAGES, that reproduces in a few seconds, rigorously-proved enumeration theorems on permutations with restricted positions, previously proved by quite a few illustrious human mathematicians, and that can go far beyond any human attempts.
In this case-study in computer-human collaboration, we develop, implement, and execute symbolic-computational algorithms for the automatic discovery and proof of explicit expressions for the expectation, variance, and higher moments of a large class of natural combinatorial statistics defined on Catalan-counted objects, enabling, inter-alia, to prove that they are not asymptotically normal. In particular, we reproduce in 0.12 seconds results of Miklos Bona, and derive far deeper results, way beyond the scope of humans, concerning higher moments of the random variable "number of occurrences of a pattern" in the set of 132-avoiding permutations for all patterns of length 2 and 3, and, more impressively, explicit expressions for the averages for all patterns of lengths up to 10. The ample output inspired us to make an intriguing conjecture concerning the number of so-called Bona classes, and we pledge to donate 100 dollars to the OEIS Foundation in honor of the prover (or disprover).
Joshua Cooper and Mark Walters initiated the subject that we call here Enumerative Geometric Genealogy, (and that lead to the hard-to-count OEIS sequence A140468) but they did not realize the broader impact of their research to the population explosion of a certain far-away planet, whose inhabitants are much smarter, and more civilized, than we are.
The beautiful theory of statistical gambling, started by Dubins and Savage (for subfair games) and continued by Kelly and Breiman (for superfair games) has mostly been studied under the unrealistic assumption that we live in a continuous world, that money is indefinitely divisible, and that our life is indefinitely long. Here we study these fascinating problems from a purely discrete, finitistic, and computational, viewpoint, using Both Symbol-Crunching and Number-Crunching (and simulation just for checking purposes).
Roger Apery's seminal method for proving irrationality is "turned on its head" and taught to computers, enabling a one second redux of the original proof of zeta(3), and many new irrationality proofs of many new constants, alas, none of them is both famous and not-yet-proved-irrational.
Using the Morris-Selberg Constant Term Identity, I sketch a proof of a recent conjecture by Karola Meszaros and Alejandro Morales, that I believe could be easily made fully rigorous by a sufficiently skilled and, sufficiently interested, analyst. This conjecture is an analog to the root system $D_n$ of a conjecture made in 1998 by Clara Chan, the late David P. Robbins, and David Yuen, that I proved immediately after, also using the Morris identity.
Recently, Bill Chen, together with his disciples Alvin Dai and Robin Zhou, discovered, and very elegantly proved, an algebraic equation satisfied by the generating function enumerating 123-avoiding words with two occurrences of each of 1, ..., n. Inspired by this result, we present an algorithm for finding such an algebraic equation for the ordinary generating function enumerating 123-avoiding words with exactly r occurrences of each of 1, ... n for any positive integer r, thereby proving that they are algebraic and not merely D-finite (a fact that is promised by WZ theory). Our algorithm consists of presenting an algebraic enumeration scheme, combined with the Buchberger algorithm
In this article, dedicated with admiration and gratitude to guru Neil Sloane on his 75-th birthday, we observe that the generating functions for multi-set permutations that do not contain an increasing subsequence of length d, and where every letter appears the same number of times, say r, are always D-finite, (for every d and every r), and we actually crank out the first few terms of quite a few of them, many of whom are not yet in the OEIS. We also state a conjectured asymptotic formula for these sequences, that reduces to Amitai Regev's famous formula when r=1, and pledge a 100 dollar donation to the OEIS in honor of the first one to prove our conjecture. We pledge another 100 dollars for extending Ira Gessel's spectacular Bessel determinant, from the r=1 case to general r.
This short tribute to the guru of Enumerative and Algebraic Combinatorics started out when one the authors(DZ) attended the Stanely@70 conference, that took place at the same time as the preliminary stage of the 2014 World Cup. It states a surprising application of an analog of Richard Stanley's famous theorem about the enumeration of magic squares to the enumeration of possible outcomes in a World Cup Group.
This short "education note" was inspired by Zvi Artstein's masterpiece Mathematics and the Real World, the Remarkable Role of Evolution in the Making of Mathematics (p. 53, and p. 400)
This article is a sequel to a recent article by Eric Rowland and Reem Yassawi, presenting yet another approach to the fast determination of congruence properties of `famous' combinatorial sequences. The present approach can be taught to a computer, and our beloved servant, Shalosh B. Ekhad, was able to generate many new theorems, for famous sequences, of course, but also for many obscure ones!
We give a short proof of a Ptolemy-style result first discovered and proved by Jane McDougall. It may be viewed as a generalization to any even number of points of the cubic relation connecting the six joint distances of four points on a circle (whose quadratic relation is the famed Plucker relation, alias Ptolemy's theorem). This article is in fond memory of Andrei Zelevinsky (1953-2013) who loved Ptolemy's theorem.
When Mike Hirschhorn showed us his lovely gem, that gives the simplest-to-date proof of Ramanujan's famous result that p(11n+6) is divisible by 11, we realized that his amazing method can be extended, and taught to a computer, and can prove even deeper identities. We would have done much more if not for the existence of Silviu Radu's powerful algorithm that handle any Ramanujan type congruence for any modular form (of a very general type), but it is still nice to know that in order to prove such simply stated results, that can be explained to a seven-year-old, one does not need the intimidating edifice of the "web of modularity", that Ramanujan never mastered, and probably would not have liked.
We show how to extend the Karolyi-Nagy beautiful proof of the Zeilberger-Bressoud q-Dyson theorem, (first proved by Zeilberger and Bressoud in 1985, and originally conjectured by George Andrews in 1975), that states that the constant term of a certain Laurent polynomial equals the q-multinomial coefficient, how to evaluate any other specific coefficient. The algorithm implies that any such coefficient is always a certain rational function (that the algorithm finds) times the q-multinomial coefficient.
Jacobi said "man muss immer umkehren". And indeed it takes a genius like Michael Somos to take a specific non-linear recurrence, like a(n)=(a(n-1)a(n-3)+a(n-2)^2)/a(n-4), subject to a(1)=1, a(2)=1, a(3)=1, a(4)=1, and observe that surprise, surprise, they always generate integers. Then it takes other geniuses to actually prove this fact (and the more general so-called Laurent phenomenon). But let's follow Jacobi's advise and go backwards. Rather than try to shoot a target fifty meters away, and most probably miss it, let's shoot first, and then draw the bull'e eye. Then we are guaranteed to be champion target-shooters. So let's take a sequence of integers that manifestly and obviously only consists of integers, and ask our beloved computers to find non-linear recurrences satisfied by the sequence itself, or by well-defined subsequences.
We study statistical properties of the random variables $X_σ(π)$, the number of occurrences of the pattern $σ$ in the permutation $π$. We present two contrasting approaches to this problem: traditional probability theory and the ``less traditional'' computational approach. Through the perspective of the first one, we prove that for any pair of patterns $σ$ and $τ$, the random variables $X_σ$ and $X_τ$ are jointly asymptotically normal (when the permutation is chosen from $S_{n}$). From the other perspective, we develop algorithms that can show asymptotic normality and joint asymptotic normality (up to a point) and derive explicit formulas for quite a few moments and mixed moments empirically, yet rigorously. The computational approach can also be extended to the case where permutations are drawn from a set of pattern avoiders to produce many empirical moments and mixed moments. This data suggests that some random variables are not asymptotically normal in this setting.
The aim of this paper is to describe the inversion of the sum $\sum_{n\geq 0}a^nb^n$ where $a$ and $b$ are non-commuting variables as a formal series in $a$ and $b$. We show that the inversion satisfies a non-commutative quadratic equation and that the number of certain monomials in its homogeneous components equals to a Catalan number. We also study general solutions of similar quadratic equations.
We use recurrence equations (alias difference equations) to enumerate the number of formula-representations of positive integers using only addition and multiplication, and using addition, multiplication, and exponentiation, where all the inputs are ones. We also describe efficient algorithms for the random generation of such representations, and use Dynamical Programming to find a shortest possible formula representing any given positive integer.
The brilliant idea of Jean Betrema and Jean-Guy Penaud that proved the celebrated "three to the power n" theorem of Dominique Gouyou-Beauchamps and Xavier Viennot, counting towers of domino pieces is extended and used to enumerate much more general towers, where the pieces can be many i-mers.
The deductive method ruled mathematics for the last 2500 years, now it is the turn of the inductive method. Here we make a modest start by using the inductive method to discover and prove (rigorously) explicit generating functions for the number of dimer (and monomer-dimer) tilings of large families of "skinny" plane regions.
In how many ways can you place n chocolate pieces all of different sizes in an n by n chocolate box, in such a way that when you go from left to right and from top to bottom, there are no gaps AND the sizes increase along each row and each column? The answer is the well-known OEIS Sequence Number 85. To our amazement, the analogous sequence for a three-dimensional chocolate box was not there. Here we fill this gap, and more importantly, offer some computational and theoretical challenges about enumerating families of Solid Standard Young Tableaux.
We apply a classic result in Theoretical Computer Science to solve a sticky problem, and give a neat and slick quick proof of half of it
The conjecture that the orbit-counting generating function for totally symmetric plane partitions can be written as an explicit product formula, has been stated independently by George Andrews and David Robbins around 1983. We present a proof of this long-standing conjecture.
The most amazing (at least to me) result in Enumerative Combinatorics is Dominique Gouyou-Beauchamps and Xavier Viennot's theorem that states that the number of so-called directed animals with compact source (that are equivalent, via Viennot's beautiful concept of heaps, to towers of dominoes, that I take the liberty of renaming xaviers) with n+1 points equals 3^n. This amazing result received an even more amazing proof by Jean Bétrema and Jean-Guy Penaud. Both theorem and proof deserve to be better known! Hence this article, that is also accompanied by a comprehensive Maple package http://www.math.rutgers.edu/~zeilberg/tokhniot/BORDELAISE that implements everything (and much more)
This article, written in fond memory of Herbert Saul Wilf (June 13, 1931- Jan. 7, 2012), explores integer partitions where each part shows up a different number of times than the other parts (if it shows up at least once), thereby making a modest contribution towards the solution of one of the eight intrigiung problems posted by Herb Wilf on his website on Dec. 13, 2010
One of the most challenging problems in enumerative combinatorics is to count Wilf classes, where you are given a pattern, or set of patterns, and you are asked to find a "formula", or at least an efficient algorithm, that inputs a positive integer n and outputs the number of permutations avoiding that pattern. In 1996, John Noonan and Doron Zeilberger initiated the counting of permutations that have a prescribed, r, say, occurrences of a given pattern. They gave an ingenious method to generate Functional Equations, alas, with an unbounded number of "catalytic variables", but then described a clever way, using multivariable calculus, how to get enumeration schemes. Alas, their method becomes very complicated for r larger than 1. In the present article we describe a far simpler way to squeeze the necessary information, in polynomial time, for increasing patterns of any length, and for any number of occurrences, r.
Global asymptotic stability of rational difference equations is an area of research that has been well studied. In contrast to the many current methods for proving global asymptotic stability, we propose an algorithmic approach. The algorithm we summarize here employs the idea of contractions. Given a particular rational difference equation, defined by a function $Q$ which maps the $k+1$ dimensional real numbers to itself, we attempt to find an integer, $K$, for which $Q^K$ shrinks distances to the difference equation's equilibrium point. We state some general results that our algorithm has been able to prove, and also mention the implementation of our algorithm using Maple.
In 1996, my brilliant student John Noonan, discovered, and proved that there are 3(2n)!/(n(n+3)!(n-3)!) ways to line-up n people of different heights in such a way that out of the n(n-1)(n-2)/6 possible triples of people exactly one is such that the tallest stands (not necessarily immediately) in front of the second-tallest, who in turn, stands (not necessarily immediately) in front of the shortest. In that article, I promised a prize of 25 dollars for a nice combinatorial proof. Alex Burstein gave such a proof. On Oct. 14, 2011, I talked about Alex's lovely proof at the Howard U. math colloquium, and publicly presented the 25-dollar prize. The present note is the outcome. Congratulations Alex!
This short article, dedicated to our beloved guru Philippe FLAJOLET (1948-2011), is a case-study in computer-generated combinatorial research, where the computer, all by itself, is using the transfer-matrix method to derive (rigorously!) rational generating functions for chromatic polynomials for infinite sequences of graphs generalizing the action of taking the Cartesian product with a path of length n, n=1,2,... .
This article, dedicated to Herbert Saul Wilf on the occaison of his forthcoming 80-th birthday, 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. The Maple packages, and lots of sample output, is available from the webpage of this article: http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/auto.html
Richard Stanely proposed, in a recent Amer. Math. Monthly Problem, to prove a nice explicit formula for the generating function for the number of n-letter words in {H,T} that have as many occurrences of HT as HH. In this article, we show how to prove this problem automatically, and ANY problem of that type, regardless of the size of the alphabet and the length of the two chosen strings
We comment on, elaborate, and extend the work of Warren Ewens and Herbert Wilf, described in their http://www.pnas.org/content/104/27/11189.full.pdf about the maximum in balls-and-boxes problem. In particular we meta-apply their ingenious method to show that it is not really needed, and that one is better off using the so-called Poisson Approximation, at least in applications to the real world, because extremely unlikely events mever happen in real life. This article is accompanied by the Maple package http://www.math.rutgers.edu/~zeilberg/tokhniot/BallsInBoxes">BallsInBoxes.
In order to appreciate how well off we mathematicians and scientists are today, with extremely fast hardware and lots and lots of memory, as well as with powerful software, both for numeric and symbolic computation, it may be a good idea to go back to the early days of electronic computers and compare how things went then. We have chosen, as a case study, a problem that was considered a huge challenge at the time. Namely, we looked at C.L. Pekeris's seminal 1958 work on the ground state energies of two-electron atoms. We went through all the computations ab initio with today's software and hardware, with a special emphasis on the symbolic computations which in 1958 had to be made by hand, and which nowadays can be automated and generalized.
While it is trivial to multiply two C-finite sequences (just like integers), it is not quite so trivial to "factorize" them, or to decide whether they are "prime". The former is plain linear algebra, while the latter is heavy-duty non-linear algebra, getting hairy systems of algebraic equations that can be solved, in principle, using Gröbner bases and the Buchberger algorithm, but, alas, sooner or later it becomes too hard even for the fastest and largest computers. The main technical novely of this article is a fast "algorithm" (it cheats and uses floating-point arithmetic, please don't tell anyone!) for deciding whether a given C-finite sequence can be written as a product of C-finite sequences of lower order. This article accompanies the Maple package Cfinite available from http://www.math.rutgers.edu/~zeilberg/tokhniot/Cfinite .
One of the landmarks of the modern theory of partial differential equations is the Malgrange- Ehrenpreis theorem that states that every non-zero linear partial differential operator with constant coefficients has a Green function (alias fundamental solution). In this short note I state the discrete analog, and give two proofs. The first one is Ehrenpreis- style, using duality, and the second one is constructive, using formal Laurent series. This article is accompanied by the Maple package LEON available from: http://www.math.rutgers.edu/~zeilberg/tokhniot/LEON .
We use recurrences (alias difference equations) to prove the longstanding conjecture that the two most important permutation statistics, namely the number of inversions and the major index, are asymptotically joint-independently-normal. We even derive more-precise-than needed asymptotic formulas for the (normalized) mixed moments. This is the fully revised second edition, incorportating the many insightful comments of nine conscientious NON-anonymous referees listed under the authors' names. This article is exclusively published in the on-line journal "Personal Journal of Shalosh B. Ekhad and Doron Zeilberger" and this arxiv.
This paper considers the problem of showing that every pair of binary trees with the same number of leaves parses a common word under a certain simple grammar. We enumerate the common parse words for several infinite families of tree pairs and discuss several ways to reduce the problem of finding a parse word for a pair of trees to that for a smaller pair. The statement that every pair of trees has a common parse word is equivalent to the statement that every planar graph is four-colorable, so the results are a step toward a language theoretic proof of the four color theorem.
There is no trivial mathematics, there are only trivial mathematicians! A mathematician is trivial if he or she believes that there exists trivial mathematics. Being a non-trivial mathematician myself, I will describe ten different proofs of the seemingly trivial fact that the number of ways of choosing k people out of n people is less than or equal to the number of ways of choosing k+1 people out of n people, provided that k is less than half of n.
In a recent article in American Scientist, Theodore Hill described a coin-tossing game whose pay-off is the number of heads over the total number of throws. Suppose that at a given point during the game you have 5 heads and 3 tails, should you stop and get 5/8, or should you keep playing, hoping to get a better score? This is still an open problem. In the present article, we explore different strategies to this game from the Experimental Mathematics perspective.
We present an elegant bijection between standard Young tableaux with 2n cells and at most two rows, and pairs of standard Young tableaux of the same shape, with n+1 cells, where only the top row can have more than one cell.
One of the main uses of computers is to do statistical analysis of data. But, so far, the theory of statistics, and its noble mother, Probability theory, were all discovered and developed by lowly humans. No more! Computers can also develop probability theory (and statistics), and discover (and prove!) general theorems of much larger depth than those discovered by human-kind. Of course, at this time of writing, they still need these inferior humans to give them a head-start by teaching (i.e. programming) them to develop probability theory ab initio (only better!), but even this will soon be superfluous.
We provide guessed recurrence equations for the counting sequences of rook paths on d-dimensional chess boards starting at (0..0) and ending at (n..n), where d=2,3,...,12. Our recurrences suggest refined asymptotic formulas of these sequences. Rigorous proofs of the guessed recurrences as well as the suggested asymptotic forms are posed as challenges to the reader.
We present a computer-aided, yet fully rigorous, proof of Ira Gessel's tantalizingly simply-stated conjecture that the number of ways of walking $2n$ steps in the region $x+y \geq 0, y \geq 0$ of the square-lattice with unit steps in the east, west, north, and south directions, that start and end at the origin, equals $16^n\frac{(5/6)_n(1/2)_n}{(5/3)_n(2)_n}$ .
We present general algorithms (fully implemented in Maple) for calculations of various quantities related to constrained directed walks for a general set of steps on the square lattice in two dimensions. As a special case, we rederive results of earlier works.
It is remarked that Dave Robbins's Expression for the integral of an alternant over the unit simplex (math.CO/9805108) follows immediately from an excercise in Polya-Szego.
Weinstein's[2] brilliant short proof of de Branges'[1] theorem can be made yet much shorter(modulo routine calculations), completely elementary (modulo Löwner theory), self contained(no need for the esoteric Legendre polynomials' addition theorem), and motivated(ditto), as follows.