Yesterday, I did a computation on the number of unlabeled simple graphs on \(n\) vertices. The correct mathematical formulation is the number of isomorphism classes of simple graphs on \(n\) vertices. The computation I gave yesterday has a horrendous time complexity (approximately \(\mathcal{O}(n!)\)). Today, I am going to improve on it.
The number I wanted to compute was \[ \frac{1}{n!} \sum_{g\in S_n} 2^{\ell(g)} \]
where \(\ell(g)\) was the number of disjoint orbits of the action of \(g\) on the set of edges of the complete graph \(K_n\). One observation I made was that \(\ell(g)\) depends on the shape of \(g\) in terms of cycle decomposition of \(g\).
There are many different ways of representing permutations on \(n\)-objects. Mathematicians view them as one-to-one and onto functions. In my count yesterday, I was writing a permutation as a specific ordering of the numbers from \(1\) to \(n\). Mathematicians usually write is as a matrix. Here is an example of a permutation of \(5\)
\[ \left(\begin{matrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 1 & 5 & 4 \end{matrix}\right) \]
where we read them as ’‘\(1\) is mapped to \(2\), \(2\) is mapped to \(3\) …’’ etc.
There is another way of representing permutations by objects called cycles. A cycle is a sequence of numbers connected via repeated action of a permutation. For example in the example above, if we start with \(1\) and use the permutation, we obtain \(2\). If we apply the permutation again on \(2\) we get \(3\), and if we apply again we get \(1\), and complete the cycle \((123)\). If we take a remaining element, say \(4\) and apply the permutation repeatedly we get the cycle \((45)\). Combining them together we get a cycle representation \((123)(45)\) of the same permutation. Every permutation has a representation in terms of disjoint cycles.
Note that the cycle \((123)\) can also be represented as \((231)\) or \((312)\) depending on where we start applying. The usual convention is to start with the smallest number in the cycle. Moreover, \((123)(45)\) and \((45)(123)\) also represent the same permutation. We usually order cycles using a suitable version of the lexicographical ordering.
So, here is a simple way of writing a unique representative permutation corresponding to a specific shape:
(defun cycle (n &optional (shift 1))
(append (loop for i from (1+ shift) below (+ n shift) collect i)
(list shift)))
(defun permutation (xs &optional (shift 1) ret)
(if (null xs)
ret
(permutation (cdr xs)
(+ shift (car xs))
(append ret (cycle (car xs) shift)))))
(permutation '(3 3 2 1 1))CYCLE
PERMUTATION
(2 3 1 5 6 4 8 7 9 10)Note that I am not using the cycle representation, but the original representation of a permutation as a specific ordering of numbers from \(1\) to \(n\).
Given two permutations \(\sigma\) and \(\mu\), there is an operation called conjugation \(\sigma\mu\sigma^{-1}\). Conjugating a permutation \(\mu\) via another permutation \(\sigma\) does not change its cycle decomposition but it relabels the numbers in \(\mu\) using the order defined by \(\sigma\). Thus one can see that we can conjugate any permutation into something like
\[ (1\cdots a_1)((a_1+1)\cdots a_2)\cdots((a_{m-1}+1)\cdots a_m)((a_m+1)\cdots n) \]
where numbers satisfy \(1<a_1<\cdots<a_2<\cdots<a_m<\cdots<n\) as in our example. Here are all of the permutations that have the same shape as our example:
\[ (123)(45), (132)(45), (124)(35), (142)(35), (125)(34), (152)(34), (134)(25), (143)(25), (135)(24), (153)(24), \]
\[ (145)(23), (154)(23), (234)(15), (243)(15), (235)(14), (253)(14), (245)(13), (254)(13), (345)(12), (354)(12) \]
The shape is dictated by a partition of \(5\). In this case \(5=3+2\). Now, we have two problems:
Given an \(n\), how do we get all partitions of \(n\) to get an index set for permutations?
How do we count the number of all permutations that fit into a specific shape defined by a partition?
Luckily, I wrote about partitions before. But I am not going to recycle the code from that post. The function below returns all possible partitions of an integer unbound by its size
(defun partitions (n &optional k)
(cond
((null k) (loop for i from 1 to n append (partitions n i)))
((< n k) nil)
((= k 1) (list (list n)))
((= n k) (list (loop repeat n collect 1)))
(t (append (mapcar (lambda (xs) (append xs (list 1))) (partitions (1- n) (1- k)))
(mapcar (lambda (xs) (mapcar #'1+ xs)) (partitions (- n k) k))))))
(partitions 5)PARTITIONS
((5) (4 1) (3 2) (3 1 1) (2 2 1) (2 1 1 1) (1 1 1 1 1))The partitions above correspond to the following permutations:
\[ (12345), (1234)(5), (123)(45), (123)(4)(5), (12)(34)(5), (12)(3)(4)(5), (1)(2)(3)(4)(5) \]
I listed above 20 permutations that have the same shape as \((123)(45)\). So, how do we count them. For this we need to count the number of conjugacy classes. And for that we need to count the number of elements of the subgroup of centralizers.
If permutation has the shape \(n = m_1 + \cdots + m_k\) where \(m_1\geq m_2\geq \cdots \geq m_k\) we first write the partition as
\[n = a_1 n_1 + \cdots + a_\ell n_\ell \]
where this time \(n_i\neq n_j\) and we have \(a_1\)-many \(m_1\) in \(n\), \(a_2\)-many \(m_2\) in \(n\) … etc. For example if \(10 = 3 + 3 + 2 + 1 + 1\) then we have \(10 = 2\cdot 3 + 1\cdot 2 + 2\cdot 1\). In that case, the number of permutations sharing this shape is given by
\[ \frac{n!}{a_1!\cdots a_\ell! n_1^{a_1}\cdots n_\ell^{a_l}} \]
For our first example \(5=3+2\) we get
\[ \frac{5!}{1!\cdot 1!\cdot 3^1\cdot 2^1} = \frac{120}{6} = 20 \]
In our second example
\[ \frac{10!}{2!\cdot 1!\cdot 2!\cdot 3^2\cdot 2^1\cdot 1^2} = \frac{3628800}{72} = 50400 \]
there are \(50400\) permutations sharing the shape \((123)(456)(78)(9)(10)\).
So, here is the lisp code that counts these permutations:
(defun blocks (xs &optional prev size count)
(cond
((null xs) (* count size prev))
((null prev) (blocks (cdr xs) (car xs) 1 1))
((= prev (car xs)) (blocks (cdr xs) prev (* count size prev) (1+ count)))
(t (blocks (cdr xs) (car xs) (* size count prev) 1))))
(defun fact (n)
(if (or (zerop n)
(= n 1))
1
(* n (fact (1- n)))))
(defun number-of-permutations (xs)
(/ (fact (reduce #'+ xs))
(blocks xs)))
(number-of-permutations '(3 3 2 1 1))BLOCKS
FACT
NUMBER-OF-PERMUTATIONS
50400Let us start by recycling the code from yesterday:
(defun edge-orbit (perm xs &optional carry)
(let ((ys (sort (mapcar (lambda (x) (elt perm (1- x))) xs) #'<)))
(if (member xs carry :test #'equal)
carry
(edge-orbit perm ys (append carry (list xs))))))
(defun number-of-orbits (perm edges &optional (number 0))
(if (null edges)
number
(let* ((ys (edge-orbit perm (car edges)))
(zs (set-difference edges ys :test #'equal)))
(number-of-orbits perm zs (incf number)))))
(defun complete-graph (n)
(loop for i from 1 below n
append (loop for j from (1+ i) to n
collect (list i j))))EDGE-ORBIT
NUMBER-OF-ORBITS
COMPLETE-GRAPHNow, the final count code:
(defun experiment (n)
(let ((sum 0)
(edges (complete-graph n)))
(dolist (part (partitions n) (/ sum (fact n)))
(let* ((size (number-of-permutations part))
(perm (permutation part)))
(incf sum (* size (expt 2 (number-of-orbits perm edges))))))))
(time (loop for i from 1 to 35 collect (experiment i)))EXPERIMENT
(1 2 4 11 34 156 1044 12346 274668 12005168 1018997864 165091172592
50502031367952 29054155657235488 31426485969804308768 64001015704527557894928
245935864153532932683719776 1787577725145611700547878190848
24637809253125004524383007491432768 645490122795799841856164638490742749440
32220272899808983433502244253755283616097664
3070846483094144300637568517187105410586657814272
559946939699792080597976380819462179812276348458981632
195704906302078447922174862416726256004122075267063365754368
131331393569895519432161548405816890146389214706146483380458576384
169487618400693135671278778610295749756246061427513800357039083537927168
421260006519643885757174107650953992882782878952295704539600450662355704738816
2019295999678571395728328980890810345860807065053566265347514137546665672316696821760
18691352722478956041683441055221773100906878077027397169675907651818104181986752359177684992
334494316309257669249439569928080028956631479935393064329967834887217734534880582749030521599504384
11585815044205812673379511928863764381265040141261061227725971383046167307510698791401041768792169368940544
777510571865055903406188374366190476598442307924741916354899631006385898637671205231827093391614863192904415807488
101193386573463039354269401142741027463145963826790815082084909468028166503553807396859190074836698829732761747606799118336
25566013871397723851094108820013106182843555852275358804907199250742354688175618766408178934854794054153633107026075263960686854144
12549164197724499332787928665161136748157345371749938537602740270461084253679848281438831503478413083988473184510534726477777359587588087808)Yesterday, it took about 10 seconds to calculate the number of isomorphism classes up to 10 vertices. Today, it took roughly less than a second to the same calculation. It took about a minute and a half seconds up to 25 vertices.