A331501 -id:A331501 - cp's OEIS frontend

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

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

A379411 a(n) = n + floor(ns/r) + floor(nt/r), where r = e^(1/4), s = e^(1/2), t = e^(3/4).

Original entry on oeis.org

3, 7, 10, 15, 19, 22, 26, 31, 34, 38, 43, 46, 50, 54, 58, 62, 66, 70, 74, 77, 81, 86, 89, 93, 98, 101, 105, 109, 113, 117, 121, 125, 129, 133, 136, 141, 145, 148, 153, 156, 160, 164, 168, 172, 176, 180, 184, 188, 191, 196, 200, 203, 208, 212, 215, 219, 223

Offset: 1

Clark Kimberling, Jan 18 2025

nonn

This sequence and A379412 and A379413 partition the positive integers; see A184812 for a proof. For each k in A000027, write "a" if k=A379411(n) for some n, "b" if k=A379412(n) for some n, and "c" if k=A379413(n) for some n. Concatenating these letters for k = 1,2,3,... spells the following infinite word:

cbacbcabcacbcbacbcabcacbcabcbcacbacbcabcbcacbacbcabccabcbacbcabccabcbacbcacbacbcabcbcacbacbcabccbacbacbcabccabcbacbcacbcabcbacbcacbcabcabccbacb...

Cf. A184812, A379412, A379413.

Cf. A092042, A019774, A331501.

r = E^(1/4); s = E^(1/2); t = E^(3/4);
Table[n + Floor[n*s/r] + Floor[n*t/r], {n, 1, 120}]  (* A379411 *)
Table[n + Floor[n*r/s] + Floor[n*t/s], {n, 1, 120}]  (* A379412 *)
Table[n + Floor[n*r/t] + Floor[n*s/t], {n, 1, 120}]  (* A379413 *)

a(n) = n + floor(n*r) + floor(n*r^2), where r = e^(1/4).

A379413 a(n) = n + floor(nr/t) + floor(ns/t), where r = e^(1/4), s = e^(1/2), t = e^(3/4).

Original entry on oeis.org

1, 4, 6, 9, 11, 13, 16, 18, 21, 23, 25, 28, 30, 32, 35, 37, 40, 42, 44, 47, 49, 52, 53, 56, 59, 61, 64, 65, 68, 71, 73, 75, 78, 80, 83, 85, 87, 90, 92, 95, 96, 99, 102, 104, 107, 108, 111, 114, 116, 118, 120, 123, 126, 128, 130, 132, 135, 138, 139, 142, 144

Offset: 1

Clark Kimberling, Jan 18 2025

nonn

This sequence and A379411 and A379412 partition the positive integers; see A378142 for a proof.

Cf. A378142, A379411, A379412.

Cf. A092042, A019774, A331501.

r = E^(1/4); s = E^(1/2); t = E^(3/4);
Table[n + Floor[n*s/r] + Floor[n*t/r], {n, 1, 120}]  (* A379411 *)
Table[n + Floor[n*r/s] + Floor[n*t/s], {n, 1, 120}]  (* A379412 *)
Table[n + Floor[n*r/t] + Floor[n*s/t], {n, 1, 120}]  (* A379413 *)

a(n) = n + floor(n/r) + floor(n*r^2), where r = e^(1/4).

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

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Formula

A379411 a(n) = n + floor(n*s/r) + floor(n*t/r), where r = e^(1/4), s = e^(1/2), t = e^(3/4).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A379413 a(n) = n + floor(n*r/t) + floor(n*s/t), where r = e^(1/4), s = e^(1/2), t = e^(3/4).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

A331502 Decimal expansion of exp(4/9).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A379411 a(n) = n + floor(ns/r) + floor(nt/r), where r = e^(1/4), s = e^(1/2), t = e^(3/4).

A379413 a(n) = n + floor(nr/t) + floor(ns/t), where r = e^(1/4), s = e^(1/2), t = e^(3/4).