OFFSET
0,9
COMMENTS
From Petros Hadjicostas, May 30 2020: (Start)
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
Warren P. Johnson, The curious history of Faà di Bruno's formula, American Mathematical Monthly, 109 (2002), 217-234.
Warren P. Johnson, The curious history of Faà di Bruno's formula, American Mathematical Monthly, 109 (2002), 217-234.
Winston C. Yang, Derivatives are essentially integer partitions, Discrete Mathematics, 222(1-3), July 2000, 235-245.
FORMULA
There is a recurrence involving the partition function A008284.
Sum_{k=0..n} T(n,k) = A039809(n+1). - Philippe Deléham, Sep 30 2006
From Petros Hadjicostas, May 30 2020: (Start)
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 = A008284 *)
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
N. J. A. Sloane, Apr 05 2003
EXTENSIONS
More terms from Emeric Deutsch, Feb 28 2005
STATUS
approved