cp's OEIS Frontend

A048194 Total number of split graphs (chordal + chordal complement) on n vertices.

%I A048194 #84 Feb 16 2025 08:32:39
%S A048194 1,2,4,9,21,56,164,557,2223,10766,64956,501696,5067146,67997750,
%T A048194 1224275498,29733449510,976520265678,43425320764422,2616632636247976,
%U A048194 213796933371366930,23704270652844196754,3569464106212250952762,730647291666881838671052
%N A048194 Total number of split graphs (chordal + chordal complement) on n vertices.
%C A048194 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
%C A048194 All split graphs are perfect. - _Falk Hüffner_, Nov 29 2015
%C A048194 Inverse Euler transform gives A007776 with initial 1. - _Andrew Howroyd_, Oct 03 2018
%H A048194 Alois P. Heinz, <a href="/A048194/b048194.txt">Table of n, a(n) for n = 1..40</a>
%H A048194 B. A. Chat, S. Pirzada, and A. Iványi, <a href="http://www.acta.sapientia.ro/acta-info/C6-2/info62-7.pdf">Recognition of split-graphic sequences</a>, Acta Universitatis Sapientiae, Informatica, 6, 2 (2014) 252-286.
%H A048194 Karen L. Collins and Ann N. Trenk, <a href="https://arxiv.org/abs/1706.03092">Finding Balance: Split Graphs and Related Classes</a>, arXiv:1706.03092 [math.CO], June 2017.
%H A048194 Karen L. Collins and Ann N. Trenk, <a href="https://doi.org/10.37236/7091">Finding Balance: Split Graphs and Related Classes</a>, Electron. J. Combin., 25 (2018), #P1.73.
%H A048194 S. Hougardy, <a href="http://www.or.uni-bonn.de/~hougardy/">Home Page</a>.
%H A048194 S. Hougardy, <a href="http://dx.doi.org/10.1016/j.disc.2006.05.021">Classes of perfect graphs</a>, Discr. Math. 306 (2006), 2529-2571.
%H A048194 Vladeta Jovovic, <a href="/A005748/a005748.pdf">Binary matrices up to row and column permutations</a>.
%H A048194 Gordon F. Royle, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL3/ROYLE/royle.html">Counting set covers and split graphs</a>, J. Integer Seqs., Vol. 3 (2000), #00.2.6.
%H A048194 J. M. Troyka, <a href="https://doi.org/10.37236/8278">Split graphs: combinatorial species and asymptotics</a>, Electron. J. Combin., 26 (2019), #P2.42.
%H A048194 J. M. Troyka, <a href="https://arxiv.org/abs/1803.07248">Split graphs: combinatorial species and asymptotics</a>, arXiv:1803.07248 [math.CO], 2019.
%H A048194 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/SplitGraph.html">Split Graph</a>.
%H A048194 <a href="/index/Pos#posets">Index entries for sequences related to posets</a>
%F A048194 a(n) = A049312(n) - A049312(n-1) (see the Collins and Trenk link, Thms. 5 and 15). - _Justin M. Troyka_, Oct 29 2018
%F A048194 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
%F A048194 a(n) = A263859(n,1) + 1. - _Geoffrey Critzer_, Feb 05 2024
%t A048194 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}]]];
%t A048194 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]}];
%t A048194 A[n_, k_] := g[Min[n, k], Abs[n - k]];
%t A048194 a[d_] := Sum[A[n, d - n], {n, 0, d}] - Sum[A[n, d - n - 1], {n, 0, d - 1}];
%t A048194 Table[a[n], {n, 1, 25}] (* _Jean-François Alcover_, May 26 2019, after _Alois P. Heinz_ in A049312 *)
%Y A048194 Cf. A007776, A048192, A048193, A049312, A055080, A263859.
%Y A048194 Detlef Pauly remarks that this is the unlabeled analog of A001831.
%K A048194 nonn,nice,easy
%O A048194 1,2
%A A048194 _Gordon F. Royle_