|
|
A081719
|
|
Triangle T(n,k) read by rows, related to Faà di Bruno's formula (n >= 0 and 0 <= k <= n).
|
|
3
|
|
|
1, 0, 1, 0, 1, 1, 0, 1, 3, 1, 0, 1, 5, 5, 1, 0, 1, 9, 14, 7, 1, 0, 1, 13, 32, 27, 9, 1, 0, 1, 20, 66, 80, 44, 11, 1, 0, 1, 28, 123, 203, 160, 65, 13, 1, 0, 1, 40, 222, 465, 486, 280, 90, 15, 1, 0, 1, 54, 377, 985, 1305, 990, 448, 119, 17, 1, 0, 1, 75, 630, 1978, 3203, 3051, 1807, 672, 152, 19, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,9
|
|
COMMENTS
|
We may prove Philippe Deléham's formula by induction on n. Let P(n,k) = A008284(n,k) and b(n) = A039809(n). For n = 0, Sum_{k=0..0} T(0,k) = 1 = b(1). Let n >= 1, and assume his formula is true for all s < n, i.e., Sum_{k=0..s} T(s,k) = b(s+1).
Then Sum_{k=0..n} T(n, k) = Sum_{k=1..n} T(n,k) = Sum_{k=1..n} Sum_{s=k-1..n-1} P(n+1, s+1)*T(s, k-1) = Sum_{s=0..n-1} P(n+1, s+1) Sum_{k=1..s+1} T(s, k-1) = Sum_{s=0..n-1} P(n+1, s+1) Sum_{m=0..s} T(s,m) = Sum_{s=0..n-1} P(n+1, s+1)*b(s+1) = Sum_{r=1..n} P(n+1, r)*b(r) = b(n+1) (by the definition of b = A039809). (End)
|
|
LINKS
|
|
|
FORMULA
|
There is a recurrence involving the partition function A008284.
T(n, k) = Sum_{s=k-1..n-1} A008284(n+1, s+1)*T(s, k-1) for 1 <= k <= n with T(0,0) = 1 and T(n,0) = 0 for n >= 1.
|
|
EXAMPLE
|
Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins:
1;
0, 1;
0, 1, 1;
0, 1, 3, 1;
0, 1, 5, 5, 1;
0, 1, 9, 14, 7, 1;
0, 1, 13, 32, 27, 9, 1;
0, 1, 20, 66, 80, 44, 11, 1;
...
|
|
MATHEMATICA
|
b[n_, k_]:= b[n, k]= If[n>0 && k>0, b[n-1, k-1] + b[n-k, k], Boole[n==0 && k==0]];
T[n_, k_]:= T[n, k]= If[n==0 && k==0, 1, If[k==0, 0, Sum[T[j, k-1]*b[n+1, j+1], {j, k-1, n-1}] ]];
Table[T[n, k], {n, 0, 12}, {k, 0, n}]//Flatten (* G. C. Greubel, May 31 2020 *)
|
|
PROG
|
(PARI) P(n, k)=#partitions(n-k, k); /* A008284 */
tabl(nn) = {A = matrix(nn, nn, n, k, 0); A[1, 1] = 1; for(n=2, nn, for(k=2, n, A[n, k] = sum(s=k-2, n-2, P(n, s+1)*A[s+1, k-1])));
for (n=1, nn, for (k=1, n, print1(A[n, k], ", "); ); print(); ); } \\ Petros Hadjicostas, May 29 2020
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|