Megan A. Martinez - cp's OEIS frontend

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

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

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

Original entry on oeis.org

1, 1, 2, 6, 22, 90, 396, 1833, 8801, 43441, 219092, 1124201, 5850414, 30805498, 163824559, 878655117, 4747341879, 25815026491, 141173582016, 775920816789, 4283833709457, 23746640019657, 132116647765569, 737485227605338, 4129174120158569, 23183379592361839

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

			The length 4 inversion sequences avoiding (110, 120, 201, 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, 201, 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..1294
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, A263777, A263778, A263779, A263780, A279551, A279552, A279553, A279554, A279555, A279556, A279557, A279558, A279559, A279560, A279561, A279562, A279563, A279564, A279565, A279566, A279567, A279569, A279570, A279571, A279572, A279573.

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

b[n_, i_, l_] := b[n, i, l] = If[n == 0, 1, Sum[b[n-1, i-#+2, j-#+1]& @ Max[1, If[j == l, 0, l]], {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 * d^n / n^(3/2), where d = 5.98041772076926677236919875200507... is the positive root of the equation -32 - 195*d - 12*d^2 - 112*d^3 + 20*d^4 = 0 and c = 0.1056946795054351807407212356928404107733262398133039312067247126343... - Vaclav Kotesovec, Oct 07 2021

a(10)-a(25) from Alois P. Heinz, Feb 23 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

A279570 Number of length n inversion sequences avoiding the patterns 110 and 120.

Original entry on oeis.org

1, 1, 2, 6, 22, 92, 423, 2091, 10950, 60120, 343453, 2029809, 12354661, 77168197, 493189283, 3217459119, 21382723456, 144518555231, 991885282987, 6904454991721, 48691257834999, 347542736059492, 2508603139285095, 18297609829743478, 134772911886028731

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 and 120.

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

Benjamin Testart, Table of n, a(n) for n = 0..350
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
Benjamin Testart, Completing the enumeration of inversion sequences avoiding one or two patterns of length 3, arXiv:2407.07701 [math.CO], 2024.

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, A279571, A279572, A279573.

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

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

Original entry on oeis.org

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

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

Original entry on oeis.org

1, 1, 2, 6, 21, 82, 343, 1509, 6893, 32419, 156058, 765578, 3815062, 19263736, 98368919, 507197436, 2637242188, 13814247530, 72834238423, 386244387688, 2058933104170, 11026807340592, 59304897232442, 320181600386661, 1734685419170666, 9428340999504441

Offset: 0

Megan A. Martinez, Feb 09 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 100, 110, 120, and 210.

			The length 4 inversion sequences avoiding (100, 110, 120, 210) are 0000, 0001, 0002, 0003, 0010, 0011, 0012, 0013, 0020, 0021, 0022, 0023, 0101, 0102, 0103, 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.

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

b:= proc(n, i, m) option remember; `if`(n=0, 1, add((h->
      b(n-1, i-h+1, max(m, j)-h))(max(0, min(m-1, j))), j=1..i))
    end:
a:= n-> b(n, 1, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Feb 23 2017

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

a(n) ~ c * (1 + sqrt(2))^(2*n) / n^(3/2), where c = 0.066085708825649431003670013119332303648755519420440375... - Vaclav Kotesovec, Oct 07 2021

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

A279566 Number of length n inversion sequences avoiding the patterns 102 and 201.

Original entry on oeis.org

1, 1, 2, 6, 22, 87, 354, 1465, 6154, 26223, 113236, 494870, 2185700, 9743281, 43784838, 198156234, 902374498, 4131895035, 19012201080, 87864535600, 407664831856, 1898184887679, 8867042353912, 41543375724751, 195164372948152, 919138464708907, 4338701289961694, 20524046955770940

Offset: 0

Megan A. Martinez, Feb 09 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 102 and 201.

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

Benjamin Testart, Table of n, a(n) for n = 0..1400
Megan A. Martinez, Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016-2018.
Benjamin Testart, Completing the enumeration of inversion sequences avoiding one or two patterns of length 3, arXiv:2407.07701 [math.CO], 2024.
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, A279567, A279568, A279569, A279570, A279571, A279572, A279573.

G.f.: (-8*x^4 + 18*x^3 - 10*x^2 - 8*x + 4 + 2 * (2*x - 1) * (x^2 - 2*x + 2) * ((5*x - 1)*(x - 1))^(1/2)) / (4*x * (2*x - 1) * (x - 1) * (x - 2)^2). - Benjamin Testart, Jul 12 2024

a(n) ~ 41 * 5^(n + 3/2) / (648 * sqrt(Pi) * n^(3/2)). - Vaclav Kotesovec, Nov 21 2024

a(10)-a(11) from Alois P. Heinz, Feb 24 2017
a(12)-a(17) from Bert Dobbelaere, Dec 30 2018
a(18) and beyond from Benjamin Testart, Jul 12 2024

A279565 Number of length n inversion sequences avoiding the patterns 100, 110, 120, 201, and 210.

Original entry on oeis.org

1, 1, 2, 6, 21, 81, 332, 1420, 6266, 28318, 130412, 609808, 2887582, 13818590, 66726628, 324713196, 1590853485, 7840315329, 38843186366, 193342353214, 966409013021, 4848846341569, 24412146213116, 123290812268404, 624448756434476, 3171046361310556

Offset: 0

Megan A. Martinez, Feb 09 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. This is the same as the set of length n inversion sequences avoiding 100, 110, 120, 201, and 210.

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

Alois P. Heinz, Table of n, a(n) for n = 0..1372
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. A000108, A057552, A263777, A263778, A263779, A263780, A279551, A279552, A279553, A279554, A279555, A279556, A279557, A279558, A279559, A279560, A279561, A279562, A279563, A279564, A279566, A279567, A279568, A279569, A279570, A279571, A279572, A279573.

I:=[6, 21, 81]; [1,1,2] cat [n le 3 select I[n] else ( (n+1)*(17*n+6)*Self(n-1) +(49*n^2+11*n+22)*Self(n-2) +3*(3*n-1)*(3*n-2)*Self(n-3) )/(5*(n+2)*(n+1)) : n in [1..30]]; // G. C. Greubel, Mar 29 2019

a:= proc(n) option remember; `if`(n<3, n!,
      ((n-1)*(17*n-28)*a(n-1) +(49*n^2-185*n+196)*a(n-2)
       +(3*(3*n-7))*(3*n-8)*a(n-3)) / (5*n*(n-1)))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Feb 22 2017

a[n_] := a[n] = If[n < 3, n!, (((n - 1)*(17*n - 28)*a[n-1] + (49*n^2 - 185*n + 196)*a[n-2] + (3*(3*n - 7))*(3*n - 8)*a[n-3]) / (5*n*(n - 1)))]; Array[a, 30, 0] (* Jean-François Alcover, Nov 06 2017, after Alois P. Heinz *)
Join[{1}, Table[(1/n)*Sum[m*Sum[Binomial[k, n-m-k]*Binomial[n+k-1, k], {k, 0, n-m}], {m, 1, n}], {n, 1, 30}]] (* G. C. Greubel, Mar 29 2019 *)

a(n):=if n=0 then 1 else sum(m*sum(binomial(k,n-m-k)*binomial(n+k-1,k),k,0,n-m),m,1,n)/n; /* Vladimir Kruchinin, Mar 26 2019 */

my(x='x+O('x^30)); Vec(round(3/(4-4*sin(asin((27*x+11)/16)/3)))) \\ G. C. Greubel, Mar 29 2019

[1] +[(1/n)*(sum(sum(k*binomial(j,n-k-j)*binomial(n+j-1,j) for j in (0..n-k)) for k in (1..n))) for n in (1..30)] # G. C. Greubel, Mar 29 2019

G.f.: 3/(4-4*sin(asin((27*x+11)/16)/3)). - Vladimir Kruchinin, Mar 25 2019
a(n) = (1/n)*Sum_{m=1..n} m*Sum_{k=0..n-m} C(k,n-m-k)*C(n+k-1,k), n>0, a(0)=1. - Vladimir Kruchinin, Mar 26 2019
a(n) ~ 3^(3*n + 1/2) / (2^(7/2) * sqrt(Pi) * n^(3/2) * 5^(n - 1/2)). - Vaclav Kotesovec, Oct 07 2021
Conjecture: a(n) = (v_n + v_{n+1})/2 for n > 0 with a(0) = 1 where we start with vector v of fixed length m with elements v_i = 1 and for i=1..m-2, for j=i+2..m apply v_j := Sum_{k=0..2} v_{j-k}. - Mikhail Kurkov, Sep 03 2024

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

A279564 Number of length n inversion sequences avoiding the patterns 000 and 100.

Original entry on oeis.org

1, 1, 2, 5, 16, 60, 260, 1267, 6850, 40572, 260812, 1805646, 13377274, 105487540, 881338060, 7770957903, 72060991394, 700653026744, 7123871583656, 75561097962918, 834285471737784, 9570207406738352, 113855103776348136, 1402523725268921870, 17863056512845724036, 234910502414771617316, 3185732802058088068444, 44501675392317774477088

Offset: 0

Megan A. Martinez, Feb 09 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. This is the same as the set of length n inversion sequences avoiding 000 and 100.

Benjamin Testart, Table of n, a(n) for n = 0..540
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
Benjamin Testart, Completing the enumeration of inversion sequences avoiding one or two patterns of length 3, arXiv:2407.07701 [math.CO], 2024.
Chunyan Yan and 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, A279565, A279566, A279567, A279568, A279569, A279570, A279571, A279572, A279573.

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

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

The length 4 inversion sequences avoiding (000,100) are 0011, 0012, 0013, 0021, 0022, 0023, 0101, 0102, 0103, 0110, 0112, 0113, 0120, 0121, 0122, 0123.

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

a(24)-a(27) from Vaclav Kotesovec, Oct 08 2021

cp's OEIS Frontend

User: Megan A. Martinez

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A279568 Number of length n inversion sequences avoiding the patterns 110, 120, 201, 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

A279570 Number of length n inversion sequences avoiding the patterns 110 and 120.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula