Fast recursion

As I described in the comment, I use n-permutations for creating m-tuples, m=2n or m=2n+1.
Let me construct a recurrence leading from (k-1)- to k-permutations. They may end on k as long as k<n. 
Each permutation is described by 4 parameters k,s,d,c:
a) s=2: The permutation ends on k; s=1 otherwise.
b) d=-1,1,0: k-1 is left-, right- or not-adjacent to k respectively
c) c is the number of adjacent pairs (j-1,j) or (j,j-1), j<k.

Examples (notation: permutation -> (k,s,d,c)) 
k = 2: (1,2) -> (2,2,-1,0) and (2,1) -> (2, 1, 1, 0).
k = 7: (1,2,4,3,5,6,7) -> (7,2,-1,3)
For k=2, the parameter sets correspond just to one permutation each and so the recurrence starts 
with the frequencies f(2, 2, -1, 0) = 1 and f(2, 1, 1, 0) = 1.
Let us analyze the transition from k=7 to k=8 with the example above. There are 8 places to insert "8" 
generating 8 parameter sets (from left to right): 
(8,1,0,4), (8,1,0,3), (8,1,0,4), (8,1,0,3), (8,1,0,4), (8,1,0,3), (8,1,1,3), (8,2,-1,4).
With y = f(7,2,-1,3), for example, we yield the following increments: 
f(8,1,0,4):+3y, f(8,1,0,3):+3y, f(8,1,1,3):+y, f(8,2,-1,4):+y.

This is the basic idea of the recursion. I will not discuss further details, but give the resulting 
program in VBA (Excel) which lists a(k) for 3<=k<=14 (the first column in the active sheet should be 
set to "text"). For larger values I had to modify the program because, in VB, the length of integers 
is limited. So I had to replace summation and multiplication by string manipulations. But this has 
nothing to do with the basic algorithm.

The loop "For s = 1 To 2" occurs in the main program, but not in the subroutine "result" because s=2 
(a k-permutation ending on k) is not allowed in the result. 
The factor 2 ^ (k - c - Abs(d)) in "result" corresponds to 2^(g+1) described in the comment.


program VBA (Excel) 
Const n = 14
Dim f(n, 2, -1 To 1, n)

Sub main_program()
Erase f()
f(2, 2, -1, 0) = 1
f(2, 1, 1, 0) = 1
For k = 3 To n
  ze = 0
  For s = 1 To 2
    For d = -1 To 1
      For c = 0 To k - 2
        ff = f(k - 1, s, d, c)
        If ff > 0 Then
          Call increase(k, 1, 1, c + 1 + Sgn(d - 1), ff)
          Call increase(k, s, -1, c + 1 - Sgn(d + 1), ff)
          Call increase(k, 1, 0, c - 1 + Abs(d), c * ff)
          Call increase(k, 1, 0, c + Abs(d), (k - 3 - c) * ff)
          Call increase(k, 3 - s, 0, c + Abs(d), ff)
        End If
      Next
    Next
  Next
  Call result(k)
Next
End Sub

Sub increase(k, s, d, c, ad)
If c >= 0 And ad > 0 Then
  f(k, s, d, c) = f(k, s, d, c) + ad
End If
End Sub

Sub result(k)
su = 0
For d = -1 To 1
  For c = 0 To k - 2
    ff = f(k, 1, d, c)
    If ff > 0 Then su = su + ff * 2 ^ (k - c - Abs(d))
  Next
Next
Cells(k, 1).Value = Str(su)
End Sub