Better definition for A113166

[Creighton Dement]

Thanks Max for hitting that one out of the park!

The definition I gave for A113486:  A113116(n) - Fib(n-1), Fib = A000045
should read A113166(n) - Fib(n-1), Fib = A000045.  I'll send that
correction, along with the revised definition of A113116 as a comment
after 21st of July (when Neil gets back). 

Sincerely, 
Creighton


- - - - - - - - - - - - - - - - - - - - - - - - - - - - -

> Date: Tue, 20 Jun 2006 12:44:29 +0200
> Subject: Re: Better definition for A113166
> From: Max <maxale at gmail.com>
> To: "Creighton Dement" <crowdog at crowdog.de>

> Creighton,
> 
> From your new definition of A113166 it follows an explicit formula:
> 
> A113166(n) = \sum_{k=1}^{[n/2]} k/(n-k) \sum_{j=1}^{gcd(n,k)} {
> (n-k)*gcd(n,k,j)/gcd(n,k) \choose k*gcd(n,k,j)/gcd(n,k) }
> 
> or as a PARI/GP program:
> 
> { A113166(n) = sum(k=1,n\2, k/(n-k) * sum(j=1,gcd(n,k),
> binomial((n-k)*gcd([n,k,j])/gcd(n,k),k*gcd([n,k,j])/gcd(n,k)) )) }
> 
> In particular, for n=1..50 we have
> 0, 1, 1, 3, 3, 8, 8, 17, 23, 41, 55, 102, 144, 247, 387, 631, 987,
> 1636, 2584, 4233, 6787, 11011, 17711, 28794, 46380, 75181, 121441,
> 196685, 317811, 514712, 832040, 1346921, 2178429, 3525581, 5702937,
> 9229314, 14930352, 24160419, 39088469, 63250315, 102334155, 165587436,
> 267914296, 433505523, 701409597, 1134920903, 1836311903, 2971245198,
> 4807527024, 7778788585
> 
> This explicit formula also helps to prove the conjecture
> 
> %F A113166 Conjecture: a(p) = Fib(p-1) for all primes, where Fib =
> A000045 (Creighton Dement and Antti Karttunen).
> 
> If n=p for prime p, then gcd(n,k) and gcd(n,k,j) in the formula equal
> 1 implying much simpler formula:
> 
> A113166(p) = \sum_{k=1}^{[p/2]} k/(n-k) { n-k \choose k }
> = \sum_{k=1}^{[p/2]} { n-k-1 \choose k-1 }
> 
> which equals Fib(p-1) according to formula (61) at
> http://mathworld.wolfram.com/FibonacciNumber.html
> 
> Max