On the number of cycles and independent edges in $K_{8}$

Question

I am trying to find the number of cycles and $K_{2}$'s in $K_{8}$. That is, partition $8$ into all the ways such that the lowest part can be a $2$, so we have $8 = 8$, $6+2$, $5+3$, $2+3+3$, $4+4$, $4+2+2$, $2+2+2+2$. These then correspond to the following (not necessarily connected) subgraphs of $K_{8}$: $C_{8}$, $C_{6} \cup K_{2}$, $C_{5} \cup C_{3}$, $K_{2} \cup 2C_{3}$, $2C_{4}$, $C_{4} \cup 2K_{2}$, and $4K_{2}$.

My goal is to count these.

I know that $\#C_{8} = 7!/2$, but I'm struggling with the rest. Here are my attempts:

$\#C_{6} \cup K_{2} = {28 \choose 1}5!/2$

$\#C_{5} \cup C_{3} = {8 \choose 3}4!/4$

$\#K_{2} \cup 2C_{3} = {28 \choose 1}5!/4$

$\#2C_{4} = 7!/4!$

$\#C_{4} \cup 2K_{2} = {28 \choose 1}{15 \choose 1}5!/4$

$\#4K_{2} = {28 \choose 1}{15 \choose 1}{6 \choose 1}/4$

I feel like some of these might be undercounted. Any help would be appreciated.

Answer 1

Well, I do wonder why $K_1$ is not allowed, but basically you are doing the following:

1. Finding a partition of 8 (apparently excluding 1 as a part).
2. Split up the vertices of your graph into those parts.
3. Assigning each part a circular permutation/labeling. (Actually, not quite, since you also don't care about clockwise/counterclockwise.)

For part 1, you have first split them up into seven cases:

$$C_8, C_6\cup K_2, C5\cup C_3, C_4\cup C_4, C_4\cup C_2\cup C_2, C_3\cup C_3\cup K_2, K_2\cup K_2\cup K_2\cup K_2$$

This correctly corresponds to the seven suitable partitions of 8:

$$8, 6+2, 5+3, 4+4, 4+2+2, 3+3+2, 2+2+2+2$$

which could be derived from (for example) Mathematica as p=IntegerPartitions[8, 8, {2, 3, 4, 5, 6, 7, 8}].

For part 2, you just do a multinomial coefficient to get the right count. You'll have to divide out for repeated parts though, since one $C_3$ is the same as the next.

From there, in each part you want to compute the number of cyclic permutations of a particular cycle. (For these purposes, $K_2$ and $C_2$ are the same, the number of ways of orienting them are .. well just the one.)

The number of ways to do this for a cycle $C_k$ is $k!/(2k)=(k-1)!/2$ because you are basically just factoring out symmetry by the dihedral group on this cycle. The $k$ is for the rotation, the 2 is for the flip. This is not true for $k=2$, where we just have one orientation.

So you can run through that computation, for example if you have $C_3\cup C_3\cup C_2$, then you have $\binom{8}{3,3,2}=\frac{8!}{3!3!2!}$ ways to split them up, but you have to divide by $2!$ since the $C_2$s are indistinguishable. In each $C_3$ and $C_2$, there is really only one way to orient anything, so you just get 280.

I do not know where your $5!/4$ comes from. (I am also struggling to understand the $\binom{28}{1}$ factor.. is that supposed to be an 8?)

Now, this is all a big mess! One thing that helps is knowing a simple programming language. It can help not just with some numerical work, but with tabulating. For example, the line Map[Tally[#][[All, 2]] &, p] (with p as above) gives you the tally of repeated (or not repeated) cycles for each "type" of partition you have. In other words, it gives:

{{1}, {1, 1}, {1, 1}, {2}, {1, 2}, {2, 1}, {4}}

which can easily be used as the "extra" stuff you have to divide by (as we did with the repeated $C_3$s in the example).

So something like this will get us our count for part 2:

c1 = Map[
 Multinomial @@ #/
 Times @@ Map[Factorial, Tally[#][[All, 2]]] &,
p]

(* output: {1, 28, 56, 35, 210, 280, 105} *)

If you don't know the syntax, that's fine -- the multinomial is visible, as is our special factor to get ride of the extra stuff. For the factors coming from part 3, you can do similar:

c2 = Times @@ # & /@ Map[Ceiling[(# - 1)!/2] &, p]

(* output: {2520, 60, 12, 9, 3, 1, 1} *)

There the ceiling just resolves the issue for $K_2$ getting 1/2 instead of 1. Notice that the $C_8$ has many arrangements, but even the $C_6$ has far fewer. To get the product of those two lists (componentwise) and add them up, you get:

c1*c2
Plus@@(c1*c2)

(* {2520, 1680, 672, 315, 630, 280, 105} *)
(* 6202 *)

I should point out that this is almost the same as the number of derangements of eight elements, except in that case the "flip" (which gave us the 2 in our $k!/(2k)$) is meaningful (it reverses the clockwise/counterclockwise orientation of the cycle in the permutation, i.e. it conflates each permutation and its inverse). That is sequence A000166 in the Online Encyclopedia of Integer Sequences, while I believe the sequence corresponding to your problem is A002137.

c3 = Times @@ # & /@ Map[Ceiling[(# - 1)!] &, p]
(* {5040, 120, 48, 36, 6, 4, 1} *)
Plus @@ (c1*c3)
(* 14833 *)

To summarize nicely:

$$\begin{array}{|c|c|c|}\hline C_8 & \binom{8}{8}\frac{1}{1!}\left(\frac{(8-1)!}{2}\right) & 2520 \\ \hline C_6\cup K_2 & \binom{8}{6,2}\frac{1}{1!1!}\left(\frac{(6-1)!}{2}\right)\left(1\right) & 1680 \\ \hline C5\cup C_3 & \binom{8}{5,3}\frac{1}{1!1!}\left(\frac{(5-1)!}{2}\right)\left(\frac{(3-1)!}{2}\right) & 672 \\ \hline C_4\cup C_4 & \binom{8}{4,4}\frac{1}{2!}\left(\frac{(4-1)!}{2}\right)^2 & 315 \\ \hline C_4\cup C_2\cup C_2 & \binom{8}{4,2,2}\frac{1}{1!2!}\left(\frac{(4-1)!}{2}\right)\left(1\right)^2 & 630 \\ \hline C_3\cup C_3\cup K_2 & \binom{8}{3,3,2}\frac{1}{2!1!}\left(\frac{(3-1)!}{2}\right)^2\left(1\right) & 280 \\ \hline K_2\cup K_2\cup K_2\cup K_2 & \binom{8}{2,2,2,2}\frac{1}{4!}\left(1\right)^4 & 105\\ \hline & \mathrm{Total:}& 6202 \\ \hline \end{array} $$

Each row corresponds to part 1, partitions of 8. Each box in the second column contains a multinomial corresponding to part 2, picking which vertices go with each part. This is multiplied by a correction (often $1/1!$ or the like) since each cycle of the same size is indistinguishable. The rest of the factors correspond to the number of ways to create a cycle out of that many parts, which is $(k-1)!/2$ except for $k=2$ (where it is just 1).