The count of cycles (simple and not simple) of length n or less for Kn is given by the following function C(n). The count consists of the count of cycles for each length 2 <= l <= n given by C(n, l). The count for a given length l consists of the count of cycles (simple and not simple) from each vertex 1 <= i <= n given by C(i, n, l).

C(n) = C(n, 2) + C(n, 3) + ... + C(n, n)

C(n, l) = C(1, n, l) + C(2, n, l) + ... + C(n, n, l)

C(i, n, l) = 0                                  if l < 2
C(i, n, l) = (n - i)^(l - 1) - C(i, n, l - 1)   otherwise

The following OCaml program counts the number of cycles for complete graphs K2 to K20.

#!/usr/bin/env ocaml

#load "nums.cma"

include Big_int

let rec pow b e =
  if e = 0 then unit_big_int
  else mult_big_int (big_int_of_int b) (pow b (e - 1))

let rec c i n l =
  if l < 2 then zero_big_int
  else sub_big_int (pow (n - i) (l - 1)) (c i n (l - 1))

let rec iter n f acc =
  if n = 0 then acc
  else iter (n - 1) f (f n acc)

let c n l =
  iter n (fun i acc -> add_big_int acc (c i n l)) zero_big_int

let c n =
  iter n (fun l acc -> add_big_int acc (c n l)) zero_big_int

let rec upto m n f =
  if m == n then f m
  else begin f m; upto (m + 1) n f end

let rec format_number s =
  let l = String.length s in
  if l <= 3 then s
  else
    let prefix = String.sub s 0 (l - 3) in
    let suffix = String.sub s (l - 3) 3 in
      Printf.sprintf "%s,%s" (format_number prefix) suffix

let (>>) x f = f x

let count n =
  let count = c n >> string_of_big_int >> format_number in
  Printf.printf "K%2d %40s\n" n count

let _ = upto 2 20 count

To run the program in Linux or OSX, install the OCaml interpreter, save the program in a file, and grant execution permission to the file. In OSX with Homebrew, when you save the program in file count-cycles.ml you install and run the program as follows.

ruslan$ brew install ocaml
==> Downloading https://homebrew.bintray.com/bottles/ocaml-4.02.3.el_capitan.bottle.tar.gz
...
ruslan$ chmod a+x count-cycles.ml
ruslan$ ./count-cycles.ml
 K2:                                       1
 K3:                                       5
 K4:                                      42
 K5:                                     384
 K6:                                   4,665
 K7:                                  69,537
 K8:                               1,230,124
 K9:                              25,140,552
K10:                             582,508,305
K11:                          15,084,077,381
K12:                         431,646,196,806
K13:                      13,525,545,361,080
K14:                     460,576,563,322,057
K15:                  16,935,036,272,292,001
K16:                 668,691,718,661,091,000
K17:              28,220,125,532,003,984,176
K18:           1,267,597,789,008,779,578,401
K19:          60,381,304,029,673,985,693,205
K20:       3,040,239,935,992,309,703,757,730

Comments