login
a(n) = (2n-1)*a(n-1) + 2*(n-2)*a(n-2).
5

%I #26 May 24 2023 15:18:06

%S 1,2,6,34,262,2562,30278,419234,6651846,118950658,2366492038,

%T 51837444642,1239591067526,32130200470274,897265598318022,

%U 26856087563449762,857662151219847238,29108533617158451714,1046243865439580921606,39700713164247881457698,1585992592561492290028038

%N a(n) = (2n-1)*a(n-1) + 2*(n-2)*a(n-2).

%C a(n) is the number of reduced rearrangement maps on n blocks. A rearrangement map is a signed permutation, e.g., +2 -1 -3. If the permutation contains (i)(i+1) or -(i+1)-(i) for any i, then it is not reduced.

%C Number of permutations p of [2n] such that each element in p has exactly one neighbor whose value is smaller or larger by one. a(2) = 6: 1243, 2134, 2143, 3412, 3421, 4312. - _Alois P. Heinz_, May 24 2023

%D J. Burns, Counting a Class of Signed Permutations and Rigid Vertex Graphs related to Patterns of DNA Rearrangement, Preprint.

%H Alois P. Heinz, <a href="/A271212/b271212.txt">Table of n, a(n) for n = 0..404</a>

%F a(n) = (2n-1)*a(n-1) + 2*(n-2)*a(n-2); a(0)=1; a(1)=2;

%F a(n) = e^(-1/2)*(2n+1)*Gamma(n,-1/2)+(-1)^n

%F a(n) = e^(-1/2)*(2n+1)*2^(n-1)*(n-1)! + (-1)^(n+1)*(2n^2 + 3n)^(-1)* 2_F_2(1, n+1/2; n+1, n+5/2; -1/2)

%F a(n) = round( e^(-1/2)*(2n+1)*2^(n-1)*(n-1)! )

%F a(n) ~ (Pi*2n/e)^(1/2) * (2n/e)^n

%F From _Peter Bala_, May 29 2022: (Start)

%F a(n) = Sum_{k = 0..n-1} (-1)^(n-1+k)*2^(k+1)*(k+1)!*binomial(n-1,k) for n >= 1.

%F 2*exp(-x)/(1 - 2*x)^2 = 2 + 6*x + 34*x^2/2! + 262*x^3/3! + 2562*x^4/4! + ... = Sum_{n >= 0} a(n+1)*x^n/n! is an e.g.f. for the sequence (a(n+1))n>=0.

%F a(n) = A000354(n) + A000354(n-1) for n >= 1. (End)

%e For n=1 the a(1)=2 solutions are {+1,-1}.

%e For n=2 the a(2)=6 solutions are {+1-2,-1+2,-1-2,+2+1,+2-1,-2+1}. Note that {+1+2,-2-1} are not reduced rearrangement maps.

%t RecurrenceTable[{a[n]==(2n-1)*a[n-1]+2(n-2)*a[n-2],a[0]==1,a[1]==2},a[n],{n,0,10}]

%t Table[Round[Exp[-1/2]*(2n+1)*2^(n-1)*(n-1)!],{n,10}]

%Y Cf. A000165, A000354.

%K nonn,easy

%O 0,2

%A _Jonathan Burns_, Apr 02 2016