A117106 -id:A117106 - cp's OEIS frontend

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

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

A363682 Number of plane bipolar posets (i.e., plane bipolar orientations with no transitive edge) with n edges.

Original entry on oeis.org

1, 1, 1, 2, 5, 12, 32, 93, 279, 872, 2830, 9433, 32223, 112527, 400370, 1448520, 5320023, 19802827, 74612164, 284238390, 1093757436, 4247742956, 16636921148, 65671960544, 261111950308, 1045172796381, 4209807155949, 17055625810984, 69476952146529, 284467866640048

Offset: 1

Éric Fusy, Jun 16 2023

nonn

a(n) is also the number of walks of length n-1 in the quadrant, starting and ending at the origin, with step-set {0,E,S,NW,SE} (where 0 is the stay-step).

Éric Fusy, Erkan Narmanli, and Gilles Schaeffer, On the enumeration of plane bipolar posets and transversal structures, arXiv:2105.06955 [math.CO], 2021-2022.

Cf. A001181, A296419, A117106, A151335.

A:=proc(n,i,j) option remember:
if n=0 and i=0 and j=0 then return 1:
elif n<=0 or j<0 or i<0 then return 0:
else
return A(n-1,i,j)+A(n-1,i-1,j)+A(n-1,i,j+1)+A(n-1,i+1,j-1)+A(n-1,i-1,j+1):
fi:
end proc:
seq(A(n-1,0,0),n=1..20);

cp's OEIS Frontend

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