A114608 Triangle read by rows: T(n,k) is the number of bicolored Dyck paths of semilength n and having k peaks of the form ud (0 <= k <= n). A bicolored Dyck path is a Dyck path in which each up-step is of two kinds: u and U.

1, 1, 1, 3, 4, 1, 11, 19, 9, 1, 45, 96, 66, 16, 1, 197, 501, 450, 170, 25, 1, 903, 2668, 2955, 1520, 365, 36, 1, 4279, 14407, 18963, 12355, 4165, 693, 49, 1, 20793, 78592, 119812, 94528, 41230, 9856, 1204, 64, 1, 103049, 432073, 748548, 693588, 372078, 117054

Offset

0,4

Comments

Row sums yield A052701. Column 0 yields the little Schroeder numbers (A001003). Sum_{k=0..n} k*T(n,k) = A069720(n).

Triangle T(n,k), 0 <= k <= n, read by rows; given by [1, 2, 1, 2, 1, 2, 1, 2, 1, 2, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Dec 23 2005

Links

Table of n, a(n) for n=0..50.

Paul Barry, Generalized Eulerian Triangles and Some Special Production Matrices, arXiv:1803.10297 [math.CO], 2018.

Formula

T(n,k) = (1/n)*binomial(n,k)*Sum_{j=0..n-k} 2^j*binomial(n, j+1)*binomial(n-k, j) (k <= n-1); T(n, n)=1.

G.f. = G = G(t, z) satisfies G = 1 + z*(G-1+t)*G + z*G^2.

Example

T(3,2)=9 because we have (ud)(ud)Ud, (ud)Ud(ud), Ud(ud)(ud), (ud)u(ud)d,
(ud)U(ud)d, u(ud)d(ud), U(ud)d(ud), u(ud)(ud)d and U(ud)(ud)d (the ud peaks are shown between parentheses).
Triangle starts:
   1;
   1,  1;
   3,  4,  1;
  11, 19,  9,  1;
  45, 96, 66, 16,  1;

Maple

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

Mathematica

T[n_, k_] := If[k <= n-1, (1/n)*Binomial[n, k]*Sum[2^j*Binomial[n, j+1]* Binomial[n-k, j], {j, 0, n-k}], If[k == n, 1, 0]];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 11 2018, from Maple *)

Crossrefs

Cf. A001003, A052701, A069720.

Sequence in context: A138263 A147721 A172094 * A154602 A216154 A325174

Adjacent sequences: A114605 A114606 A114607 * A114609 A114610 A114611

Keyword

nonn,tabl

Author

Emeric Deutsch, Dec 15 2005

Status

approved