FIVE Applications of WIlf-Zeilberger Theory to Enumeration and Probability

By Moa APAGODU and Doron ZEILBERGER

.pdf   .ps   .tex
[Appeared in "COMPUTER ALGEBRA 2006, Latest Advances in Symbolic Algorithms" (Abramov Festschrift, dedicated to Sergey Abramov's 60th birthday), edited by Ilias S Kotsireas and Eugene V Zima, World Scientific, Aug. 2007.]
Dedicated to Sergei Abramov, a pioneer of Symbolic Computation, on his sixty-th birthday
Written: Oct. 20, 2006.
Wilf-Zeilberger Theory (WZ theory) has lots and lots of potential applications. In this article, dedicated to Sergei Abramov, we only discuss (briefly!) five of them. Initially I was hoping to contribute something of more direct relevance to Sergei Abramov's great research accomplishments, but hopefully he would like it all the same, since he loves computer algebra so much.

# Sample Input and Output for AppsWZ

• In order to find recurrences (and asymptotics!) for the probabilty, ak (n), of rolling a fair 2k-faced die (marked with 1, 2, ..., 2k) 2n times, and getting the total number of points to come out EXCTLY the expected number ((2k+1)n), for k=1,2,3,4,5,
the input yields the output.
• In order to find a recurrence for the number of r-tuples (r arbitrary!) [L1, ..., Lr] where each Li is a partition that only uses the parts {1,2,3,4} and the sum of the parts of all the Li's is n,
the input yields the output.
• In order to find the number of ways of paying a bill of n cents with (up to r) people participating, where the coins used are pennies, nickels, dimes, and quarters
the input yields the output.
• In order to find the number of ways of paying a bill of n cents with (up to r) people participating, where the coins used are pennies, nickels, dimes, quarters, half-dollars and dollar-coins,
the input yields the output.
• In order to find out, in a Hidden Markov Model with two dice, one fair and one loaded (with Pr(Head)=1/3), and where the outcome tunred out to be 10i Head and 10i Tails (i=1..5), to find an estimate, a la Bayes-Laplace, the probability that the fair die was used.
the input yields the output.

# Sample Input and Output for AppsWZmutli

• In order to find recurrences for the number of ways of walking from (0,0) to (m,n), in the square lattice, using the steps [0,1],[1,0],[1,1], and the recurrence for the number of ways of walking to (n,n) [and the asymtotics!]
the input yields the output.
• In order to find recurrences for the number of ways of walking from (0,0) to (m,n), in the square lattice, using the steps [0,2],[2,0],[1,1], and the recurrence for the number of ways of walking to (n,n) [and the asymtotics!]
the input yields the output.
• In order to find recurrences for the number of possible score-sequences in an [old-time] basketball game (where a three-pointer was not allowed) in a game that ended in a score m:n, as well as the pure recurrence for a game that ended in n:n (and the implied asymptotics),
the input yields the output.
• In order to find recurrences for the number of possible score-sequences in a [contemporary] basketball game (where also a three-pointer is allowed), in a game that ended in a score m:n, as well as the pure recurrence for a game that ended in n:n (and the implied asymptotics),
the input yields the output.
• In order to find the (trivial) recurrence for the probabibility of being at the origin after n steps in a symmetic random walk on the square lattice with unit steps,
the input yields the output.
• In order to find a recurrence for the probability of a King travelling (uniformly) randomly on an infinite chessboard returning to its starting point after n steps,
the input yields the output.
• In order to find the recurrence for the probabibility of being at the origin after n steps in a symmetic random walk on the cubic lattice with unit steps,
the input should yield the desired recurrence. But it took too long, so I stopped it. (Note that in this case it is more efficient to do some preprocessing and express the quantity of interest as a single-summation that can be done in a few seconds by the Zeilberger algorithm using EKHAD).

Doron Zeilberger's List of Papers