OFFSET
0,9
COMMENTS
Equals A096465 when the leading column (k = 0) is removed. - Georg Fischer, Jul 26 2023
FORMULA
For n>0 and k>0 let X(n, k) denote the set of all tuples of length n with elements from {0, ..., k-1} with sum < k. Let C(m) denote the m-th Catalan number. Then: A(n, k) = Sum_{(j1,...,jn) in X(n, k)} C(j1)*C(j2)*...*C(jn).
A(n, k) = T(n + k, k) with T(n, k) = T(n-1, k) + T(n, k-1) with T(n, k) = 0 if n <= 0 or k < 0 and T(n, n) = 1.
EXAMPLE
The square array starts:
[n\k] 0 1 2 3 4 5 6 7 8 9
---------------------------------------------------------------
[0] 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... A057427
[1] 0, 1, 2, 4, 9, 23, 65, 197, 626, 2056, ... A014137
[2] 0, 1, 3, 8, 22, 64, 196, 625, 2055, 6917, ... A014138
[3] 0, 1, 4, 13, 41, 131, 428, 1429, 4861, 16795, ... A001453
[4] 0, 1, 5, 19, 67, 232, 804, 2806, 9878, 35072, ... A114277
[5] 0, 1, 6, 26, 101, 376, 1377, 5017, 18277, 66727, ... A143955
[6] 0, 1, 7, 34, 144, 573, 2211, 8399, 31655, 118865, ...
[7] 0, 1, 8, 43, 197, 834, 3382, 13378, 52138, 201364, ...
[8] 0, 1, 9, 53, 261, 1171, 4979, 20483, 82499, 327656, ...
[9] 0, 1, 10, 64, 337, 1597, 7105, 30361, 126292, 515659, ...
.
Triangle given by ascending antidiagonals:
0;
0, 1;
0, 1, 1;
0, 1, 2, 1;
0, 1, 3, 4, 1;
0, 1, 4, 8, 9, 1;
0, 1, 5, 13, 22, 23, 1;
0, 1, 6, 19, 41, 64, 65, 1;
0, 1, 7, 26, 67, 131, 196, 197, 1;
0, 1, 8, 34, 101, 232, 428, 625, 626, 1;
.
The difference table of a column successively gives the preceding columns, here starting with column 6.
col(6) = 1, 65, 196, 428, 804, 1377, 2211, 3382, 4979, 7105, ...
col(5) = 64, 131, 232, 376, 573, 834, 1171, 1597, 2126, ...
col(4) = 67, 101, 144, 197, 261, 337, 426, 529, ...
col(3) = 34, 43, 53, 64, 76, 89, 103, ...
col(2) = 9, 10, 11, 12, 13, 14, ...
col(1) = 1, 1, 1, 1, 1, ...
col(0) = 0, 0, 0, 0, ...
.
Example for the sum formula: C(0) = 1, C(1) = 1, C(2) = 2 and C(3) = 5.
X(3, 4) = {{0,0,0}, {0,0,1}, {0,1,0}, {1,0,0}, {0,0,2}, {0,1,1}, {0,2,0}, {1,0,1},
{1,1,0}, {2,0,0}, {0,0,3}, {0,1,2}, {0,2,1}, {0,3,0}, {1,0,2}, {1,1,1}, {1,2,0},
{2,0,1}, {2,1,0}, {3,0,0}}. T(3,4) = 1+1+1+1+2+1+2+1+1+2+5+2+2+5+2+1+2+2+2+5 = 41.
MAPLE
Row := proc(n, len) local C, ogf, ser; C := (1-sqrt(1-4*x))/(2*x);
ogf := C^n*x/(1-x); ser := series(ogf, x, (n+1)*len+1);
seq(coeff(ser, x, j), j=0..len) end:
for n from 0 to 9 do Row(n, 9) od;
# Alternatively by recurrence:
B := proc(n, k) option remember; if n <= 0 or k < 0 then 0
elif n = k then 1 else B(n-1, k) + B(n, k-1) fi end:
A := (n, k) -> B(n + k, k): seq(lprint(seq(A(n, k), k=0..9)), n=0..9);
MATHEMATICA
(* Illustrating the sum formula, not efficient. *) T[0, K_] := Boole[K != 0];
T[N_, K_] := Module[{}, r[n_, k_] := FrobeniusSolve[ConstantArray[1, n], k];
X[n_] := Flatten[Table[r[N, j], {j, 0, n - 1}], 1];
Sum[Product[CatalanNumber[m[[i]]], {i, 1, N}], {m , X[K]}]];
Trow[n_] := Table[T[n, k], {k, 0, 9}]; Table[Trow[n], {n, 0, 9}]
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Peter Luschny, Jan 24 2019
STATUS
approved