login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A203717 A Catalan triangle by rows. 7
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
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
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.
Sequence in context: A273719 A274488 A351889 * A143953 A114276 A152879
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 04:26 EDT 2024. Contains 370952 sequences. (Running on oeis4.)