A138464 -id:A138464 - cp's OEIS frontend

A001858 Number of forests of trees on n labeled nodes.

1, 1, 2, 7, 38, 291, 2932, 36961, 561948, 10026505, 205608536, 4767440679, 123373203208, 3525630110107, 110284283006640, 3748357699560961, 137557910094840848, 5421179050350334929, 228359487335194570528, 10239206473040881277575, 486909744862576654283616

Offset: 0

N. J. A. Sloane and Simon Plouffe

The number of integer lattice points in the permutation polytope of {1,2,...,n}. - Max Alekseyev, Jan 26 2010
Equals the number of score sequences for a tournament on n vertices. See Prop. 7 of the article by Bartels et al., or Example 3.1 in the article by Stanley. - David Radcliffe, Aug 02 2022
Number of labeled acyclic graphs on n vertices. The unlabeled version is A005195. The covering case is A105784, connected A000272. - Gus Wiseman, Apr 29 2024

			From _Gus Wiseman_, Apr 29 2024: (Start)
Edge-sets of the a(4) = 38 forests:
  {}  {12}  {12,13}  {12,13,14}
      {13}  {12,14}  {12,13,24}
      {14}  {12,23}  {12,13,34}
      {23}  {12,24}  {12,14,23}
      {24}  {12,34}  {12,14,34}
      {34}  {13,14}  {12,23,24}
            {13,23}  {12,23,34}
            {13,24}  {12,24,34}
            {13,34}  {13,14,23}
            {14,23}  {13,14,24}
            {14,24}  {13,23,24}
            {14,34}  {13,23,34}
            {23,24}  {13,24,34}
            {23,34}  {14,23,24}
            {24,34}  {14,23,34}
                     {14,24,34}
(End)

B. Bollobas, Modern Graph Theory, Springer, 1998, p. 290.
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).

Alois P. Heinz, Table of n, a(n) for n = 0..388 (first 101 terms from T. D. Noe)
J. E. Bartels, J. Mount, and D. J. A. Welsh, The polytope of win vectors. Annals of Combinatorics 1, 1-15 (1997). https://doi.org/10.1007/BF02558460
David Callan, A Combinatorial Derivation of the Number of Labeled Forests, J. Integer Seqs., Vol. 6, 2003.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.o
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002 [Local copy, with permission]
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 132.
Samuele Giraudo, Combalgebraic structures on decorated cliques, Formal Power Series and Algebraic Combinatorics, Séminaire Lotharingien de Combinatoire, 78B.15, 2017, p. 7, arXiv:1709.08416 [math.CO], 2017.
Anton Izosimov, Matrix polynomials, generalized Jacobians, and graphical zonotopes, arXiv:1506.05179 [math.AG], 2015.
Qipeng Kuang, Ondřej Kuželka, Yuanhong Wang, and Yuyi Wang, Bridging Weighted First Order Model Counting and Graph Polynomials, arXiv:2407.11877 [cs.LO], 2024. See pp. 32-33.
Arun P. Mani and Rebecca J. Stones, Congruences for weighted number of labeled forests, INTEGERS 16 (2016). #A17.
J. Pitman, Coalescent Random Forests, J. Combin. Theory, A85 (1999), 165-193.
J. Riordan, Forests of labeled trees, J. Combin. Theory, 5 (1968), 90-103.
J. Riordan, Letter to N. J. A. Sloane, Oct 19 1970
J. Riordan, Letter to N. J. A. Sloane, Nov 10 1975
John Riordan and N. J. A. Sloane, Correspondence, 1974
N. J. A. Sloane, Letter to J. Riordan, Nov. 1970
R. Stanley, Decompositions of rational convex polytopes, Ann. Discrete Math 6.6 (1980): 333-342.
L. Takacs, On the number of distinct forests, SIAM J. Discrete Math., 3 (1990), 574-581.
E. M. Wright, A relationship between two sequences, Proc. London Math. Soc. (3) 17 (1967) 296-304.
Index entries for sequences related to forests

The connected case is A000272, rooted A000169.
The unlabeled version is A005195, connected A000055.
The covering case is A105784, unlabeled A144958.
Row sums of A138464.
For triangles instead of cycles we have A213434, covering A372168.
For a unique cycle we have A372193, covering A372195.
A002807 counts cycles in a complete graph.
A006125 counts simple graphs, unlabeled A000088.
A006129 counts covering graphs, unlabeled A002494.
Cf. A006572, A006573, A088956.
Cf. A053530, A054548, A137916, A263340, A322661, A367863, A372176.

