A114277 -id:A114277 - cp's OEIS frontend

A279557 Number of length n inversion sequences avoiding the patterns 110, 120, and 021.

1, 1, 2, 6, 20, 68, 233, 805, 2807, 9879, 35073, 125513, 452389, 1641029, 5986994, 21954974, 80884424, 299233544, 1111219334, 4140813374, 15478839554, 58028869154, 218123355524, 821908275548, 3104046382352, 11747506651600, 44546351423300, 169227201341652

Offset: 0

Megan A. Martinez, Jan 16 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 021.

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

Alois P. Heinz, Table of n, a(n) for n = 0..1668
Megan A. Martinez, Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.

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

a:= proc(n) option remember; `if`(n<3, n!,
      ((5*n^2-6*n-2)*a(n-1)-(4*n-2)*(n-1)*a(n-2))/(n^2-4))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, Mar 11 2017

a[n_] := 1 + Sum[(k - t - 1) (k - t)/(n - t + 1)* Binomial[2 n - k - t + 1, n - k + 1], {t, n - 1}, {k, t + 2, n + 1}]; Array[a, 28, 0] (* Robert G. Wilson v, Feb 25 2017 *)

a(n) = 1 + Sum_{t=1..n-1} Sum_{k=t+2..n+1} (k-t-1)*(k-t)/(n-t+1) * binomial(2n-k-t+1,n-k+1).
Conjecture: a(n) = C_{n+1}-Sum_{i=1..n} C_i where C_i is the i-th Catalan number, binomial(2i,i)/(i+1).
Assuming the conjecture a(n) ~ (64/3)*4^n/((4*n+7)^(3/2)*sqrt(Pi)). - Peter Luschny, Feb 24 2017
From Alois P. Heinz, Mar 11 2017: (Start)
a(n) = 1 + A114277(n-2) for n>1.
G.f.: (sqrt(1-4*x)+2*x-1)*(2*x-1)/(2*(1-x)*x^2). (End)
D-finite with recurrence: (n+2)*a(n) +(-7*n-4)*a(n-1) +2*(7*n-5)*a(n-2) +4*(-2*n+3)*a(n-3)=0. - R. J. Mathar, Feb 21 2020

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

a(13) onward Robert G. Wilson v, Feb 25 2017

A323224 A(n, k) = [x^k] C^nx/(1 - x) where C = 2/(1 + sqrt(1 - 4x)), square array read by ascending antidiagonals with n >= 0 and k >= 0.

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 4, 1, 0, 1, 4, 8, 9, 1, 0, 1, 5, 13, 22, 23, 1, 0, 1, 6, 19, 41, 64, 65, 1, 0, 1, 7, 26, 67, 131, 196, 197, 1, 0, 1, 8, 34, 101, 232, 428, 625, 626, 1, 0, 1, 9, 43, 144, 376, 804, 1429, 2055, 2056, 1

Offset: 0

Peter Luschny, Jan 24 2019

Equals A096465 when the leading column (k = 0) is removed. - Georg Fischer, Jul 26 2023

			The square array starts:
   [n\k]  0  1   2   3    4     5     6      7       8       9
    ---------------------------------------------------------------
    [0]   0, 1,  1,  1,   1,    1,    1,     1,      1,      1, ... A057427
    [1]   0, 1,  2,  4,   9,   23,   65,   197,    626,   2056, ... A014137
    [2]   0, 1,  3,  8,  22,   64,  196,   625,   2055,   6917, ... A014138
    [3]   0, 1,  4, 13,  41,  131,  428,  1429,   4861,  16795, ... A001453
    [4]   0, 1,  5, 19,  67,  232,  804,  2806,   9878,  35072, ... A114277
    [5]   0, 1,  6, 26, 101,  376, 1377,  5017,  18277,  66727, ... A143955
    [6]   0, 1,  7, 34, 144,  573, 2211,  8399,  31655, 118865, ...
    [7]   0, 1,  8, 43, 197,  834, 3382, 13378,  52138, 201364, ...
    [8]   0, 1,  9, 53, 261, 1171, 4979, 20483,  82499, 327656, ...
    [9]   0, 1, 10, 64, 337, 1597, 7105, 30361, 126292, 515659, ...
.
Triangle given by ascending antidiagonals:
    0;
    0, 1;
    0, 1, 1;
    0, 1, 2,  1;
    0, 1, 3,  4,   1;
    0, 1, 4,  8,   9,   1;
    0, 1, 5, 13,  22,  23,   1;
    0, 1, 6, 19,  41,  64,  65,   1;
    0, 1, 7, 26,  67, 131, 196, 197,   1;
    0, 1, 8, 34, 101, 232, 428, 625, 626, 1;
.
The difference table of a column successively gives the preceding columns, here starting with column 6.
col(6) = 1, 65, 196, 428, 804, 1377, 2211, 3382, 4979, 7105, ...
col(5) =    64, 131, 232, 376,  573,  834, 1171, 1597, 2126, ...
col(4) =         67, 101, 144,  197,  261,  337,  426,  529, ...
col(3) =              34,  43,   53,   64,   76,   89,  103, ...
col(2) =                    9,   10,   11,   12,   13,   14, ...
col(1) =                          1,    1,    1,    1,    1, ...
col(0) =                                0,    0,    0,    0, ...
.
Example for the sum formula: C(0) = 1, C(1) = 1, C(2) = 2 and C(3) = 5.
X(3, 4) = {{0,0,0}, {0,0,1}, {0,1,0}, {1,0,0}, {0,0,2}, {0,1,1}, {0,2,0}, {1,0,1},
{1,1,0}, {2,0,0}, {0,0,3}, {0,1,2}, {0,2,1}, {0,3,0}, {1,0,2}, {1,1,1}, {1,2,0},
{2,0,1}, {2,1,0}, {3,0,0}}. T(3,4) = 1+1+1+1+2+1+2+1+1+2+5+2+2+5+2+1+2+2+2+5 = 41.

The coefficients of the polynomials generating the columns are in A323233.
Sums of antidiagonals and row 1 are A014137. Main diagonal is A242798.
Rows: A057427 (n=0), A014137 (n=1), A014138 (n=2), A001453 (n=3), A114277 (n=4), A143955 (n=5).
Columns: A000027 (k=2), A034856 (k=3), A323221 (k=4), A323220 (k=5).
Similar array based on central binomials is A323222.
Cf. A096465.

Row := proc(n, len) local C, ogf, ser; C := (1-sqrt(1-4*x))/(2*x);
ogf := C^n*x/(1-x); ser := series(ogf, x, (n+1)*len+1);
seq(coeff(ser, x, j), j=0..len) end:
for n from 0 to 9 do Row(n, 9) od;
# Alternatively by recurrence:
B := proc(n, k) option remember; if n <= 0 or k < 0 then 0
elif n = k then 1 else B(n-1, k) + B(n, k-1) fi end:
A := (n, k) -> B(n + k, k): seq(lprint(seq(A(n, k), k=0..9)), n=0..9);

(* Illustrating the sum formula, not efficient. *) T[0, K_] := Boole[K != 0];
T[N_, K_] := Module[{}, r[n_, k_] := FrobeniusSolve[ConstantArray[1, n], k];
X[n_] := Flatten[Table[r[N, j], {j, 0, n - 1}], 1];
Sum[Product[CatalanNumber[m[[i]]], {i, 1, N}], {m , X[K]}]];
Trow[n_] := Table[T[n, k], {k, 0, 9}]; Table[Trow[n], {n, 0, 9}]

For n>0 and k>0 let X(n, k) denote the set of all tuples of length n with elements from {0, ..., k-1} with sum < k. Let C(m) denote the m-th Catalan number. Then: A(n, k) = Sum_{(j1,...,jn) in X(n, k)} C(j1)*C(j2)*...*C(jn).

A(n, k) = T(n + k, k) with T(n, k) = T(n-1, k) + T(n, k-1) with T(n, k) = 0 if n <= 0 or k < 0 and T(n, n) = 1.

A118964 Triangle read by rows: T(n,k) is the number of Grand Dyck paths of semilength n that have k double rises above the x-axis (n >= 1, k >= 0).

Original entry on oeis.org

2, 5, 1, 14, 5, 1, 42, 19, 8, 1, 132, 67, 40, 12, 1, 429, 232, 166, 79, 17, 1, 1430, 804, 634, 395, 145, 23, 1, 4862, 2806, 2335, 1708, 879, 249, 30, 1, 16796, 9878, 8480, 6824, 4376, 1823, 404, 38, 1, 58786, 35072, 30691, 26137, 19334, 10521, 3542, 625, 47, 1

Offset: 1

Emeric Deutsch, May 07 2006

A Grand Dyck path of semilength n is a path in the half-plane x >= 0, starting at (0,0), ending at (2n,0) and consisting of steps u = (1,1) and d = (1,-1); a double rise in a Grand Dyck path is an occurrence of uu in the path.

For all double rises (above, below and on the x-axis), see A118963.

			T(3,1) = 5 because we have u/ududd,u/uddud,udu/udd,duu/udd and u/udddu (the double rises above the x-axis are indicated by /).
Triangle starts:
  2;
  5,   1;
  14,  5,  1;
  42,  19, 8,  1;
  132, 67, 40, 12, 1;

Alois P. Heinz, Rows n = 1..141, flattened

T(n,0) = A000108(n+1) (Catalan numbers), T(n,1) = A114277(n-2).

Cf. A000984 (row sums), A000108, A000531, A118963.

C:=(1-sqrt(1-4*z))/2/z: r:=(1-z-t*z-sqrt(z^2*t^2-2*z^2*t-2*z*t+z^2-2*z+1))/2/t/z: G:=(1+r)/(1-z*C*(1+r))-1: Gser:=simplify(series(G,z=0,15)): for n from 1 to 11 do P[n]:=coeff(Gser,z,n) od: for n from 1 to 11 do seq(coeff(P[n],t,j),j=0..n-1) od; # yields sequence in triangular form
# second Maple program:
b:= proc(x, y, t) option remember; `if`(abs(y)>x, 0,
      `if`(x=0, 1, expand(`if`(t=2, z, 1)*b(x-1, y+1,
      `if`(y>=0, min(t+1, 2), 1)) +b(x-1, y-1, 1))))
    end:
T:= n-> (p-> seq(coeff(p,z,i), i=0..n-1))(b(2*n, 0, 1)):
seq(T(n), n=1..12);  # Alois P. Heinz, Jun 16 2014

b[x_, y_, t_] := b[x, y, t] = If[Abs[y] > x, 0, If[x == 0, 1, Expand[If[t == 2, z, 1]*b[x-1, y+1, If[y >= 0, Min[t+1, 2], 1]] + b[x-1, y-1, 1]]]]; T[n_] := Function[ {p}, Table[Coefficient[p, z, i], {i, 0, n-1}]][b[2*n, 0, 1]]; Table[T[n], {n, 1, 12}] // Flatten (* Jean-François Alcover, Feb 19 2015, after Alois P. Heinz *)

Sum_{k>=0} k*T(n,k) = A000531(n-1).

G.f.: G(t,z) = (1+r)/[1-z(1+r)C]-1, where r = r(t,z) is the Narayana function, defined by (1+r)(1+tr)z = r, r(t,0) = 0 and C = C(z) = [1-sqrt(1-4z)]/(2z) is the Catalan function. More generally, the g.f. H = H(t,s,u,z), where t,s and u mark double rises above, below and on the x-axis, respectively, is H = [1 + r(s,z)]/[1 - z(1 + tr(t,z))(1 + ur(s,z))].

Keyword tabf changed to tabl by Michel Marcus, Apr 07 2013

A112307 Triangle read by rows: T(n,k) is number of Dyck paths of semilength n with height of second peak equal to k (n>=1; 0<=k<=n-1).

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 4, 6, 3, 1, 9, 16, 12, 4, 1, 23, 44, 39, 20, 5, 1, 65, 128, 123, 76, 30, 6, 1, 197, 392, 393, 268, 130, 42, 7, 1, 626, 1250, 1284, 928, 505, 204, 56, 8, 1, 2056, 4110, 4287, 3216, 1880, 864, 301, 72, 9, 1, 6918, 13834, 14583, 11224, 6885, 3438, 1379

Offset: 1

Emeric Deutsch, Nov 30 2005

Row sums are the Catalan numbers (A000108). T(n,0)=1 (paths have only one peak); The g.f. for column k is kz^(k+1)*c^k/(1-z), where c=[1-sqrt(1-4z)]/(2z) is the Catalan function. T(n,1)=A014137(n-1); T(n,2)=2*A014138(n-3); T(n,3)=3*A001453(n-2); T(n,4)=4*A114277(n-5); Sum(k*T(n,k), k=0..n-1)=A112308(n-2).

			T(4,1)=4 because we have UDUDUDUD, UDUDUUDD, UUDDUDUD and UUUDDDUD, where U=(1,1), D=(1,-1).
Triangle begins:
1;
1,1;
1,2,2;
1,4,6,3;
1,9,16,12,4;

Cf. A000108, A014137, A014138, A001453, A114277, A112308.

