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

%I #50 Oct 23 2024 16:13:51

%S 1,1,2,6,22,88,374,1668,7744,37182,183666,929480,4803018,25274088,

%T 135132886,732779504,4023875702,22346542912,125368768090,709852110576,

%U 4053103780006,23320440656376,135126739754922,788061492048436,4623591001082002,27277772831911348

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

%C a(n) is also the number of permutations obtained by retaining only the even entries in a complete Baxter permutation of length 2n+1.

%D W. M. Boyce, Generation of a class of permutations associated with commuting functions, Math. Algorithms, 2 (1967), 19-26.

%H Alois P. Heinz, <a href="/A214358/b214358.txt">Table of n, a(n) for n = 0..400</a>

%H A. Asinowski, G. Barequet, M. Bousquet-Mélou, T. Mansour, R. Pinter, <a href="https://doi.org/10.37236/2607">Orders induced by segments in floorplans and (2-14-3,3-41-2)-avoiding permutations</a>, Electronic Journal of Combinatorics, 20:2 (2013), Paper P35; also arXiv preprint <a href="https://arxiv.org/abs/1011.1889">arXiv:1011.1889 [math.CO]</a>, 2010-2012.

%H W. M. Boyce, <a href="/A001181/a001181_4.pdf">Baxter Permutations and Functional Composition</a>, Houston Journal of Mathematics, Volume 7, No. 2, 1981

%H F. R. K. Chung, R. L. Graham, V. E. Hoggatt Jr. and M. Kleiman, <a href="https://doi.org/10.1016/0097-3165(78)90068-7">The number of Baxter permutations</a> J. Combin. Theory Ser. A 24 (1978), no. 3, 382-394.

%H CombOS - Combinatorial Object Server, <a href="http://combos.org/rect">Generate block-aligned rectangulations</a>

%H Elizabeth Hartung, Hung Phuc Hoang, Torsten Mütze, Aaron Williams, <a href="https://arxiv.org/abs/1906.06069">Combinatorial generation via permutation languages. I. Fundamentals</a>, arXiv:1906.06069 [cs.DM], 2019.

%H Arturo Merino, Torsten Mütze, <a href="https://arxiv.org/abs/2103.09333">Combinatorial generation via permutation languages. III. Rectangulations</a>, arXiv:2103.09333 [math.CO], 2021.

%H Jannik Silvanus, <a href="http://hdl.handle.net/20.500.11811/7936">Improved Cardinality Bounds for Rectangle Packing Representations</a>, Doctoral Dissertation, University of Bonn (Rheinische Friedrich Wilhelms Universität, Germany 2019).

%F The coefficients are P-recursive:

%F a(0) = 1, a(1) = 1, a(2) = 2, a(3) = 6, a(4) = 22, a(5) = 88 and

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

%F Equivalently, the GF is D-finite with recurrence:

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

%F a(n) ~ 512*(3*sqrt(2)-4) * (4+2*sqrt(2))^n/(Pi*sqrt(3)*n^4). - _Vaclav Kotesovec_, Aug 15 2013

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

%p a:= proc(n) option remember;

%p `if`(n<6, [1, 1, 2, 6, 22, 88][n+1], ((8*n^3+240-8*n-48*n^2)*a(n-6)+

%p (80*n-576-32*n^3+144*n^2)*a(n-5)+ (462+41*n^3-158*n^2-129*n)*a(n-4)+

%p (-11*n^3-138+104*n^2+85*n)*a(n-3)+ (-14*n^3-80*n^2-92*n-30)*a(n-2)+

%p (9*n^3+46*n^2+81*n+48)*a(n-1)) / ((n+4)*(n+3)*(n+1)))

%p end:

%p seq(a(n), n=0..30); # _Alois P. Heinz_, Jul 13 2012

%t 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_ *)

%Y Cf. A001181.

%K nonn,easy

%O 0,3

%A _Mireille Bousquet-Mélou_, Jul 13 2012