OFFSET
0,3
COMMENTS
a(n) is also the number of permutations obtained by retaining only the even entries in a complete Baxter permutation of length 2n+1.
REFERENCES
W. M. Boyce, Generation of a class of permutations associated with commuting functions, Math. Algorithms, 2 (1967), 19-26.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..400
A. Asinowski, G. Barequet, M. Bousquet-Mélou, T. Mansour, R. Pinter, Orders induced by segments in floorplans and (2-14-3,3-41-2)-avoiding permutations, Electronic Journal of Combinatorics, 20:2 (2013), Paper P35; also arXiv preprint arXiv:1011.1889 [math.CO], 2010-2012.
W. M. Boyce, Baxter Permutations and Functional Composition, Houston Journal of Mathematics, Volume 7, No. 2, 1981
F. R. K. Chung, R. L. Graham, V. E. Hoggatt Jr. and M. Kleiman, The number of Baxter permutations J. Combin. Theory Ser. A 24 (1978), no. 3, 382-394.
CombOS - Combinatorial Object Server, Generate block-aligned rectangulations
Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, Aaron Williams, Combinatorial generation via permutation languages. I. Fundamentals, arXiv:1906.06069 [cs.DM], 2019.
Arturo Merino, Torsten Mütze, Combinatorial generation via permutation languages. III. Rectangulations, arXiv:2103.09333 [math.CO], 2021.
Jannik Silvanus, Improved Cardinality Bounds for Rectangle Packing Representations, Doctoral Dissertation, University of Bonn (Rheinische Friedrich Wilhelms Universität, Germany 2019).
FORMULA
The coefficients are P-recursive:
a(0) = 1, a(1) = 1, a(2) = 2, a(3) = 6, a(4) = 22, a(5) = 88 and
(-192-280*k-96*k^2-8*k^3)*a(k) +(1824+32*k^3+432*k^2+1648*k)*a(k+1)+ (-2856-41*k^3-580*k^2-2403*k)*a(k+2) +(-1740+11*k^3+94*k^2-145*k)*a(k+3)+ (6486+14*k^3+332*k^2+2564*k)*a(k+4) +(-4134-9*k^3-208*k^2-1605*k)*a(k+5)+(630+k^3+26*k^2+223*k)*a(k+6) = 0.
Equivalently, the GF is D-finite with recurrence:
12*(t-1)*(2*t-1)^3 +(104*t-338*t^2+512*t^3 -294*t^4-110*t^5 +192*t^6-48*t^7-12) * A(t) -2*t*(t-1)*(40*t^6-128*t^5+89*t^4+53*t^3-88*t^2+35*t-4) * (d/dt)A(t) -t^2*(2*t-1)*(8*t^2-8*t+1) * (t^2-t-1)*(t-1)^2 * (d^2/dt^2)A(t) = 0.
a(n) ~ 512*(3*sqrt(2)-4) * (4+2*sqrt(2))^n/(Pi*sqrt(3)*n^4). - Vaclav Kotesovec, Aug 15 2013
EXAMPLE
For n=4, the two permutations not in this class are 2143 and 3412.
MAPLE
a:= proc(n) option remember;
`if`(n<6, [1, 1, 2, 6, 22, 88][n+1], ((8*n^3+240-8*n-48*n^2)*a(n-6)+
(80*n-576-32*n^3+144*n^2)*a(n-5)+ (462+41*n^3-158*n^2-129*n)*a(n-4)+
(-11*n^3-138+104*n^2+85*n)*a(n-3)+ (-14*n^3-80*n^2-92*n-30)*a(n-2)+
(9*n^3+46*n^2+81*n+48)*a(n-1)) / ((n+4)*(n+3)*(n+1)))
end:
seq(a(n), n=0..30); # Alois P. Heinz, Jul 13 2012
MATHEMATICA
a[n_] := a[n] = If[n<6, {1, 1, 2, 6, 22, 88}[[n+1]], ((8*n^3 + 240 - 8*n - 48*n^2)* a[n-6] + (80*n - 576 - 32*n^3 + 144*n^2)*a[n-5] + (462 + 41*n^3 - 158*n^2 - 129*n) *a[n-4] + (-11*n^3 - 138 + 104*n^2 + 85*n)*a[n-3] + (-14*n^3 - 80*n^2 - 92*n - 30 )*a[n-2] + (9*n^3 + 46*n^2 + 81*n + 48)*a[n-1]) / ((n+4)*(n+3)*(n+1))]; Table[ a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 30 2015, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Mireille Bousquet-Mélou, Jul 13 2012
STATUS
approved