login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. [From Paul Barry, Jan 27 2009]

Triangle read by rows, product of A033184 and A130595 considered as infinite lower triangular arrays; A065600 = A033184*A130595. [From Philippe Deléham, Dec 07 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

Alois P. Heinz, Rows n = 0..200, flattened

E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, ECO method and hill-free generalized Motzkin paths, Séminaire Lotharingien de Combinatoire, B46b (2001), 14 pp.

Naiomi Cameron, J. E. McLeod, Returns and Hills on Generalized Dyck Paths, Journal of Integer Sequences, Vol. 19, 2016, #16.6.1.

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.

Filippo Disanto, Andrea Frosini and Simone Rinaldi, Renzo Pinzani, The Combinatorics of Convex Permutominoes, Southeast Asian Bulletin of Mathematics (2008) 32: 883-912.

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

FindStat - Combinatorial Statistic Finder, The number of centered tunnels of a Dyck path.

R. Pemantle and M. C. Wilson, Twenty Combinatorial Examples of Asymptotics Derived from Multivariate Generating Functions, SIAM Rev., 50 (2008), no. 2, 199-272. See p. 235

A. Robertson, D. Saracino and D. Zeilberger, Refined restricted permutations, arXiv:math/0203033 [math.CO], 2002.

Index entries for sequences related to Łukasiewicz

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

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)):

seq(T(n), n=0..12);  # Alois P. Heinz, Nov 02 2017

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

First two columns are A000957, A065601.

Sequence in context: A089246 A291684 A105929 * A029583 A011289 A288387

Adjacent sequences:  A065597 A065598 A065599 * A065601 A065602 A065603

KEYWORD

nonn,tabl,easy,nice

AUTHOR

N. J. A. Sloane, Dec 02 2001

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 24 05:48 EST 2018. Contains 299597 sequences. (Running on oeis4.)