login
A319536
Number of signed permutations of length n where numbers occur in consecutive order.
1
0, 2, 14, 122, 1278, 15802, 225886, 3670074, 66843902, 1349399162, 29912161758, 722399486074, 18881553923326, 531063524702778, 15993786127174238, 513533806880120762, 17512128958240460286, 632099987274779910394, 24076353238897830158302
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
FORMULA
a(n) = A000165(n) - A271212(n).
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
Sequence in context: A267906 A199560 A283184 * A060468 A349261 A121082
KEYWORD
nonn
AUTHOR
Leigh Foster, Sep 22 2018
STATUS
approved