A054592 -id:A054592 - cp's OEIS frontend

A327078 Binomial transform of A001187 (labeled connected graphs), if we assume A001187(1) = 0.

1, 1, 2, 8, 61, 969, 31738, 2069964, 267270033, 68629753641, 35171000942698, 36024807353574280, 73784587576805254653, 302228602363365451957793, 2475873310144021668263093202, 40564787336902311168400640561084

Offset: 0

Gus Wiseman, Aug 25 2019

nonn

Here we consider that there is no nonempty connected graph with one vertex (different from A001187 and A182100).

			The a(0) = 1 through a(3) = 8 edge-sets:
  {}  {}  {}       {}
          {{1,2}}  {{1,2}}
                   {{1,3}}
                   {{2,3}}
                   {{1,2},{1,3}}
                   {{1,2},{2,3}}
                   {{1,3},{2,3}}
                   {{1,2},{1,3},{2,3}}

Cf. A001187, A006129, A054592, A182100, A287689, A327075.

b:= proc(n) option remember; `if`(n=0, 1, 2^(n*(n-1)/2)-add(
      k*binomial(n, k)*2^((n-k)*(n-k-1)/2)*b(k), k=1..n-1)/n)
    end:
a:= n-> add(b(n-j)*binomial(n, j), j=0..n-2)+1:
seq(a(n), n=0..18);  # Alois P. Heinz, Aug 27 2019

