A263780 -id:A263780 - cp's OEIS frontend

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

1, 1, 2, 6, 22, 91, 409, 1953, 9763, 50583, 269697, 1472080, 8193306, 46359256, 266023710, 1545165168, 9070274236, 53739936609, 321025143482, 1931764542709, 11700651842997, 71288958790413, 436662467207291, 2687623420862395, 16615163817647042, 103131646740020637

Offset: 0

Megan A. Martinez, Feb 21 2017

nonn

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 110, 120, and 210.

It was shown that a_n also counts those 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 100, 120, and 210.

			The length 4 inversion sequences avoiding (110, 120, 210) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0021, 0022, 0023, 0100, 0101, 0102, 0103, 0111, 0112, 0113, 0121, 0122, 0123.
The length 4 inversion sequences avoiding (100, 120, 210) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0021, 0022, 0023, 0101, 0102, 0103, 0110, 0111, 0112, 0113, 0121, 0122, 0123.

Alois P. Heinz, Table of n, a(n) for n = 0..400
Megan A. Martinez, Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
Hanna Mularczyk, Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations, arXiv:1908.04025 [math.CO], 2019.

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

b:= proc(n, i, t) option remember; `if`(n=0, 1,
      add(b(n-1, i-min(t, j)+2, abs(t-j)+1), j=1..i))
    end:
a:= n-> b(n, 1$2):
seq(a(n), n=0..30);  # Alois P. Heinz, Feb 21 2017

b[n_, i_, t_] := b[n, i, t] = If[n == 0, 1, Sum[b[n - 1, i - Min[t, j] + 2, Abs[t-j]+1], {j, 1, i}]]; a[n_] :=  b[n, 1, 1]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jul 10 2017, after Alois P. Heinz *)

a(n) ~ c * (27/4)^n / n^(3/2), where c = 0.0111684107126703379786799829348... - Vaclav Kotesovec, Oct 07 2021

a(10)-a(25) from Alois P. Heinz, Feb 21 2017

A279571 Number of length n inversion sequences avoiding the patterns 100, 101, and 201.

Original entry on oeis.org

1, 1, 2, 6, 22, 92, 424, 2106, 11102, 61436, 353980, 2110366, 12955020, 81569168, 525106698, 3447244188, 23028080268, 156246994264, 1075127143948, 7492458675666, 52820934349420, 376331681648402, 2707312468516446, 19650530699752470, 143807774782994412, 1060472244838174574, 7875713244761349666, 58876660310205135380, 442862775457168812898, 3350397169412102710198

Offset: 0

Megan A. Martinez, Feb 21 2017

nonn

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_j <= e_k and e_i >= e_k. This is the same as the set of length n inversion sequences avoiding 100, 101, and 201.

			The length 4 inversion sequences avoiding (100,101,201) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0021, 0022, 0023, 0102, 0103, 0110, 0111, 0112, 0113, 0120, 0121, 0122, 0123.

Vaclav Kotesovec, Table of n, a(n) for n = 0..32
Megan A. Martinez, Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.

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

b:= proc(n, i, s, m) option remember;
      `if`(n=0, 1, add(b(n-1, i+1, s minus {$j..m-
      `if`(j=m, 1, 0)} union {i+1}, max(m, j)), j=s))
    end:
a:= n-> b(n, 1, {1}, 0):
seq(a(n), n=0..15);  # Alois P. Heinz, Feb 22 2017

b[n_, i_, s_, m_] := b[n, i, s, m] = If[n == 0, 1, Sum[b[n-1, i+1, s  ~Complement~ Range[j, m - If[j == m, 1, 0]] ~Union~ {i+1}, Max[m, j]], {j, s}]];
a[n_] := b[n, 1, {1}, 0];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Oct 27 2017, after Alois P. Heinz *)

a(10)-a(25) from Alois P. Heinz, Feb 22 2017

a(26)-a(29) from Vaclav Kotesovec, Oct 07 2021

A279573 Number of length n inversion sequences avoiding the patterns 120 and 210.

