A308700 a(n) = n * 2^(n - 2) * (2^(n - 1) - 1).

0, 0, 2, 18, 112, 600, 2976, 14112, 65024, 293760, 1308160, 5761536, 25153536, 109025280, 469704704, 2013143040, 8589672448, 36506664960, 154617643008, 652832538624, 2748773826560, 11544861081600, 48378488553472, 202310091276288, 844424829468672, 3518436999168000

Offset

0,3

Comments

Given a pseudo-graph P of the set X = {1, 2, ..., n}, defined as a graph represented by the discrete topology on the set X (the power set of X), for n > 0, a(n) is the number of edges of the topological graph arising by deleting loops in P (see Theorem 3.3 in Kozae et al.).

Links

Table of n, a(n) for n=0..25.

A. M. Kozae, A. A. El Atik, A. Elrokh and M. Atef, New types of graphs induced by topological spaces, Journal of Intelligent & Fuzzy Systems, vol. 36, no. 6 (2019), pp. 5125-5134; on Research Gate.

Index entries for linear recurrences with constant coefficients, signature (12,-52,96,-64).

Formula

O.g.f.: -2 * x^2 * (-1 + 3*x)/((-1 + 2*x)^2 * (-1 + 4*x)^2).

E.g.f.: (1/2) * exp(2*x) * (-1 + exp(2*x)) * x.

a(n) = 12 * a(n - 1) - 52*a(n - 2) + 96*a(n - 3) - 64*a(n - 4) for n > 3.

a(n) = n * 2^(n - 2) * (2^(n - 1) - 1).

Lim_{n -> infinity} a(n)/a(n - 1) = 4.

a(n) = A082134(n) - A001787(n).

a(n) = A005843(A001787(n)) * A000225(n - 1).

a(n) = n * A006516(n - 1).

a(n) = n * A171476(n - 2).

a(n) = n * A171496(n - 3).

Example

For n = 3, the set X = {1,2,3},
  the power set 2^X = {{}, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, X} and the pseudo-graph P represented by 2^X has the following edges, here grouped into...
  simple loops:
  {1} --- {1}, {2} --- {2}, {3} --- {3} for a total of 3.
  double loops:
  {1,2} --- {1,2}, {1,3} --- {1,3}, {2,3} --- {2,3} for a total of 6 simple loops.
  triple loop:
  X --- X for a total of 3 simple loops.
  simple edges:
  {1} --- {1,2}, {1} --- {1,3}, {1} --- X, {2} --- {1,2}, {2} --- {2,3}, {2} --- X, {3} --- {1,3}, {3} --- {2,3}, {3} --- X, {1,2} --- {1,3}, {1,2} --- {2,3}, {1,3} --- {2,3} for a total of 12.
  double edges:
  {1,2} --- X, {1,3} --- X, {2,3} --- X for a total of 6 simple edges.
  By deleting the loops in P, there remain a total of a(3) = 12 + 6 = 18 edges for the topological graph arising from P.

Maple

a:=n->n*2^(n-2)*(2^(n-1)-1): seq(a(n), n=0..25);

Mathematica

Table[n 2^(n - 2)(2^(n - 1) - 1), {n, 0, 31}]

Prog

(GAP) Flat(List([0..25], n->n*2^(n-2)*(2^(n-1)-1)))
(Magma) [n*2^(n-2)*(2^(n-1)-1): n in [0..25]];
(Maxima) makelist(n*2^(n-2)*(2^(n-1)-1), n, 0, 25);
(PARI) a(n)=n*2^(n-2)*(2^(n-1)-1);

Crossrefs

Cf. A000225, A001787, A005843, A006516, A036239, A082134, A171476, A171496.

Cf. A082134 (total number of edges of the pseudo-graph P).

Sequence in context: A112328 A370732 A038721 * A064837 A224902 A027433

Adjacent sequences: A308697 A308698 A308699 * A308701 A308702 A308703

Keyword

nonn,easy

Author

Stefano Spezia, Jun 17 2019

Status

approved