exp(x+x^2+add(n^(n-2)*x^n/n!, n=3..50));
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(
      binomial(n-1, j-1)*j^(j-2)*a(n-j), j=1..n))
    end:
seq(a(n), n=0..20);  # Alois P. Heinz, Sep 15 2008
# third Maple program:
F:= exp(-LambertW(-x)*(1+LambertW(-x)/2)):
S:= series(F,x,51):
seq(coeff(S,x,j)*j!, j=0..50); # Robert Israel, May 21 2015

nn=20;t=Sum[n^(n-1)x^n/n!,{n,1,nn}];Range[0,nn]!CoefficientList[ Series[Exp[t-t^2/2],{x,0,nn}],x] (* Geoffrey Critzer, Sep 05 2012 *)
nmax = 20; CoefficientList[Series[-LambertW[-x]/(x*E^(LambertW[-x]^2/2)), {x, 0, nmax}], x] * Range[0, nmax]! (* Vaclav Kotesovec, Jul 19 2019 *)

a(n)=if(n<0,0,sum(m=0,n,sum(j=0,m,binomial(m,j)*binomial(n-1,n-m-j)*n^(n-m-j)*(m+j)!/(-2)^j)/m!)) /* Michael Somos, Aug 22 2002 */

E.g.f.: exp( Sum_{n>=1} n^(n-2)*x^n/n! ). This implies (by a theorem of Wright) that a(n) ~ exp(1/2)*n^(n-2). - N. J. A. Sloane, May 12 2008 [Corrected by Philippe Flajolet, Aug 17 2008]
E.g.f.: exp(T - T^2/2), where T = T(x) = Sum_{n>=1} n^(n-1)*x^n/n! is Euler's tree function (see A000169). - Len Smiley, Dec 12 2001
Shifts 1 place left under the hyperbinomial transform (cf. A088956). - Paul D. Hanna, Nov 03 2003
a(0) = 1, a(n) = Sum_{j=0..n-1} C(n-1,j) (j+1)^(j-1) a(n-1-j) if n>0. - Alois P. Heinz, Sep 15 2008

More terms from Michael Somos, Aug 22 2002

A105599 Triangle read by rows: T(n, m) = number of forests with n nodes and m labeled trees. Also number of forests with exactly n - m edges on n labeled nodes.

Original entry on oeis.org

1, 1, 1, 3, 3, 1, 16, 15, 6, 1, 125, 110, 45, 10, 1, 1296, 1080, 435, 105, 15, 1, 16807, 13377, 5250, 1295, 210, 21, 1, 262144, 200704, 76608, 18865, 3220, 378, 28, 1, 4782969, 3542940, 1316574, 320544, 55755, 7056, 630, 36, 1, 100000000, 72000000, 26100000, 6258000, 1092105, 143325, 14070, 990, 45, 1

Offset: 1

Washington Bomfim, Apr 14 2005; revised May 19 2005

Row sums equal A001858 (number of forests of labeled trees with n nodes).
Also the Bell transform of A000272(n+1). For the definition of the Bell transform see A264428. - Peter Luschny, Jan 27 2016
The permutohedron (convex hull of permutations on 1,...,n in R^n) has Ehrhart polynomial Sum_{k=0..n-1} T(n,n-k) t^k. - Matthieu Josuat-Vergès, Mar 31 2018

			T(3, 2) = 3 because there are 3 such forests with 3 nodes and 2 trees.
Triangle begins:
      1;
      1,     1;
      3,     3,    1;
     16,    15,    6,    1;
    125,   110,   45,   10,   1;
   1296,  1080,  435,  105,  15,  1;
  16807, 13377, 5250, 1295, 210, 21, 1;

B. Bollobas, Graph Theory - An Introductory Course (Springer-Verlag, New York, 1979)

Alois P. Heinz, Rows n = 1..141, flattened
E. Britikov, Asymptotic number of forests from unrooted trees, Mat. Zametki (1988).
Mathoverflow, Is there a formula for the number of labeled forests with k components on n vertices?

Cf. A033185, A106240.
Rows reflected give A138464. - Alois P. Heinz, Sep 10 2008
Columns k=1-10 give: A000272, A083483, A239910, A240681, A240682, A240683, A240684, A240685, A240686, A240687.
T(2n,n) gives A302112.

