MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


share|cite|improve this question
Is $k$ non-negative? – Boris Novikov Feb 26 '13 at 15:19
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
            result = 0
        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)
    return result

for n in range(5):
    print [A(n,k) for k in range(-n, n+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 Also, wikipedia has a perfectly reasonable page on the Eulerian numbers: 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|cite|improve this answer

$k$ can be negative.

share|cite|improve this answer

Your Answer


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.