[seqfan] Re: A157015: graphs with n vertices having a bipartite connected components

[Richard Mathar]

eww> Eric W. Weisstein eww at wolfram.com
eww> Sat May 2 19:01:15 CEST 2009
eww> 
eww> A157015(8) is indeed incorrect.   a(8) = 1389 is correct.
eww> 
eww> In[1]:= <<Combinatorica`
eww> In[2]:= Table[Count[Graphs[n], _?(Function[g,
eww>        Or @@ BipartiteQ /@ (InduceSubgraph[g, #] & /@
eww>            ConnectedComponents[g])])], {n, 8}] // Timing
eww> Out[2]= {28.2611, {1, 2, 3, 8, 18, 60, 232, 1389}}

This implies A157016(8) also needs to change to 12346-1389=10957, supposed that
A157015(n)=A000088(n)-A157016(n)  and A000088(8)=12346 are correct.

Since A157016 is commented to be the Euler transform of A157051,
this implies also a change to A157051 (even without such a change,
A157051(8) and A157051(10) etc are not consistent with that claim)...:

read("transforms") ;

L := [0, 0, 1, 3, 16, 96, 812, 10957, 260494, 11713892, 1006689874, 164059932991, 50335918374390, 29003488479342757, 31397381309486943966, 63969560164056605070568, 245871831711240782889155306, 1787331725280384281423635294536, 24636021429463931875328536155116965] ;

EULERi(L) ;


1, 0, 0, 1, 3, 16, 95, 809, 10935, 260350, 11712659, 1006674970, 164059622178, 50335905627537, 29003487431981858, 31397381142185993626, 63969560113211017780732, 245871831682083553779883870, 1787331725248899067715239350964, 24636021429399867654036554665853909

Unfortunately, this seems to break the formula in A157051 which says

A157051(n) = A001349(n)-A005142(n):

A001349 := [1, 1, 1, 2, 6, 21, 112, 853, 11117, 261080, 11716571, 1006700565, 164059830476, 50335907869219, 29003487462848061, 31397381142761241960, 63969560113225176176277, 245871831682084026519528568, 1787331725248899088890200576580, 24636021429399867655322650759681644] ;

A005142 := [0, 1, 1, 1, 3, 5, 17, 44, 182, 730, 4032, 25598, 212780, 2241730, 31193324, 575252112, 14218209962, 472740425319, 21208887576786, 1286099113807999, 105567921675718772] ;

for i from 1 do
        printf("%d ", op(i,A001349) - op(i,A005142)) ;
od:

In summary, there is more to be done than correcting a single value A157015(8),
I think, but I have no clue what else needs to be done.

Richard