Flat(List([1..11],n->List([1..n],m->(1/Factorial(m)*Sum([0..m],j->(-1/2)^j*Binomial(m,j)*Binomial(n-1,m+j-1)*n^(n-m-j)*Factorial(m+j)))))); # Muniru A Asiru, Apr 01 2018

T:= proc(n,m) option remember;
      if n<0 then 0
    elif n=m then 1
    elif m<1 or m>n then 0
    else add(binomial(n-1,j-1)*j^(j-2)*T(n-j,m-1), j=1..n-m+1)
      fi
    end:
seq(seq(T(n, m), m=1..n), n=1..12); # Alois P. Heinz, Sep 10 2008
# The function BellMatrix is defined in A264428.
# Adds (1,0,0,0, ..) as column 0.
BellMatrix(n -> (n+1)^(n-1), 9); # Peter Luschny, Jan 27 2016

f[list_]:=Select[list,#>0&];Flatten[Map[f, Transpose[Table[t = Sum[n^(n - 2) x^n/n!, {n, 1, 20}];Drop[Range[0, 8]! CoefficientList[Series[t^k/k!, {x, 0, 8}], x],1], {k, 1, 8}]]]] (* Geoffrey Critzer, Nov 22 2011 *)
T[n_, m_] := Sum[(-1/2)^j*Binomial[m, j]*Binomial[n-1, m+j-1]*n^(n-m-j)*(m + j)!, {j, 0, m}]/m!; Table[T[n, m], {n, 1, 10}, {m, 1, n}] // Flatten (* Jean-François Alcover, Jan 09 2016, after Max Alekseyev *)
rows = 10;
t = Table[(n+1)^(n-1), {n, 0, rows}];
T[n_, k_] := BellY[n, k, t];
Table[T[n, k], {n, 1, rows}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 22 2018, after Peter Luschny *)

{ T(n,m) = sum(j=0,m, (-1/2)^j * binomial(m,j) * binomial(n-1,m+j-1) * n^(n-m-j)* (m+j)! )/m! } /* Max Alekseyev, Oct 08 2014 */

T(n,m) = Sum_{k=1..n-m+1} binomial(n-1,k-1)*k^(k-2)*T(n-k,m-1), T(n,0) = 0 if n > 0, T(0,0) = 1. - Vladeta Jovovic and Washington Bomfim
The value of T(n, m) can be calculated by the formula in Bollobas, pp. 172, exercise 44. Also T(n, m) = sum N/D over the partitions of n, 1*K(1) + 2*K(2) + ... + n*K(n), with exactly m parts, where N = n! * Product_{i = 1..n} i^( (i-2) * K(i) ) and D = Product_{i = 1..n} ( K(i)! * (i!)^K(i) ).
From Peter Bala, Aug 14 2012: (Start)
E.g.f.: A(x,t) := exp(t*F(x)) = 1 + t*x + (t + t^2)*x^2/2! + (3*t + 3*t^2 + t^3)*x^3/3! + ..., where F(x) = sum {n >= 1} n^(n-2)*x^n/n! is the e.g.f. for labeled trees (see A000272). The row polynomials R(n,t) are thus a sequence of binomial type polynomials.
Differentiating A(x,t) w.r.t. x yields A'(x,t) = t*A(x,t)*F'(x) leading to the recurrence equation for the row polynomials R(n,t) = t*sum {k = 0..n-1} (k+1)^(k-1)*binomial(n-1,k)*R(n-k-1,t) with R(0,t) = 1 and R(1,t) = t: the above recurrence for the table entries follows from this.
(End)
T(n,m) = (1/m!) * Sum_{j=0..m} (-1/2)^j * binomial(m,j) * binomial(n-1,m+j-1) * n^(n-m-j)* (m+j)!. Due to A. Renyi. - Max Alekseyev, Oct 08 2014
T(n,m) = (n!/m!)*Sum_{k_1+...+k_m=n, k_i>=1} Product_{j=1..m} k_j^(k_j-2)/k_j!. See Britikov reference. - Roland Vincze, Apr 18 2020

A302112 Number of forests with 2n nodes and n labeled trees. Also number of forests with exactly n edges on 2n labeled nodes.

Original entry on oeis.org

1, 1, 15, 435, 18865, 1092105, 79170399, 6899167275, 702495121185, 81857181636945, 10742799174110575, 1568060617808784099, 251983549987815976785, 44207398164005846558425, 8407483858740005340602175, 1722961754698440157865926875, 378507890849998531093971032385

Offset: 0

Alois P. Heinz, Apr 01 2018

nonn

From Washington Bomfim, Mar 20 2020: (Start)
Considering the uniform model of graph evolution [see the Flajolet link] with 2n vertices initially isolated, the probability of the occurrence of an acyclic graph at the critical point n is P(n) = a(n) * n! * 2^n / (2n)^(2n). Concerning the permutation model [see same link] the corresponding probability is Pp(n) = a(n) / A331505(2n).
By Kotesovec's approximation of a(n), P(n) ~ c1/n^(1/6), and Pp(n) ~ e^(3/4)* P(n), c1 = 0.577983047665... = (2/3)^(1/3) * sqrt(Pi) / Gamma(1/3).
In both models the presence of cycles in graphs evolving near the critical time should be estimated by the above approximations. (End)

Alois P. Heinz, Table of n, a(n) for n = 0..310
P. Flajolet, D. E. Knuth, and B. Pittel, The first cycles in an evolving graph, Discrete Mathematics, 75(1-3):167-215, 1989.

Cf. A000272, A138464, A331500, A331505.

T:= proc(n, m) option remember; `if`(n<0, 0, `if`(n=m, 1,
      `if`(m<1 or m>n, 0, add(binomial(n-1, j-1)*j^(j-2)*
       T(n-j, m-1), j=1..n-m+1))))
    end:
a:= n-> T(2*n, n):
seq(a(n), n=0..20);

Flatten[{1, Table[Sum[(-1)^k * Binomial[n, k] * Binomial[2*n - 1, n - k] * 2^(n - 2*k) * n^(n - k) * (n + k)!, {k, 0, n} ] / n!, {n, 1, 20}]}] (* Vaclav Kotesovec, Jul 19 2019 *)
Table[(-1)^n * HypergeometricPFQ[{1 - 2*n, -n}, {1, -2*n}, 4*n] * (2*n)! / (n!*2^n), {n, 0, 20}] (* Vaclav Kotesovec, Jul 19 2019 *)
Table[(-1)^n * 2^n * Gamma[n + 1/2] * (2*n*Hypergeometric1F1[1 - n, 2, 4*n] + LaguerreL[n, 4*n]) / Sqrt[Pi], {n, 0, 20}] (* Vaclav Kotesovec, Feb 19 2020 *)

a(n) = A105599(2*n,n) = A138464(2*n,n).
a(n) ~ c * 2^n * exp(n) * n^(n - 2/3), where c = 0.2305818... = 1 / (2^(1/6) * 3^(1/3) * Gamma(1/3)) [symbolic expression for c is conjectural]. - Vaclav Kotesovec, Jul 20 2019, updated Feb 20 2020
a(n) = (1/n!) * Sum_{j=0..n} (-1/2)^j * binomial(n,j) * binomial(2*n-1,n+j-1) * (2*n)^(n-j) * (n+j)!. - Jon E. Schoenfield, Jan 13 2020
a(n) = (-1)^n * (2*n)! * (Laguerre(n, 4*n) + 2*n*hypergeometric1F1(1 - n, 2, 4*n)) / (n! * 2^n). - Vaclav Kotesovec, Feb 19 2020
a(n) = (A332679(n) - 2*n*A332680(n)) * binomial(2*n, n) / 2^n. - Vaclav Kotesovec, Feb 20 2020
a(n) = (2*n)! * Sum_{P(2*n,n)} Product_{p=1..2*n} f(p)^c_p / (c_p! * p!^c_p), where f(n) = A000272(n) = n^(n-2) and P(2*n,n) are the partitions of 2*n with n parts, 1*c_1 + 2*c_2 + ... + (2*n)*c_n; c_1, c_2, ..., c_(2*n) >= 0.
- Washington Bomfim, Apr 05 2020

A083483 Number of forests with two connected components in the complete graph K_{n}.

Original entry on oeis.org

0, 1, 3, 15, 110, 1080, 13377, 200704, 3542940, 72000000, 1656409535, 42568187904, 1208912928522, 37603105146880, 1271514111328125, 46443371157258240, 1822442358054692408, 76461926986744528896, 3415753581721829617275

Offset: 1

Woong Kook (andrewk(AT)math.uri.edu), Jun 08 2003

nonn

Note that the above sequence is dominated by the sequence n^{n-2} (n > 0), A000272, which enumerates the number of spanning trees in K_{n} : 1, 1, 3, 16, 125, 1296, 16807, 262144, ... This is a consequence of the result in [EKT] which shows that the sequence of independent set numbers of cycle matroid of K_{n} is (strictly) monotone increasing (when n > 3).

W. Kook, Categories of acyclic graphs and automorphisms of free groups, Ph.D. thesis (G. Carlsson, advisor), Stanford University, 1996.

Vincenzo Librandi, Table of n, a(n) for n = 1..200
N. Eaton, W. Kook, and L. Thoma, Monotonicity for complete graphs, preprint
A. Kassel, R. Kenyon, and W. Wu, Random two-component spanning forests, Ann. Inst. H. Poincaré Probab. Statist., 51 (2015), 1457-1464.
C. J. Liu and Yutze Chow, On operator and formal sum methods for graph enumeration problems, SIAM J. Algebraic Discrete Methods, 5 (1984), no. 3, 384--406. MR0752043 (86d:05059). See Eq. (47). - From _N. J. A. Sloane_, Apr 09 2014

Cf. A000272, A053506, A239910.

Column m=2 of A105599. A diagonal of A138464. - Alois P. Heinz, Apr 10 2014

[n^(n-4)*(n-1)*(n+6)/2 : n in [1..20]]; // Vincenzo Librandi, Apr 10 2014

f:=n->(n-1)!*n^(n-4)*(n+6)/(2*(n-2)!); [seq(f(n),n=2..30)]; # N. J. A. Sloane, Apr 09 2014

(* first 20 terms starting with n=1 *) T := Sum[i^(i - 2)*(x^i)/i!, {i, 1, 20}]; T2 := Expand[(T^{2})/2! ]; C2[i_] := Coefficient[T2, x^{i}]*i!; M := MatrixForm[Table[C2[i], {i, 20}]]; M
Table[n^(n - 4) (n - 1) (n + 6)/2, {n, 1, 40}] (* Vincenzo Librandi, Apr 10 2014 *)

for(n=1,30, print1(n^(n-4)*(n-1)*(n+6)/2, ", ")) \\ G. C. Greubel, Nov 14 2017

E.g.f.: T(x)^{2}/2!, where T(x) is the e.g.f. for the number of spanning trees in K_{n}, i.e., T(x) = Sum_{i>=1} i^(i-2)*x^i/i!.
E.g.f.: (1/8)*LambertW(-x)^2*(2+LambertW(-x))^2. - Vladeta Jovovic, Jul 08 2003
a(n) = n^(n-4)*(n-1)*(n+6)/2. - Vaclav Kotesovec, Oct 18 2013

Edited by N. J. A. Sloane, Apr 09 2014

A136605 Triangle read by rows: T(n,k) = number of forests on n unlabeled nodes with k edges (n>=1, 0<=k<=n-1).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 3, 3, 1, 1, 2, 4, 6, 6, 1, 1, 2, 4, 7, 11, 11, 1, 1, 2, 4, 8, 14, 23, 23, 1, 1, 2, 4, 8, 15, 29, 46, 47, 1, 1, 2, 4, 8, 16, 32, 60, 99, 106, 1, 1, 2, 4, 8, 16, 33, 66, 128, 216, 235, 1, 1, 2, 4, 8, 16, 34, 69, 143, 284, 488, 551, 1, 1, 2, 4, 8, 16, 34, 70, 149, 315, 636, 1121, 1301

Offset: 1

N. J. A. Sloane, May 09 2008

			Triangle begins:
1
1,1
1,1,1
1,1,2,2
1,1,2,3,3
1,1,2,4,6,6 <- T(6,3) = 4 forests on 6 nodes with 3 edges.
1,1,2,4,7,11,11
1,1,2,4,8,14,23,23
1,1,2,4,8,15,29,46,47
1,1,2,4,8,16,32,60,99,106
1,1,2,4,8,16,33,66,128,216,235
1,1,2,4,8,16,34,69,143,284,488,551
1,1,2,4,8,16,34,70,149,315,636,1121,1301
1,1,2,4,8,16,34,71,152,330,710,1467,2644,3159

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, pp. 58-59.

Alois P. Heinz, Rows n = 1..141, flattened

Row sums give A005195. Rightmost diagonal gives A000055. Cf. A001858, A138464.

Rows converge to A215930. Reflected table is A095133. - Alois P. Heinz, Apr 11 2014

with(numtheory):
b:= proc(n) option remember; `if`(n<=1, n, (add(add(
      d*b(d), d=divisors(j)) *b(n-j), j=1..n-1))/ (n-1))
    end:
t:= n-> `if`(n=0, 1, b(n)-(add(b(k)*b(n-k), k=0..n)-
        `if`(irem(n, 2)=0, b(n/2), 0))/2):
g:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, expand(add(binomial(t(i)+j-1, j)*
       g(n-i*j, i-1)*x^j, j=0..n/i))))
    end:
