A179534 Number of labeled split graphs on n vertices.

1, 2, 8, 58, 632, 9654, 202484, 5843954, 233064944, 12916716526, 998745087980, 108135391731690, 16434082400952296, 3513344943520006118, 1058030578581541945316, 449389062270642095128546, 269419653009366144571801568, 228157953744571034350576205790

Offset: 1

Author

Vladislav Bina, Jul 18 2010

Keywords

• nonn
• easy

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

• Andrew Howroyd, Table of n, a(n) for n = 1..100
• 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).
• Venkatesan Guruswami, Enumerative aspects of certain subclasses of perfect graphs, Discrete Mathematics 205 (1999), 97-117.
• J. M. Troyka, Split graphs: combinatorial species and asymptotics, arXiv:1803.07248 [math.CO], 2018-2019.
• J. M. Troyka, Split graphs: combinatorial species and asymptotics, Electron. J. Combin., 26 (2019), #P2.42.

Crossrefs

Cf. A047863, A048194, A058862, A006125.

Programs

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

PARI

b(n) = {sum(k=0, n, binomial(n, k)*2^(k*(n-k)))} \\ A047863(n)
a(n) = b(n) - n*b(n-1) \\ Andrew Howroyd, Jun 06 2021

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)

Extensions

a(12)-a(16) corrected and terms a(17) and beyond from Andrew Howroyd, Jun 06 2021