A363810 Number of permutations of [n] that avoid the patterns 2-41-3, 3-14-2, 2-14-3, and 4-5-3-1-2.

1, 1, 2, 6, 21, 79, 306, 1196, 4681, 18308, 71564, 279820, 1095533, 4298463, 16913428, 66769536, 264526329, 1051845461, 4197832133, 16813161765, 67571221016, 272448598737, 1101876945673, 4469106749281, 18174503562880, 74093063050412, 302753929958872

Offset: 0

Author

Andrei Asinowski, Jun 23 2023

Keywords

• nonn

Comments

Equivalently, for n>0, the number of separable permutations of [n] that avoid 2-14-3 and 2-1-3-5-4.

The number of guillotine rectangulations (with respect to the weak equivalence) that avoid the geometric patterns "5" and "8". See the Merino and Mütze reference, Table 3, entry "123458".

Links

• Andrei Asinowski and Cyril Banderier, From geometry to generating functions: rectangulations and permutations, arXiv:2401.05558 [cs.DM], 2024. See page 2.
• Arturo Merino and Torsten Mütze. Combinatorial generation via permutation languages. III. Rectangulations. Discrete & Computational Geometry, 70 (2023), 51-122. Preprint: arXiv:2103.09333 [math.CO], 2021.

Crossrefs

Other entries including the patterns 1, 2, 3, 4 in the Merino and Mütze reference: A006318, A106228, A363809, A078482, A033321, A363811, A363812, A363813, A006012.

Programs

Maple

with(gfun): seq(coeff(algeqtoseries(x^8*(-2+x)^2*F^4 - x^3*(x-1)*(-2+x)*(x^5-7*x^4+4*x^3-6*x^2+5*x-1)*F^3 - x*(x-1)*(4*x^7-22*x^6+37*x^5-42*x^4+53*x^3-35*x^2+10*x-1)*F^2 - (5*x^6-16*x^5+15*x^4-28*x^3+23*x^2-8*x+1)*(x-1)^2*F - (2*x^5-5*x^4+4*x^3-10*x^2+6*x-1)*(x-1)^2, x, F, 32, true)[1], x, n+1), n = 0..30); # Vaclav Kotesovec, Jun 24 2023

Formula

The generating function F=F(x) satisfies the equation x^8*(x - 2)^2*F^4 - x^3*(x - 1)*(x - 2)*(x^5 - 7*x^4 + 4*x^3 - 6*x^2 + 5*x - 1)*F^3 - x*(x - 1)*(4*x^7 - 22*x^6 + 37*x^5 - 42*x^4 + 53*x^3 - 35*x^2 + 10*x - 1)*F^2 - (5*x^6 - 16*x^5 + 15*x^4 - 28*x^3 + 23*x^2 - 8*x + 1)*(x - 1)^2*F - (2*x^5 - 5*x^4 + 4*x^3 - 10*x^2 + 6*x - 1)*(x - 1)^2 = 0.