cp's OEIS Frontend

A246188 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k occurrences of the string ududu, where u=(1,1), d=(1,-1).

%I A246188 #24 Sep 23 2022 13:52:30
%S A246188 1,1,2,4,1,11,2,1,31,8,2,1,92,28,9,2,1,283,99,34,10,2,1,893,354,129,
%T A246188 40,11,2,1,2875,1273,492,161,46,12,2,1,9407,4598,1882,646,195,52,13,2,
%U A246188 1,31189,16679,7199,2597,816,231,58,14,2,1,104555,60712,27570,10400,3422,1002,269,64,15,2,1
%N A246188 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having k occurrences of the string ududu, where u=(1,1), d=(1,-1).
%C A246188 Row n contains n-1 entries (n>=2).
%C A246188 Sum of entries in row n is the Catalan number A000108(n).
%C A246188 Sum(k*T(n,k), k>=0) = A001791(n-2) (n>=2).
%C A246188 T(21,k) = A243752(21,k), T(n,0) = A243753(n,21) = A247333(n). - _Alois P. Heinz_, Sep 13 2014
%H A246188 Alois P. Heinz, <a href="/A246188/b246188.txt">Rows n = 0..150, flattened</a>
%H A246188 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.
%F A246188 G.f.:  C(z*(1-t*z-z^2+t*z^2)/(1-t*z-z^3+t*z^3)), where C(u) = (1-sqrt(1-4*u))/(2*u) is the Catalan function. See Corollary 2.2 in the Mansour reference.
%e A246188 Row 4 is 11, 2, 1; indeed in the 14 Dyck paths of semilength 4 ududu occurs only once in ududuudd, once in uudududd, and twice in udududud.
%e A246188 Triangle starts:
%e A246188    1;
%e A246188    1;
%e A246188    2;
%e A246188    4, 1;
%e A246188   11, 2, 1;
%e A246188   31, 8, 2, 1;
%e A246188   ...
%p A246188 C := proc (u) options operator, arrow: (1/2-(1/2)*sqrt(1-4*u))/u end proc: G := C(z*(1-t*z-z^2+t*z^2)/(1-t*z-z^3+t*z^3)): Gser := simplify(series(G, z = 0, 20)): T := proc (n, k) options operator, arrow: coeff(coeff(Gser, z, n), t, k) end proc: 1; 1; for n from 2 to 12 do seq(T(n, k), k = 0 .. n-2) end do; # yields sequence in triangular form
%p A246188 # second Maple program:
%p A246188 b:= proc(x, y, t) option remember; `if`(y<0 or y>x, 0,
%p A246188      `if`(x=0, 1, expand(b(x-1, y+1, [2, 2, 4, 2, 4][t])*
%p A246188      `if`(t=5, z, 1) +b(x-1, y-1, [1, 3, 1, 5, 1][t]))))
%p A246188     end:
%p A246188 T:= n->(p->seq(coeff(p, z, i), i=0..degree(p)))(b(2*n, 0, 1)):
%p A246188 seq(T(n), n=0..15);  # _Alois P. Heinz_, Sep 10 2014
%t A246188 b[x_, y_, t_] := b[x, y, t] = If[y<0 || y>x, 0, If[x == 0, 1, Expand[b[x-1, y+1, {2, 2, 4, 2, 4}[[t]] ]*If[t == 5, z, 1] + b[x-1, y-1, {1, 3, 1, 5, 1}[[t]] ]]]]; T[n_] := Function[{p}, Table[Coefficient[p, z, i], {i, 0, Exponent[p, z]}]][b[2*n, 0, 1]];Table[T[n], {n, 0, 15}] // Flatten (* _Jean-François Alcover_, May 27 2015, after _Alois P. Heinz_ *)
%Y A246188 Cf. A000108, A001791, A243752, A243753, A247333.
%K A246188 nonn,tabf
%O A246188 0,3
%A A246188 _Emeric Deutsch_, Sep 10 2014