login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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