A000949 -id:A000949 - cp's OEIS frontend

A000951 Number of forests with n nodes and height at most 4.

1, 3, 16, 125, 1296, 16087, 229384, 3687609, 66025360, 1303751051, 28151798544, 659841763957, 16681231615816, 452357366282655, 13095632549137576, 403040561722348913, 13138626717852194976, 452179922268565180819, 16381932383826669204640

Offset: 1

N. J. A. Sloane

nonn

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..100
John Riordan, Forests of labeled trees, J. Combin. Theory, 5 (1968), 90-103.

Cf. A000248, A000949, A000950, A052512-A052514.

Column k=4 of A210725. - Alois P. Heinz, Mar 15 2013

nn = 20; Range[0, nn]! CoefficientList[Series[Exp[x*Exp[x*Exp[x*Exp[x*Exp[x]]]]], {x, 0, nn}], x] (* T. D. Noe, Jun 21 2012 *)

E.g.f.: exp(x*exp(x*exp(x*exp(x*exp(x))))).

More terms from Vladeta Jovovic, Apr 07 2001

A060905 Expansion of e.g.f. exp(xexp(x) + 1/2x^2*exp(x)^2).

Original entry on oeis.org

1, 1, 4, 19, 110, 751, 5902, 52165, 509588, 5437729, 62828306, 780287839, 10351912276, 145944541159, 2176931651546, 34225419288421, 565282627986368, 9779830102138945, 176776613812205074, 3330780287838743575

Offset: 0

Vladeta Jovovic, Apr 07 2001

nonn

Number of functions f from a set of size n to itself such that f(f(f(x))) = f(x). - Joel B. Lewis, Dec 12 2011

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.

Alois P. Heinz, Table of n, a(n) for n = 0..200
Vladimir Kruchinin, Composition of ordinary generating functions, arXiv:1009.2565 [math.CO], 2010.

Cf. A000949 - A000951, A060905 - A060913.

Column k=3 of A245501.

nn=20;a=x Exp[x];Range[0,nn]!CoefficientList[Series[Exp[a+a^2/2],{x,0,nn}],x]  (* Geoffrey Critzer, Sep 18 2012 *)

a(n):=sum(sum(k^(n-k)/(n-k)!*binomial(m,k-m)*(1/2)^(k-m),k,m,n)/m!,m,1,n); /* Vladimir Kruchinin, Aug 20 2010 */

E.g.f.: exp(Sum_{d|m} T_k^d/d), where T_k = x*exp(T_(k - 1)), k >= 1, T_0 = x; k = 1, m = 2.

a(n) = sum(sum(k^(n-k)/(n-k)!*binomial(m,k-m)*(1/2)^(k-m),k,m,n)/m!,m,1,n), n>0. - Vladimir Kruchinin, Aug 20 2010

A060913 E.g.f.: exp(xexp(xexp(xexp(x))) + 1/3x^3exp(xexp(x*exp(x)))^3).

Original entry on oeis.org

1, 1, 3, 18, 157, 1656, 20727, 300784, 4955337, 91229616, 1853584651, 41147256624, 989990665677, 25647894553048, 711630284942319, 21049888453838136, 661180220075555473, 21976354057916680416

Offset: 0

Vladeta Jovovic, Apr 07 2001

nonn

a(n) is the number of functions f:{1,2,...,n} -> {1,2,...,n} such that the functional digraphs have cycles of length 1 or 3 and no element is at a distance of more than 3 from a cycle. - Geoffrey Critzer, Sep 23 2012

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983.

Cf. A000949-A000951, A060905-A060913.

nn=20; a=x Exp[x]; b=x Exp[a]; c=x Exp[b]; t=Sum[n^(n-1)x^n/n!, {n, 1, nn}]; Range[0,nn]! CoefficientList[Series[Exp[c+c^3/3], {x, 0, nn}], x] (* Geoffrey Critzer, Sep 23 2012 *)

