A302112 -id:A302112 - cp's OEIS frontend

A331500 a(n) = A302112(n) * n! * 2^n.

1, 2, 120, 20880, 7244160, 4193683200, 3648171985920, 4450790792448000, 7251098441261875200, 15208619045076276019200, 39919072914444753469440000, 128188338317208930555828633600, 494389344738688341547326898176000, 2255096937522349816552823932846080000

Offset: 0

Washington Bomfim, Feb 02 2020

nonn

Considering the uniform model of graph evolution [Flajolet] with 2n vertices initially isolated, the probability of the occurrence of an acyclic graph at time n is P(n) = a(n)/(2n)^(2n). See the following.
Since endpoints of edges are in 1..2n, if at time n we write side by side the 2n endpoints of the included n edges, we can have any one of the (2n)^(2n) strings of length 2n in 2n characters [A085534]. A single forest G(V,E) corresponds to n! * 2^n sequences because the n edges of E(G) are exchanged for n! ways, and each permutation corresponds to 2^n sequences since each edge u-v can be in a sequence as u-v or v-u. So the number of distinct sequences of length 2n on 2n symbols formed by A302112(n) forests is a(n) = A302112(n) * n! * 2^n.
If t < n, P(n) is a lower bound of P(t). If t > n, P(n) is an upper bound of P(t), P(t) the probability of an acyclic graph in time t.
The expected value of the number of trials until the appearance of a forest at time n is ev(n) = 1/P(n) = (2*n)^(2*n) / a(n). Below is a table of n and corresponding values of ev(n) for selected values of n.
        ----------------------------------------------
n      | 1 |  10 |  100 | 1000 | 10^4 |  10^5 |  10^6 |
       |---+-----+------+------+------+-------+-------|
ev(n)  | 2 |2.63 | 3.76 | 5.48 | 8.03 | 11.79 | 17.30 |
        ----------------------------------------------
(Expected values for n >= 10^4 determined using Vaclav Kotesovec's approximation of A302112.)
To obtain a bijection h: S -> {1,2,...,n}, where S is a given set of n elements (keys) it is only necessary to determine an acyclic graph from the elements of S. Because the expected number of generated graphs is small when the number of nodes N = 2n we can use space proportional to 2n to store a graph. If n = 10^5, for example, from table above we expect to generate 11.79 graphs. For details about determination of bijections see [Havas].

			If n = 1 a(n) = 2, a(n)/(2*n)^(2*n) = 1/2. If we toss two coins we obtain one of the four ordered pairs: (H,H), (H,T), (T,H), or (T,T). The probability of a forest is 1/2, and the expected value of trials until a forest is 2.

Washington Bomfim, Experimental expected values
P. Flajolet, D. E. Knuth, and B. Pittel, The first cycles in an evolving graph, Discrete Mathematics, 75(1-3):167-215, 1989.
George Havas and Bohdan S. Majewski, Optimal algorithms for minimal perfect hashing

Cf. A000165, A085534, A302112, 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)*n!*2^n:
seq(a(n), n=0..14);  # Alois P. Heinz, Jun 24 2021

