A193777 Number of signed permutations of size 2n invariant under D and D'bar and avoiding (-2, 1) and (2, -1).

1, 2, 6, 18, 58, 190, 642, 2206, 7746, 27662, 100738, 373550, 1413506, 5457710, 21546466, 87025806, 360264258, 1529624366, 6669850466, 29877013902, 137560725890, 650780790894, 3162711095074, 15774862353614, 80687636530882, 422713072650286, 2265833731786594

Offset: 0

Author

Andy Hardt, Aug 04 2011

Keywords

• nonn

Comments

Also the number of signed permutations of size n invariant under D and avoiding (-2, 1) and (2, -1).

Links

• Andy Hardt and Justin M. Troyka, Restricted Symmetric Signed Permutations, 2012.

Crossrefs

Cf. A193778, A000085.

Programs

Maple

inv := proc(n) option remember; if n<2 then 1 else inv(n-1)+(n-1)*inv(n-2) fi end:
a := proc(n) option remember; if n < 2 then n+1 else
2*a(n-1) + n*a(n-2) - add(j*a(j)*inv(n-j-2), j=1..n-3) fi end:
seq(a(n), n=0..26); # Peter Luschny, Dec 09 2018

Mathematica

inv[n_] := inv[n] = If[n<2, 1, inv[n-1] + (n-1) inv[n-2]];
a[n_] := a[n] = If[n<2, n+1, 2 a[n-1] + n a[n-2] - Sum[j a[j] inv[n-j-2], {j, 1, n-3}]];
Table[a[n], {n, 0, 26}] (* Jean-François Alcover, Jun 26 2019, after Peter Luschny *)

Formula

a(n) = 2*a(n-1) + n*a(n-2) - Sum_{j=1..k-3} j*a(j)*|S_{k-j-3}^D|, where S_n^D is the set of unsigned permutations of length n invariant under D.

a(n) = 2*a(n-1) + n*a(n-2) - Sum_{j=1..n-3} j*a(j)*A000085(n-j-2). - Andrew Howroyd, Dec 09 2018

Extensions

Terms a(9) and beyond from Peter Luschny, Dec 09 2018