E.g.f.: exp(Sum_{d|m} T_k^d/d), where T_k = x*exp(T_(k - 1)), k >= 1, T_0 = x; k = 3, m = 3.

A187761 Number of maps f: [n] -> [n] with f(x)<=x and f(f(x)) = f(f(f(x))).

Original entry on oeis.org

1, 1, 2, 6, 23, 106, 568, 3459, 23544, 176850, 1451253, 12904312, 123489888, 1264591561, 13790277294, 159466823794, 1948259002647, 25066729706582, 338670605492700, 4792623436607059, 70873649458154500, 1092969062435462254, 17543703470388927229, 292600906102204630092

Offset: 0

Joerg Arndt, Jan 04 2013

This sequence and A187771 and A187824 are winners in the contest held at the 2013 AMS/MAA Joint Mathematics Meetings. - T. D. Noe, Jan 14 2013
Number of monotonic-labeled forests on n vertices with rooted trees of height less than 3. A labeled rooted tree is monotonic-labeled if the label of any parent vertex is (strictly) smaller than the label of any offspring vertex. (See comment by Dennis P. Walsh at A000110; with "greater" instead of "smaller".) To see this, consider the maps [1,2,...,n] -> [0,1,...,n-1] with f(x) < x.
As the maps are valid (left) inversion tables for permutations (see example), we obtain a simple bijection between permutations and such forests.
For n>=3 column 3 of A179455; maps such that f^[k](x) = f^[k-1](x) correspond to column k of A179455 (for n>=k).
Explanation of the Maple routine by Alois P. Heinz, Jan 15 2013: (Start)
b(n,x,y) is the number of forests consisting of trees we want to count, where n nodes are still to be inserted and x nodes at level 0 (the roots) and y nodes at level 1 are already present, plus perhaps some nodes at level 2 (whose number is not of interest).
If the next node is inserted at level 0 then n-1 remaining nodes are to be inserted (and level 0 has one more node: x+1).  There is only one possibility to do that.
If the next node is inserted at level 1 then again n-1 nodes are to be inserted (and level 1 has one more node: y+1).  The inserted node can have x different predecessors (at level 0), accounted by the multiplication by x.
If a node is inserted at level 2 then (again) n-1 nodes are to be inserted and level 2 has one more node (which is not counted).  The inserted node can have y predecessors, accounted by the multiplication by y.
b(0,x,y) = 1 counts any fixed forest that has received all its nodes.
b(n,0,0) counts all forests that can be constructed by inserting n nodes into the empty forest.
(End)
Also the row sums of the Bell transform of the Bell numbers. Since the Bell numbers are the row sums of the Bell transform of the Stirling_2 numbers they might also be called second order Bell numbers. (Also note that the Stirling_2 numbers are the row sums of the Bell transform of the simplest sequence of positive numbers 1,1,1,... which in turn are the row sums of the Bell transform of the characteristic function of 0. See the link 'Bell Transform' for more about this hierarchy which might be called the Bell hierarchy.) - Peter Luschny, Jan 23 2016

			There are a(4)=23 such maps f: [0,1,2,3] -> [0,1,2,3], all 4-digit mixed-radix numbers [f(0), f(1), f(2), f(3)] where 0 <= f(k) <= k (rising factorial basis) except for [ 0 0 1 2 ], as f(3)=2 and f(f(3)) = f(2) = 1 != f(f(f(3))) = f(f(2)) = f(1) = 0.
The exception corresponds to the tree 0 -- 1 -- 2 -- 3 (0 is the root), which can be identified with the map [1,2,3,4] -> [0,1,2,3] where f(k)=k-1.

Alois P. Heinz, Table of n, a(n) for n = 0..493
Peter Luschny, The Bell transform
Peter Luschny, Permutation Trees
D. P. Walsh, Counting forests with Stirling and Bell numbers

