Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given a sequence $A_n(k)$ defined as follows:

$A_0(0)=1$, $A_0(k)=0$ for all nonzero integers $k$ and $$A_{n}(k)=(n+1-k)^2A_{n-1}(k-1)+2(n(n+1)-k^2)A_{n-1}(k)+(n+1+k)^2A_{n-1}(k+1)$$ for all positive integers $n$ and integers $k$. Does there exist an explicit formula for $A_n(k)$? This sequence is related to the function values of the uniform cardinal B-splines at the integers.

Thanks for any help in advance

Markus

share|improve this question
    
Is $k$ non-negative? –  Boris Novikov Feb 26 '13 at 15:19
add comment

2 Answers

up vote 2 down vote accepted

Edit: ok, now that I have more than 5 minutes to spare I can clean this up a bit and add a wikipedia reference.

I'm going to write A(n,k) for $A_n(k)$. First of all, note that it's easy to see that A(n,k) = A(n,-k) by induction on n, and that the A(n,k) are zero unless -n <= k <= n. So we may as well just start computing these things (with dynamic programming, for good practice) before we start thinking terribly hard:

Sage code:

values = {}
def A(n,k):
    if (n,k) in values:
        return values[(n,k)]
    if n==0:
        if k==0:
            result = 1
        else:
            result = 0
    else:
        result =  (n + 1 - k)**2 * A(n-1, k-1)
        result += 2*(n*(n+1)-k**2) * A(n-1, k)
        result += (n + 1 + k)**2 * A(n-1, k+1)
    values[(n,k)]=result
    return result

for n in range(5):
    print [A(n,k) for k in range(-n, n+1)]

Output:

[1]
[1, 4, 1]
[1, 26, 66, 26, 1]
[1, 120, 1191, 2416, 1191, 120, 1]
[1, 502, 14608, 88234, 156190, 88234, 14608, 502, 1]

One glance at the third row will tell any combinatorist that these are Eulerian numbers (at least, for odd n). See sequence A008292 at oeis.org. Also, wikipedia has a perfectly reasonable page on the Eulerian numbers: http://en.wikipedia.org/wiki/Eulerian_number. There you can find a recursive formula. I'll use E(n,m) since A is taken already:

$E(n,m) = (n-m)E(n-1,m-1) + (m+1)E(n-1,m)$.

Of course this notation is different than yours; I think your numbers are $E(2n+1, m-n)$, You should be able to see this by applying the above recursive formula twice and doing the above change of variables to recover your own formula, though I haven't done it and may have made an error. There's lots of formulas for the Eulerian numbers and there's a lot known about them.

share|improve this answer
add comment

$k$ can be negative.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.