A116424 - OEIS

%I #32 Apr 11 2024 10:50:04

%S 1,1,2,4,1,9,5,22,19,1,57,66,9,154,221,53,1,429,729,258,14,1223,2391,

%T 1131,116,1,3550,7829,4652,745,20,10455,25638,18357,4115,220,1,31160,

%U 84033,70404,20598,1790,27,93802,275765,264563,96286,12104,379,1,284789

%N 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 T(n,k) also gives the number of Dyck paths of semilength n with k UUDU's.

%C Column k=0 gives A105633(n-1) for n > 0.

%H Alois P. Heinz, <a href="/A116424/b116424.txt">Rows n = 0..200, flattened</a>

%H 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 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 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 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 G.f. G = G(t,z) satisfies G = 1 + z^2(1-t)G + z(1-z+tz)G^2.

%e Triangle begins:

%e 00 :     1;

%e 01 :     1;

%e 02 :     2;

%e 03 :     4,    1;

%e 04 :     9,    5;

%e 05 :    22,   19,    1;

%e 06 :    57,   66,    9;

%e 07 :   154,  221,   53,   1;

%e 08 :   429,  729,  258,  14;

%e 09 :  1223, 2391, 1131, 116,  1;

%e 10 :  3550, 7829, 4652, 745, 20;

%e ...

%e T(4,1) = 5 because there exist five Dyck paths of semilength 4 with one occurrence of UDUU : UDUUUDDD, UDUUDUDD, UDUUDDUD, UUDUUDDD, UDUDUUDD.

%p b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,

%p      `if`(x=0, 1, expand(b(x-1, y+1, [2, 2, 4, 2][t])*

%p      `if`(t=4, z, 1) +b(x-1, y-1, [1, 3, 1, 3][t]))))

%p     end:

%p T:= n-> (p-> seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):

%p seq(T(n), n=0..15);  # _Alois P. Heinz_, Jun 02 2014

%t 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 CoefficientList[#, t]& /@ s // Flatten (* updated by _Jean-François Alcover_, Feb 14 2021 *)

%Y Cf. A105633, A243752.

%K nonn,tabf

%O 0,3

%A I. Tasoulas (jtas(AT)unipi.gr), Feb 15 2006