Cf. A000110 (Number of maps f: [n] -> [n] where f(x)<=x and f(f(x))=f(x) ).
Cf. A179455 (permutation trees of power n and height <= k+1 ).
Cf. A000949 (maps f: [n] -> [n] where f(f(x)) = f(f(f(x))) ).

b:= proc(n, x, y) option remember; `if`(n=0, 1,
       b(n-1, x+1, y) +x*b(n-1, x, y+1) +y*b(n-1, x, y))
    end:
a:= n-> b(n, 0, 0):
seq(a(n), n=0..25);  # Alois P. Heinz, Jan 09 2013
# The function BellMatrix is defined in A264428.
B := BellMatrix(n -> combinat:-bell(n), 24):
seq(add(i, i=LinearAlgebra:-Row(B,n)), n=1..24); # Peter Luschny, Jan 23 2016
# alternative Maple program:
b:= proc(n, h) option remember; `if`(min(n, h)=0, 1, add(
      binomial(n-1, j-1)*b(j-1, h-1)*b(n-j, h), j=1..n))
    end:
a:= n-> b(n, 2):
seq(a(n), n=0..25);  # Alois P. Heinz, Aug 21 2017

b[n_, x_, y_] := b[n, x, y] = If[n == 0, 1, b[n-1, x+1, y]+x*b[n-1, x, y+1]+y*b[n-1, x, y]]; a[n_] := b[n, 0, 0]; Table[a[n], {n, 0, 23}] (* Jean-François Alcover, Feb 25 2014, after Alois P. Heinz *)
Table[Sum[BellY[n, k, BellB[Range[n] - 1]], {k, 0, n}], {n, 0, 20}] (* Vladimir Reshetnikov, Nov 09 2016 *)

/* using e.g.f. A(x) */
x = 'x + O('x^66);
B = exp( exp(x) - 1 );  /* e.g.f. of Bell numbers */
A = serconvol( x * B, -log(1-x) );
/* A = intformal(B) */ /* alternative to last line */
A = exp( A );
Vec( serlaplace( A ) )

from sympy.core.cache import cacheit
from sympy import binomial
@cacheit
def b(n, h): return 1 if min(n, h)==0 else sum([binomial(n - 1, j - 1)*b(j - 1, h - 1)*b(n - j, h) for j in range(1, n + 1)])
def a(n): return b(n, 2)
print([a(n) for n in range(31)]) # Indranil Ghosh, Aug 21 2017, after second Maple program by Alois P. Heinz

Conjecture (confirmed below) about the e.g.f. A(x): Let B(x) = Sum_{n>=0} b(n) * x^n/n! = exp(exp(x)-1) the e.g.f. of the Bell numbers (A000110). Then A(x) = Sum_{n>=0} a(n) * x^n/n! = exp( Sum_{n>=0} b(n) * x^(n+1)/(n+1)! ), see PARI program.
From Joerg Arndt, Jan 14 2013: (Start)
Conjecture (confirmed below):  Let C(0,x) = 1 and for k>=1 C(k, x) = exp( integral(C(k-1,x)) ) then C(k,x) is the e.g.f. for monotonic-labeled forests on n vertices with rooted trees of height less than k (column k of A179455(n,k) for k>=1, n>=k).
For k=1 (C(1,x)=exp(x)) and k=2 (C(2,x)=exp(exp(x)-1)) this is known to be true, for k=3 this is the conjecture above. (End)
From Joerg Arndt, Jan 15 2013: (Start)
Gareth McCaughan, on the math-fun mailing list (Jan 14 2013), writes
"If F is the e.g.f. for Things Of Size n, then exp(F) is the e.g.f. for Multisets Of Things Whose Sizes Add Up To n. (The factorials turn into multinomial coefficients.)
"Which means the conjecture is right. (The integral turns that into 'multisets of things whose sizes plus 1 add up to n'; a tree is a forest together with a new node on top.)"
(End)

A235328 Number of ordered pairs of endofunctions (f,g) on a set of n elements satisfying f(x) = g(f(f(x))).

Original entry on oeis.org