G:=((1-t*z*c)^2+t*z^2*c)/(1-z)/(1-t*z*c)^2-1: c:=(1-sqrt(1-4*z))/2/z: Gser:=simplify(series(G,z=0,15)): for n from 1 to 12 do P[n]:=coeff(Gser,z^n) od: for n from 1 to 12 do seq(coeff(t*P[n],t^j),j=1..n) od; # yields sequence in triangular form

G.f.=[(1-tzc)^2+tz^2*c]/[(1-z)(1-tzc)^2]-1, where c=[1-sqrt(1-4z)]/(2z) is the Catalan function.

A114276 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having length of second ascent equal to k (0<=k<=n-1).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 8, 4, 1, 1, 22, 13, 5, 1, 1, 64, 41, 19, 6, 1, 1, 196, 131, 67, 26, 7, 1, 1, 625, 428, 232, 101, 34, 8, 1, 1, 2055, 1429, 804, 376, 144, 43, 9, 1, 1, 6917, 4861, 2806, 1377, 573, 197, 53, 10, 1, 1, 23713, 16795, 9878, 5017, 2211, 834, 261, 64, 11, 1, 1

Offset: 1

Emeric Deutsch, Nov 20 2005

Column 1 yields A014138, column 2 yields A001453, column 3 yields A114277. Row sums are the Catalan numbers (A000108).

			T(4,2)=4 because we have UD(UU)DDUD, UD(UU)DUDD, UUD(UU)DDD and UUDD(UU)DD (second ascent shown between parentheses).

Cf. A000108, A014138, A001453, A114277.

T:=proc(n,k) if k=0 then 1 elif k<=n-1 then (k+1)*sum(binomial(2*n-k+1-2*j,n-j+1)/(2*n-k-2*j+1),j=1..n-k) else 0 fi end: for n from 1 to 12 do seq(T(n,k),k=0..n-1) od; # yields sequence in triangular form

T(n, k)=(k+1)*sum(binomial(2*n-k+1-2*j, n-j+1)/(2*n-k-2*j+1), j=1..n-k) if 1<=k<=n-1; T(n, 0)=1. G.f. = (1-tz)/[(1-z)(1-tzC)]-1 where C=[1-sqrt(1-4z)]/(2z) is the Catalan function.

A127156 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n starting with exactly k consecutive pyramids. A pyramid in a Dyck path is a factor of the form U^j D^j (j>0), starting at the x-axis. Here U=(1,1) and D=(1,-1). This definition differs from the one in A091866.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 1, 1, 2, 1, 5, 2, 3, 3, 1, 19, 7, 5, 6, 4, 1, 67, 26, 12, 11, 10, 5, 1, 232, 93, 38, 23, 21, 15, 6, 1, 804, 325, 131, 61, 44, 36, 21, 7, 1, 2806, 1129, 456, 192, 105, 80, 57, 28, 8, 1, 9878, 3935, 1585, 648, 297, 185, 137, 85, 36, 9, 1, 35072, 13813, 5520

Offset: 0

Emeric Deutsch, Feb 27 2007

Row sums yield the Catalan numbers (A000108). T(n,0)=A114277(n-3) for n>=3. Sum(k*T(n,k), k=0..n)=A014318(n-1) for n>=1.

			T(5,2)=5 because we have (UDUD)UUDUDD, (UUDDUUUDDD), (UUUDDDUUDD), (UDUUUUDDDD) and (UUUUDDDDUD) (the initial 2 pyramids are shown between parentheses).
Triangle starts:
1;
0,1;
0,1,1;
1,1,2,1;
5,2,3,3,1;
19,7,5,6,4,1;

Cf. A000108, A114277, A014318.

C:=(1-sqrt(1-4*z))/2/z: G:=(1-2*z)*C/(1-z-t*z): Gser:=simplify(series(G,z=0,15)): P[0]:=1: for n from 1 to 12 do P[n]:=sort(expand(coeff(Gser,z^n))) od: for n from 0 to 12 do seq(coeff(P[n],t,j),j=0..n) od; # yields sequence in triangular form

G.f.=G(t,z)=(1-2z)C/(1-z-tz), where C=[1-sqrt(1-4z)]/(2z) is the Catalan function. T(n,k)=T(n-1,k)+T(n-1,k-1) for n,k>=1.

A283054 Triangle read by rows: T(n,k) = T(n,k-1) + T(n-1,k), T(n,0)=1, T(n,n) = T(n,n-1) + 1.

