login
A279555
Number of length n inversion sequences avoiding the patterns 110, 210, 120, and 010.
27
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,3
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<j<k) such that e_j > 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<j<k) such that e_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)
LINKS
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.
FORMULA
a(n) ~ c * (1 + sqrt(2))^(2*n) / n^(3/2), where c = 0.00391075995650885016134430802... - Vaclav Kotesovec, Jan 23 2025
EXAMPLE
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.
KEYWORD
nonn
AUTHOR
Megan A. Martinez, Dec 16 2016
EXTENSIONS
a(10)-a(26) from Alois P. Heinz, Jan 05 2017
STATUS
approved