1, 1, 6, 69, 1336, 39145, 1598256, 85996561, 5872177536, 494848403793, 50333180780800, 6068500612311841, 854434117410352128, 138752719761249646585, 25714777079368557164544, 5389541081414619785888625, 1267387594395443339970052096, 332074775201035547446532113825

Offset: 0

Chad Brewbaker, Mar 26 2014

nonn

This also counts pairs (f,g) satisfying f(x) = g(f^{r}(x)) for r > 1. - David Einstein, Nov 18 2016

Alois P. Heinz, Table of n, a(n) for n = 0..263

Cf. A000248, A000949, A181162, A351795.

a:= proc(n) option remember; local b; b:=
      proc(m, i) option remember; `if`(m=0, n^i, `if`(i<1, 0,
        add(b(m-j, i-1)*binomial(m, j)*j, j=0..m)))
      end: forget(b):
      b(n$2)
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Jul 23 2014

a[n_] := If[n==0, 1, Sum[k! Binomial[n, k] (n k)^(n - k), {k, 1, n}]]
  Table[a[n],{n,20}] (* David Einstein, Oct 10 2016 *)

a(n) = Sum_{k=1..n} k! * C(n, k) * (n*k)^(n-k). - David Einstein, Oct 10 2016
a(n) = n! * [x^n] 1/(1 - x*exp(n*x)). - Ilya Gutkovskiy, Nov 26 2017
log(a(n)) ~ log(sqrt(2*Pi) * n^(2*n - n/LambertW(exp(1)*n) + 1/2) / (LambertW(exp(1)*n) * exp(n/LambertW(exp(1)*n)) * (LambertW(exp(1)*n) - 1)^(n*(1 - 1/LambertW(exp(1)*n))))). - Vaclav Kotesovec, Feb 20 2022
More precise asymptotics: a(n) ~ sqrt(2*Pi) * (w^2 - w - 1 + 2/w) * exp(n*(1/w^3 - 1/w)) * n^(2*n + n/w^3 - n/w + 1/2) * (w^2 - 1)^(n*(1 + 1/w^3 - 1/w)) * (1 - w^2 + w^3)^(n/w - n - n/w^3 - 1), where w = LambertW(exp(1)*n). - Vaclav Kotesovec, Feb 23 2022

a(6)-a(7) from Giovanni Resta, Mar 26 2014

a(8)-a(17) from Alois P. Heinz, Jul 23 2014

A210725 Triangle read by rows: T(n,k) = number of forests of labeled rooted trees with n nodes and height at most k (n>=1, 0<=k<=n-1).

Original entry on oeis.org

1, 1, 3, 1, 10, 16, 1, 41, 101, 125, 1, 196, 756, 1176, 1296, 1, 1057, 6607, 12847, 16087, 16807, 1, 6322, 65794, 160504, 229384, 257104, 262144, 1, 41393, 733833, 2261289, 3687609, 4480569, 4742649, 4782969, 1, 293608, 9046648, 35464816, 66025360, 87238720, 96915520, 99637120, 100000000

Offset: 1

N. J. A. Sloane, May 09 2012

			Triangle begins:
  1;
  1,    3;
  1,   10,   16;
  1,   41,  101,   125;
  1,  196,  756,  1176,  1296;
  1, 1057, 6607, 12847, 16087, 16807;
  ...

Alois P. Heinz, Rows n = 1..141, flattened
J. Riordan, Forests of labeled trees, J. Combin. Theory, 5 (1968), 90-103.

Diagonals include A000248, A000949, A000950, A000951, A000272.

f:= proc(k) f(k):= `if`(k<0, 1, exp(x*f(k-1))) end:
T:= (n, k)-> coeff(series(f(k), x, n+1), x, n) *n!:
seq(seq(T(n, k), k=0..n-1), n=1..9); # Alois P. Heinz, May 30 2012
# second Maple program:
T:= proc(n, h) option remember; `if`(min(n, h)=0, 1, add(
      binomial(n-1, j-1)*j*T(j-1, h-1)*T(n-j, h), j=1..n))
    end:
