|
|
A179534
|
|
Number of labeled split graphs on n vertices.
|
|
2
|
|
|
1, 2, 8, 58, 632, 9654, 202484, 5843954, 233064944, 12916716526, 998745087980, 108135391731690, 16434082400952296, 3513344943520006118, 1058030578581541945316, 449389062270642095128546, 269419653009366144571801568, 228157953744571034350576205790
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
A split graph is a graph whose vertices can be partitioned into a clique and an independent set. - Justin M. Troyka, Oct 28 2018
|
|
REFERENCES
|
V. Bina, Enumeration of Labeled Split Graphs and Counts of Important Superclasses. In Adacher L., Flamini, M., Leo, G., Nicosia, G., Pacifici, A., Picialli, V. (Eds.). CTW 2011, Villa Mondragone, Frascati, pp. 72-75 (2011).
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 1 + Sum_{k=2..n} binomial(n,k) ( (2^k-1)^(n-k) - Sum_{j=1..n-k) j*k*binomial(n-k,j)*(2^(k-1)-1)^(n-k-j) /(j+1) ).
a(n) = [ Sum_{k=0..n} binomial(n,k) 2^(k(n-k)) ] - [ n Sum_{k=0..n-1} binomial(n-1,k)*2^(k(n-k-1)) ] (see the Troyka link, Cor. 3.4).
a(n) ~ A047863(n) (see Bender, Richmond, and Wormald, Cor. 1). (End)
|
|
MAPLE
|
A179534 := proc(n) local a, k; a := 1 ; for k from 2 to n do a := a+binomial(n, k)*( (2^k-1)^(n-k) -add(j*k*binomial(n-k, j)*(2^(k-1)-1)^(n-k-j)/(j+1), j=1..n-k) ) end do: a ; end proc: # R. J. Mathar, Jun 21 2011
|
|
MATHEMATICA
|
a[n_] := 1 + Sum[Binomial[n, k]*((2^k-1)^(n-k) - Sum[j*k*Binomial[n-k, j]*(2^(k-1)-1)^(n-k-j)/(j+1), {j, 1, n-k}]), {k, 2, n}]; Array[a, 20] (* Stefano Spezia, Oct 29 2018 *)
|
|
PROG
|
(PARI)
b(n) = {sum(k=0, n, binomial(n, k)*2^(k*(n-k)))} \\ A047863(n)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(12)-a(16) corrected and terms a(17) and beyond from Andrew Howroyd, Jun 06 2021
|
|
STATUS
|
approved
|
|
|
|