Original entry on oeis.org

1, 1, 2, 6, 23, 102, 499, 2625, 14601, 84847, 510614, 3161964, 20050770, 129718404, 853689031, 5701759424, 38574689104, 263936457042, 1824032887177, 12718193293888, 89386742081688, 632746535420834, 4508140253686638, 32308561883462867, 232790342330880572

Offset: 0

Megan A. Martinez, Feb 21 2017

nonn

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_j > e_k and e_i > e_k. This is the same as the set of length n inversion sequences avoiding 120 and 210.

			The length 4 inversion sequences avoiding (120,210) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0021, 0022, 0023, 0100, 0101, 0102, 0103, 0110, 0111, 0112, 0113, 0121, 0122, 0123.

Alois P. Heinz, Table of n, a(n) for n = 0..400
Megan A. Martinez, Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
Chunyan Yan, Zhicong Lin, Inversion sequences avoiding pairs of patterns, arXiv:1912.03674 [math.CO], 2019.

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

a(n) ~ c * 8^n / n^(3/2), where c = 0.0013548789253263217919... - Vaclav Kotesovec, Oct 07 2021

a(10)-a(24) from Alois P. Heinz, Feb 21 2017

A279554 Number of length n inversion sequences avoiding the patterns 010, 101, 120, 201, and 210.

Original entry on oeis.org

1, 1, 2, 5, 15, 51, 188, 733, 2979, 12495, 53708, 235396, 1048168, 4728757, 21569339, 99309057, 460932778, 2154402107

Offset: 0

Megan A. Martinez, Dec 15 2016

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_j <> e_k and e_i >= e_k. This is the same as the set of length n inversion sequences avoiding 010, 101, 120, 201, and 210.

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

Megan A. Martinez, Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016-2018.

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

a(10)-a(11) from Alois P. Heinz, Feb 24 2017

a(12)-a(17) from Bert Dobbelaere, Dec 30 2018

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

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 200, 830, 3654, 16869, 80963, 401300, 2043610, 10649335, 56604706, 306101789, 1680515427

Offset: 0

Megan A. Martinez, Jan 17 2017

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_j > e_k and e_i >= e_k. This is the same as the set of length n inversion sequences avoiding 010, 120, and 210.

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

Megan A. Martinez, Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016-2018.

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

a(10)-a(12) from Alois P. Heinz, Feb 24 2017

a(13)-a(16) from Bert Dobbelaere, Dec 30 2018

A279572 Number of length n inversion sequences avoiding the patterns 120, 201, and 210.

Original entry on oeis.org

1, 1, 2, 6, 23, 101, 484, 2468, 13166, 72630, 411076, 2374188, 13938018, 82932254, 499031324, 3031610924, 18568429963, 114541486785, 710973143614, 4437415155234, 27831038618735, 175318861863701, 1108762012137252, 7037137177329268, 44808588430903068

Offset: 0

Megan A. Martinez, Feb 21 2017

nonn

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_j <> e_k and e_i > e_k. This is the same as the set of length n inversion sequences avoiding 120, 201, and 210.

			The length 4 inversion sequences avoiding (120, 201, 210) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0021, 0022, 0023, 0100, 0101, 0102, 0103, 0110, 0111, 0112, 0113, 0121, 0122, 0123.

Toufik Mansour, Howard Skogman, and Rebecca Smith, Sorting inversion sequences, arXiv:2401.06662 [math.CO], 2024. See Theorem 4.3 at page 16.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016-2018.

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

a(12)-a(15) from Bert Dobbelaere, Dec 30 2018

a(16)-a(24) from Toufik Mansour et al. added by Stefano Spezia, Jan 20 2024

A374545 Number of length n inversion sequences avoiding the patterns 100 and 101.

Original entry on oeis.org

1, 1, 2, 6, 22, 93, 439, 2267, 12628, 75119, 473610, 3146376, 21923158, 159610880, 1210421617, 9536525715, 77885388296, 658112437816, 5743744103287, 51701114086088, 479340725109862, 4572111104329002, 44818226981293308, 451062570619242508, 4656687307250419533