seq(seq(T(n, k), k=0..n-1), n=1..10);  # Alois P. Heinz, Aug 21 2017

f[?Negative] = 1; f[k] := Exp[x*f[k-1]]; t[n_, k_] := Coefficient[Series[f[k], {x, 0, n+1}], x, n]*n!; Table[Table[t[n, k], {k, 0, n-1}], {n, 1, 9}] // Flatten (* Jean-François Alcover, Oct 30 2013, after Maple *)

from sympy.core.cache import cacheit
from sympy import binomial
@cacheit
def T(n, h): return 1 if min(n, h)==0 else sum([binomial(n - 1, j - 1)*j*T(j - 1, h - 1)*T(n - j, h) for j in range(1, n + 1)])
for n in range(1, 11): print([T(n, k) for k in range(n)]) # Indranil Ghosh, Aug 21 2017, after second Maple code

A231091 Number of distinct (modulo rotation) unicursal star polygons (not necessarily regular, no edge joins adjacent vertices) that can be formed by connecting the vertices of a regular n-gon.

Original entry on oeis.org

0, 0, 0, 0, 1, 1, 5, 27, 175, 1533, 14361, 151575, 1735869, 21594863, 289365383, 4158887007, 63822480809, 1041820050629, 18027531255745, 329658402237171, 6352776451924233, 128686951765990343, 2733851297673484765, 60781108703102022027, 1411481990523638719737

Offset: 1

Stewart Gordon, Nov 03 2013

For polygons in general see A000939 and A000949, and especially the Golomb-Welch reference. - N. J. A. Sloane, Nov 21 2013

			For n=5, only solution is the regular pentagram.
For n=6, only solution is the unicursal hexagram (see Wikipedia link).
For n=7, two regular heptagrams and three irregular forms are possible.

Andrew Howroyd, Table of n, a(n) for n = 1..200
Stewart Gordon, The five possible stars for n=7 (SVG file)
Wikipedia, Unicursal hexagram

Cf. A000939 (if edges may join adjacent vertices), A000940, A002816 (rotations and reflections counted separately), A326411, A370459 (up to rotations and reflections), A370068 (directed edges).

Cf. A283184.

\\ Requires a370068 from A370068, b(n) is A283184.
b(n)={subst(serlaplace(polcoef((1 - x)/(1 + (1 - 2*y)*x + 2*y*x^2) + O(x*x^n), n)), y, 1)}
a(n)={(if(n%2==0 && n > 2, b(n/2-1)/2) + a370068(n))/2} \\ Andrew Howroyd, Mar 01 2024

a(n) = (A370068(n) + A283184(n/2-1)/2)/2 for even n >= 4; a(n) = A370068(n)/2 for odd n. - Andrew Howroyd, Feb 24 2024

a(15) onwards from Andrew Howroyd, Feb 23 2024

A000950 Number of forests with n nodes and height at most 3.

Original entry on oeis.org

1, 3, 16, 125, 1176, 12847, 160504, 2261289, 35464816, 612419291, 11539360944, 235469524237, 5170808565976, 121535533284999, 3043254281853496, 80852247370051793, 2270951670959226336, 67221368736302224819, 2091039845329887687136

Offset: 1

N. J. A. Sloane

nonn

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..100
John Riordan, Forests of labeled trees, J. Combin. Theory, 5 (1968), 90-103.

Cf. A000248, A000949-A000951, A052512-A052514.

Column k=3 of A210725. - Alois P. Heinz, Mar 15 2013

nn = 20; Range[0, nn]! CoefficientList[Series[Exp[x*Exp[x*Exp[x*Exp[x]]]], {x, 0, nn}], x] (* T. D. Noe, Jun 21 2012 *)

E.g.f.: exp(x*exp(x*exp(x*exp(x)))).

More terms from Vladeta Jovovic, Apr 07 2001

