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

 

Logo

Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A203717 A Catalan triangle by rows. 7
1, 1, 1, 1, 3, 1, 1, 8, 4, 1, 1, 20, 15, 5, 1, 1, 50, 53, 21, 6, 1, 1, 126, 182, 84, 28, 7, 1, 1, 322, 616, 326, 120, 36, 8, 1, 1, 834, 2070, 1242, 495, 165, 45, 9, 1, 1, 2187, 6930, 4680, 1997, 715, 220, 55, 10, 1, 1, 5797, 23166, 17512, 7942, 3003, 1001, 286, 66, 11, 1 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

Row sums = the Catalan sequence starting with offset 1: (1, 2, 5, 14, 42,...).

T(n,k) is the number of Dyck n-paths whose maximum ascent length is k. - David Scambler, Aug 22 2012

T(n,k) is the number of ordered rooted trees with n non-root nodes and maximal outdegree k. T(4,3) = 4:

.    o      o      o      o

.    |     /|\    /|\    /|\

.    o    o o o  o o o  o o o

.   /|\   |        |        |

.  o o o  o        o        o   - Alois P. Heinz, Jun 29 2014

T(n,k) also is the number of permutations p of [n] such that in 0p the largest up-jump equals k and no down-jump is larger than 1. An up-jump j occurs at position i in p if p_{i} > p_{i-1} and j is the index of p_i in the increasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are larger than p_{i-1}. A down-jump j occurs at position i in p if p_{i} < p_{i-1} and j is the index of p_i in the decreasingly sorted list of those elements in {p_{i}, ..., p_{n}} that are smaller than p_{i-1}. First index in the lists is 1 here. T(4,3) = 4: 1432, 3214, 3241, 3421. - Alois P. Heinz, Aug 29 2017

LINKS

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

FORMULA

Finite differences of antidiagonals of an array in which n-th array row is generated from powers of M, extracting successive upper left terms. M for n-th row of the array is an infinite square production matrix composed of (n+1) diagonals of 1's and the rest zeros. Given the upper left term of the array is (1,1), the diagonals begin at (1,2), (1,1), (2,1), (3,1), (4,1),...

T(n,k) = A288942(n,k) - A288942(n,k-1). - Alois P. Heinz, Sep 01 2017

EXAMPLE

First few rows of the array begin:

1,...1,...1,...1,...1,...;

1,...2,...4,...9,..21,...; = A001006

1,...2,...5,..13,..36,...; = A036765

1,...2,...5,..14,..41,...; = A036766

1,...2,...5,..14,..42,...; = A036767

... Taking finite differences of array terms starting from the top by columns, we obtain row terms of the triangle. First few rows of the triangle are:

1;

1,    1;

1,    3,    1;

1,    8,    4,    1;

1,   20,   15,    5,    1;

1,   50,   53,   21,    6,   1;

1,  126,  182,   84,   28,   7,   1;

1,  322,  616,  326,  120,  36,   8,  1;

1,  834, 2070, 1242,  495, 165,  45,  9,  1;

1, 2187, 6930, 4680, 1997, 715, 220, 55, 10, 1;

...

Example: Row 4 of the triangle = (1, 8, 4, 1) = the finite differences of (1, 9, 13, 14), column 4 of the array. Term (3,4) = 13 of the array is the upper left term of M^4, where M is an infinite square production matrix with four diagonals of 1's starting at (1,2), (1,1), (2,1), and (3,1); with the rest zeros.

MAPLE

b:= proc(n, t, k) option remember; `if`(n=0, 1, `if`(t>0,

      add(b(j-1, k$2)*b(n-j, t-1, k), j=1..n), b(n-1, k$2)))

    end:

T:= (n, k)-> b(n, k-1$2) -`if`(k=1, 0, b(n, k-2$2)):

seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Jun 29 2014

# second Maple program:

b:= proc(u, o, k) option remember; `if`(u+o=0, 1,

      add(b(u-j, o+j-1, k), j=1..min(1, u))+

      add(b(u+j-1, o-j, k), j=1..min(k, o)))

    end:

T:= (n, k)-> b(0, n, k)-`if`(k=0, 0, b(0, n, k-1)):

seq(seq(T(n, k), k=1..n), n=1..14);  # Alois P. Heinz, Aug 28 2017

MATHEMATICA

b[n_, t_, k_] := b[n, t, k] = If[n == 0, 1, If[t > 0, Sum[b[j-1, k, k]*b[n - j, t-1, k], {j, 1, n}], b[n-1, k, k]]]; T[n_, k_] := b[n, k-1, k-1] - If[k == 1, 0, b[n, k-2, k-2]]; Table[T[n, k], {n, 1, 14}, {k, 1, n}] // Flatten (* Jean-Fran├žois Alcover, May 27 2016, after Alois P. Heinz *)

PROG

(Python)

from sympy.core.cache import cacheit

@cacheit

def b(u, o, k): return 1 if u + o==0 else sum([b(u - j, o + j - 1, k) for j in range(1, min(1, u) + 1)]) + sum([b(u + j - 1, o - j, k) for j in range(1, min(k, o) + 1)])

def T(n, k): return b(0, n, k) - (0 if k==0 else b(0, n, k - 1))

for n in range(1, 16): print ([T(n, k) for k in range(1, n + 1)]) # Indranil Ghosh, Aug 30 2017

CROSSREFS

Cf. A000108, A001006, A036765, A036766, A036767, A291680, A288942.

Columns k=1-3 give: A057427, A140662(n-1) for n>1, A303271.

T(2n,n) gives A291662.

T(2n+1,n+1) gives A005809.

T(n,ceiling(n/2)) gives A303259.

Sequence in context: A121461 A273719 A274488 * A143953 A114276 A152879

Adjacent sequences:  A203714 A203715 A203716 * A203718 A203719 A203720

KEYWORD

nonn,tabl

AUTHOR

Gary W. Adamson, Jan 04 2012

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 December 16 00:33 EST 2019. Contains 330013 sequences. (Running on oeis4.)