A203717 A Catalan triangle by rows.

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

Offset: 1

Author

Gary W. Adamson, Jan 04 2012

Keywords

• nonn
• tabl

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

Examples

			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.
		

Links

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

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.

Programs

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 *)

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

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