A081719 - OEIS

%I #31 Jun 02 2020 01:58:41

%S 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,

%T 66,80,44,11,1,0,1,28,123,203,160,65,13,1,0,1,40,222,465,486,280,90,

%U 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

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

%C From _Petros Hadjicostas_, May 30 2020: (Start)

%C 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).

%C 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)

%H Warren P. Johnson, <a href="https://www.maa.org/sites/default/files/pdf/upload_library/22/Ford/Johnson217-234.pdf">The curious history of Faà di Bruno's formula</a>, American Mathematical Monthly, 109 (2002), 217-234.

%H Warren P. Johnson, <a href="https://www.jstor.org/stable/2695352?seq=1">The curious history of Faà di Bruno's formula</a>, American Mathematical Monthly, 109 (2002), 217-234.

%H Winston C. Yang, <a href="http://dx.doi.org/10.1016/S0012-365X(99)00412-4">Derivatives are essentially integer partitions</a>, Discrete Mathematics, 222(1-3), July 2000, 235-245.

%F There is a recurrence involving the partition function A008284.

%F Sum_{k=0..n} T(n,k) = A039809(n+1). - _Philippe Deléham_, Sep 30 2006

%F From _Petros Hadjicostas_, May 30 2020: (Start)

%F 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.

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

%e Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins:

%e   1;

%e   0, 1;

%e   0, 1,  1;

%e   0, 1,  3,  1;

%e   0, 1,  5,  5,  1;

%e   0, 1,  9, 14,  7,  1;

%e   0, 1, 13, 32, 27,  9,  1;

%e   0, 1, 20, 66, 80, 44, 11, 1;

%e   ...

%t (* b = A008284 *)

%t 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 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}] ]];

%t Table[T[n, k], {n, 0, 12}, {k, 0, n}]//Flatten (* _G. C. Greubel_, May 31 2020 *)

%o (PARI) P(n, k)=#partitions(n-k, k); /* A008284 */

%o 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])));

%o for (n=1, nn, for (k=1, n, print1(A[n, k], ", "); ); print(); ); }  \\ _Petros Hadjicostas_, May 29 2020

%Y Cf. A007042, A008284, A039809, A047812.

%K nonn,tabl,easy

%O 0,9

%A _N. J. A. Sloane_, Apr 05 2003

%E More terms from _Emeric Deutsch_, Feb 28 2005