A263777 -id:A263777 - 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

A336070 Number of inversion sequences avoiding the vincular pattern 10-0 (or 10-1).

Original entry on oeis.org

1, 1, 2, 6, 23, 106, 567, 3440, 23286, 173704, 1414102, 12465119, 118205428, 1199306902, 12958274048, 148502304614, 1798680392716, 22953847041950, 307774885768354, 4325220458515307, 63563589415836532, 974883257009308933, 15575374626562632462, 258780875395778033769, 4464364292401926006220

Offset: 0

Michael De Vlieger, Jul 07 2020

nonn

From Joerg Arndt, Jan 20 2024: (Start)
a(n) is the number of weak ascent sequences of length n.
A weak ascent sequence is a sequence [d(1), d(2), ..., d(n)] where d(1)=0, d(k)>=0, and d(k) <= 1 + asc([d(1), d(2), ..., d(k-1)]) and asc(.) counts the weak ascents d(j) >= d(j-1) of its argument.
The number of length-n weak ascent sequences with maximal number of weak ascents is A000108(n).
(End)

			From _Joerg Arndt_, Jan 20 2024: (Start)
There are a(4) = 23 weak ascent sequences (dots for zeros):
   1:  [ . . . . ]
   2:  [ . . . 1 ]
   3:  [ . . . 2 ]
   4:  [ . . . 3 ]
   5:  [ . . 1 . ]
   6:  [ . . 1 1 ]
   7:  [ . . 1 2 ]
   8:  [ . . 1 3 ]
   9:  [ . . 2 . ]
  10:  [ . . 2 1 ]
  11:  [ . . 2 2 ]
  12:  [ . . 2 3 ]
  13:  [ . 1 . . ]
  14:  [ . 1 . 1 ]
  15:  [ . 1 . 2 ]
  16:  [ . 1 1 . ]
  17:  [ . 1 1 1 ]
  18:  [ . 1 1 2 ]
  19:  [ . 1 1 3 ]
  20:  [ . 1 2 . ]
  21:  [ . 1 2 1 ]
  22:  [ . 1 2 2 ]
  23:  [ . 1 2 3 ]
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..400
Juan S. Auli and Sergi Elizalde, Wilf equivalences between vincular patterns in inversion sequences, arXiv:2003.11533 [math.CO], 2020. See p. 5, Table 1. Gives terms 1-10.
Beata Benyi, Anders Claesson, and Mark Dukes, Weak ascent sequences and related combinatorial structures, arXiv:2111.03159 [math.CO], (4-November-2021).

Cf. A000079, A000108, A000110, A022493, A091768, A102038, A113227, A263777, A328441, A336071, A336072.

Row sums of A369321.

b:= proc(n, i, t) option remember; `if`(n=0, 1,
      add(b(n-1, j, t+`if`(j>=i, 1, 0)), j=0..t+1))
    end:
a:= n-> b(n, -1$2):
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 23 2024

b[n_, i_, t_] := b[n, i, t] = If[n == 0, 1, Sum[b[n - 1, j, t + If[j >= i, 1, 0]], {j, 0, t + 1}]];
a[n_] := b[n, -1, -1];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jan 18 2025, after Alois P. Heinz *)

\\ see formula (5) on page 18 of the Benyi/Claesson/Dukes reference
N=40;
M=matrix(N,N,r,c,-1);  \\ memoization
a(n,k)=
{
    if ( n==0 && k==0, return(1) );
    if ( k==0, return(0) );
    if ( n==0, return(0) );
    if ( M[n,k] != -1 , return( M[n,k] ) );
    my( s );
    s = sum( i=0, n, sum( j=0, k-1,
         (-1)^j * binomial(k-j,i) * binomial(i,j) * a( n-i, k-j-1 )) );
    M[n,k] = s;
    return( s );
}
for (n=0, N, print1( sum(k=1,n,a(n,k)),", "); );
\\ print triangle a(n,k), see A369321:
\\ for (n=0, N, for(k=0,n, print1(a(n,k),", "); ); print(););
\\ Joerg Arndt, Jan 20 2024

a(0)=1 prepended and more terms from Joerg Arndt, Jan 20 2024

A360052 Number of length n inversion sequences avoiding the patterns 010 and 201 (or 010 and 210).

Original entry on oeis.org

1, 1, 2, 5, 15, 53, 214, 958, 4650, 24103, 131974, 757011, 4519321, 27933252, 177987808, 1165057411, 7811122974, 53506838952, 373693431140, 2656088059747, 19182588092365, 140577110057850, 1044102585724522, 7851149068600037, 59714190403840142, 459001044591439621

Offset: 0

Benjamin Testart, Jan 23 2023

nonn

Benjamin Testart, Table of n, a(n) for n = 0..200
Benjamin Testart, Inversion sequences avoiding the pattern 010, arXiv:2212.07222 [math.CO], 2022. See Table 2 p. 2.
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. A263779, A263777.

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

A336071 Number of inversion sequences avoiding the vincular pattern 1-01 (or 1-10).

Original entry on oeis.org

1, 2, 6, 23, 107, 584, 3655, 25790, 202495, 1750763

Offset: 1

Michael De Vlieger, Jul 07 2020

Juan S. Auli, Sergi Elizalde, Wilf equivalences between vincular patterns in inversion sequences, arXiv:2003.11533 [math.CO], 2020. See p. 5, Table 1. Gives terms 1-10.

Cf. A000079, A000110, A022493, A091768, A102038, A113227, A263777, A328441, A336070, A336072.

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

A336070 Number of inversion sequences avoiding the vincular pattern 10-0 (or 10-1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A360052 Number of length n inversion sequences avoiding the patterns 010 and 201 (or 010 and 210).

Views

Author

Keywords