|
%I #52 Sep 08 2022 08:46:21
%S 0,0,2,18,112,600,2976,14112,65024,293760,1308160,5761536,25153536,
%T 109025280,469704704,2013143040,8589672448,36506664960,154617643008,
%U 652832538624,2748773826560,11544861081600,48378488553472,202310091276288,844424829468672,3518436999168000
%N a(n) = n * 2^(n - 2) * (2^(n - 1) - 1).
%C 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.).
%H A. M. Kozae, A. A. El Atik, A. Elrokh and M. Atef, <a href="https://doi.org/10.3233/JIFS-171561">New types of graphs induced by topological spaces</a>, Journal of Intelligent & Fuzzy Systems, vol. 36, no. 6 (2019), pp. 5125-5134; on <a href="https://www.researchgate.net/publication/331824936_New_types_of_graphs_induced_by_topological_spaces">Research Gate</a>.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (12,-52,96,-64).
%F O.g.f.: -2 * x^2 * (-1 + 3*x)/((-1 + 2*x)^2 * (-1 + 4*x)^2).
%F E.g.f.: (1/2) * exp(2*x) * (-1 + exp(2*x)) * x.
%F a(n) = 12 * a(n - 1) - 52*a(n - 2) + 96*a(n - 3) - 64*a(n - 4) for n > 3.
%F a(n) = n * 2^(n - 2) * (2^(n - 1) - 1).
%F Lim_{n -> infinity} a(n)/a(n - 1) = 4.
%F a(n) = A082134(n) - A001787(n).
%F a(n) = A005843(A001787(n)) * A000225(n - 1).
%F a(n) = n * A006516(n - 1).
%F a(n) = n * A171476(n - 2).
%F a(n) = n * A171496(n - 3).
%e For n = 3, the set X = {1,2,3},
%e 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...
%e simple loops:
%e {1} --- {1}, {2} --- {2}, {3} --- {3} for a total of 3.
%e double loops:
%e {1,2} --- {1,2}, {1,3} --- {1,3}, {2,3} --- {2,3} for a total of 6 simple loops.
%e triple loop:
%e X --- X for a total of 3 simple loops.
%e simple edges:
%e {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.
%e double edges:
%e {1,2} --- X, {1,3} --- X, {2,3} --- X for a total of 6 simple edges.
%e By deleting the loops in P, there remain a total of a(3) = 12 + 6 = 18 edges for the topological graph arising from P.
%p a:=n->n*2^(n-2)*(2^(n-1)-1): seq(a(n),n=0..25);
%t Table[n 2^(n - 2)(2^(n - 1) - 1), {n, 0, 31}]
%o (GAP) Flat(List([0..25], n->n*2^(n-2)*(2^(n-1)-1)))
%o (Magma) [n*2^(n-2)*(2^(n-1)-1): n in [0..25]];
%o (Maxima) makelist(n*2^(n-2)*(2^(n-1)-1), n, 0, 25);
%o (PARI) a(n)=n*2^(n-2)*(2^(n-1)-1);
%Y Cf. A000225, A001787, A005843, A006516, A036239, A082134, A171476, A171496.
%Y Cf. A082134 (total number of edges of the pseudo-graph P).
%K nonn,easy
%O 0,3
%A _Stefano Spezia_, Jun 17 2019
|
