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

Max Alekseyev maxale at gmail.com
Sat May 2 22:52:45 CEST 2009

```Vladeta Jovovic has found that errors are actually in A157015 and
A157016, but not in A157051.
And my calculations from scratch agree.

Correct values are:

A157016:
1,0,0,1,3,16,96,812,10957,260494,11713772,1006689871,164059928509,50335918374222,29003488479015273,31397381309486933777,63969560164056545231089,245871831711240782887877980,1787331725280384281389706209909

A157015:
0,1,2,3,8,18,60,232,1389,14174,291396,12307993,1031244083,166112993730,50667178220215,29104660317374991,31455540471012663839,64032442292149795841796,245999865227419158171980939

Regards,
Max

On Sat, May 2, 2009 at 2:45 PM, Richard Mathar
<mathar at strw.leidenuniv.nl> wrote:
>
>
> 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)...:
>
>
> 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
>
>
>
> _______________________________________________
>
> Seqfan Mailing list - http://list.seqfan.eu/
>

```