|
| |
|
|
A065600
|
|
Triangle T(n,k) giving number of Dyck paths of length 2n with exactly k hills (0 <= k <= n).
|
|
13
|
|
|
|
1, 0, 1, 1, 0, 1, 2, 2, 0, 1, 6, 4, 3, 0, 1, 18, 13, 6, 4, 0, 1, 57, 40, 21, 8, 5, 0, 1, 186, 130, 66, 30, 10, 6, 0, 1, 622, 432, 220, 96, 40, 12, 7, 0, 1, 2120, 1466, 744, 328, 130, 51, 14, 8, 0, 1, 7338, 5056, 2562, 1128, 455, 168, 63, 16, 9, 0, 1, 25724, 17672, 8942, 3941, 1590, 602, 210, 76, 18, 10, 0, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,7
|
|
|
COMMENTS
|
T(n,k) is the number of Łukasiewicz paths of length n having k level steps (i.e., (1,0)) on the x-axis. 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) (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, 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, 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, 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, Sep 06 2007
Inverse of Riordan array ((1-2x)/(1-x)^2,x(1-2x)/(1-x)^2); see A124394. - Paul Barry, Jan 27 2009
T(n,k) is the number of ordered, unlabeled, rooted trees with n+1 nodes that have exactly k subtrees of size 1. A subtree of size 1 is a subtree attached to the root that consists of only a single node. Cf. A000957 (column 1). - Geoffrey Critzer, Sep 16 2013
|
|
|
LINKS
|
|
|
|
FORMULA
|
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, 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). - Paul Barry, Jan 27 2009
G.f.: ((1-sqrt(1-4*x))/(3-sqrt(1-4*x)))^k = Sum_{n>=k} T(n+1,k+1)*x^n, where T(n,k) = (Sum_{i=0..n-k} (-1)^i*(k+i+1)*binomial(k+i,i)*binomial(2*n-k-i,n))/(n+1). - Vladimir Kruchinin, Dec 20 2011
T(n,k) = T(n-1,k-1) + Sum_{i>=0} T(n-1,k+1+i)*2^i. - Philippe Deléham, Feb 23 2012
G.f.: 2 / (1 + 2*x + (1 - 4*x)^(1/2) - 2*x*y). - Michael Somos, Jun 01 2016
|
|
|
EXAMPLE
|
Triangle begins:
1;
0, 1;
1, 0, 1;
2, 2, 0, 1;
6, 4, 3, 0, 1;
18, 13, 6, 4, 0, 1;
57, 40, 21, 8, 5, 0, 1; (End)
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).
|
|
|
MAPLE
|
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:
# second Maple program:
b:= proc(x, y, t) option remember; expand(`if`(x=0, 1,
`if`(y>0, b(x-1, y-1, 0)*`if`(t*y=1, z, 1), 0)+
`if`(y<x-1, b(x-1, y+1, 1), 0)))
end:
T:= n-> (p-> seq(coeff(p, z, i), i=0..n))(b(n+n, 0$2)):
# Uses function PMatrix from A357368. Adds a row above and a column to the left.
|
|
|
MATHEMATICA
|
t[n_, k_] := If[ k<n , Sum[i*Binomial[k+i, i]*Binomial[2*n-2*k-2*i, n-k]/(n-k-i), {i, 0, Floor[(n-k)/2]}] , If[ k == n, 1, 0]]; Flatten[ Table[t[n, k], {n, 0, 11}, {k, 0, n}]] (* Jean-François Alcover, Dec 14 2011, after Maple *)
nn=10; g=(1-(1-4x)^(1/2))/2; CoefficientList[Series[x/(1-(g-x+y x)), {x, 0, nn}], {x, y}]//Grid (* Geoffrey Critzer, Sep 16 2013 *)
T[ n_, k_] := If[ k < 0 || k > n, 0, Coefficient[ SeriesCoefficient[ Series[ 2 / (1 + 2*x + Sqrt[1 - 4*x] - 2*x*y), {x, 0, n}], {x, 0, n}], y, k]]; (* Michael Somos, Jun 01 2016 *)
|
|
|
PROG
|
(PARI) {T(n, k) = if( k<0 || k>n, 0, polcoeff( polcoeff( 2 / (1 + 2*x + (1 - 4*x)^(1/2) - 2*x*y) + x * O(x^n), n), k))}; /* Michael Somos, Jun 01 2016 */
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Mar 29 2003
|
|
|
STATUS
|
approved
|
| |
|
|