T:= n-> (p-> seq(coeff(p, x, n-i), i=0..n-1))(g(n$2)):
seq(T(n), n=1..14);  # Alois P. Heinz, Apr 11 2014

b[n_] := b[n] = If[n <= 1, n, (Sum[Sum[d*b[d], {d, Divisors[j]}]*b[n-j], {j, 1, n-1}])/(n-1)]; t[n_] := If[n == 0, 1, b[n] - (Sum[b[k]*b[n-k], {k, 0, n}] - If[Mod[n, 2] == 0, b[n/2], 0])/2]; g[n_, i_] := g[n, i] = If[n == 0, 1, If[i < 1, 0, Expand[Sum[Binomial[t[i] + j - 1, j]*g[n - i*j, i-1]*x^j, {j, 0, n/i}]]]]; T[n_] := CoefficientList[g[n, n], x] // Reverse // Most; Table[T[n], {n, 1, 14}] // Flatten (* Jean-François Alcover, Apr 16 2014, after Alois P. Heinz *)

G.f.: Product_{k>=1} 1/(1 - y^(k-1)*x^k)^A000055(k). - Geoffrey Critzer, Nov 10 2014

A362968 Number of integral points in 2 * permutohedron of order n.

Original entry on oeis.org

1, 3, 19, 201, 3081, 62683, 1598955, 49180113, 1773405649, 73410669171, 3432267261699, 178922825114905, 10291053760222041, 647436905815864011, 44229766376059342171, 3260749830852693615777, 258039101519624535653025

