[seqfan] Re: A graph counting problem

[hv at crypt.org]

Andrew Weimholt <andrew.weimholt at gmail.com> wrote:
:My program gives
:
:1,1,2,3,6,12,28,65,173   (last term was off by one)
:
:I had all the graphs in my hand computation but miscounted
:
:I can adapt my program to get a few more terms by taking advantage of
:the restriction
:that nodes with the same label cannot be connected. This will allow me
:to use a less
:brute-force approach to counting the graphs, particularly for sets of
:labels with a high
:number of repeats.
:
:Andrew

I've also written some code for this. Defining f(n) as the number of
graphs and g(n) as the number of connected graphs, I find:
f( 2) =    2; g( 2) =    1
f( 3) =    4; g( 3) =    2
f( 4) =    8; g( 4) =    3
f( 5) =   16; g( 5) =    6
f( 6) =   35; g( 6) =   12
f( 7) =   77; g( 7) =   28
f( 8) =  179; g( 8) =   65
f( 9) =  440; g( 9) =  173
f(10) = 1160; g(10) =  496
f(11) = 3264; g(11) = 1527
f(12) = 9950; g(12) = 5092

.. and am currently working on n=13, which should take about 3 hours of
CPU time.

Since the actual values of the partition are not relevant, my code starts
by resolving each partition to the multiset of counts of each node value
(so that for example the partition 4+4+4+3+3 resolves to the multiset {3, 2}),
and uses a cache of graph counts for each multiset.

The code is pretty simplistic, but the easiest win would be to find
formulae for particular classes of multiset to avoid the need to generate
any graphs at all for those cases.

Letting f(M), g(M) be defined for a given multiset analogously to those
above, I have proven the easy ones:
f({n}) = 1, g({n}) = c(n=1)
f({n, 1}) = n+1, g({n, 1}) = 1

It also looks like:
f({n, 2}) = A002623(n), g({n, 2}) = A002620(n)
f({n, 3}) = A002727(n), [g({n, 3}) not in OEIS]
g({n, n}) = A069736(n - 1), [f({n, n}) not in OEIS]
f({n, 1, 1}) = A007290(n - 3), g({n, 1, 1}) = (n+1)^2

If these latter can be proven, and perhaps more such identities found, it
would substantially speed up calculation.

Current code (including more detailed results at the end) is at
http://crypt.org/hv/puzzle/fillograph, and I'll try to remember to update
it from time to time. It is 200 lines of perl-code, quite well commented.

Hugo