login
Triangle read by rows: T(n,k) is number of Dyck n-paths with k UUDDs, 0 <= k <= n/2.
2

%I #38 Jan 31 2019 19:35:19

%S 1,1,1,1,2,3,5,8,1,13,23,6,35,69,27,1,97,212,110,10,275,662,426,66,1,

%T 794,2091,1602,360,15,2327,6661,5912,1760,135,1,6905,21359,21534,8022,

%U 945,21,20705,68850,77685,34840,5685,246,1,62642,222892,278192,146092

%N Triangle read by rows: T(n,k) is number of Dyck n-paths with k UUDDs, 0 <= k <= n/2.

%C T(n,k) is the number of Łukasiewicz paths of length n having k peaks. A Łukasiewicz path of length n is a path in the first quadrant from (0,0) to (n,0) using rise steps (1,k) for any positive integer k, level steps (1,0) and fall steps (1,-1). Example: T(3,1)=3 because we have HUD, UDH and U(2)DD, where H=(1,0), U(1,1), U(2)=(1,2) and D=(1,-1). (see R. P. Stanley reference). - _Emeric Deutsch_, Jan 06 2005

%D R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, p. 223, Exercise 6.19w; the integers are the slopes of the steps. - _Emeric Deutsch_, Jan 06 2005

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

%H Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL21/Barnabei/barnabei5.html">Motzkin and Catalan Tunnel Polynomials</a>, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.

%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. - From _N. J. A. Sloane_, May 05 2012

%H <a href="/index/Lu#Lukasiewicz">Index entries for sequences related to Łukasiewicz</a>

%F G.f.: (1 + z^2 - t*z^2 - (-4*z + (-1 - z^2 + t*z^2)^2)^(1/2))/(2*z) = Sum_{n>=0, 0<=k<=n/2} T(n, k)z^n*t^k and it satisfies G = 1 + G^2*z + G*(-z^2 + t*z^2).

%F T(n,k) = Sum_{j=0..floor(n/2)-k} (-1)^j * binomial(n-(j+k), j+k) * binomial(2n-3(j+k), n-(j+k)-1) * binomial(j+k, k)/(n-(j+k)). - I. Tasoulas (jtas(AT)unipi.gr), Feb 19 2006

%e Table begins

%e \ k 0, 1, 2, ...

%e n

%e 0 | 1;

%e 1 | 1;

%e 2 | 1, 1;

%e 3 | 2, 3;

%e 4 | 5, 8, 1;

%e 5 | 13, 23, 6;

%e 6 | 35, 69, 27, 1;

%e 7 | 97, 212, 110, 10;

%e 8 |275, 662, 426, 66, 1;

%e T(3,1) = 3 because each of UUUDDD, UDUUDD, UUDDUD has one UUDD.

%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, 3, 3, 2][t])

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

%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 10 2014

%t T[n_, k_] := Binomial[n-k, k] Binomial[2n-3k, n-k-1] HypergeometricPFQ[{k -n/2-1/2, k-n/2, k-n/2, k-n/2+1/2}, {k-2n/3, k-2n/3+1/3, k-2n/3+2/3}, 16/27]/(n-k); T[0, 0] = 1; Flatten[Table[T[n, k], {n, 0, 15}, {k, 0, n/2}]] (* _Jean-François Alcover_, Dec 21 2016, after 2nd formula *)

%Y Column k=0 is A025242 (apart from first term).

%Y Cf. A243752.

%K nonn,tabf

%O 0,5

%A _David Callan_, Oct 24 2004