A319536 - OEIS

%I #18 Feb 26 2020 08:15:12

%S 0,2,14,122,1278,15802,225886,3670074,66843902,1349399162,29912161758,

%T 722399486074,18881553923326,531063524702778,15993786127174238,

%U 513533806880120762,17512128958240460286,632099987274779910394,24076353238897830158302

%N Number of signed permutations of length n where numbers occur in consecutive order.

%C a(n) also represents the number of reducible signed permutations of length n. A permutation is reducible when an adjacency occurs in the permutation.

%C The first 8 terms of this sequence were found by exhaustive search of all signed permutations.

%D Manaswinee Bezbaruah, Henry Fessler, Leigh Foster, Marion Scheepers, George Spahn, Context Directed Sorting: Robustness and Complexity, draft.

%H Leigh Foster, <a href="/A319536/b319536.txt">Table of n, a(n) for n = 1..50</a>

%F a(n) = A000165(n) - A271212(n).

%e Of the 8 signed permutations of length 2: {[1,2], [-1,2], [1,-2], [-1,-2], [2,1], [-2,1], [2,-1], [-2,-1]} only two are reducible: [1,2] and [-2,-1]. Thus a(2) = 2.

%t Table[(2 n)!!, {n, 1, 20}] - RecurrenceTable[{a[n]==(2n-1)*a[n-1]+2(n-2)*a[n-2], a[0]==1, a[1]==2}, a[n], {n, 1, 20}]

%o (SageMath)

%o from ast import literal_eval

%o def checkFunc(n):

%o     p = SignedPermutations(n)

%o     permlist = p.list()

%o     permset = set(permlist)

%o     for perm in permlist:

%o         perm_literal = literal_eval(str(perm))

%o         for i in range(n-1):

%o             a = perm_literal[i]

%o             if perm_literal[i + 1] == a + 1:

%o                 permset.remove(perm)

%o                 break

%o     print(factorial(n)*(2^n)-len(permset))

%o # usage: checkFunc({desired permutation length})

%Y Cf. A000165, A271212.

%K nonn

%O 1,2

%A _Leigh Foster_, Sep 22 2018