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.
Important: This article is accompanied by Maple
packages
AppsWZ
that has applications of the Almkvist-Zeilberger algorithm
and
AppsWZmulti
that has applications of the Apagodu-Zeilberger mutli-Almkvist-Zeilberger algorithm.
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
Doron Zeilberger's Home Page