login
Number of reduced rearrangement patterns with n blocks.
3

%I #14 Apr 26 2019 08:48:45

%S 1,1,2,10,71,653,7638,104958,1664083,29740057,591645738,12959409010,

%T 309898317151,8032551265957,224316415082750,6714021923017318,

%U 214415538303362411,7277133405318569009,261560966377901961810,9925178291099012783322,396498148141095399675511

%N Number of reduced rearrangement patterns with n blocks.

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

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

%H G. C. Greubel, <a href="/A271214/b271214.txt">Table of n, a(n) for n = 0..400</a>

%H J. Burns, <a href="http://jtburns.myweb.usf.edu/tables/rearrangement_maps.html">Table of Rearrangement Maps and Patterns for n = 1, 2, and 3</a>.

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

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

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

%e For n=0 the a(0)=1 solution is { ∅ }

%e For n=1 the a(1)=1 solution is { +1 }

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

%e 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 }

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

%Y Cf. A271212, A271217.

%K nonn,easy

%O 0,3

%A _Jonathan Burns_, Apr 13 2016