login
A214358
Number of (2-14-3, 3-41-2)-avoiding permutations of size n.
1
1, 1, 2, 6, 22, 88, 374, 1668, 7744, 37182, 183666, 929480, 4803018, 25274088, 135132886, 732779504, 4023875702, 22346542912, 125368768090, 709852110576, 4053103780006, 23320440656376, 135126739754922, 788061492048436, 4623591001082002, 27277772831911348
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
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
Cf. A001181.
Sequence in context: A096267 A150264 A294593 * A107944 A150265 A150266
KEYWORD
nonn,easy
AUTHOR
STATUS
approved