A279555 Number of length n inversion sequences avoiding the patterns 110, 210, 120, and 010.

1, 1, 2, 5, 15, 51, 189, 746, 3091, 13311, 59146, 269701, 1256820, 5966001, 28773252, 140695923, 696332678, 3483193924, 17589239130, 89575160517, 459648885327, 2374883298183, 12346911196912, 64555427595970, 339276669116222, 1791578092326881, 9501960180835998

Offset: 0

Author

Megan A. Martinez, Dec 16 2016

Keywords

• nonn

Comments

A length n inversion sequence e_1e_2...e_n is a sequence of integers where 0 <= e_i <= i-1. The term a(n) counts those length n inversion sequences with no entries e_i, e_j, e_k (where i e_k and e_i >= e_k. This is the same as the set of length n inversion sequences avoiding 010, 110, 120, and 210.

It can be shown that this sequence also counts the length n inversion sequences with no entries e_i, e_j, e_k (where i e_j >=e_k and e_i >= e_k. This is the same as the set of length n inversion sequences avoiding 010, 100, 120, and 210.

From Andrei Asinowski, Jan 22 2025: (Start)

It also enumerates seven other classes of inversion sequences defined by avoidance of four patterns of length 3 (case 166 in Callan and Mansour).

It also enumerates inversion sequences that avoid the patterns 011 and 201, and inversion sequences that avoid the patterns 011 and 210.

For n >= 1, it also enumerates strong rectangulations that avoid T-shaped joints. (End)

Examples

			The length 3 inversion sequences avoiding (010, 110, 120, 210) are 000, 001, 002, 011, 012.
The length 4 inversion sequences avoiding (010, 110, 120, 210) are 0000, 0001, 0002, 0003, 0011, 0012, 0013, 0021, 0022, 0023, 0111, 0112, 0113, 0122, 0123.
		

Links

• Jay Pantone, Table of n, a(n) for n = 0..500
• Andrei Asinowski and Michaela A. Polley, Patterns in rectangulations. Part I: T-like patterns, inversion sequence classes I(010, 101, 120, 201) and I(011, 201), and rushed Dyck paths, arXiv:2501.11781 [math.CO], 2025.
• David Callan and Toufik Mansour, Inversion sequences avoiding quadruple length-3 patterns, Integers, 23 (2023), Article A78.
• Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
• Jay Pantone, The enumeration of inversion sequences avoiding the patterns 201 and 210, Enumerative Combinatorics and Applications, 4:4 (2024), Article S2R25.
• Chunyan Yan and Zhicong Lin, Inversion sequences avoiding pairs of patterns, arXiv:1912.03674 [math.CO], 2019.

Crossrefs

Cf. A263777, A263778, A263779, A263780, A279551, A279552, A279553, A279554, A279556, A279557, A279558, A279559, A279560, A279561, A279562, A279563, A279564, A279565, A279566, A279567, A279568, A279569, A279570, A279571, A279572, A279573.

Formula

a(n) ~ c * (1 + sqrt(2))^(2*n) / n^(3/2), where c = 0.00391075995650885016134430802... - Vaclav Kotesovec, Jan 23 2025

Extensions

a(10)-a(26) from Alois P. Heinz, Jan 05 2017