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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A203717 A Catalan triangle by rows. 4
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.

T(2n,n) gives A291662.

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

License Agreements, Terms of Use, Privacy Policy .

Last modified September 21 20:22 EDT 2017. Contains 292325 sequences.