A132890 -id:A132890 - cp's OEIS frontend

A291883 Number T(n,k) of symmetrically unique Dyck paths of semilength n and height k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 5, 3, 1, 0, 1, 9, 11, 4, 1, 0, 1, 19, 31, 19, 5, 1, 0, 1, 35, 91, 69, 29, 6, 1, 0, 1, 71, 250, 252, 127, 41, 7, 1, 0, 1, 135, 690, 855, 540, 209, 55, 8, 1, 0, 1, 271, 1863, 2867, 2117, 1005, 319, 71, 9, 1, 0, 1, 527, 5017, 9339, 8063, 4411, 1705, 461, 89, 10, 1

Offset: 0

Alois P. Heinz, Sep 05 2017

			: T(4,2) = 5:       /\      /\        /\/\    /\  /\    /\/\/\
:              /\/\/  \  /\/  \/\  /\/    \  /  \/  \  /      \
:
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,   1;
  0, 1,   2,   1;
  0, 1,   5,   3,   1;
  0, 1,   9,  11,   4,   1;
  0, 1,  19,  31,  19,   5,   1;
  0, 1,  35,  91,  69,  29,   6,  1;
  0, 1,  71, 250, 252, 127,  41,  7, 1;
  0, 1, 135, 690, 855, 540, 209, 55, 8, 1;
  ...

Alois P. Heinz, Rows n = 0..140, flattened

Columns k=0-10 give: A000007, A057427, A056326, A291887, A291888, A291889, A291890, A291891, A291892, A291893, A291894.
Main and first two lower diagonals give A000012, A001477, A028387(n-1) for n>0.
Row sums give A007123(n+1).
T(2n,n) give A291885.
Cf. A080936, A132890, A291886.

b:= proc(x, y, k) option remember; `if`(x=0, z^k, `if`(y0, b(x-1, y-1, k), 0))
    end:
g:= proc(x, y, k) option remember; `if`(x=0, z^k, `if`(y>0,
      g(x-2, y-1, k), 0)+ g(x-2, y+1, max(y+1, k)))
    end:
T:= n-> (p-> seq(coeff(p, z, i)/2, i=0..n))(b(2*n, 0$2)+g(2*n, 0$2)):
seq(T(n), n=0..14);

b[x_, y_, k_] := b[x, y, k] = If[x == 0, z^k, If[y < x - 1, b[x - 1, y + 1, Max[y + 1, k]], 0] + If[y > 0, b[x - 1, y - 1, k], 0]];
g[x_, y_, k_] := g[x, y, k] = If[x == 0, z^k, If[y > 0, g[x - 2, y - 1, k], 0] + g[x - 2, y + 1, Max[y + 1, k]]];
T[n_] := Function[p, Table[Coefficient[p, z, i]/2, {i, 0, n}]][b[2*n, 0, 0] + g[2*n, 0, 0]];
Table[T[n], {n, 0, 14}] // Flatten (* Jean-François Alcover, Jun 03 2018, from Maple *)

from sympy.core.cache import cacheit
from sympy import Poly, Symbol, flatten
z=Symbol('z')
@cacheit
def b(x, y, k): return z**k if x==0 else (b(x - 1, y + 1, max(y + 1, k)) if y0 else 0)
@cacheit
def g(x, y, k): return z**k if x==0 else (g(x - 2, y - 1, k) if y>0 else 0) + g(x - 2, y + 1, max(y + 1, k))
def T(n): return 1 if n==0 else [i//2 for i in Poly(b(2*n, 0, 0) + g(2*n, 0, 0)).all_coeffs()[::-1]]
print(flatten(map(T, range(15)))) # Indranil Ghosh, Sep 06 2017

T(n,k) = (A080936(n,k) + A132890(n,k))/2.

Sum_{k=1..n} k * T(n,k) = A291886(n).

A132891 Sum of the heights of all left factors of Dyck paths of length n.

Original entry on oeis.org

1, 3, 6, 14, 28, 61, 121, 257, 508, 1065, 2103, 4372, 8634, 17842, 35254, 72524, 143396, 293968, 581630, 1189102, 2354168, 4802331, 9512984, 19370764, 38391332, 78056544, 154773135, 314281350, 623427154, 1264546021, 2509378855, 5085153822, 10094528146

Offset: 1

Emeric Deutsch, Sep 08 2007

nonn

See A132890 for the statistic "height" on left factors of Dyck paths.

			a(4)=14 because the six left factors of Dyck paths of length 4 are UDUD, UDUU, UUDD, UUDU, UUUD and UUUU, having heights 1, 2, 2, 2, 3 and 4, respectively.

Alois P. Heinz, Table of n, a(n) for n = 1..700
Toufik Mansour and Gokhan Yilidirim, Longest increasing subsequences in involutions avoiding patterns of length three, Turkish Journal of Mathematics (2019), Section 2.2.

Cf. A132890.

v := ((1-sqrt(1-4*z^2))*1/2)/z: g := proc (k) options operator, arrow: v^k*(1+v)*(1+v^2)/((1+v^(k+1))*(1+v^(k+2))) end proc: T := proc (n, k) options operator, arrow; coeff(series(g(k), z = 0, 70), z, n) end proc: seq(add(k*T(n, k), k = 1 .. n), n = 1 .. 30);

b[x_, y_, k_] := b[x, y, k] = If[x == 0, z^k, If[y > 0, b[x - 2, y - 1, k], 0] + b[x - 2, y + 1, Max[y + 1, k]]];
T[n_] := Table[Coefficient[b[2n, 0, 0], z, i], {i, 1, n}];
a[n_] := T[n].Range[n];
Array[a, 33] (* Jean-François Alcover, Nov 10 2020, after Alois P. Heinz in A132890 *)

a(n) = Sum_{k=1..n} k * A132890(n,k).

cp's OEIS Frontend

A291883 Number T(n,k) of symmetrically unique Dyck paths of semilength n and height k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula