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!)
A101974 Triangle read by rows: number of Dyck paths of semilength n with k peaks before the first return (1<= k <n). 1
1, 2, 4, 1, 9, 4, 1, 23, 11, 7, 1, 65, 27, 28, 11, 1, 197, 66, 87, 62, 16, 1, 626, 170, 239, 250, 122, 22, 1, 2056, 471, 627, 829, 630, 219, 29, 1, 6918, 1398, 1656, 2448, 2553, 1419, 366, 37, 1, 23714, 4381, 4554, 6803, 8813, 6979, 2917, 578, 46, 1, 82500, 14282 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

REFERENCES

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

LINKS

Table of n, a(n) for n=1..58.

FORMULA

T(n, 1)=sum(c(i), i=0..n-1), T(n, k)=sum(c(j)*binomial(n-1-j, k-1)*binomial(n-1-j, k)/(n-1-j), j=0..n-2) for k>1, where c(i)=binomial(2i, i)/(i+1) (i=0, 1, ...) are the Catalan numbers (A000108);

G.f.=1+tzC(z)[1+r(t, z)], where C(z)=1+zC(z)^2 is the Catalan function and r(t, z)=z[1+r(t, z)][1+tr(t, z)] is the Narayana function.

EXAMPLE

T(4,2)=4 because we have U(UD)(UD)D|UD, U(UD)U(UD)DD|, UU(UD)D(UD)D| and

UU(UD)(UD)DD|, where U=(1,1), D=(1,-1) (the peaks before the first return | are shown between parentheses).

     1

       2

     4      1

     9      4      1

    23     11      7      1

    65     27     28     11      1

   197     66     87     62     16      1

   626    170    239    250    122     22      1

  2056    471    627    829    630    219     29      1

  6918   1398   1656   2448   2553   1419    366     37      1

23714   4381   4554   6803   8813   6979   2917    578     46      1

82500  14282  13231  18571  27362  28364  17206   5567    872     56      1

MAPLE

c:=n->binomial(2*n, n)/(n+1):

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

T(1, 1);

for n from 1 to 12 do seq(T(n, k), k=1..n-1) od; # yields the sequence in triangular form

CROSSREFS

Cf. A000108 (row sums), A014137 (column k=1), A014151 (column k=2), A101975.

Sequence in context: A321461 A092107 A114489 * A097607 A132893 A273896

Adjacent sequences:  A101971 A101972 A101973 * A101975 A101976 A101977

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Dec 22 2004

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 August 3 22:03 EDT 2021. Contains 346441 sequences. (Running on oeis4.)