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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A179534 Number of labeled split graphs on n vertices. 2
1, 2, 8, 58, 632, 9654, 202484, 5843954, 233064944, 12916716526, 998745087980, 108135391731689, 16434082400952295, 3513344943520006169, 1058030578581541938616, 449389062270642127911734 (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

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

E. A. Bender, L. B. Richmond, and N. C. Wormald, Almost all chordal graphs split, J. Austral. Math. Soc. (Series A), 38 (1985), 214-221.

V. Bina, Multidimensional probability distributions: Structure and learning, PHD Thesis. Fac. of Management, University of Economics in Prague (2011).

J. M. Troyka, Split graphs: combinatorial species and asymptotics, arXiv:1803.07248 [math.CO], 2018.

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) ).

From Justin M. Troyka, Oct 28 2018: (Start)

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) - n*A047863(n-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

(R) print(1); print(1); for (n in 2:20) { N.spl <- 1; for (k in 2:n) { tmp <- 0; for (j in 1:(n-k)) { tmp <- tmp + j/(j+1)*k*choose(n-k, j)*(2^(k-1)-1)^(n-k-j); }; N.spl <- N.spl + choose(n, k)*((2^k-1)^(n-k) - tmp); }; print(n); print(N.spl); }

CROSSREFS

Cf. A048194, A058862, A006125.

Sequence in context: A319590 A005804 A162067 * A256034 A086907 A132186

Adjacent sequences:  A179531 A179532 A179533 * A179535 A179536 A179537

KEYWORD

nonn

AUTHOR

Vladislav Bina, Jul 18 2010

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 February 15 16:25 EST 2019. Contains 320136 sequences. (Running on oeis4.)