login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A048194 Total number of split graphs (chordal + chordal complement) on n vertices. 14
1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, 5067146, 67997750, 1224275498, 29733449510, 976520265678, 43425320764422, 2616632636247976, 213796933371366930, 23704270652844196754, 3569464106212250952762, 730647291666881838671052 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Also number of bipartite graphs with n vertices and no isolated vertices in distinguished bipartite block, up to isomorphism; so a(n) equals first differences of A049312. - Vladeta Jovovic, Jun 17 2000

All split graphs are perfect. - Falk Hüffner, Nov 29 2015

Inverse Euler transform gives A007776 with initial 1. - Andrew Howroyd, Oct 03 2018

LINKS

Alois P. Heinz, Table of n, a(n) for n = 1..40

B. A. Chat, S. Pirzada, A. Iványi, Recognition of split-graphic sequences, Acta Universitatis Sapientiae, Informatica, 6, 2 (2014) 252-286.

Karen L. Collins, Ann N. Trenk, Finding Balance: Split Graphs and Related Classes, arXiv:1706.03092 [math.CO], June 2017.

Karen L. Collins, Ann N. Trenk, Finding Balance: Split Graphs and Related Classes, Electron. J. Combin., 25 (2018), #P1.73.

S. Hougardy, Home Page

S. Hougardy, Classes of perfect graphs, Discr. Math. 306 (2006), 2529-2571.

Vladeta Jovovic, Binary matrices up to row and column permutations.

Gordon F. Royle, Counting set covers and split graphs, J. Integer Seqs., Vol. 3 (2000), #00.2.6.

J. M. Troyka, Split graphs: combinatorial species and asymptotics, Electron. J. Combin., 26 (2019), #P2.42.

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

Index entries for sequences related to posets

FORMULA

a(n) = A049312(n) - A049312(n-1) (see the Collins and Trenk link, Thms. 5 and 15). - Justin M. Troyka, Oct 29 2018

a(n) ~ A049312(n) ~ 1/n! Sum_{k=0..n} binomial(n,k) * 2^(k(n-k)) (see the Troyka link, Thms. 3.7 and 3.10). - Justin M. Troyka, Oct 29 2018

MATHEMATICA

b[n_, i_] := b[n, i] = If[n == 0, {0}, If[i < 1, {}, Flatten @ Table[ Map[ Function[{p}, p + j*x^i], b[n - i*j, i - 1]], {j, 0, n/i}]]];

g[n_, k_] := g[n, k] = Sum[Sum[2^Sum[Sum[GCD[i, j]*Coefficient[s, x, i]* Coefficient[t, x, j], {j, 1, Exponent[t, x]}], {i, 1, Exponent[s, x]}]/ Product[i^Coefficient[s, x, i]*Coefficient[s, x, i]!, {i, 1, Exponent[s, x]}]/Product[i^Coefficient[t, x, i]*Coefficient[t, x, i]!, {i, 1, Exponent[t, x]}], {t, b[n + k, n + k]}], {s, b[n, n]}];

A[n_, k_] := g[Min[n, k], Abs[n - k]];

a[d_] := Sum[A[n, d - n], {n, 0, d}] - Sum[A[n, d - n - 1], {n, 0, d - 1}];

Table[a[n], {n, 1, 25}] (* Jean-François Alcover, May 26 2019, after Alois P. Heinz in A049312 *)

CROSSREFS

Cf. A007776, A048192, A048193, A049312, A055080.

Detlef Pauly remarks that this is the unlabeled analog of A001831.

Sequence in context: A148074 A130866 A123458 * A148075 A058718 A148076

Adjacent sequences:  A048191 A048192 A048193 * A048195 A048196 A048197

KEYWORD

nonn,nice,easy

AUTHOR

Gordon F. Royle

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 March 30 12:10 EDT 2020. Contains 333125 sequences. (Running on oeis4.)