Re: [WP34S] A suggestion about C(x,y) Message #8 Posted by Eduardo Duenez on 29 Jan 2013, 11:49 a.m., in response to message #7 by Paul Dale
Quote:
These functions are implemented using LnGamma. This avoids the overflow issues, although there is still some risk of loss of accuracy I think.
The reflection formula you mention could be used. Is there similar for permutations?
- Pauli
Pauli,
I'm certain that some accuracy is lost using LnGamma to compute C(x,y). This must definitely be the case when x is close to a negative integer. I can swear there must be algorithms to give a better approximation in such cases, but I'm not an expert. If there is a chance to possibly re-implementing C(x,y), I can try looking in the specialized literature.
Your question about the permutations is absolutely pertinent. For any real or complex z and k an integer >=0, define
P(z,k) = z(z-1)(z-2)...(z-k+1)
Then what I asked at the top of the thread was to extend the definition of C(z,k) as P(z,k)/k! .
The above definition of P(z,k) is known in discrete math/computer science under the quirky name of "z to the k-th falling power". Using a notation introduced, I believe, by Donald Knuth, it is denoted by z^k with the exponent k *underlined*. There is a similar definition of z to the k-th rising power, z^k with the exponent k *overlined* (looks like k is complex-conjugated) given by
z(z+1)(z+2)...(z+k-1)
but I will presently focus only on the falling powers, that is P(z,k) as defined above.
In discrete mathematics, falling powers are very useful. P(z,k) are polynomials in z of degree k, and they are the natural polynomials to use in discrete interpolation. The "finite-differences formula", the discrete analog of Tayor's formula, reads
f(z) = c0 + c1*P(z,1) + c2*P(z,2)/2! + c3*P(z,3)/3! + ... +cn*P(z,n)/n!
= c0 + c1*C(z,1) + c2*C(z,2) + c3*C(z,3) + ... +cn*C(z,n)
The above formula gives the only polynomial of degree n with given differences
c0 = f(0)
c1 = Delta_1(f)(0) = f(1)-f(0)
c2 = Delta_2(f)(0)/2! = f(2)-2f(1)+f(0)
...
(I won't write the definition of the higher difference quotients to avoid too much clutter.)
The difference quotients depend only on the values f(0), f(1), ..., f(n), so the finite-differences formula is basically a more explicit and cleaner form of the Lagrange polynomial interpolation formula in the special (but very common and useful case) when the values of the interpolated function are known at n+1 *equally spaced* points. It's easy to write a user program to compute the finite differences of a given function. In conjunction with P(z,x), this would solve many polynomial interpolation problems easily. (Heck, I do volunteer to write a quick-n-dirty library to compute the finite differences if there's interest.)
Summing up the above, it makes perfect sense to extend both P(z,k) and C(z,k) to all complex z and integer k>=0. Of course using the Gamma function one may extend the above even to arbitrary real or complex k; this is almost the same as asking for the calculation of Euler's beta (which the 34S computes already).
Finally, we have the following general reflection formula (directly from the definition):
P(-z,k) = (-1)^k P(z+k-1,k)
and the same identity holds for C(x,y) instead of P(x,y).
Eduardo
|