[seqfan] Re: A graph counting problem

[hv at crypt.org]

hv at crypt.org wrote:
: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.

f(13) = 33206; g(13) = 18669

It did take 3 hours, but further improvements have got it down to 10 minutes.
f(14) should (now) take about 2 hours, but for now I'm going to concentrate
on completing a rewrite into C.

Version 0.2 of the code is available at [1], and a tarball with some other
bits and pieces at [2]. Changes since the previous version:
- explicit calculations for multisets with sum of tail <= 3
  - warning: I don't fully understand the tail=3 code (so use with caution),
    but it gives correct results up to {7,3}, {6,2,1} and {5,1,1,1}, i.e.
    those needed to calculate f(13)
  - if I can understand it better, it may be possible to generalize this
    and remove all need for graph construction
- test graphs only when at least half the edges are set: the inverse graph
  only needs testing for connectedness
- canonical_graph optimizations:
  - empty vertices must be the tail of their equivalence class
  - full vertices must be the head of their equivalance class
  - canonical if no vertices to permute after full/empty vertices are removed
- use Ehrlich's swap method to make the transition from one mapping to the
  next require only a single swap, and rearrange the permutation analysis to
  take advantage of this
- note that under permutation the ordering of vertices in an edge can never
  change
- started writing new version in C (only 20% complete)

: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.

f({n, 2}) = \sum_0^n{(n-i+1)(1+\floor(i/2))
  = 1/24 [ (n+2)(n+4)(2n+3) - 3o(n) ] where o(n) = 1 if n is odd, else 0
This matches the given formula for A002623(n) = floor(1/24 (n+2)(n+4)(2n+3)).

g({n, 2}) = \sum_0^{n-1}{1+\floor(i/2)}
  = 1/4 [ (n+1)^2 - o(n+1) ]
  = A002620(n+1)

f({n, 1, 1}) = 2 \sum_0^n{(n-i+1)(i+1)
  = 1/3 (n+1)(n+2)(n+3)
  = A007290(n-3)

g({n, 1, 1}) = \sum_0^{n-1}{2(i+1)} + (n+1)
  = (n+1)^2

Hugo

[1] http://crypt.org/hv/puzzle/fillograph
[2] http://crypt.org/hv/puzzle/fillograph-0.2.tar.gz