A271214 Number of reduced rearrangement patterns with n blocks.

1, 1, 2, 10, 71, 653, 7638, 104958, 1664083, 29740057, 591645738, 12959409010, 309898317151, 8032551265957, 224316415082750, 6714021923017318, 214415538303362411, 7277133405318569009, 261560966377901961810, 9925178291099012783322, 396498148141095399675511

Offset

0,3

Comments

a(n) is the number of reduced rearrangement patterns, i.e., the number of reduced rearrangement map equivalence classes formed from the two rotation involutions.

References

J. Burns, Counting a Class of Signed Permutations and Chord Diagrams related to DNA Rearrangement, Preprint.

Links

G. C. Greubel, Table of n, a(n) for n = 0..400

J. Burns, Table of Rearrangement Maps and Patterns for n = 1, 2, and 3.

Formula

a(n) = ( round( 2^n e^(-1/2) (n+1/2) (n-1)! ) + round( 2^n e^(-1/4) (1-(1+(-1)^n)/4n)) floor(n/2)! ) / 4.

a(n) ~ sqrt( Pi*n / 8*e) * (2n / e)^n.

a(n) = (A271212(n) + A271217(n)) / 4.

Example

For n=0 the a(0)=1 solution is { ∅ }
For n=1 the a(1)=1 solution is { +1 }
For n=2 the a(2)=2 solutions are { +2+1, +1-2 }
For n=3 the a(3)=10 solutions are { +3-2+1, +1+3-2, +2-3+1, +1+3+2, +2+1-3, +3+1-2, +1-3+2, +3+2+1, +3+2-1, +1-2+3 }

Mathematica

Table[(Round[2^n*Exp[-1/2]*(n + 1/2)*(n - 1)!] + Round[2^n*Exp[ -1/4]*(1 - (1 + (-1)^n)/(4 n))*Floor[n/2]!])/4, {n,  1, 20}]

Crossrefs

Cf. A271212, A271217.

Sequence in context: A362821 A060842 A245834 * A366241 A321446 A111554

Adjacent sequences: A271211 A271212 A271213 * A271215 A271216 A271217

Keyword

nonn,easy

Author

Jonathan Burns, Apr 13 2016

Status

approved