login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A322064 Number of ways to choose a stable partition of a simple connected graph with n vertices. 7
1, 1, 1, 7, 141, 6533, 631875, 123430027, 48659732725, 39107797223409, 64702785181953175, 221636039917857648631, 1575528053913118966200441, 23249384407499950496231003021, 711653666389829384034090082068939, 45128328085994437067694854477617868995 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,4

COMMENTS

A stable partition of a graph is a set partition of the vertices where no non-singleton edge has both ends in the same block.

LINKS

Andrew Howroyd, Table of n, a(n) for n = 0..75

EXAMPLE

The a(3) = 7 stable partitions. The simple connected graph is on top, and below is a list of all its stable partitions.

  {1,3}{2,3}     {1,2}{2,3}     {1,2}{1,3}     {1,2}{1,3}{2,3}

  --------       --------       --------       --------

  {{1,2},{3}}    {{1,3},{2}}    {{1},{2,3}}    {{1},{2},{3}}

  {{1},{2},{3}}  {{1},{2},{3}}  {{1},{2},{3}}

MATHEMATICA

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];

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

Table[Sum[Length[Select[Subsets[Complement[Subsets[Range[n], {2}], Union@@Subsets/@stn]], And[Union@@#==Range[n], Length[csm[#]]==1]&]], {stn, sps[Range[n]]}], {n, 5}]

PROG

(PARI) \\ See A322278 for M.

seq(n)={concat([1], (M(n)*vectorv(n, i, 1))~)} \\ Andrew Howroyd, Dec 01 2018

CROSSREFS

Row sums of A322278.

Cf. A000110, A000569, A001187, A006125, A048143, A229048, A240936, A245883, A277203, A321911, A321979, A322063, A322065.

Sequence in context: A221267 A070074 A051397 * A179569 A082157 A258176

Adjacent sequences:  A322061 A322062 A322063 * A322065 A322066 A322067

KEYWORD

nonn

AUTHOR

Gus Wiseman, Nov 25 2018

EXTENSIONS

Terms a(7) and beyond from Andrew Howroyd, Dec 01 2018

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 11 18:50 EST 2019. Contains 329031 sequences. (Running on oeis4.)