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

%I #30 Jun 26 2019 07:52:31

%S 1,2,6,18,58,190,642,2206,7746,27662,100738,373550,1413506,5457710,

%T 21546466,87025806,360264258,1529624366,6669850466,29877013902,

%U 137560725890,650780790894,3162711095074,15774862353614,80687636530882,422713072650286,2265833731786594

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

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

%H Andy Hardt and Justin M. Troyka, <a href="https://people.carleton.edu/~eegge/rssp.pdf">Restricted Symmetric Signed Permutations</a>, 2012.

%F 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.

%F 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

%p inv := proc(n) option remember; if n<2 then 1 else inv(n-1)+(n-1)*inv(n-2) fi end:

%p a := proc(n) option remember; if n < 2 then n+1 else

%p 2*a(n-1) + n*a(n-2) - add(j*a(j)*inv(n-j-2), j=1..n-3) fi end:

%p seq(a(n), n=0..26); # _Peter Luschny_, Dec 09 2018

%t inv[n_] := inv[n] = If[n<2, 1, inv[n-1] + (n-1) inv[n-2]];

%t 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}]];

%t Table[a[n], {n, 0, 26}] (* _Jean-François Alcover_, Jun 26 2019, after _Peter Luschny_ *)

%Y Cf. A193778, A000085.

%K nonn

%O 0,2

%A _Andy Hardt_, Aug 04 2011

%E Terms a(9) and beyond from _Peter Luschny_, Dec 09 2018