A271212 a(n) = (2n-1)*a(n-1) + 2*(n-2)*a(n-2).

1, 2, 6, 34, 262, 2562, 30278, 419234, 6651846, 118950658, 2366492038, 51837444642, 1239591067526, 32130200470274, 897265598318022, 26856087563449762, 857662151219847238, 29108533617158451714, 1046243865439580921606, 39700713164247881457698, 1585992592561492290028038

Offset

0,2

Comments

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.

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

References

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

Links

Alois P. Heinz, Table of n, a(n) for n = 0..404

Formula

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

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

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)

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

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

From Peter Bala, May 29 2022: (Start)

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

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.

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

Example

For n=1 the a(1)=2 solutions are {+1,-1}.
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.

Mathematica

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}]
Table[Round[Exp[-1/2]*(2n+1)*2^(n-1)*(n-1)!], {n, 10}]

Crossrefs

Cf. A000165, A000354.

Sequence in context: A328884 A002685 A262391 * A325296 A052878 A168362

Adjacent sequences: A271209 A271210 A271211 * A271213 A271214 A271215

Keyword

nonn,easy

Author

Jonathan Burns, Apr 02 2016

Status

approved