Offset: 1

Max Alekseyev, Jun 17 2023

nonn

Every vectorial sum of two permutations represents an integral point in 2*permutohedron, however the converse does not hold. Hence, a(n) >= A175176(n) for all n, where the equality holds only for n <= 5.

Number of points up to their components order is given by A007747.

C. Bebeacua, T. Mansour, A. Postnikov, and S. Severini. On the X-rays of permutations, arXiv:math/0506334 [math.CO], 2005.
Wikipedia, Permutohedron.

Cf. A007747, A138464, A175176, A362967.

w := LambertW(-2*x): egf := exp(-w * (2 + w) / 4): ser := series(egf, x, 20):
seq(n! * coeff(ser, x, n), n = 1..17); # Peter Luschny, Jun 19 2023

a362968(n) = my(x=y+O(y^(n+1))); n! * polcoef( exp(-lambertw(-2*x)/2 - lambertw(-2*x)^2/4), n );

a(n) = Sum_{k=0..n-1} A138464(n,k) * 2^k, which is the value of the Ehrhart polynomial of permutohedron at t = 2.

E.g.f.: exp(-W(-2*x)/2 - W(-2*x)^2/4), where W() is the Lambert function.

A239910 Number of forests with three connected components in the complete graph K_{n}.

Original entry on oeis.org