Offset: 0

Benjamin Testart, Jul 12 2024

nonn

Benjamin Testart, Table of n, a(n) for n = 0..580
Benjamin Testart, Completing the enumeration of inversion sequences avoiding one or two patterns of length 3, arXiv:2407.07701 [math.CO], 2024.

Cf. A113227, A263780, A279564, A279570, A374544.

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

Original entry on oeis.org

1, 1, 2, 4, 10, 26, 73, 214, 651, 2040, 6549, 21453, 71485, 241702, 827603, 2865087, 10014927, 35307628, 125427569, 448616693, 1614432373, 5842129120, 21247505098, 77631329535, 284832049361, 1049092809734, 3877749157355, 14380314221305, 53490244751332

Offset: 0

Megan A. Martinez, Dec 14 2016

nonn

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 000, 010, 100, 110, 120, and 210.

			For n=3, the inversion sequences are 001, 002, 011, 012.

Alois P. Heinz, Table of n, a(n) for n = 0..600
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.

Cf. A000085, A263777, A263778, A263779, A263780.

b:= proc(n, i, m) option remember; `if`(i=0, 1, add(
      b(n-min(m, j), i-1, abs(m-j)), j=1..n-i+1))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Dec 15 2016

b[n_, i_, m_] := b[n, i, m] = If[i == 0, 1, Sum[b[n - Min[m, j], i - 1, Abs[m - j]], {j, 1, n - i + 1}]];
a[n_] := b[n, n, 0];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 10 2017, after Alois P. Heinz *)

a(n) ~ c * 4^n / n^(3/2), where c = 0.0549097036253448014962069269284638611865763295943683310517... - Vaclav Kotesovec, Oct 07 2021

a(10)-a(28) from Alois P. Heinz, Dec 14 2016

Name and description corrected by Nicholas R. Beaton, May 02 2024

A374549 Number of length n inversion sequences avoiding the patterns 100 and 120.

Original entry on oeis.org

1, 1, 2, 6, 22, 92, 421, 2062, 10646, 57324, 319436, 1831585, 10758458, 64513454, 393846399, 2442328993, 15356020884, 97741913382, 628994116349, 4087863691061, 26805206933158, 177198351316543, 1180073345351131, 7912190584017869, 53380776660751987

Offset: 0

Benjamin Testart, Jul 17 2024

nonn

Benjamin Testart, Table of n, a(n) for n = 0..350
Benjamin Testart, Completing the enumeration of inversion sequences avoiding one or two patterns of length 3, arXiv:2407.07701 [math.CO], 2024.

Cf. A263778, A263780, A279559, A279564, A279570, A374544.

A374554 Number of length n inversion sequences avoiding the patterns 100 and 102.

Original entry on oeis.org

1, 1, 2, 6, 21, 80, 318, 1305, 5487, 23535, 102603, 453400, 2026408, 9144361, 41607161, 190675552, 879318056, 4077566276, 19001732690, 88940105945, 417948841012, 1971086634986, 9326180071850, 44258248464408, 210605264950063, 1004694354945863, 4804017049287049

Offset: 0

Benjamin Testart, Jul 17 2024

nonn

Benjamin Testart, Table of n, a(n) for n = 0..400
Benjamin Testart, Completing the enumeration of inversion sequences avoiding one or two patterns of length 3, arXiv:2407.07701 [math.CO], 2024.

Cf. A200753, A263780, A279564, A279566, A374541, A374542, A374544, A374545, A374553.

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A279571 Number of length n inversion sequences avoiding the patterns 100, 101, and 201.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Extensions

A279573 Number of length n inversion sequences avoiding the patterns 120 and 210.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A279554 Number of length n inversion sequences avoiding the patterns 010, 101, 120, 201, and 210.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A279572 Number of length n inversion sequences avoiding the patterns 120, 201, and 210.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A374545 Number of length n inversion sequences avoiding the patterns 100 and 101.

Views

Author

Keywords

Links

Crossrefs

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica