The Kitchen Sink and Other Oddities

Atabey Kaygun

Counting Connected Labeled Graphs

Description of the problem

There is a recursive formula that calculates the number of connected labeled graphs on \(N\) nodes. \[ G(N) = 2^{\binom{N\ }{2}} - \sum_{k=1}^{N-1} (N-k)\binom{N}{k} 2^{\binom{k}{2}}\ G(N-k) \] Today, I am going to write a common lisp function that calculates \(G(N)\).

Implementation

First, I need an implementation of the binomial coefficients.

(defun binom (n k &optional (carry 1))
  (cond
    ((> k n) 0)
    ((or (= k 0) (= n k)) carry)
    ((> k (- n k)) (binom n (- n k)))
    (t (binom (1- n) (1- k) (* carry (/ n k))))))
BINOM

Next, the implementation:

(let ((table (make-hash-table)))
  (defun count-connected-graphs (n)
    (if (zerop n)
        1
        (or (gethash n table)
            (setf (gethash n table)
                  (- (expt 2 (binom n 2))
                     (* (/ n)
                        (loop for k from 1 below n sum
                             (* (- n k)
                                (binom n k)
                                (expt 2 (binom k 2))
                                (count-connected-graphs (- n k)))))))))))
COUNT-CONNECTED-GRAPHS

Notice that I am using a hand-wrapped memoization. And here are a couple of these numbers:

(loop for i from 0 to 30 collect (count-connected-graphs i))
(1 1 1 4 38 728 26704 1866256 251548592 66296291072 34496488594816
 35641657548953344 73354596206766622208 301272202649664088951808
 2471648811030443735290891264 40527680937730480234609755344896
 1328578958335783201008338986845427712
 87089689052447182841791388989051400978432
 11416413520434522308788674285713247919244640256
 2992938411601818037370034280152893935458466172698624
 1569215570739406346256547210377768575765884983264804405248
 1645471602537064877722485517800176164374001516327306287561310208
 3450836972295011606260171491426093685143754611532806996347023345844224
 14473931784581530777452916362195345689326195578125463551466449404195748970496
 121416458387840348322477378286414146687038407628418077332783529218671227143860518912
 2037032940914341967692256158580080063148397956869956844427355893688994716051486372603625472
 68351532186533737864736355381396298734910952426503780423683990730318777915378756861378792989392896
 4586995386487343986845036190980325929492297212632066142611360844233962960637520118252235915249481987129344
 615656218382741242234508631976838051282411931197630362747033724174222395343543109861028695816566950855890811486208
 165263974343528091996230919398813154847833461047104477666952257939564080953537482898938408257044203946031706125367800496128
 88725425253946309579607515290733826999038832348034303708272765654674479763074364231597119435621862686597717341418971119460584259584)