0, 0, 1, 6, 45, 435, 5250, 76608, 1316574, 26100000, 587030895, 14780620800, 412069511139, 12604714327296, 419801484375000, 15123782440058880, 586049426860524300, 24307340986526810112, 1074495780444130114509, 50429952000000000000000

Offset: 1

N. J. A. Sloane, Apr 09 2014

nonn

Equation (47) of Liu-Chow (1984) also gives the analogous formulas for four and five components. (They should also be entered into the OEIS, in case someone wants to help.)

Vincenzo Librandi, Table of n, a(n) for n = 1..200
C. J. Liu and Yutze Chow, On operator and formal sum methods for graph enumeration problems, SIAM J. Algebraic Discrete Methods, 5 (1984), no. 3, 384-406. MR0752043 (86d:05059).

Cf. A000272, A083483.

Column m=3 of A105599. A diagonal of A138464. - Alois P. Heinz, Apr 10 2014

[(n-1)*(n-2)*n^(n-6)*(n^2+13*n+60)/8: n in [1..20]]; // Vincenzo Librandi, Apr 10 2014

f := n-> (n-1)*(n-2)*n^(n-6)*(n^2+13*n+60)/8; [seq(f(n),n=3..20)];

Table[(n-1)*(n-2) * n^(n - 6) * (n^2 + 13 n + 60)/8, {n, 1, 20}] (* Vincenzo Librandi, Apr 10 2014, simplified by Vaclav Kotesovec, Feb 20 2020 *)

