0,7

T(n,k) is the number of Lukasiewicz paths of length n having k level steps (i.e. (1,0)) on the x-axis. A Lukasiewicz 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) (see 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). Example: T(3,1)=2 because we have HUD and UDH, where H=(1,0), U(1,1) and D=(1,-1). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Jan 06 2005

The summand i*binomial(k+i,i)*binomial(2*n-2*k-2*i,n-k)/(n-k-i) in the Maple formula below counts Dyck n-paths containing k low peaks and k+i returns altogether. For example, with n=3, k=1, i=1, it counts the 2 paths UDUUDD, UUDDUD: each has k=1 low peaks and k+i=2 returns to ground level. - David Callan (callan(AT)stat.wisc.edu), Nov 02 2005

Renewal array for the Fine numbers: Riordan array (f(x)/x,f(x)) where f(x) is the g.f. for A000957. Row sums are the Catalan numbers A000108. - Paul Barry (pbarry(AT)wit.ie), Oct 30 2006, Jan 27 2009

T(n,k) is the number of 321-avoiding permutations of [n] having k fixed points. Example: T(4,2)=3 because we have 1243, 1324 and 2134. T(n,k) is the number of Dyck paths of semilength n having k centered tunnels. Example: T(4,2)=3 because we have UD(U)(U)(D)(D)UD, (U)UD(U)(D)UD(D) and (U)(U)UDUD(D)(D) (the extremities of the centered tunnels are shown between parentheses). - Emeric Deutsch (deutsch(AT)duke.poly.edu), Sep 06 2007

Inverse of Riordan array ((1-2x)/(1-x)^2,x(1-2x)/(1-x)^2). [From Paul Barry (pbarry(AT)wit.ie), Jan 27 2009]

E. Deutsch, Dyck path enumeration, Discrete Math., 204 (1999), 167-202.

E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.

S. Elizalde and I. Pak, Bijections for refined restricted permutations, Journal of Combinatorial Theory Ser. A, 105, 2004, 207-219.

E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, ECO method and hill-free generalized Motzkin paths

A. Robertson, D. Saracino and D. Zeilberger, Refined restricted permutations.

See Maple line.

G.f. (1 - (1 - 4*x)^(1/2))/(x*(3 - y + (1 - 4*x)^(1/2)*(y-1))) = Sum_{n>=0, k>=0} T(n, k)x^n*y^k. - David Callan (callan(AT)stat.wisc.edu), Aug 17 2004

G.f.: 1/(1-xy-x^2/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-.... (continued fraction). [From Paul Barry (pbarry(AT)wit.ie), Jan 27 2009]

1; 0,1; 1,0,1; 2,2,0,1; 6,4,3,0,1; ...

T(4,2)=3 because we have (UD)(UD)UUDD, (UD)UUDD(UD) and UUDD(UD)(UD), where U=(1,1), D=(1,-1) (the hills, i.e. peaks at level 1, are shown between parentheses).

T := proc(n, k) if k<n then sum(i*binomial(k+i, i)*binomial(2*n-2*k-2*i, n-k)/(n-k-i), i=0..floor((n-k)/2)) elif k=n then 1 else 0 fi end:

First two columns are A000957, A065601.

Sequence in context: A102404 A089246 A105929 this_sequence A029583 A011289 A141720

Adjacent sequences: A065597 A065598 A065599 this_sequence A065601 A065602 A065603

nonn,tabl,easy,nice

N. J. A. Sloane (njas(AT)research.att.com), Dec 02 2001

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003