

A271214


Number of reduced rearrangement patterns with n blocks.


3



1, 1, 2, 10, 71, 653, 7638, 104958, 1664083, 29740057, 591645738, 12959409010, 309898317151, 8032551265957, 224316415082750, 6714021923017318, 214415538303362411, 7277133405318569009, 261560966377901961810, 9925178291099012783322, 396498148141095399675511
(list;
graph;
refs;
listen;
history;
text;
internal format)



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



FORMULA

a(n) = ( round( 2^n e^(1/2) (n+1/2) (n1)! ) + 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.


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, +12 }
For n=3 the a(3)=10 solutions are { +32+1, +1+32, +23+1, +1+3+2, +2+13, +3+12, +13+2, +3+2+1, +3+21, +12+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



KEYWORD

nonn,easy


AUTHOR



STATUS

approved