Original entry on oeis.org

1, 1, 2, 1, 3, 4, 1, 4, 8, 9, 1, 5, 13, 22, 23, 1, 6, 19, 41, 64, 65, 1, 7, 26, 67, 131, 196, 197, 1, 8, 34, 101, 232, 428, 625, 626, 1, 9, 43, 144, 376, 804, 1429, 2055, 2056, 1, 10, 53, 197, 573, 1377, 2806, 4861, 6917, 6918, 1, 11, 64, 261, 834, 2211, 5017, 9878, 16795, 23713, 23714, 1, 12, 76, 337, 1171, 3382, 8399, 18277, 35072, 58785, 82499, 82500

Offset: 0

Ely Golden, Feb 27 2017

The left diagonals form polynomial sequences. This is due to the observation that diagonal 0 D_0(x) = 1, and D_n(x) = D_n(x-1)+D_(n-1)(x+1), with D_n(-1) = 1 which is a recurrence that can be solved.
These polynomials begin 1, x+2, (x(x+7)+8)/2, (x(x(x+15)+62)+54)/6, (x(x(x(x+26)+227)+730)+552)/24, etc., the first 3 of which correspond to A000012(n), A000027(n+2), and A034856(n+2), respectively.
The rightmost diagonal appears to follow A014137(n). The second rightmost appears to follow A014138(n+1), the third appears to follow A001453(n+2), the fourth appears to follow A114277(n), and the fifth appears to follow A143955(n+3).
A closed-form formula for T(n,k) would be very desirable.

			First 7 rows:
  1;
  1,   2;
  1,   3,   4;
  1,   4,   8,   9;
  1,   5,  13,  22,  23;
  1,   6,  19,  41,  64,  65;
  1,   7,  26,  67, 131, 196, 197;

Ely Golden, Rows n = 0..124 of triangle, flattened
Ely Golden, Java program for generating the triangle
Ely Golden, Sage program for computing the polynomial of the n-th left diagonal

T[0, 0] = 1; T[n_, k_] := T[n, k] = Which[k == 0, 1, k == n, T[n, n - 1] + 1, True, T[n, k - 1] + T[n - 1, k]]; Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Michael De Vlieger, Feb 27 2017 *)

T(n,k)=if(k==0,return(1));if(k==n,return(T(n,n-1)+1));T(n,k-1)+T(n-1,k)
for(n=0,10,for(k=0,n,print1(T(n,k),", "))) \\ Derek Orr, Feb 28 2017

def sideTriangleAt(a,b):
    if(b==0): return 1
    elif(b==a): return sideTriangleAt(a,b-1)+1
    else: return sideTriangleAt(a,b-1)+sideTriangleAt(a-1,b)
def sideTriangle(size):
    li=[]
    for c in range(size):
        for d in range(c+1):
            if(d==0): li.append([1])
            elif(d==c): li[c].append(li[c][d-1]+1)
            else: li[c].append(li[c][d-1]+li[c-1][d])
    return li
trig=sideTriangle(125)
for c in range(len(trig)):
    print(str(trig[c])[1:-1].replace(",",""))

cp's OEIS Frontend

A279557 Number of length n inversion sequences avoiding the patterns 110, 120, and 021.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A323224 A(n, k) = [x^k] C^n*x/(1 - x) where C = 2/(1 + sqrt(1 - 4*x)), square array read by ascending antidiagonals with n >= 0 and k >= 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A118964 Triangle read by rows: T(n,k) is the number of Grand Dyck paths of semilength n that have k double rises above the x-axis (n >= 1, k >= 0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A112307 Triangle read by rows: T(n,k) is number of Dyck paths of semilength n with height of second peak equal to k (n>=1; 0<=k<=n-1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

A114276 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having length of second ascent equal to k (0<=k<=n-1).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

A127156 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n starting with exactly k consecutive pyramids. A pyramid in a Dyck path is a factor of the form U^j D^j (j>0), starting at the x-axis. Here U=(1,1) and D=(1,-1). This definition differs from the one in A091866.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Formula

A283054 Triangle read by rows: T(n,k) = T(n,k-1) + T(n-1,k), T(n,0)=1, T(n,n) = T(n,n-1) + 1.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

PARI

SageMath

A323224 A(n, k) = [x^k] C^nx/(1 - x) where C = 2/(1 + sqrt(1 - 4x)), square array read by ascending antidiagonals with n >= 0 and k >= 0.