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 (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