login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A249754 The number of ordered pairs (G,S) where G is a simple labeled graph of order n and S is a subset of the vertices of G such that every element (vertex) in S is in the same connected component of G. 1
1, 2, 7, 51, 814, 27562, 1881132, 252352192, 66437453648, 34544598832464, 35670629662833824, 73386908116413720320, 301341520134976454507520, 2471940307185604520086223360, 40530105576773294054842498631680, 1328619037998490196005266772240585728, 87091009170221273841091095272951672891392 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
COMMENTS
Every graph paired with the empty set is included in this count. Every graph paired with a single vertex is also included.
a(n)/(2^binomial(n,2)*2^n) is the probability that a random simple labeled graph contains a random subset of its vertices in a single connected component.
LINKS
EXAMPLE
a(2)=7 because every such ordered pair is counted except (G,{1,2}) where G is the disconnected graph on 2 labeled nodes.
MATHEMATICA
nn = 16; f[list_] :=
Table[Sum[list[[i, j]]*Binomial[i, j], {j, 1, i}] + list[[i, 1]], {i,
1, Length[list]}];
a[x_] := Sum[2^Binomial[n, 2] x^n/n!, {n, 0, nn + 100}];
c[x_] := Log[a[x]]; Prepend[
f[Table[Table[
PadLeft[Range[0, nn]! CoefficientList[
Series[ D[c[ x], {x, n}] a[x], {x, 0, nn}], x], nn + n], {n,
1, nn}][[All, j]], {j, 1, nn}]], 1]
CROSSREFS
Sequence in context: A324513 A086902 A265042 * A224879 A345678 A279198
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Nov 04 2014
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 29 01:36 EDT 2024. Contains 371264 sequences. (Running on oeis4.)