cp's OEIS Frontend

A091869 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k peaks at even height.

%I A091869 #69 Sep 01 2024 10:33:15
%S A091869 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,
%T A091869 127,357,441,315,140,42,7,1,323,1016,1428,1176,630,224,56,8,1,835,
%U A091869 2907,4572,4284,2646,1134,336,72,9,1,2188,8350,14535,15240,10710,5292,1890,480,90,10,1
%N A091869 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k peaks at even height.
%C A091869 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.
%C A091869 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).
%C A091869 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
%C A091869 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
%C A091869   /\.../\.
%C A091869   |.....|.
%C A091869 each have one edge of outdegree 1. - _David Callan_, Oct 25 2004
%C A091869 Exponential Riordan array [exp(x)*Bessel_I(1,2x)/x, x]. - _Paul Barry_, Mar 09 2010
%C A091869 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
%H A091869 Alois P. Heinz, <a href="/A091869/b091869.txt">Rows n = 1..200, flattened</a>
%H A091869 J. L. Baril and S. Kirgizov, <a href="http://jl.baril.u-bourgogne.fr/Stirling.pdf">The pure descent statistic on permutations</a>, Preprint, 2016. See Table 2.
%H A091869 David Callan, <a href="https://arxiv.org/abs/1702.06150">Bijections for Dyck paths with all peak heights of the same parity</a>, arXiv:1702.06150 [math.CO], 2017.
%H A091869 M. Dziemianczuk, <a href="http://dx.doi.org/10.1016/j.disc.2014.07.024">Enumerations of plane trees with multiple edges and Raney lattice paths</a>, Discrete Mathematics 337 (2014): 9-24.
%H A091869 Sergi Elizalde, Johnny Rivera Jr., and Yan Zhuang, <a href="https://arxiv.org/abs/2408.15111">Counting pattern-avoiding permutations by big descents</a>, arXiv:2408.15111 [math.CO], 2024. See p. 11.
%H A091869 A. Sapounakis, I. Tasoulas and P. Tsikouras, <a href="http://dx.doi.org/10.1016/j.disc.2007.03.005">Counting strings in Dyck paths</a>, Discrete Math., 307 (2007), 2909-2924.
%H A091869 Yidong Sun, <a href="http://dx.doi.org/10.1016/j.disc.2004.07.002">The statistic "number of udu's" in Dyck paths</a>, Discrete Math., 287 (2004), 177-186.
%H A091869 Chao-Jen Wang, <a href="http://people.brandeis.edu/~gessel/homepage/students/wangthesis.pdf">Applications of the Goulden-Jackson cluster method to counting Dyck paths by occurrences of subwords</a>.
%F A091869 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.
%F A091869 G.f.: G = G(t, z) satisfies z*G^2 - (1 + z - t*z)*G + 1 + z - t*z = 0.
%F A091869 T(n, k) = M(n-k-1)*binomial(n-1, k), where M(n) = A001006(n) are the Motzkin numbers.
%F A091869 T(n+1, k+1) = n*T(n, k)/(k+1). - _David Callan_, Dec 09 2004
%F A091869 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
%F A091869 E.g.f.: exp(x+xy)*Bessel_I(1,2x)/x. - _Paul Barry_, Mar 10 2010
%e A091869 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).
%e A091869 Triangle begins:
%e A091869     1;
%e A091869     1,    1;
%e A091869     2,    2,    1;
%e A091869     4,    6,    3,    1;
%e A091869     9,   16,   12,    4,    1;
%e A091869    21,   45,   40,   20,    5,    1;
%e A091869    51,  126,  135,   80,   30,    6,   1;
%e A091869   127,  357,  441,  315,  140,   42,   7,  1;
%e A091869   323, 1016, 1428, 1176,  630,  224,  56,  8, 1;
%e A091869   835, 2907, 4572, 4284, 2646, 1134, 336, 72, 9, 1;
%e A091869   ...
%p A091869 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);
%p A091869 # second Maple program:
%p A091869 b:= proc(x, y, t) option remember; expand(`if`(x=0, 1,
%p A091869       `if`(y>0, b(x-1, y-1, 0)*z^irem(t*y+t, 2), 0)+
%p A091869       `if`(y<x-1, b(x-1, y+1, 1), 0)))
%p A091869     end:
%p A091869 T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0$2)):
%p A091869 seq(T(n), n=1..16);  # _Alois P. Heinz_, May 12 2017
%t A091869 (* 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 *)
%o A091869 (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 */
%Y A091869 Cf. A001006, A005717, A102839, A371408, A375253, A375259.
%Y A091869 Cf. A000108, A001791, A091187, A243752.
%Y A091869 T(2n,n) gives A371411.
%K A091869 nonn,tabl
%O A091869 1,4
%A A091869 _Emeric Deutsch_, Mar 10 2004