A331505 -id:A331505 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

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

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

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

A331563 Number of labeled cyclic graphs with n edges and 2n vertices.

Original entry on oeis.org

0, 0, 20, 1610, 129654, 11688369, 1194822915, 137766789810, 17758192128830, 2535895233070628, 397875362655895761, 68087081506276861665, 12626853606957534296975, 2523446241515288646389325

Offset: 1

Washington Bomfim, Jan 20 2020

nonn

			a(4) = 1610 since we have 3 non-isomorphic cyclic graphs with 4 edges and 8 nodes. (See illustration below.)
To compute a(4) we can consult A057500, which provides the number of labeled connected unicycles. Because A057500(4)=15, and knowing that there are 3 labeled squares, we have 15-3 = 12 Paw Graphs [see Weisstein link]. So graph 1 is labeled in 12 * C(8,4) = 840 ways. Graph 2 is labeled in 3* C(8,4) = 210 ways. A105599 gives 10 as the number of labeled forests with 5 nodes and 4 components, so graph 3 is labeled in 10 * C(8,3) = 560 ways. We have 840 + 210 + 560 = 1610.
.
  graph 1    graph 2    graph 3 (triangle + forest with
                                 5 nodes and 4 components)
   *--*       *--*       *--* *
   | /|       |  |       | /  |
   |/ |       |  |       |/   |
   *  *       *--*       *    *
  * * * *    * * * *      * * *

Eric Weisstein's World of Mathematics, Paw Graph

Cf. A331505, A302112, A057500, A105599.

a(n) = A331505(2n) - A302112(n).

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A331501 Decimal expansion of exp(3/4).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A331502 Decimal expansion of exp(4/9).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A331563 Number of labeled cyclic graphs with n edges and 2n vertices.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula