cp's OEIS Frontend

A116424 Triangle read by rows: T(n,k) = the number of Dyck paths of semilength n with k UDUU's, 0 <= k <= floor((n-1)/2).

%I A116424 #32 Apr 11 2024 10:50:04
%S A116424 1,1,2,4,1,9,5,22,19,1,57,66,9,154,221,53,1,429,729,258,14,1223,2391,
%T A116424 1131,116,1,3550,7829,4652,745,20,10455,25638,18357,4115,220,1,31160,
%U A116424 84033,70404,20598,1790,27,93802,275765,264563,96286,12104,379,1,284789
%N A116424 Triangle read by rows: T(n,k) = the number of Dyck paths of semilength n with k UDUU's, 0 <= k <= floor((n-1)/2).
%C A116424 T(n,k) also gives the number of Dyck paths of semilength n with k UUDU's.
%C A116424 Column k=0 gives A105633(n-1) for n > 0.
%H A116424 Alois P. Heinz, <a href="/A116424/b116424.txt">Rows n = 0..200, flattened</a>
%H A116424 Jean-Luc Baril, Pamela E. Harris, Kimberly J. Harry, Matt McClinton, and José L. Ramírez, <a href="https://arxiv.org/abs/2404.05672">Enumerating runs, valleys, and peaks in Catalan words</a>, arXiv:2404.05672 [math.CO], 2024. See p. 18.
%H A116424 Toufik Mansour, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Mansour/mansour86.html">Statistics on Dyck Paths</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.5.
%H A116424 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.
%F A116424 T(n,k) = Sum_{i=k..floor((n-1)/2)} (-1)^(i+k) * binomial(i,k) * binomial(n-i,i) * binomial(2*n-3*i, n - 2*i -1)/(n-i), n >= 1.
%F A116424 G.f. G = G(t,z) satisfies G = 1 + z^2(1-t)G + z(1-z+tz)G^2.
%e A116424 Triangle begins:
%e A116424 00 :     1;
%e A116424 01 :     1;
%e A116424 02 :     2;
%e A116424 03 :     4,    1;
%e A116424 04 :     9,    5;
%e A116424 05 :    22,   19,    1;
%e A116424 06 :    57,   66,    9;
%e A116424 07 :   154,  221,   53,   1;
%e A116424 08 :   429,  729,  258,  14;
%e A116424 09 :  1223, 2391, 1131, 116,  1;
%e A116424 10 :  3550, 7829, 4652, 745, 20;
%e A116424 ...
%e A116424 T(4,1) = 5 because there exist five Dyck paths of semilength 4 with one occurrence of UDUU : UDUUUDDD, UDUUDUDD, UDUUDDUD, UUDUUDDD, UDUDUUDD.
%p A116424 b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
%p A116424      `if`(x=0, 1, expand(b(x-1, y+1, [2, 2, 4, 2][t])*
%p A116424      `if`(t=4, z, 1) +b(x-1, y-1, [1, 3, 1, 3][t]))))
%p A116424     end:
%p A116424 T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
%p A116424 seq(T(n), n=0..15);  # _Alois P. Heinz_, Jun 02 2014
%t A116424 s = Series[((1 + (t - 1) z^2) - Sqrt[(1 + (t - 1) z^2)^2 - 4*z*(1 - z + z*t)])/(2*z*(1 - z + z*t)), {z, 0, 15}] // CoefficientList[#, z]&;
%t A116424 CoefficientList[#, t]& /@ s // Flatten (* updated by _Jean-François Alcover_, Feb 14 2021 *)
%Y A116424 Cf. A105633, A243752.
%K A116424 nonn,tabf
%O A116424 0,3
%A A116424 I. Tasoulas (jtas(AT)unipi.gr), Feb 15 2006