A214358 Number of (2-14-3, 3-41-2)-avoiding permutations of size n.

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

Author

Mireille Bousquet-Mélou, Jul 13 2012

Keywords

• nonn
• easy

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.

Examples

			For n=4, the two permutations not in this class are 2143 and 3412.
		

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).

Crossrefs

Cf. A001181.

Programs

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 *)

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