login
A Catalan triangle by rows.
7

%I #45 Nov 17 2020 19:26:16

%S 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,

%T 322,616,326,120,36,8,1,1,834,2070,1242,495,165,45,9,1,1,2187,6930,

%U 4680,1997,715,220,55,10,1,1,5797,23166,17512,7942,3003,1001,286,66,11,1

%N A Catalan triangle by rows.

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

%C T(n,k) is the number of Dyck n-paths whose maximum ascent length is k. - _David Scambler_, Aug 22 2012

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

%C . o o o o

%C . | /|\ /|\ /|\

%C . o o o o o o o o o o

%C . /|\ | | |

%C . o o o o o o - _Alois P. Heinz_, Jun 29 2014

%C 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

%H Alois P. Heinz, <a href="/A203717/b203717.txt">Rows n = 1..141, flattened</a>

%F 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),...

%F T(n,k) = A288942(n,k) - A288942(n,k-1). - _Alois P. Heinz_, Sep 01 2017

%e First few rows of the array begin:

%e 1,...1,...1,...1,...1,...;

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

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

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

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

%e ... 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:

%e 1;

%e 1, 1;

%e 1, 3, 1;

%e 1, 8, 4, 1;

%e 1, 20, 15, 5, 1;

%e 1, 50, 53, 21, 6, 1;

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

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

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

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

%e ...

%e 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.

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

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

%p end:

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

%p seq(seq(T(n, k), k=1..n), n=1..14); # _Alois P. Heinz_, Jun 29 2014

%p # second Maple program:

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

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

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

%p end:

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

%p seq(seq(T(n, k), k=1..n), n=1..14); # _Alois P. Heinz_, Aug 28 2017

%t 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_ *)

%o (Python)

%o from sympy.core.cache import cacheit

%o @cacheit

%o 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)])

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

%o for n in range(1, 16): print([T(n, k) for k in range(1, n + 1)]) # _Indranil Ghosh_, Aug 30 2017

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

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

%Y T(2n,n) gives A291662.

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

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

%K nonn,tabl

%O 1,5

%A _Gary W. Adamson_, Jan 04 2012