OFFSET
1,4
COMMENTS
Number of ordered trees with n edges having k leaves at even height. Row sums are the Catalan numbers (A000108). T(n,0)=A001006(n-1) (the Motzkin numbers). Sum_{k=0..n-1} k*T(n,k) = binomial(2n-2, n-2) = A001791(n-1). Mirror image of A091187.
T(n,k) is the number of Dyck paths of semilength n and having k dud's (here u=(1,1) and d=(1,-1)). Example: T(4,2)=3 because we have uud(du[d)ud], uu(dud)(dud) and uu(du[d)ud]d (the dud's are shown between parentheses).
T(n,k) is the number of Dyck paths of semilength n and containing exactly k double rises whose matching down steps form a doublefall. Example: UUUDUDDD has 2 double rises but only the first has matching Ds - the path's last 2 steps - forming a doublefall. (Travel horizontally east from an up step to encounter its matching down step.) - David Callan, Jul 15 2004
T(n,k) is the number of ordered trees on n edges containing k edges of outdegree 1. (The outdegree of an edge is the outdegree of its child vertex. Thus edges of outdegree 1 correspond to non-root vertices of outdegree 1.) T(3,2)=2 because
/\.../\.
|.....|.
each have one edge of outdegree 1. - David Callan, Oct 25 2004
Exponential Riordan array [exp(x)*Bessel_I(1,2x)/x, x]. - Paul Barry, Mar 09 2010
T(n, k) is the number of Dyck paths of semilength n and having k udu's (here u=(1,1) and d=(1,-1)). Note that reversing a path swaps u and d, thus udu becomes dud and vice versa. - Michael Somos, Feb 26 2020
LINKS
Alois P. Heinz, Rows n = 1..200, flattened
J. L. Baril and S. Kirgizov, The pure descent statistic on permutations, Preprint, 2016. See Table 2.
David Callan, Bijections for Dyck paths with all peak heights of the same parity, arXiv:1702.06150 [math.CO], 2017.
M. Dziemianczuk, Enumerations of plane trees with multiple edges and Raney lattice paths, Discrete Mathematics 337 (2014): 9-24.
Sergi Elizalde, Johnny Rivera Jr., and Yan Zhuang, Counting pattern-avoiding permutations by big descents, arXiv:2408.15111 [math.CO], 2024. See p. 11.
A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
Yidong Sun, The statistic "number of udu's" in Dyck paths, Discrete Math., 287 (2004), 177-186.
FORMULA
T(n, k) = binomial(n-1, k)*(Sum_{j=0..ceiling((n-k)/2)} binomial(n-k, j)*binomial(n-k-j, j-1))/(n-k) for 0 <= k < n; T(n, k)=0 for k >= n.
G.f.: G = G(t, z) satisfies z*G^2 - (1 + z - t*z)*G + 1 + z - t*z = 0.
T(n, k) = M(n-k-1)*binomial(n-1, k), where M(n) = A001006(n) are the Motzkin numbers.
T(n+1, k+1) = n*T(n, k)/(k+1). - David Callan, Dec 09 2004
G.f.: 1/(1-x-xy-x^2/(1-x-xy-x^2/(1-x-xy-x^2/(1-x-xy-x^2/(1-... (continued fraction). - Paul Barry, Aug 03 2009
E.g.f.: exp(x+xy)*Bessel_I(1,2x)/x. - Paul Barry, Mar 10 2010
EXAMPLE
T(4,1)=6 because we have u(ud)dudud, udu(ud)dud, ududu(ud)d, uuudd(ud)d, u(ud)uuddd and uuu(ud)ddd (here u=(1,1), d=(1,-1) and the peaks at even height are shown between parentheses).
Triangle begins:
1;
1, 1;
2, 2, 1;
4, 6, 3, 1;
9, 16, 12, 4, 1;
21, 45, 40, 20, 5, 1;
51, 126, 135, 80, 30, 6, 1;
127, 357, 441, 315, 140, 42, 7, 1;
323, 1016, 1428, 1176, 630, 224, 56, 8, 1;
835, 2907, 4572, 4284, 2646, 1134, 336, 72, 9, 1;
...
MAPLE
T := proc(n, k) if k<n then binomial(n-1, k)*sum(binomial(n-k, j)*binomial(n-k-j, j-1), j=0..ceil((n-k)/2))/(n-k) else 0 fi end: seq(seq(T(n, k), k=0..n-1), n=1..11);
# second Maple program:
b:= proc(x, y, t) option remember; expand(`if`(x=0, 1,
`if`(y>0, b(x-1, y-1, 0)*z^irem(t*y+t, 2), 0)+
`if`(y<x-1, b(x-1, y+1, 1), 0)))
end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0$2)):
seq(T(n), n=1..16); # Alois P. Heinz, May 12 2017
MATHEMATICA
(* m = MotzkinNumber *) m[0] = 1; m[n_] := m[n] = m[n - 1] + Sum[m[k]*m[n - 2 - k], {k, 0, n - 2}]; t[n_, n_] = 1; t[n_, k_] := m[n - k]*Binomial[n - 1, k - 1]; Table[t[n, k], {n, 1, 11}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 10 2013 *)
PROG
(PARI) {T(n, k) = my(y, c, w); if( k<0 || k>=n, 0, w = vector(n); forvec(v=vector(2*n, k, [0, 1]), c=y=0; for(k=1, 2*n, if( 0>(y += (-1)^v[k]), break)); if( y, next); for(i=1, 2*n-2, c += ([0, 1, 0] == v[i..i+2])); w[c+1]++); w[k+1])}; /* Michael Somos, Feb 26 2020 */
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Mar 10 2004
STATUS
approved