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,3

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

Table of n, a(n) for n=0..26.

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.

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.

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

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.

Sequence in context: A121941 A150194 A150195 * A150196 A366082 A148491

Adjacent sequences: A363807 A363808 A363809 * A363811 A363812 A363813

Keyword

nonn

Author

Andrei Asinowski, Jun 23 2023

Status

approved