Error in A115866

[David W. Cantrell]

On 3/4/07, Dan Dima <dimad72 at gmail.com> wrote:
> Also f(a(1),a(2),...,a(k)) can be computed as the coefficient of
> x(1)^a(1)...x(k)^a(k) in the expansion:
> 1/2 * 1/(1 - (1+x(1))*...*(1+x(k))/2)

There is also a closed-form result using hypergeometric functions. I
found it, also more than a year ago, when working on that same
Missouri State challenge problem. AFAIK, this does not appear in the
literature. Using pseudo-Mathematica-style notation,
f(a(1),a(2),...,a(k))  is

2^(-1 - a(1)) (a(1)!)^(k-1)/(a(2)! a(3)! ... a(k)!) *
HypergeometricPFQRegularized[{1, 1 + a(1), 1 + a(1),..., 1 + a(1)},
{1, 1 + a(1) - a(2), 1 + a(1) - a(3),..., 1 + a(1) - a(k)}, 1/2]

N.B. Although it should be obvious from the above that there are k
denominatorial parameters, it is not obvious that there are to be
(k+1) numeratorial parameters [one of which is 1 and the other k of
them are 1 + a(1)]. In other words, we have P = k + 1 and Q = k.

For information about HypergeometricPFQRegularized, see
http://functions.wolfram.com/HypergeometricFunctions/HypergeometricPFQRegularized/.

> On 3/4/07, Dan Dima <dimad72 at gmail.com> wrote:
>> Hi all,
>>
>> I found this more than a year ago when I tried to solve the
>> following puzzle:
>> http://faculty.missouristate.edu/l/lesreid/POW08_0506.html
>>
>> However I found a very simple (although infinite sum) formula for
>> the number of paths from (0,0,...,0) to (a(1),a(2),...,a(k)) using
>> "nonzero" (2^k-1) steps of the form (x(1),x(2),...,x(k)) where x(i)
>> is in {0,1} for 1<=i<=k, k-dimensions.
>>
>> I have looked carefully on the web and I found many articles
>> related
>> to this issue - Multi-Dimensional Lattice Paths with Diagonal Steps
>> (or various kind of steps) - but none of them matches my simple
>> infinite sum:
>>
>> f(a(1),a(2),...,a(k))  =
>> Sum( (C(n;a(1)) * C(n;a(2)) * ... C(n;a(k))) / 2^{n+1} , {n,
>> max(a(1),a(2),...,a(k)), infinity}),
>> Sum( (C(n;a(1)) * C(n;a(2)) * ... C(n;a(k))) / 2^{n+1} , {n, 0,
>> infinity}),
>> C(n;a)=n!/a!(n-a)! & we assumed C(n;a)=0 if n<a
>>
>> Please can someone correct me if I am wrong!

You're not wrong. But Les has an obvious typo in what he says you did.
See the last line of his solution page; one of those C(k;a) factors
should be C(k;b) instead.

>> Nick: If you want to compute larger terms for those sequences
>> please avoid recursivity - a lot of redundant work will be done ;)
>> ...
>> just use straightforward "for loops" instead...

Even better, I should think, is to use the closed form I gave above.
Of course, that assumes one has a convenient way of evaluating such
hypergeometric functions.

>> Neil: what things happen at about 8 or 9 dimensions?

I'm going to go out on a limb, or should I rather say "hang by a
thread" ;-)  and guess that Neil might have been thinking about string
theory.

Best regards,
David W. Cantrell