OFFSET
1,2
COMMENTS
a(n) also represents the number of reducible signed permutations of length n. A permutation is reducible when an adjacency occurs in the permutation.
The first 8 terms of this sequence were found by exhaustive search of all signed permutations.
REFERENCES
Manaswinee Bezbaruah, Henry Fessler, Leigh Foster, Marion Scheepers, George Spahn, Context Directed Sorting: Robustness and Complexity, draft.
LINKS
Leigh Foster, Table of n, a(n) for n = 1..50
EXAMPLE
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.
MATHEMATICA
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}]
PROG
(SageMath)
from ast import literal_eval
def checkFunc(n):
p = SignedPermutations(n)
permlist = p.list()
permset = set(permlist)
for perm in permlist:
perm_literal = literal_eval(str(perm))
for i in range(n-1):
a = perm_literal[i]
if perm_literal[i + 1] == a + 1:
permset.remove(perm)
break
print(factorial(n)*(2^n)-len(permset))
# usage: checkFunc({desired permutation length})
CROSSREFS
KEYWORD
nonn
AUTHOR
Leigh Foster, Sep 22 2018
STATUS
approved