Array[(-1)^#*HypergeometricPFQ[{1 - 2 #, -#}, {1, -2 #}, 4 #]*(2 #)! &, 7] (* Michael De Vlieger, Feb 07 2020, after Vaclav Kotesovec at A302112 *)

A302112(n) = { \\ From Jon E. Schoenfield's formula in A302112.
sum(j = 0, n, (-1/2)^j * binomial(n, j) * binomial(2*n-1, n+j-1) * (2*n)^(n-j) * (n+j)!) / n! };
a(n) = A302112(n) * n! * 2^n;

a(n) = A302112(n) * n! * 2^n = A000165(n) * A302112(n).

Edited by Washington Bomfim, Jun 14 2021

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

A138464 Triangle read by rows: T(n, k) is the number of forests on n labeled nodes with k edges. T(n, k) for n >= 1 and 0 <= k <= n-1.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, May 09 2008

The rows of the triangle give the coefficients of the Ehrhart polynomials of integral Coxeter permutahedra of type A. These polynomials count lattice points in a dilated lattice polytope. For a definition see Ardila et al. (p. 1158), the generating functions of these polynomials for the classical root systems are given in theorem 5.2 (p. 1163). - Peter Luschny, May 01 2021

			Triangle begins:
[1]  1;
[2]  1,  1;
[3]  1,  3,   3;
[4]  1,  6,  15,   16;
[5]  1, 10,  45,  110,  125;
[6]  1, 15, 105,  435, 1080,  1296;
[7]  1, 21, 210, 1295, 5250, 13377, 16807;

Alois P. Heinz, Rows n = 1..141, flattened
Federico Ardila, Matthias Beck, and Jodi McWhirter, The arithmetic of Coxeter permutahedra, Rev. Acad. Colomb. Cienc. Ex. Fis. Nat. 44(173):1152-1166, 2020.
John Riordan and N. J. A. Sloane, Correspondence, 1974

Row sums give A001858. Rightmost diagonal gives A000272. Cf. A136605.
Rows reflected give A105599. - Alois P. Heinz, Oct 28 2011
Cf. A088956.
Lower diagonals give: A083483, A239910, A240681, A240682, A240683, A240684, A240685, A240686, A240687. - Alois P. Heinz, Apr 11 2014
T(2n,n) gives A302112.
For Ehrhart polynomials of integral Coxeter permutahedra of classical type cf. this sequence (type A), A343805 (type B), A343806 (type C), A343807 (type D).

T:= proc(n) option remember; if n=0 then 0 else T(n-1) +n^(n-1) *x^n/n! fi end: TT:= proc(n) option remember; expand(T(n) -T(n)^2/2) end: f:= proc(k) option remember; if k=0 then 1 else unapply(f(k-1)(x) +x^k/k!, x) fi end: A:= proc(n,k) option remember; series(f(k)(TT(n)), x,n+1) end: aa:= (n,k)-> coeff(A(n,k), x,n) *n!: a:= (n,k)-> aa(n,n-k) -aa(n,n-k-1): seq(seq(a(n,k), k=0..n-1), n=1..10);  # Alois P. Heinz, Sep 02 2008
alias(W = LambertW): EhrA := exp(-W(-t*x)/t - W(-t*x)^2/(2*t)):
ser := series(EhrA, x, 12): cx := n -> n!*coeff(ser, x, n):
T := n -> seq(coeff(cx(n), t, k), k=0..n-1):
seq(T(n), n = 1..10); # Peter Luschny, Apr 30 2021

t[0, 0] = 1; t[n_ /; n >= 1, k_] /; (0 <= k <= n-1) := t[n, k] = Sum[(i+1)^(i-1)*Binomial[n-1, i]*t[n-i-1, k-i], {i, 0, k}]; t[, ] = 0; Table[t[n, k], {n, 1, 10}, {k, 0, n-1}] // Flatten (* Jean-François Alcover, Jan 14 2014, after Peter Bala *)
gf := E^(-(ProductLog[-(t x)] (2 + ProductLog[-(t x)]))/(2 t));
ser := Series[gf, {x, 0, 12}]; cx[n_] := n! Coefficient[ser, x, n];
Table[CoefficientList[cx[n], t], {n, 1, 10}] // Flatten  (* Peter Luschny, May 01 2021 *)

From Peter Bala, Aug 14 2012: (Start)
T(n+1,k) = Sum_{i=0..k} (i+1)^(i-1)*binomial(n,i)*T(n-i,k-i) with T(0,0)=1.
Recurrence equation for row polynomials R(n,t): R(n,t) = Sum_{k=0..n-1} (k+1)^(k-1)*binomial(n-1,k)*t^k*R(n-k-1,t) with R(0,t) = R(1,t) = 1.
The production matrix for the row polynomials of the triangle is obtained from A088956 and starts:
    1    t
    1    1    t
    3    2    1    t
   16    9    3    1    t
  125   64   18    4    1   t
(End)
E.g.f.: exp( Sum_{n >= 1} n^(n-2)*t^(n-1)*x^n/n! ). - Peter Bala, Nov 08 2015
T(n, k) = [t^k] n! [x^n] exp(-W(-t*x)/t - W(-t*x)^2/(2*t)), where W denotes the Lambert function. - Peter Luschny, Apr 30 2021 [Typo corrected after note from Andrew Howroyd, Peter Luschny, Jun 20 2021]

More terms from Alois P. Heinz, Sep 02 2008

A332679 a(n) = (-1)^n * n! * Laguerre(n, 4*n).

Original entry on oeis.org

1, 3, 34, 642, 16920, 571880, 23577552, 1147008912, 64304389504, 4081584090240, 289302692908800, 22648001532831488, 1940655970832219136, 180654087647513945088, 18153823412468554639360, 1958590905998560664832000, 225799980396482832660529152, 27702168947661388727726931968

Offset: 0

Vaclav Kotesovec, Feb 19 2020

nonn

Vaclav Kotesovec, Table of n, a(n) for n = 0..335

Cf. A277423, A332692, A332693, A332694, A332695.

Cf. A277418, A295408, A302112, A332680.

Table[(-1)^n*n!*LaguerreL[n, 4*n], {n, 0, 20}]
Join[{1}, Table[n! * Sum[(-1)^(n-k) * Binomial[n, k] * (4*n)^k/k!, {k, 0, n}], {n, 1, 20}]]
Table[(-1)^n*n!*Hypergeometric1F1[-n, 1, 4*n], {n, 0, 20}]

a(n) = (-1)^n*n!*pollaguerre(n, 0, 4*n); \\ Michel Marcus, Feb 05 2021

A302112(n) = (a(n) - 2*n*A332680(n)) * binomial(2*n, n) / 2^n.
a(n) / (n*A332680(n)) ~ 2.
a(n) ~ c * n^(n + 1/6) * exp(n), where c = Gamma(1/3) / (2^(5/6) * 3^(1/6) * sqrt(Pi)) = 0.706332637459...

A331505 Number of labeled graphs with n nodes and floor(n/2) edges.

Original entry on oeis.org

1, 1, 3, 15, 45, 455, 1330, 20475, 58905, 1221759, 3478761, 90858768, 256851595, 8093990190, 22760723700, 840261910995, 2353351951665, 99615373765775, 278110855548955, 13278694407181203, 36976937738226486

Offset: 1

Washington Bomfim, Jan 18 2020

Considering the permutation model of graph evolution (see the Flajolet reference) with 2n vertices initially isolated, the probability of the occurrence of an acyclic graph at the critical point n is Pp(n) = A302112(n)/a(2n). Note that a(2n) is the number of labeled graphs with 2n nodes and n edges.
Since a(2n) = C(C(2n, 2), n) we have Pp(n)= A302112(n)/C(C(2n, 2), n).
Therefore, by Vaclav Kotesovec's approximation in A302112, Pp(n) ~ e^(3/4) * P(n), where P(n) = c1 / n^(1/6) is the corresponding probability in the uniform model. Cf. A331500.
If t < n, P(n) is a lower bound of P(t). If t > n, P(n) is an upper bound of P(t). Here P(t) is the probability of an acyclic graph in time t.
Concerning the permutation model, the presence of cycles in graphs evolving near the critical time should be estimated by the above approximation.

			a(4) is 15 because for n = 4, floor(n/2) = 2, and there are two graphs with four points and two edges. See the figure below or the J. Riordan reference.
The non-isomorphic graphs with four nodes and two edges along with the corresponding number of labeled graphs are as follows:
.
  *--*     *  *
  |        |  |
  |        |  |
  *  *     *  *
   12        3
Pp(2) = A302112(2)/a(4) = 15/15 = 1. All the graphs with four nodes and two edges are acyclic.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 109.

Washington Bomfim, Approximation of Pp(n)
P. Flajolet, D. E. Knuth, and B. Pittel, The first cycles in an evolving graph, Discrete Mathematics, 75(1-3):167-215, 1989.
Carlos R. Lucatero, Combinatorial Enumeration of Graphs.

Cf. A000717, A084546, A331504, A302112 (numerators of Pp(n)), A331500, A331501.

C(x, y) = binomial(x, y);
a(n) = C(C(n,2), n\2);
A302112(n)={my(S=0, j); /* From Jon E. Schoenfield's formula in A302112. */
for(j = 0, n,
   S+=(-1/2)^j* C(n, j) * C(2*n-1, n+j-1) * (2*n)^(n-j) * (n+j)!
   );
(1/n!)*S
}; /* end A302112(n) */
c1 = (2/3)^(1/3) * sqrt(Pi) / gamma(1/3);
UpBoundP(n) = c1 / n^(1/6);            /* Approximation for P(n) */
UpBoundPp(n) = exp(3/4) * UpBoundP(n); /* Approximation for Pp(n) */
Pp(n) = A302112(n)/a(2*n);
Ratio(n) = UpBoundPp(n) / Pp(n);

a(n) = C( C(n,2), floor(n/2) ).

A331501 Decimal expansion of exp(3/4).

Original entry on oeis.org

2, 1, 1, 7, 0, 0, 0, 0, 1, 6, 6, 1, 2, 6, 7, 4, 6, 6, 8, 5, 4, 5, 3, 6, 9, 8, 1, 9, 8, 3, 7, 0, 9, 5, 6, 1, 0, 1, 3, 4, 4, 9, 1, 5, 8, 4, 7, 0, 2, 4, 0, 3, 4, 2, 1, 7, 7, 9, 1, 3, 3, 0, 3, 0, 8, 1, 0, 9, 8, 4, 5, 3, 3, 3, 6, 4, 0, 1, 2, 8, 2, 0, 0, 0, 2, 7, 9, 1, 5, 6, 0, 2, 6, 6, 6, 1, 5, 7, 9, 8, 2, 1, 8, 8, 8

Offset: 1

Washington Bomfim, Feb 27 2020

Considering graph evolutions (see the Flajolet link) with 2n vertices initially isolated, the probability of the occurrence of an acyclic graph at the critical point n in the uniform model, will be denoted by P(n). In the case of the permutation model, the respective probability will be denoted by Pp(n).

Pp(n) / P(n) ~ exp(3/4) since Pp(n) = A302112(n) / A331505(2n) = A302112(n) / C(C(2n,2), n), and P(n) = A302112(n) * n! * 2^n / (2n)^(2n), Pp(n) / P(n) = (2n)^(2n) / (C(C(2n,2), n) * n! * 2^n), and lim_{n->oo} Pp(n) / P(n) = exp(3/4).

			2.1170000166126746685453698198370956101344915847024...

Philippe Flajolet, Donald E. Knuth, and Boris Pittel, The first cycles in an evolving graph, Discrete Mathematics, Vol. 75, No. 1-3 (1989), pp. 167-215.
Leonard Giugiuc and Dan Stefan Marinescu, Problem 4257, Crux Mathematicorum, Vol. 43, No. 6 (2017), pp. 263 and 265; Solution to Problem 4257, ibid., Vol. 44, No. 6 (2018), pp. 268-270.
Index entries for transcendental numbers

Cf. A000178, A001113, A019774, A092042, A302112, A331500, A331502, A331505.

Maple
```
evalf(exp(3/4), 134);
```

RealDigits[Exp[3/4], 10, 100][[1]] (* Amiram Eldar, Apr 12 2022 *)

exp(3/4) \\ Charles R Greathouse IV, Nov 21 2024

Equals lim_{n->oo} Pp(n) / P(n) = lim_{n->oo} (2*n)^(2*n) / (binomial(binomial(2n,2), n) * n! * 2^n).

Equals lim_{n->oo} sqrt(n)/A000178(n)^(1/(n*(n+1))) (Giugiuc and Marinescu, 2017). - Amiram Eldar, Apr 12 2022

A332680 a(n) = -(-1)^n * n! * hypergeometric1F1(1 - n, 2, 4*n).

Original entry on oeis.org

-1, 1, 6, 78, 1576, 43320, 1507824, 63549808, 3145681536, 178865283456, 11488065875200, 822528662774016, 64957295774721024, 5609010346397166592, 525718830294548330496, 53154054477553828608000, 5766597997397483718344704, 668177890990349738366042112, 82355042760252520538828242944

Offset: 0

Vaclav Kotesovec, Feb 19 2020

sign

Vaclav Kotesovec, Table of n, a(n) for n = 0..336

Cf. A302112, A332679.

Table[-(-1)^n * n! * Hypergeometric1F1[1 - n, 2, 4*n], {n, 0, 20}]
Join[{-1}, Table[n! * Sum[(-1)^(n-k+1) * Binomial[n-1, k] * (4*n)^k / (k+1)!, {k, 0, n-1}], {n, 1, 20}]]

A302112(n) = (A332679(n) - 2*n*a(n)) * binomial(2*n, n) / 2^n.

a(n) ~ c * n^(n - 5/6) * exp(n), where c = Gamma(1/3) / (2^(11/6) * 3^(1/6) * sqrt(Pi)) = 0.3531663187295...

A332959 Triangle read by rows: T(n,k) is the number of labeled forests with n trees and 2n nodes and with the largest tree having exactly k nodes, (n >= 1, 2 <= k <= n+1).

Original entry on oeis.org

1, 3, 12, 15, 180, 240, 105, 5040, 6720, 7000, 945, 151200, 352800, 315000, 272160, 10395, 6029100, 21067200, 20790000, 17962560, 13311144, 135135, 276215940, 1387386000, 1765764000, 1471133664, 1211314104, 787218432, 2027025, 14983768800, 105945840000, 165225060000, 146023637760, 121131410400, 94466211840, 54717165360

Offset: 1

Washington Bomfim, Apr 13 2020

The first formula is based on Kolchin's formula (1.4.2) [see the Kolchin reference].

			Triangle T(n,k) begins:
      1;
      3,      12;
     15,     180,      240;
    105,    5040,     6720,     7000;
    945,  151200,   352800,   315000,   272160;
  10395, 6029100, 21067200, 20790000, 17962560, 13311144;
  ...
The graphs for T(2,2) and T(2,3) are illustrated below:
   o---o   :   o   o
           :   |
   o---o   :   o---o
T(2,2) = 3 since the graph on the left has 3 labelings.
T(2,3) = 12 since the graph on the right has 12 labelings.

V. F. Kolchin, Random Graphs. Encyclopedia of Mathematics and Its Applications 53. Cambridge Univ. Press, Cambridge, 1999, pp 30-31.

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)

