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