| FIVE Applications of Wilf-Zeilberger Theory to Enumeration and Probability 1 Explicit Formulas vs. Algorithms (2008) | |||||||||||||||
Abstract | |||||||||||||||
| In the old days, when one had to find some sequence, a(n), there were two extremes. In the lucky case, one had an explicit formula. For example, the probability of tossing a fair coin 2n times and getting exactly n Heads, equals (2n)!/(2 2n n! 2). Sometimes, cheatingly, one considered as ‘explicit’ expressions in terms of sums (or multisums) or integrals (or multi-integrals). The other extreme was to just have a numerical algorithm, that for each (numeric!) input n, found the output. In that case the algorithm was rated by its efficiency. Another compromise was an asymptotic formula, valid (approximately!) for large n. But what’s a formula?, it is a kind of algorithm. Of course, it is more than that, theoretically, but from a practical point of view it should be judged by the efficiency of the implied algorithm. The Holonomic Ansatz Let’s look at the explicit formulas that are called ‘closed-form’, or more precisely hypergeometric sequences. A sequence a(n) is called hypergeometric if the ratio a(n+1)/a(n) is a rational function of n, i.e. a quotient P (n)/Q(n) where P (n) and Q(n) are polynomials. For example for the above-mentioned probability of getting exactly n Heads when tossing a fair coin 2n times, p(n):= (2n)!/(2 2n n! 2), we have p(n + 1)/p(n) = (2n + 1)/(2(n + 1)), or, by cross-multiplying 2(n + 1)p(n + 1) − (2n + 1)p(n) = 0. This is an example of a first-order linear recurrence equation with polynomial coefficients. Once you have the trivial value p(0) = 1 you can use it to compile a table of p(n) for n < N, for any desired N in O(N) operations. The same is true for solutions of any linear recurrence equation with polynomial coefficients, L� ai(n)p(n + i) = 0, i=0 of order L. The only difference is that we need L initial conditions, p(0), p(1),..., p(L − 1). We also assume that aL(n) = 0 has no positive integer roots. 1 Oct. 18, 2006. Accompanied by Maple packages AppsWZ and AppsWZmulti downloadable from Zeilberger’s website. Sample input and output can be viewed in: | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||