A022815 -id:A022815 - cp's OEIS frontend

A022811 Number of terms in n-th derivative of a function composed with itself 3 times.

1, 1, 3, 6, 13, 23, 44, 74, 129, 210, 345, 542, 858, 1310, 2004, 2996, 4467, 6540, 9552, 13744, 19711, 27943, 39452, 55172, 76865, 106200, 146173, 199806, 272075, 368247, 496642, 666201, 890602, 1184957, 1571417, 2075058, 2731677, 3582119, 4683595, 6102256

Offset: 0

Winston C. Yang (yang(AT)math.wisc.edu)

nonn

This also counts a restricted set of plane partitions of n. Each element of the set which contains the A000041(n) partitions of n can be converted into plane partitions by insertion of line feeds at some or all places of the "pluses." Since the length of rows in plane partitions must be nonincreasing, there are only A000041(L(P)) ways to comply with this rule, where L(P) is the number of terms in that particular partition. Example for n=4: consider all five partitions 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1 of four. The associated a(4)=13 plane partitions are 4, 31, 3|1, 22, 2|2, 211, 21|1, 2|1|1, 1111, 111|1, 11|11, 11|1|1 and 1|1|1|1, where the bar represents start of the next row, where a(4) = A000041(L(4)) + A000041(L(3+1)) + A000041(L(2+2)) + A000041(L(2+1+1))+ A000041(L(1+1+1+1)) = A000041(1) + A000041(2) + A000041(2) + A000041(3) + A000041(4). By construction from sorted partitions, all the plane partitions are strictly decreasing along each row and each column. - R. J. Mathar, Aug 12 2008

Also the number of pairs of integer partitions, the first with sum n and the second with sum equal to the length of the first. - Gus Wiseman, Jul 19 2018

			From _Gus Wiseman_, Jul 19 2018: (Start)
Using the chain rule, we compute the second derivative of f(f(f(x))) to be the following sum of a(2) = 3 terms.
  d^2/dx^2 f(f(f(x))) =
  f'(f(x)) f'(f(f(x))) f''(x) +
  f'(x)^2 f'(f(f(x))) f''(f(x)) +
  f'(x)^2 f'(f(x))^2 f''(f(f(x))).
(End)

W. C. Yang, Derivatives of self-compositions of functions, preprint, 1997.

Alois P. Heinz, Table of n, a(n) for n = 0..3000 (terms n = 501..959 from Vaclav Kotesovec)
W. C. Yang, Derivatives are essentially integer partitions, Discrete Mathematics, 222(1-3), July 2000, 235-245.

Column k=3 of A022818.
First column of A039805.
A row or column of A081718.
Cf. A008778, A022812, A022813, A022814, A022815, A022816, A022817, A024207, A024208, A024209, A024210, A131408.

A022811 := proc(n) local a,P,p,lp ; a := 0 ; P := combinat[partition](n) ; for p in P do lp := nops(p) ; a := a+combinat[numbpart](lp) ; od: RETURN(a) ; end: for n from 1 do print(n,A022811(n)) ; od: # R. J. Mathar, Aug 12 2008

