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),...
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
KEYWORD
nonn,tabl
AUTHOR
Gary W. Adamson, Jan 04 2012
STATUS
approved