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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A108767 Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(1,1), d=(1,-2) and have k peaks (i.e., ud's). 6
1, 1, 2, 1, 6, 5, 1, 12, 28, 14, 1, 20, 90, 120, 42, 1, 30, 220, 550, 495, 132, 1, 42, 455, 1820, 3003, 2002, 429, 1, 56, 840, 4900, 12740, 15288, 8008, 1430, 1, 72, 1428, 11424, 42840, 79968, 74256, 31824, 4862, 1, 90, 2280, 23940, 122094, 325584, 465120 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

Row sums yield A001764.

From Peter Bala, Sep 16 2012: (Start)

The number of 2-Dyck paths of order n with k peaks (Cigler). A 2-Dyck path of order n is a lattice path from (0,0) to (2*n,n) with steps (0,1) (North) and (1,0) (East) that never goes below the diagonal {2*i,i} 0 <= i <= n. A peak is a consecutive North East pair.

Row reverse of A120986. Described in A173020 as generalized Runyon numbers R_{n,k}^(2).

(End)

LINKS

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Frédéric Chapoton and Philippe Nadeau, Combinatorics of the categories of noncrossing partitions, Séminaire Lotharingien de Combinatoire 78B (2017), Article #37.

J. Cigler, Some remarks on Catalan families, European J. Combin., 8(3): 261-267.

J.-C. Novelli, J.-Y. Thibon, Hopf Algebras of m-permutations,(m+1)-ary trees, and m-parking functions, arXiv preprint arXiv:1403.5962 [math.CO], 2014. See Fig. 5.

Chao-Jen Wang, Applications of the Goulden-Jackson cluster method to counting Dyck paths by occurrences of subwords, Thesis, 2011.

FORMULA

T(n,k) = binomial(n, k)*binomial(2*n, k-1)/n.

T(n,n)= A000108(n) (the Catalan numbers).

Sum_{k=1..n} k*T(n,k) = A025174(n).

G.f.: T-1, where T = T(t, z) satisfies T = 1 + z*T^2*(T - 1 + t).

From Peter Bala, Oct 22 2008: (Start)

Define a functional I on formal power series of the form f(x) = 1 + ax + bx^2 + ... by the following iterative process. Define inductively f^(1)(x) = f(x) and f^(n+1)(x) = f(x*f^(n)(x)) for n >= 1. Then set I(f(x)) = lim n -> infinity f^(n)(x) in the x-adic topology on the ring of formal power series; the operator I may also be defined by I(f(x)) := 1/x*series reversion of x/f(x).

The o.g.f. for the array of Narayana numbers A001263 is I(1 + t*x + t*x^2 + t*x^3 + ...) = 1 + t*x + (t + t^2)*x^2 + (t + 3*t^2 + t^3)*x^3 + ... . The o.g.f. for the current array is IoI(1 + t*x + t*x^2 + t*x^3 + ...) = 1 + t*x + (t + 2*t^2)*x^2 + (t + 6*t^2 + 5*t^3)*x^3 + ... . Cf. A132081 and A141618. Alternatively, the o.g.f. of this array can be obtained from a single application of I, namely, form I(1 + t*x^2 + t*x^4 + t*x^6 + ...) = 1 + t*x^2 + (t + 2*t^2)*x^4 + (t + 6*t^2 + 5*t^3)*x^6 + ... and then replace x by sqrt(x). This is a particular case of the general result that forming the n-fold composition I^(n)(f(x)) and then replacing x with x^n produces the same result as I(f(x^n)). (End)

O.g.f. is series reversion with respect to x of x/((1+x)*(1+x*u)^2). Cf. A173020. - Peter Bala, Sep 12 2012

EXAMPLE

T(3,2)=6 because we have uuduuuudd, uuuduuudd, uuuuduudd, uuuudduud, uuuuududd and uuuuuddud.

Triangle starts:

  1;

  1,  2;

  1,  6,   5;

  1, 12,  28,   14;

  1, 20,  90,  120,   42;

  1, 30, 220,  550,  495,  132;

  1, 42, 455, 1820, 3003, 2002, 429;

  ...

MAPLE

T:=(n, k)->binomial(n, k)*binomial(2*n, k-1)/n: for n from 1 to 10 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form

MATHEMATICA

T[n_, k_] := Binomial[n, k]*Binomial[2*n, k - 1]/n;

Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 11 2017, from Maple *)

PROG

(PARI) T(n, k) = binomial(n, k)*binomial(2*n, k-1)/n; \\ Andrew Howroyd, Nov 06 2017

(Python)

from sympy import binomial

def T(n, k): return binomial(n, k)*binomial(2*n, k - 1)//n

for n in range(1, 21): print([T(n, k) for k in range(1, n + 1)]) # Indranil Ghosh, Nov 07 2017

(R)

T <- function(n, k) {

  choose(n, k)*choose(2*n, k - 1)/n

} # Indranil Ghosh, Nov 07 2017

CROSSREFS

Cf. A000108, A001764, A025174, A120986, A173020.

Sequence in context: A145960 A205455 A259332 * A046817 A193817 A227159

Adjacent sequences:  A108764 A108765 A108766 * A108768 A108769 A108770

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Jun 24 2005

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 23 04:57 EST 2018. Contains 299473 sequences. (Running on oeis4.)