Golf the Sequence whose Exponential Generating Function is tangent Almost every function can be expressed as a polynomial with infinite terms.

For example, e^x = 1 + x + x^2/2! + x^3/3! + x^4/4! + ...

For example, sin(x) = x - x^3/3! + x^5/5! - x^7/7! + ...

The coefficients of the n-th terms form a sequence, and the corresponding function is called the Generating Function of the sequence.

The coefficients of the n-th terms form a sequence.

Often, the n-th term would have a denominator of n!. Therefore, we multiply the coefficient by n! to obtain another sequence, whose Exponential Generating Function would be the original function.

For example, the sequence whose Exponential Generating Function is e^x would be 1,1,1,1,....

For example, the sequence whose Exponential Generating Function is sin(x) would be 0,1,0,-1,0,1,0,-1,....

Task

Your task is to find the n-th term of the sequence whose Exponential Generating Function is tan(x).

Testcases

n result
0 0
1 1
2 0
3 2
4 0
5 16
6 0
7 272
8 0
9 7936
10 0
11 353792
12 0
13 22368256
14 0
15 1903757312
16 0
17 209865342976
18 0
19 29088885112832
20 0
21 4951498053124096
22 0
23 1015423886506852352
24 0
25 246921480190207983616
26 0


(Copied from here.) (Warning: the 0-th term is different)

Example implementation

# copied from https://github.com/Mego/Seriously/blob/v2.0/SeriouslyCommands.py#L16
def memoized(f):
    memo = {}
    def m_fun(*args):
        if args in memo:
            return memo[args]
        else:
            res = f(*args)
            memo[args] = res
            return res
    return m_fun

# copied from https://github.com/Mego/Seriously/blob/v2.0/SeriouslyCommands.py#L169
@memoized
def binomial(n,r):
    if r &gt; n:
        return 0
    elif r==n:
        return 1
    res = 1
    i = 1
    while i&lt;=r:
        res *= (n+1-i)
        res /= i
        i+=1
    return int(res)

# 2*u(n+1) = Sum_{k=0..n} binomial(n, k)*u(k)*u(n-k)
# from A000111
@memoized
def u(n):
    if n&lt;0: return 0
    if n==0: return 1
    if n==1: return 1
    return sum([binomial(n-1,k)*u(k)*u(n-1-k) for k in range(n)])//2     

def t(n):
    if n%2 == 0: return 0
    return u(n)

print('\n'.join([str(x) + ' ' + str(t(x)) for x in range(26)]))


Ideone it!

References


Generating function on Wikipedia
Exponential generating function on Wikipedia
Exponential generating function example on Wikipedia
Generating function on MathWorld
Exponential generating function on MathWorld
Taylor series on Wikipedia
Derivation of first 9 terms of required sequence
Obligatory OEIS A009006 (Note that the 0-th term is different)
Algorithm
OEIS A000111: up/down numbers
CJam (33 32 27 26 23 20 bytes)

2,{ee::*_(@+.+}ri*0=


Online demo

Dissection

This essentially implements the recurrence described by xnor.

2,        e# [0 1] represents the base case f(0,j) = j==1
{         e# Loop...
  ee::*   e#   Multiply each array element by its index
  _(@+.+  e#   Sum the array shifted left and the array shifted right
}ri*      e# ... n times
0=        e# Evaluate at j=0




Or with a rather different approach, for 23 bytes:

ri_1&amp;a{{1$+}*]W%0+}@*0=


Online demo. Thanks to Dennis for 3 bytes.

Dissection

1a         e# Push [1]
{          e# Repeat...
  {1$+}*]  e#   Compute array of partial sums
  W%0+     e#   Reverse and append 0
}qi:A*     e# ... A times, where A is the input value
0=A1&amp;*     e# Result is first element if A odd, and 0 otherwise




Or with a very different approach, for 29 bytes:

qie!Ma-{W\+W+3ew{_$.=1=},!},,


Online demo

Unfortunately a special case is required for input 0.

Dissection

qi            e# Take an integer n from stdin
e!            e#   Compute all permutations of [0 ... n-1]
Ma-           e#   Special-case n=0
{             e#   Filter...
  W\+W+       e#     Prepend and postpend -1
  3ew         e#     Take slices of 3 consecutive elements
  {           e#     Filter...
    _$.=1=    e#       Test whether the middle element is the second largest
  },!         e#     ... and require no matches
},,           e#   ... and count




You may be thinking "WTF?! He's answering the wrong question." If so, that's understandable, but both approaches do indeed give the correct results.