From Harry Richman, Aug 17 2022: (Start)
a(n) = n^(n-6)*(n-1)*(n-2)*(n^2+13*n+60)/8.
E.g.f.: T(x)^{3}/3!, where T(x) is the e.g.f. for the number of spanning trees in K_{n} A000272, i.e., T(x) = Sum_{i>=1} i^(i-2)*x^i/i!. (End)

A144164 Number of simple graphs on n labeled nodes, where each maximally connected subgraph is either a tree or a cycle, also row sums of A144163, A215861.

Original entry on oeis.org

1, 1, 2, 8, 45, 338, 3304, 40485, 602075, 10576466, 214622874, 4941785261, 127282939615, 3625467047196, 113140481638088, 3838679644895477, 140681280613912089, 5538276165405744140, 233086092164091031114, 10443453353262112373541, 496313160155209940833001

Offset: 0

Alois P. Heinz, Sep 12 2008

nonn

			a(3) = 8, because there are 8 simple graphs on 3 labeled nodes, where each maximally connected subgraph is either a tree or a cycle, with edge-counts 0(1), 1(3), 2(3), 3(1):
.1.2. .1-2. .1.2. .1.2. .1-2. .1.2. .1-2. .1-2.
..... ..... ../.. .|... ../.. .|/.. .|... .|/..
.3... .3... .3... .3... .3... .3... .3... .3...

Alois P. Heinz, Table of n, a(n) for n = 0..140
Index entries for sequences related to trees

Row sums of triangles A144163, A215861.
The unlabeled version is A215978.
Cf. A138464, A144161, A007318, A000142.

f:= proc(n,k) option remember; local j; if k=0 then 1 elif k<0 or n<=k then 0 elif k=n-1 then n^(n-2) else add(binomial(n-1,j) *f(j+1,j) *f(n-1-j,k-j), j=0..k) fi end:
c:= proc(n,k) option remember; local i,j; if k=0 then 1 elif k<0 or n add(T(n,k), k=0..n):
seq(a(n), n=0..25);

