A081719 Triangle T(n,k) read by rows, related to Faà di Bruno's formula (n >= 0 and 0 <= k <= n).

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

Offset: 0

Author

N. J. A. Sloane, Apr 05 2003

Keywords

• nonn
• tabl
• easy

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)

Examples

			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;
  ...
		

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.

Crossrefs

Cf. A007042, A008284, A039809, A047812.

Programs

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 *)

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

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.

T(n, k=2) = A007042(n) = A047812(n,2). (End)

Extensions

More terms from Emeric Deutsch, Feb 28 2005