csm[s_]:=With[{c=Select[Tuples[Range[Length[s]],2],And[OrderedQ[#],UnsameQ@@#,Length[Intersection@@s[[#]]]>0]&]},If[c=={},s,csm[Sort[Append[Delete[s,List/@c[[1]]],Union@@s[[c[[1]]]]]]]]];
Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Length[csm[#]]<=1&]],{n,0,5}]

a(n) = A182100(n) - n.

a(n) = A287689(n) + 1.

A327367 Number of labeled simple graphs with n vertices, at least one of which is isolated.

Original entry on oeis.org

0, 1, 1, 4, 23, 256, 5319, 209868, 15912975, 2343052576, 675360194287, 383292136232380, 430038382710483623, 956430459603341708896, 4224538833207707658410103, 37106500399796746894085512140, 648740170822904504303462104598943

Offset: 0

Gus Wiseman, Sep 04 2019

nonn

The unlabeled version is A000088(n - 1).
Labeled graphs with no isolated vertices are A006129.
Covering graphs with at least one endpoint are A327227.
Cf. A006125, A006129, A054592, A245797, A327103, A327105.

b:= proc(n) option remember; `if`(n=0, 1,
      2^binomial(n, 2)-add(b(k)*binomial(n, k), k=0..n-1))
    end:
a:= n-> 2^(n*(n-1)/2)-b(n):
seq(a(n), n=0..17);  # Alois P. Heinz, Sep 04 2019

Table[Length[Select[Subsets[Subsets[Range[n],{2}]],Union@@#!=Range[n]&]],{n,0,5}]

b(n) = sum(k=0, n, (-1)^(n-k)*binomial(n, k)*2^binomial(k, 2)); \\ A006129
a(n) = 2^(n*(n-1)/2) - b(n); \\ Michel Marcus, Sep 05 2019

a(n) = A006125(n) - A006129(n).

A360603 Triangle read by rows. T(n, k) = A360604(n, k) * A001187(k) for 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 2, 2, 4, 0, 8, 6, 12, 38, 0, 64, 32, 48, 152, 728, 0, 1024, 320, 320, 760, 3640, 26704, 0, 32768, 6144, 3840, 6080, 21840, 160224, 1866256, 0, 2097152, 229376, 86016, 85120, 203840, 1121568, 13063792, 251548592

Offset: 0

Peter Luschny, Feb 20 2023

			Triangle T(n, k) starts:
[0] 1;
[1] 0,       1;
[2] 0,       1,      1;
[3] 0,       2,      2,     4;
[4] 0,       8,      6,    12,    38;
[5] 0,      64,     32,    48,   152,    728;
[6] 0,    1024,    320,   320,   760,   3640,   26704;
[7] 0,   32768,   6144,  3840,  6080,  21840,  160224,  1866256;
[8] 0, 2097152, 229376, 86016, 85120, 203840, 1121568, 13063792, 251548592.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973.

Algorithms for Competitive Programming, Counting labeled graphs, cp-algorithms.
Albert Nijenhuis and Herbert S Wilf, The enumeration of connected graphs and linked diagrams, Journal of Combinatorial Theory, Vol. 27(3), 1979, Pages 356-359.
Eric Weisstein's World of Mathematics, Connected Graph.
Eric Weisstein's World of Mathematics, Labeled Graph.

Cf. A006125 Graphs on n labeled nodes, T(n+1, 1) and Sum_{k=0..n} T(n, k).
Cf. A054592 Disconnected labeled graphs with n nodes, Sum_{k=0..n-1} T(n, k).
Cf. A001187 Connected labeled graphs with n nodes, T(n, n).
Cf. A123903 Isolated nodes in all simple labeled graphs on n nodes, T(n+2, 2).
Cf. A053549 Labeled rooted connected graphs, T(n+1, n).
Cf. A275462 Leaves in all simple labeled connected graphs on n nodes T(n+2, n).
Cf. A060818 gcd_{k=0..n} T(n, k) = gcd(n!, 2^n).
Cf. A143543 Labeled graphs on n nodes with k connected components.
Cf. A095340 Total number of nodes in all labeled graphs on n nodes.
Cf. A360604, A360860 (accumulation triangle).

T := (n, k) -> 2^binomial(n-k, 2)*binomial(n-1, k-1)*A001187(k):
for n from 0 to 9 do seq(T(n, k), k = 0..n) od;
# Based on the recursion:
Trow := proc(n) option remember; if n = 0 then return [1] fi;
seq(2^binomial(n-k, 2) * binomial(n-1, k-1) * Trow(k)[k+1], k = 1..n-1);
2^(n*(n-1)/2) - add(j, j = [%]); [0, %%, %] end:
seq(print(Trow(n)), n = 0..8);

A001187[n_] := A001187[n] = 2^((n - 1)*n/2) - Sum[Binomial[n - 1, k]*2^((k - n + 1)*(k - n + 2)/2)*A001187[k + 1], {k, 0, n - 2}];
T[n_, k_] := 2^Binomial[n - k, 2]*Binomial[n - 1, k - 1]*A001187[k];
Table[T[n, k], {n, 0, 8}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 02 2023, after Peter Luschny in A001187 *)

from math import comb as binomial
from functools import cache
@cache
def A360603Row(n: int) -> list[int]:
    if n == 0: return [1]
    s = [2 ** (((k - n + 1) * (k - n)) // 2) * binomial(n - 1, k - 1) * A360603Row(k)[k] for k in range(1, n)]
    b = 2 ** (((n - 1) * n) // 2) - sum(s)
    return [0] + s + [b]

T(n, k) = 2^binomial(n-k, 2)*binomial(n-1, k-1) * A001187(k).
Recursion over the rows of the triangle: Set row(0) = [1] where [.] denotes a 0-based list. Assume now all rows(j) for j < n computed, next compute r = [2^binomial(n-k, 2) * binomial(n-1, k-1) * row(k)[k] for k = 1..n-1] and s = 2^(n*(n-1)/2) - Sum(r). Then row(n) = [0] & r & [s], where '&' denotes the concatenation of lists. (See the Python program for an implementation.)
T(n, n) = A001187(n) (connected labeled graphs).
T(n-1, n) = A053549(n-1) for n >= 1 (labeled rooted connected graphs).
T(n, 1) = Sum_{k>=0} T(n-1, k) = A006125(n-1) for n >= 1 (all labeled graphs).
Sum_{k=0..n-1} T(n, k) = A054592(n) for n >= 1 (disconnected labeled graphs).
See additional formulas in the cross-references.

A360860 Accumulation triangle of A360603 read by rows.

Original entry on oeis.org

1, 0, 1, 0, 1, 2, 0, 2, 4, 8, 0, 8, 14, 26, 64, 0, 64, 96, 144, 296, 1024, 0, 1024, 1344, 1664, 2424, 6064, 32768, 0, 32768, 38912, 42752, 48832, 70672, 230896, 2097152, 0, 2097152, 2326528, 2412544, 2497664, 2701504, 3823072, 16886864, 268435456

Offset: 0

Peter Luschny, Feb 26 2023

			[0] 1;
[1] 0,     1;
[2] 0,     1,     2;
[3] 0,     2,     4,     8;
[4] 0,     8,    14,    26,    64;
[5] 0,    64,    96,   144,   296,  1024;
[6] 0,  1024,  1344,  1664,  2424,  6064,  32768;
[7] 0, 32768, 38912, 42752, 48832, 70672, 230896, 2097152;

Cf. A360603, A006125, A054592.

from itertools import accumulate
def A360860Row(n: int) -> list[int]:
    return list(accumulate(A360603Row(n)))
for n in range(8): print(A360860Row(n))

cp's OEIS Frontend

A054593 Number of disconnected labeled digraphs with n nodes.

Views

Author

Keywords

Links

Crossrefs

Formula

A327078 Binomial transform of A001187 (labeled connected graphs), if we assume A001187(1) = 0.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

Mathematica

Formula

A327367 Number of labeled simple graphs with n vertices, at least one of which is isolated.

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A360603 Triangle read by rows. T(n, k) = A360604(n, k) * A001187(k) for 0 <= k <= n.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A360860 Accumulation triangle of A360603 read by rows.

Views

Author

Keywords

Examples

Crossrefs

Programs

Python