Columns k=2..3 are A001147, A332960.
Row sums give A302112.
Main diagonal is A332958.
Cf. A000272, A001147, A302112, A332958, A332960.

T(n, k) = { my(S = 0);
  forpart(a = 2*n,
    if(a[n] == k,
      my(D = Set(a));
      my(Pr = prod(j=1, #D, my(p = D[j], c = #select(x->x==p, Vec(a))); p^((p-2)*c) / (p!^c*c!)));
       S += n!*Pr )
  , [1, k], [n, n]); (2*n)! / n! * S };

B(n,k)={my(p=sum(j=1, k, j^(j-2)*x^j/j!)); (2*n)!*polcoef( polcoef( exp(y*p + O(x*x^(2*n))), 2*n, x), n, y)}
T(n,k)={B(n,k)-B(n,k-1)} \\ Andrew Howroyd, May 08 2020

T(n,k) = ((2*n)!/n!) * Sum_{compositions p_1 + ... + p_n = 2*n, 1 <= p_i <= k}

Product_{j=1..n} f(p_j) / p_j!, where f(p_j) = A000272(p_j) = p_j^(p_j-2).

A331502 Decimal expansion of exp(4/9).

Original entry on oeis.org

1, 5, 5, 9, 6, 2, 3, 4, 9, 7, 6, 0, 6, 7, 8, 0, 7, 1, 5, 5, 3, 3, 7, 0, 9, 2, 8, 6, 9, 7, 9, 4, 7, 1, 1, 8, 6, 3, 9, 4, 8, 2, 4, 0, 1, 1, 4, 2, 2, 1, 4, 2, 3, 5, 4, 3, 9, 0, 2, 7, 8, 4, 3, 1, 5, 4, 3, 5, 6, 3, 8, 5, 0, 1, 3, 3, 1, 0, 6, 3, 2, 6, 4, 2, 7, 5, 8, 1, 6, 1, 2, 4, 9, 2, 9, 9, 4, 0, 1, 5, 4, 2, 9, 1, 6, 9

Offset: 1

Washington Bomfim, Mar 04 2020

Considering graph evolutions (see the Flajolet link) with 3n vertices initially isolated, the probability of the occurrence of an acyclic graph at the point n, (n = 1/3 * 3n), in the uniform model, will be denoted by P13(n). In the case of the permutation model, the respective probability will be denoted by Pp13(n).
Pp13(n) / P13(n) ~ exp(4/9) since Pp13(n) = f(n) / C(N,n), where f(n) is the number of labeled forests with 3n nodes and n edges, and C(N,n), N = 3n *(3n-1)/2 (see the Lucatero link) is the number of labeled graphs with 3n nodes and n edges.
Because P13(n) = f(n)* n!* 2^n / (3n)^(2n), Pp13(n) / P13(n) = (3n)^(2n) / (C(N,n)* n! *2^n), and Lim_{n->oo} Pp13(n) / P13(n) = exp(4/9).

			1.55962349760678071553370928697947118639482401142214...

P. Flajolet, D. E. Knuth, and B. Pittel, The first cycles in an evolving graph, Discrete Mathematics, 75(1-3):167-215, 1989.
Carlos R. Lucatero, Combinatorial Enumeration of Graphs.
Index entries for transcendental numbers

Cf. A001113, A019774, A092042, A302112, A331500, A331501, A331505.

Maple
```
evalf(exp(4/9), 134);
```

RealDigits[Exp[4/9],10,120][[1]] (* Harvey P. Dale, Jun 05 2023 *)

PARI
```
exp(4/9)
```

Equals Lim_{n->oo} Pp13(n) / P13(n) = Lim_{n->oo} (3*n)^(2*n) / (binomial((3*n *(3*n-1)/2), n) * n! * 2^n).

A332958 Number of labeled forests with 2n nodes consisting of n-1 isolated nodes and a labeled tree with n+1 nodes.

Original entry on oeis.org

1, 12, 240, 7000, 272160, 13311144, 787218432, 54717165360, 4375800000000, 396040894180360, 40038615905992704, 4473490414613093328, 547532797546896179200, 72869747140722656250000, 10478808079059531910348800, 1619337754490833097114916960

Offset: 1

Washington Bomfim, Apr 12 2020

Given 2n vertices, we can choose n-1 of them in C(2n, n-1) ways. For each of these ways there are A000272(n+1) trees. (possibilities)

			a(1) = 1. The forest is the tree of 2 nodes. It can be depicted by 1--2.
a(2) = 12. Given 4 nodes we can choose 1 of them in C(4,1) = 4 ways. For each of these 4 ways there are A000272(n+1) = (n+1)^(n-1) = 3 trees to complete the forest. The 12 forests can be represented by:
1  3-2-4,   1  2-3-4,   1  2-4-3,
2  3-1-4,   2  1-3-4,   2  1-4-3,
3  2-1-4,   3  1-2-4,   3  1-4-2,
4  2-1-3,   4  1-2-3,   4  1-3-2.

Cf. A000272, A001791, A302112.

a[n_] := Binomial[2n, n-1] * (n+1)^(n-1); Array[a,18] (* Amiram Eldar, Apr 12 2020 *)

PARI
```
a(n) = binomial(2*n,n-1) * (n+1)^(n-1);
```

a(n) = C(2*n,n-1) * (n+1)^(n-1).
a(n) = A001791(n) * A000272(n+1).
a(n) ~ exp(1) * 2^(2*n) * n^(n - 3/2) / sqrt(Pi).

cp's OEIS Frontend

A331500 a(n) = A302112(n) * n! * 2^n.

Views

Author

Keywords

Comments

Examples

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

A138464 Triangle read by rows: T(n, k) is the number of forests on n labeled nodes with k edges. T(n, k) for n >= 1 and 0 <= k <= n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A332679 a(n) = (-1)^n * n! * Laguerre(n, 4*n).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A331505 Number of labeled graphs with n nodes and floor(n/2) edges.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A331501 Decimal expansion of exp(3/4).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A332680 a(n) = -(-1)^n * n! * hypergeometric1F1(1 - n, 2, 4*n).

Views