A191312 Triangle read by rows: T(n,k) is the number of dispersed Dyck paths (i.e., Motzkin paths with no (1,0) steps at positive heights) of length n having abscissa of the first return to the horizontal axis equal to k (assumed to be 0 if there are no such returns).
1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 2, 1, 2, 1, 0, 3, 2, 2, 2, 1, 0, 6, 3, 4, 2, 4, 1, 0, 10, 6, 6, 4, 4, 4, 1, 0, 20, 10, 12, 6, 8, 4, 9, 1, 0, 35, 20, 20, 12, 12, 8, 9, 9, 1, 0, 70, 35, 40, 20, 24, 12, 18, 9, 23, 1, 0, 126, 70, 70, 40, 40, 24, 27, 18, 23, 23, 1, 0, 252, 126, 140, 70, 80, 40, 54, 27, 46, 23, 65
Offset: 0
Examples
T(5,3)=2 because we have HUDHH and HUDUD, where U=(1,1), D=(1,-1), H=(1,0). Triangle starts: 1; 1, 0; 1, 0, 1; 1, 0, 1, 1; 1, 0, 2, 1, 2; 1, 0, 3, 2, 2, 2; 1, 0, 6, 3, 4, 2, 4;
Programs
-
Maple
c := proc (j) options operator, arrow: binomial(2*j, j)/(j+1) end proc: T := proc (n, k) if n < k then 0 elif k = 0 then 1 elif k = 1 then 0 else binomial(n-k, floor((1/2)*n-(1/2)*k))*(sum(c(j), j = 0 .. floor((1/2)*k)-1)) end if end proc: for n from 0 to 12 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form G := (1-t*z+t^2*z^2*g*C-t^2*z^3*g*C)/((1-z)*(1-t*z)): g := 2/(1-2*z+sqrt(1-4*z^2)): C := ((1-sqrt(1-4*t^2*z^2))*1/2)/(t^2*z^2): Gser := simplify(series(G, z = 0, 15)): for n from 0 to 12 do P[n] := sort(coeff(Gser, z, n)) end do: for n from 0 to 12 do seq(coeff(P[n], t, k), k = 0 .. n) end do; # yields sequence in triangular form
-
Mathematica
c[j_] := Binomial[2j, j]/(j+1); T[n_, k_] := Which[n < k, 0, k == 0, 1, k == 1, 0, True, Binomial[n-k, Floor[(n-k)/2]]*(Sum[c[j], {j, 0, Floor[k/2]-1}])]; Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 22 2024, after first Maple program *)
Formula
T(n,0)=1; T(n,1)=0;
T(n,k) = binomial(n-k, floor((n-k)/2))*Sum_{j=0..floor(k/2)-1} c(j), where 2<=k<=n and c(j) = binomial(2*j,j)/(j+1) are the Catalan numbers.
G.f.: G(t,z) = 1/(1-z)+(1-sqrt(1-4*t^2*z^2))/((1-t*z)*(1-2*z+sqrt(1-4*z^2))).
For k>=1, g.f. of column 2k is b_{k-1}*z^{2k}*g and of column 2k+1 is b_{k-1}*z^{2*k+1}*g, where g = 2/(1-2*z+sqrt(1-4*z^2)) and b(k) = Sum_{j=0..k-1} c(j) with c(j) = binomial(2*j,j)/(j+1) = A000108(j) (the Catalan numbers).
Comments