login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A132890 Triangle read by rows: T(n,k) is the number of left factors of Dyck paths of length n that have height k (1 <= k <= n). 3
1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 4, 1, 1, 1, 7, 5, 5, 1, 1, 1, 7, 13, 6, 6, 1, 1, 1, 15, 18, 20, 7, 7, 1, 1, 1, 15, 39, 26, 27, 8, 8, 1, 1, 1, 31, 57, 73, 35, 35, 9, 9, 1, 1, 1, 31, 112, 99, 109, 44, 44, 10, 10, 1, 1, 1, 63, 169, 253, 152, 154, 54, 54, 11, 11, 1, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,8

COMMENTS

Sum of terms in row n = binomial(n, floor(n/2)) = A001405(n).

T(n,2) = A052551(n-2) (n >= 2).

T(n,3) = A005672(n) = Fibonacci(n+1) - 2^floor(n/2).

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

LINKS

Alois P. Heinz, Rows n = 1..141, flattened

Steven R. Finch, How far might we walk at random?, arXiv:1802.04615 [math.HO], 2018.

R. Kemp, On the average depth of a prefix of the Dycklanguage D_1, Discrete Math., 36, 1981, 155-170.

Toufik Mansour, Gokhan Yilidirim, Longest increasing subsequences in involutions avoiding patterns of length three, Turkish Journal of Mathematics (2019), Section 2.2

FORMULA

The g.f. of column k is g(k, z) = v^k*(1+v)*(1+v^2)*/((1+v^(k+1))*(1+v^(k+2))), where v = (1-sqrt(1-4*z^2))/(2*z). (Obtained as the difference G(k,z)-G(k-1,z), where G(k,z) is given in the R. Kemp reference (p. 159).)

EXAMPLE

T(5,3)=4 because we have UDUUU, UUDUU, UUUDD and UUUDU, where U=(1,1) and D=(1,-1).

Triangle starts:

  1;

  1, 1;

  1, 1, 1;

  1, 3, 1, 1;

  1, 3, 4, 1; 1;

  1, 7, 5, 5, 1, 1;

MAPLE

v := ((1-sqrt(1-4*z^2))*1/2)/z: g := proc (k) options operator, arrow: v^k*(1+v)*(1+v^2)/((1+v^(k+1))*(1+v^(k+2))) end proc: T := proc (n, k) options operator, arrow: coeff(series(g(k), z = 0, 50), z, n) end proc: for n from 0 to 12 do seq(T(n, k), k = 1 .. n) end do; # yields sequence in triangular form

# second Maple program:

b:= proc(x, y, k) option remember; `if`(x=0, z^k, `if`(y>0,

      b(x-2, y-1, k), 0)+ b(x-2, y+1, max(y+1, k)))

    end:

T:= n-> (p-> seq(coeff(p, z, i), i=1..n))(b(2*n, 0$2)):

seq(T(n), n=1..16);  # Alois P. Heinz, Sep 05 2017

MATHEMATICA

b[x_, y_, k_] := b[x, y, k] = If[x == 0, z^k, If[y > 0, b[x - 2, y - 1, k], 0] + b[x - 2, y + 1, Max[y + 1, k]]];

T[n_] := Function[p, Table[Coefficient[p, z, i], {i, 1, n}]][b[2n, 0, 0]];

Table[T[n], {n, 1, 16}] // Flatten (* Jean-Fran├žois Alcover, Apr 01 2018, after Alois P. Heinz *)

CROSSREFS

Cf. A001405, A052551, A005672, A132891, A068914.

Sequence in context: A214635 A166030 A191523 * A295295 A069290 A076476

Adjacent sequences:  A132887 A132888 A132889 * A132891 A132892 A132893

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Sep 08 2007

EXTENSIONS

Keyword tabl added by Michel Marcus, Apr 09 2013

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 26 13:40 EDT 2021. Contains 346294 sequences. (Running on oeis4.)