login
This site is supported by donations 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

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

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: A058721 A086902 A265042 * A224879 A279198 A220092

Adjacent sequences:  A249751 A249752 A249753 * A249755 A249756 A249757

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 | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 23 02:22 EDT 2018. Contains 316518 sequences. (Running on oeis4.)