f[n_, k_] := f[n, k] = Module[{j}, Which[k == 0, 1, k<0 || n <= k, 0, k == n-1, n^(n-2), True, Sum[Binomial[n-1, j]*f[j+1, j]*f[n-1-j, k-j], {j, 0, k}]]]; c[n_, k_] := c[n, k] = Module[{i, j}, If[k == 0, 1, If[k<0 || nJean-François Alcover, Mar 05 2014, after Alois P. Heinz *)

from sympy.core.cache import cacheit
from sympy import binomial, prod
@cacheit
def f(n, k): return 1 if k==0 else 0 if k<0 or n<=k else n**(n - 2) if k == n - 1 else sum(binomial(n - 1, j)*f(j + 1, j)*f(n - 1 - j, k - j) for j in range(k + 1))
@cacheit
def c(n, k): return 1 if k==0 else 0 if k<0 or nIndranil Ghosh, Aug 07 2017

a(n) = Sum_{k=0..n} A144163(n,k).

a(n) ~ c * n^(n-2), where c = 1.66789780037... . - Vaclav Kotesovec, Sep 08 2014

A144163 Triangle T(n,k), n>=0, 0<=k<=n, read by rows: T(n,k) = number of simple graphs on n labeled nodes with k edges where each maximally connected subgraph is either a tree or a cycle.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 3, 3, 1, 1, 6, 15, 20, 3, 1, 10, 45, 120, 150, 12, 1, 15, 105, 455, 1185, 1473, 70, 1, 21, 210, 1330, 5565, 14469, 18424, 465, 1, 28, 378, 3276, 19635, 81060, 213990, 280200, 3507, 1, 36, 630, 7140, 57393, 334656, 1385076, 3732300, 5029218, 30016

Offset: 0

Alois P. Heinz, Sep 12 2008

			T(4,3) = 20, because there are 20 simple graphs on 4 labeled nodes with 3 edges, where each maximally connected subgraph is either a tree or a cycle, 16 of these graphs consist of a single tree with 4 nodes and 4 consist of a cycle with 3 and a tree with 1 node:
  .1-2. .1-2. .1.2. .1.2. .1-2. .1-2. .1-2. .1-2. .1-2. .1.2.
  .|\.. ../|. ..\|. .|/.. .|... ...|. ../.. ..\.. .|.|. .|.|.
  .4.3. .4.3. .4-3. .4-3. .4-3. .4-3. .4-3. .4-3. .4.3. .4-3.
  .
  .1.2. .1.2. .1-2. .1.2. .1.2. .1.2. .1.2. .1.2. .1-2. .1-2.
  .|/|. .|\|. ..X.. ..X|. ..X.. .|X.. ../|. .|\.. .|/.. ..\|.
  .4.3. .4.3. .4.3. .4.3. .4-3. .4.3. .4-3. .4-3. .4.3. .4.3.
Triangle begins:
  1;
  1,  0;
  1,  1,  0;
  1,  3,  3,   1;
  1,  6, 15,  20,   3;
  1, 10, 45, 120, 150, 12;

Alois P. Heinz, Rows n = 0..140, flattened
Index entries for sequences related to trees

Columns k=0-3 give: A000012, A000217, A050534, A093566.
Main diagonal gives A001205.
Row sums give A144164.
Cf. A138464, A144161, A007318, A000142.

f:= proc(n,k) option remember; local j; if k=0 then 1 elif k<0 or n<=k then 0 elif k=n-1 then n^(n-2) else add(binomial(n-1,j) *f(j+1,j) *f(n-1-j,k-j), j=0..k) fi end:
c:= proc(n,k) option remember; local i,j; if k=0 then 1 elif k<0 or n

f[n_, k_] := f[n, k] = Which[k == 0, 1, k<0 || n <= k, 0, k == n-1, n^(n-2), True, Sum[Binomial[n-1, j]*f[j+1, j]*f[n-1-j, k-j], {j, 0, k}]]; c[n_, k_] := c[n, k] = Which[k == 0, 1 , k<0 || nJean-François Alcover, Jan 21 2014, translated from Alois P. Heinz's Maple code *)

T(n,k) = A138464(n,k) + Sum_{j=3..k} C(n,j) A138464(n-j,k-j) A144161 (j,j).

A240681 Number of forests with n labeled nodes and 4 trees.

Original entry on oeis.org

1, 10, 105, 1295, 18865, 320544, 6258000, 138437310, 3428282880, 94059655690, 2833936641536, 93055995703125, 3308477732618240, 126642365068676240, 5193315990469140480, 227160198500847385884, 10557603840000000000000, 519578655591970045435770

Offset: 4

Alois P. Heinz, Apr 10 2014

nonn

Alois P. Heinz, Table of n, a(n) for n = 4..200

Column m=4 of A105599. A diagonal of A138464.

T:= proc(n, m) option remember; `if`(n<0, 0, `if`(n=m, 1,
      `if`(m<1 or m>n, 0, add(binomial(n-1, j-1)*j^(j-2)*
       T(n-j, m-1), j=1..n-m+1))))
    end:
a:= n-> T(n, 4):
seq(a(n), n=4..30);

Table[n^(n-8) * (n-3)*(n-2)*(n-1)*(n^3 + 21*n^2 + 202*n + 840)/48,{n,4,20}] (* Vaclav Kotesovec, Sep 06 2014 *)

a(n) = n^(n-8) * (n-3)*(n-2)*(n-1)*(n^3 + 21*n^2 + 202*n + 840)/48. - Vaclav Kotesovec, Sep 06 2014

cp's OEIS Frontend

A001858 Number of forests of trees on n labeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A105599 Triangle read by rows: T(n, m) = number of forests with n nodes and m labeled trees. Also number of forests with exactly n - m edges on n labeled nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Formula

A302112 Number of forests with 2n nodes and n labeled trees. Also number of forests with exactly n edges on 2n labeled nodes.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A083483 Number of forests with two connected components in the complete graph K_{n}.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A136605 Triangle read by rows: T(n,k) = number of forests on n unlabeled nodes with k edges (n>=1, 0<=k<=n-1).

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A362968 Number of integral points in 2 * permutohedron of order n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Formula