a[n_] := Total[PartitionsP[Length[#]]& /@ IntegerPartitions[n]];
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 0, 80}] (* Jean-François Alcover, Apr 28 2017 *)
Table[Length[1+D[f[f[f[x]]],{x,n}]]-1,{n,10}] (* Gus Wiseman, Jul 19 2018 *)

If a(n,m) = number of terms in m-derivative of a function composed with itself n times, p(n,k) = number of partitions of n into k parts, then a(n,m) = Sum_{i=0..m} p(m,i)*a(n-1,i).

G.f.: Sum_{k>=0} p(k) * x^k / Product_{j=1..k} (1 - x^j), where p(k) = number of partitions of k. - Ilya Gutkovskiy, Jan 28 2020

Typo corrected by Neven Juric, Mar 25 2013

A022818 Square array read by antidiagonals: A(n,k) = number of terms in the n-th derivative of a function composed with itself k times (n, k >= 1).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 5, 1, 1, 5, 10, 13, 7, 1, 1, 6, 15, 26, 23, 11, 1, 1, 7, 21, 45, 55, 44, 15, 1, 1, 8, 28, 71, 110, 121, 74, 22, 1, 1, 9, 36, 105, 196, 271, 237, 129, 30, 1, 1, 10, 45, 148, 322, 532, 599, 468, 210, 42, 1, 1, 11, 55, 201, 498, 952, 1301, 1309, 867, 345, 56, 1

Offset: 1

N. J. A. Sloane

			Square array A(n,k) (with rows n >= 1 and columns k >= 1) begins:
  1,  1,   1,   1,    1,    1,    1,     1, ...
  1,  2,   3,   4,    5,    6,    7,     8, ...
  1,  3,   6,  10,   15,   21,   28,    36, ...
  1,  5,  13,  26,   45,   71,  105,   148, ...
  1,  7,  23,  55,  110,  196,  322,   498, ...
  1, 11,  44, 121,  271,  532,  952,  1590, ...
  1, 15,  74, 237,  599, 1301, 2541,  4586, ...
  1, 22, 129, 468, 1309, 3101, 6539, 12644, ...
  ...

Winston C. Yang (yang(AT)math.wisc.edu), Derivatives of self-compositions of functions, preprint, 1997.

Alois P. Heinz, Antidiagonals n = 1..141
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. [Take the transpose of Table 2 on p. 241 and omit row 0 and column 0; A(n,k) = M(k,n). - _Petros Hadjicostas_, May 30 2020]

Rows n=1-10 give: A000012, A000027, A000217, A008778, A022815, A022816, A022817, A215626, A215627, A215628.
Columns k=1-10 give: A000012, A000041, A022811, A022812, A022813, A022814, A024207, A024208, A024209, A024210.
Main diagonal gives: A192435.
Cf. A008284, A081719.

A:= proc(n, k) option remember;
      `if`(k=1, 1, add(b(n, n, i)*A(i, k-1), i=0..n))
    end:
b:= proc(n, i, k) option remember; `if`(nAlois P. Heinz, Aug 18 2012
# second Maple program:
b:= proc(n, i, l, k) option remember; `if`(k=0,
      `if`(n<2, 1, 0), `if`(n=0 or i=1, b(l+n$2, 0, k-1),
         b(n, i-1, l, k) +b(n-i, min(n-i, i), l+1, k)))
    end:
A:= (n, k)->  b(n$2, 0, k):
seq(seq(A(n, 1+d-n), n=1..d), d=1..12);  # Alois P. Heinz, Jul 19 2018

a[n_, k_] := a[n, k] = If[k == 1, 1, Sum[b[n, n, i]*a[i, k-1], {i, 0, n}]]; b[n_, i_, k_] := b[n, i, k] = If[n < k, 0, If[n == 0, 1, If[i < 1, 0, Sum[b[n-i*j, i-1, k-j], {j, 0, Min[n/i, k]}]]]]; Table[Table[a[n, 1+d-n], {n, 1, d}], {d, 1, 12}] // Flatten (* Jean-François Alcover, Jan 14 2014, translated from Alois P. Heinz's Maple code *)

P(n, k) = #partitions(n-k, k); /* A008284 */
tabl(nn) = {M = matrix(nn, nn, n, k, 0); for(n=1, nn, M[n, 1] = 1; ); for(n=1, nn, for(k=2, nn, M[n, k] = sum(s=1, n, P(n, s)*M[s, k-1]))); for (n=1, nn, for (k=1, nn, print1(M[n, k], ", "); ); print(); ); } \\ Petros Hadjicostas, May 30 2020

From Petros Hadjicostas, May 30 2020: (Start)
A(n,k) = Sum_{s=1..n} A008284(n,s)*A(s,k-1) for n >= 1 and k >= 2 with A(n,1) = 1 for n >= 1.
A(n,k) = Sum_{s=1..n} binomial(k,s-1)*A081719(n-1,s-1) for n, k >= 1. (End)

Edited by Alois P. Heinz, Aug 18 2012

A135855 A007318 * a tridiagonal matrix with (1, 4, 1, 0, 0, 0, ...) in every column.

Original entry on oeis.org

1, 5, 1, 10, 6, 1, 16, 16, 7, 1, 23, 32, 23, 8, 1, 31, 55, 55, 31, 9, 1, 40, 86, 110, 86, 40, 10, 1, 50, 126, 196, 196, 126, 50, 11, 1, 61, 176, 322, 392, 322, 176, 61, 12, 1, 73, 237, 498, 714, 714, 498, 237, 73, 13, 1

Offset: 0

Gary W. Adamson, Dec 01 2007

			First few rows of the triangle:
   1;
   5,  1;
  10,  6,   1;
  16, 16,   7,  1;
  23, 32,  23,  8,  1;
  31, 55,  55, 31,  9,  1;
  40, 86, 110, 86, 40, 10, 1;
  ...

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A007318, A022815, A052905, A101945, A134465.

A135855:= func< n,k | Binomial(n,k)*(n^2 + (2*k+7)*n - 2*(k^2 + 2*k -1))/((k+1)*(k+2)) >;
[A135855(n,k): k in [0..n], n in [0..10]]; // G. C. Greubel, Feb 06 2022

T[n_, k_]:= T[n, k]= If[k<0 || k>n, 0, If[k==0, (n^2+7*n+2)/2, If[k==n, 1, T[n-1, k-1] + T[n-1, k]]]];
Table[T[n, k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Feb 06 2022 *)

@CachedFunction
def T(n,k): # A135855
    if (k==0): return (n^2+7*n+2)/2
    elif (k==n): return 1
    else: return T(n-1, k-1) + T(n-1, k)
flatten([[T(n,k) for k in (0..n)] for n in (0..10)]) # G. C. Greubel, Feb 06 2022

Binomial transform of an infinite tridiagonal matrix with (1, 4, 1, 0, 0, 0, ...) in every column; i.e., (1, 1, 1, ...) in the main diagonal, (4, 4, 4, 0, 0, 0, ...) in the subdiagonal and (1, 1, 1, ...) in the subsubdiagonal.
T(n, 0) = A052905(n).
Sum_{k=0..n} T(n, k) = A101945(n).
From G. C. Greubel, Feb 06 2022: (Start)
T(n, k) = T(n-1, k-1) + T(n-1, k), with T(n, n) = 1, T(n, 0) = A052905(n).
T(n, k) = binomial(n,k)*(n^2 + (2*k+7)*n - 2*(k^2 + 2*k -1))/((k+1)*(k+2)).
T(n, 1) = A134465(n).
T(n, 2) = A022815(n-1).
T(n, n-1) = n+3.
T(n, n-2) = A052905(n+2). (End)

A081718 Array T(m,n) read by antidiagonals, where T(m,n) = number of m X infinity multiplicity integer partition (mip) matrix of n (m >= 0, n >= 0).

Original entry on oeis.org

1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 3, 3, 1, 0, 1, 1, 4, 6, 5, 1, 0, 1, 1, 5, 10, 13, 7, 1, 0, 1, 1, 6, 15, 26, 23, 11, 1, 0, 1, 1, 7, 21, 45, 55, 44, 15, 1, 0, 1, 1, 8, 28, 71, 110, 121, 74, 22, 1, 0, 1, 1, 9, 36, 105, 196, 271, 237, 129, 30, 1, 0, 1, 1, 10, 45, 148, 322, 532

Offset: 0

N. J. A. Sloane, Apr 05 2003

For n > 0, the n-th column is given by a polynomial of degree n-1. - David Wasserman, Jun 21 2004

			Array begins:
1 1 0 0 0 ...
1 1 1 1 1 ...
1 1 2 3 5 ...
1 1 3 6 13 ...

W. C. Yang, Derivatives are essentially integer partitions, Discrete Mathematics, 222(1-3), July 2000, 235-245.

Rows and columns give A022811, A022812, A022813, A022814, A022815, etc.

There is a recurrence involving the partition function.

More terms from David Wasserman, Jun 21 2004

cp's OEIS Frontend

A022811 Number of terms in n-th derivative of a function composed with itself 3 times.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A022818 Square array read by antidiagonals: A(n,k) = number of terms in the n-th derivative of a function composed with itself k times (n, k >= 1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A135855 A007318 * a tridiagonal matrix with (1, 4, 1, 0, 0, 0, ...) in every column.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

A081718 Array T(m,n) read by antidiagonals, where T(m,n) = number of m X infinity multiplicity integer partition (mip) matrix of n (m >= 0, n >= 0).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions