This site is supported by donations to The OEIS Foundation.



Please make a donation to keep the OEIS running. We are now in our 55th year. In the past year we added 12000 new sequences and reached 8000 citations (which often say "discovered thanks to the OEIS"). We need to raise money to hire someone to manage submissions, which would reduce the load on our editors and speed up editing.
Other ways to donate

(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A240936 Number of ways to partition the (vertex) set {1,2,...,n} into any number of classes and then select some unordered pairs (edges) <a,b> such that a and b are in distinct classes of the partition. 20
1, 1, 3, 21, 337, 11985, 930241, 155643329, 55638770689, 42200814258433, 67536939792143361, 227017234854393949185, 1596674435594864988020737, 23421099407847007850007154689, 714530983411175509576743561314305, 45227689798343820164634911814524846081 (list; graph; refs; listen; history; text; internal format)



The elements of a class are allowed to be used multiple times to form the unordered pairs.

Equivalently, a(n) is the sum of the number of k-colored graphs on n labeled nodes taken over k colors, 1<=k<=n, where labeled graphs using k colors that differ only by a permutation of the k colors are considered to be the same.

Also the number of ways to choose a stable partition of a simple graph on n vertices. A stable partition of a graph is a set partition of the vertices where no edge has both ends in the same block. - Gus Wiseman, Nov 24 2018


Alois P. Heinz, Table of n, a(n) for n = 0..75


a(n) = n! * 2^C(n,2) * [x^n] exp(E(x)-1) where E(x) is Sum_{n>=0} x^n/(n!*2^C(n,2)).

a(n) = Sum_{k=1..n} A058843(n,k) for n>0.


a(2)=3 because the empty graph with 2 nodes is counted twice (once for each partition of 2) and the complete graph is counted once. 2+1=3.


b:= proc(n, k) b(n, k):= `if`(k=1, 1, add(binomial(n, i)*

      2^(i*(n-i))*b(i, k-1)/k, i=1..n-1))


a:= n-> `if`(n=0, 1, add(b(n, k), k=1..n)):

seq(a(n), n=0..20);  # Alois P. Heinz, Aug 04 2014


nn=15; e[x_]:=Sum[x^n/(n!*2^Binomial[n, 2]), {n, 0, nn}]; Table[n!2^Binomial[n, 2], {n, 0, nn}]CoefficientList[Series[Exp[(e[x]-1)], {x, 0, nn}], x]


(PARI) seq(n)={Vec(serconvol(sum(j=0, n, x^j*j!*2^binomial(j, 2)) + O(x*x^n), exp(sum(j=1, n, x^j/(j!*2^binomial(j, 2))) + O(x*x^n))))} \\ Andrew Howroyd, Dec 01 2018


Cf. A000569, A001187, A006125, A058843, A277203, A321979.

Sequence in context: A118410 A125054 A113085 * A083228 A052445 A186271

Adjacent sequences:  A240933 A240934 A240935 * A240937 A240938 A240939




Geoffrey Critzer, Aug 03 2014



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 December 14 12:04 EST 2019. Contains 329979 sequences. (Running on oeis4.)