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

1, 1, 2, 6, 22, 89, 378, 1647, 7286, 32574, 146866, 667088, 3050619, 14039075, 64992280, 302546718, 1415691181, 6656285609, 31436228056, 149079962872, 709680131574, 3390269807364, 16248661836019, 78109838535141, 376531187219762, 1819760165454501

Offset

0,3

Comments

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

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

References

Andrei Asinowski and Cyril Banderier. Geometry meets generating functions: Rectangulations and permutations (2023).

Links

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

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^4*(x - 2)^2*F^4 + x*(x - 2)*(4*x^3 - 7*x^2 + 6*x - 1)*F^3 + (2*x^4 - x^3 - 2*x^2 + 5*x - 1)*F^2 - (4*x^3 - 7*x^2 + 6*x - 1)*F + x^2 = 0.

Crossrefs

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

Sequence in context: A150267 A271388 A165540 * A111053 A165541 A165542

Adjacent sequences: A363806 A363807 A363808 * A363810 A363811 A363812

Keyword

nonn

Author

Andrei Asinowski, Jun 23 2023

Status

approved