A239749 Number of ordered pairs of functions f,g on a set of n elements into itself satisfying f(f(x)) = g(f(g(x))).

Original entry on oeis.org

1, 1, 6, 87, 2056, 69605, 3201696, 190933435

Offset: 0

Chad Brewbaker, Mar 26 2014

			a(0) = a(1) = 1 since there is only one endofunction for n=0 or 1 and the equation is satisfied trivially. For n=2, each endofunction f on {1,2} is represented by [f(1),f(2)]. The list of a(2) = 6 pairs (f,g) which satisfy the equation is ([1,1], [1,1]), ([1,1], [1,2]), ([1,2], [1,2]), ([1,2], [2,1]), ([2,2], [1,2]), ([2,2], [2,2]). - _Michael Somos_, Mar 26 2014

Cf. A000248, A000949.

Related sequences: A053529, A181162, A239749-A239785, A239836-A239841.

a(6)-a(7) from Giovanni Resta, Mar 26 2014

A239750 Number of ordered pairs of endofunctions (f,g) on a set of n elements satisfying g(f(x)) = f(f(f(x))).

Original entry on oeis.org

1, 1, 6, 87, 2200, 84245, 4492656, 315937195, 28186856832, 3099006365769, 410478164588800, 64323095036300111, 11748771067445148672, 2470422069374379054493, 591735532838657160296448, 160004357420756572368889875, 48458574881000820765562863616

Offset: 0

Chad Brewbaker, Mar 26 2014

nonn

As observed by Yuval Filmus, this also counts pairs (f,g) that satisfy g(f(x)) = f^{k}(x) for k >= 1. - Chad Brewbaker, Mar 27 2014

Alois P. Heinz, Table of n, a(n) for n = 0..200
Yuval Filmus, Answer to 'A curious Wilf equivalence class of function compositions', Mar 27 2014

Cf. A000248, A000949, A048993, A181162, A241015.

Column k=1 of A245980.

a:= n-> add(binomial(n, k)*k^n*(n-1)^(n-k), k=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, Jul 23 2014

a[n_] := If[n<2, 1, Sum[Binomial[n, k]*k^n*(n-1)^(n-k), {k, 0, n}]];
a /@ Range[0, 20] (* Jean-François Alcover, Oct 03 2019, after Alois P. Heinz *)

a(n) = Sum_{k=0..n} C(n,k) * k^n * (n-1)^(n-k) = Sum_{k=0..n} C(n,k) * A048993(n,k) * k! * n^(n-k). - Alois P. Heinz, Jul 23 2014

a(6)-a(7) from Giovanni Resta, Mar 26 2014

a(8)-a(16) from Alois P. Heinz, Jul 17 2014

cp's OEIS Frontend

A000951 Number of forests with n nodes and height at most 4.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A060905 Expansion of e.g.f. exp(x*exp(x) + 1/2*x^2*exp(x)^2).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Maxima

Formula

A060913 E.g.f.: exp(x*exp(x*exp(x*exp(x))) + 1/3*x^3*exp(x*exp(x*exp(x)))^3).

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Mathematica

Formula

A187761 Number of maps f: [n] -> [n] with f(x)<=x and f(f(x)) = f(f(f(x))).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

A235328 Number of ordered pairs of endofunctions (f,g) on a set of n elements satisfying f(x) = g(f(f(x))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A210725 Triangle read by rows: T(n,k) = number of forests of labeled rooted trees with n nodes and height at most k (n>=1, 0<=k<=n-1).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

A231091 Number of distinct (modulo rotation) unicursal star polygons (not necessarily regular, no edge joins adjacent vertices) that can be formed by connecting the vertices of a regular n-gon.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

A060905 Expansion of e.g.f. exp(xexp(x) + 1/2x^2*exp(x)^2).

A060913 E.g.f.: exp(xexp(xexp(xexp(x))) + 1/3x^3exp(xexp(x*exp(x)))^3).