AATA Burnside’s Counting Theorem

Section 14.3 Burnside’s Counting Theorem

Suppose that we wish to color the vertices of a square with two different colors, say black and white. We might suspect that there would be

2^{4} = 16

different colorings. However, some of these colorings are equivalent. If we color the first vertex black and the remaining vertices white, it is the same as coloring the second vertex black and the remaining ones white since we could obtain the second coloring simply by rotating the square

90^{\circ}

(Figure 14.17).

Four squares with vertices labeled clockwise BWWW, WBWW, WWWB, and WWBW beginning in the upper left corner. — 🔗
Figure 14.17. Equivalent colorings of square

🔗

Burnside’s Counting Theorem offers a method of computing the number of distinguishable ways in which something can be done. In addition to its geometric applications, the theorem has interesting applications to areas in switching theory and chemistry. The proof of Burnside’s Counting Theorem depends on the following lemma.

🔗

Lemma 14.18.

🔗

Let

X

be a

G

-set and suppose that

x \sim y .

Then

G_{x}

is isomorphic to

G_{y} .

In particular,

| G_{x} | = | G_{y} | .

Proof.

Let

G

act on

X

(g, x) \mapsto g \cdot x .

Since

x \sim y,

there exists a

g \in G

such that

g \cdot x = y .

Let

a \in G_{x} .

Since

g a g^{- 1} \cdot y = g a \cdot g^{- 1} y = g a \cdot x = g \cdot x = y,

we can define a map

ϕ : G_{x} \to G_{y}

ϕ (a) = g a g^{- 1} .

The map

ϕ

is a homomorphism since

ϕ (a b) = g a b g^{- 1} = g a g^{- 1} g b g^{- 1} = ϕ (a) ϕ (b) .

Suppose that

ϕ (a) = ϕ (b) .

Then

g a g^{- 1} = g b g^{- 1}

a = b;

hence, the map is injective. To show that

ϕ

is onto, let

b

be in

G_{y};

then

g^{- 1} b g

is in

G_{x}

since

g^{- 1} b g \cdot x = g^{- 1} b \cdot g x = g^{- 1} b \cdot y = g^{- 1} \cdot y = x;

and

ϕ (g^{- 1} b g) = b .

🔗

Theorem 14.19. Burnside.

🔗

Let

G

be a finite group acting on a set

X

and let

k

denote the number of orbits of

X .

Then

k = \frac{1}{| G |} \sum_{g \in G} | X_{g} | .

Proof.

We look at all the fixed points

x

of all the elements in

g \in G;

that is, we look at all

g

’s and all

x

’s such that

g x = x .

If viewed in terms of fixed point sets, the number of all

g

’s fixing

x

’s is

\sum_{g \in G} | X_{g} | .

However, if viewed in terms of the stabilizer subgroups, this number is

\sum_{x \in X} | G_{x} |;

hence,

\sum_{g \in G} | X_{g} | = \sum_{x \in X} | G_{x} | .

By Lemma 14.18,

\sum_{y \in O_{x}} | G_{y} | = | O_{x} | \cdot | G_{x} | .

By Theorem 14.11 and Lagrange’s Theorem, this expression is equal to

| G | .

Summing over all of the

k

distinct orbits, we conclude that

\sum_{g \in G} | X_{g} | = \sum_{x \in X} | G_{x} | = k \cdot | G | .

🔗

Example 14.20.

🔗

Let

X = {1, 2, 3, 4, 5}

and suppose that

G

is the permutation group

G = {(1), (1 3), (1 3) (2 5), (2 5)} .

The orbits of

X

are

{1, 3},

{2, 5},

and

{4} .

The fixed point sets are

\begin{aligned} X_{(1)} & = X \\ X_{(1 3)} & = {2, 4, 5} \\ X_{(1 3) (2 5)} & = {4} \\ X_{(2 5)} & = {1, 3, 4} . \end{aligned}

🔗

Burnside’s Theorem says that

k = \frac{1}{| G |} \sum_{g \in G} | X_{g} | = \frac{1}{4} (5 + 3 + 1 + 3) = 3 .

🔗

Subsection A Geometric Example

🔗

Before we apply Burnside’s Theorem to switching-theory problems, let us examine the number of ways in which the vertices of a square can be colored black or white. Notice that we can sometimes obtain equivalent colorings by simply applying a rigid motion to the square. For instance, as we have pointed out, if we color one of the vertices black and the remaining three white, it does not matter which vertex was colored black since a rotation will give an equivalent coloring.

🔗

The symmetry group of a square,

D_{4},

is given by the following permutations:

\begin{aligned} (1) & (1 3) & (2 4) & (1 4 3 2) \\ (1 2 3 4) & (1 2) (3 4) & (1 4) (2 3) & (1 3) (2 4) \end{aligned}

🔗

The group

G

acts on the set of vertices

{1, 2, 3, 4}

in the usual manner. We can describe the different colorings by mappings from

X

into

Y = {B, W}

where

B

and

W

represent the colors black and white, respectively. Each map

f : X \to Y

describes a way to color the corners of the square. Every

σ \in D_{4}

induces a permutation

\tilde{σ}

of the possible colorings given by

\tilde{σ} (f) = f \circ σ

for

f : X \to Y .

For example, suppose that

f

is defined by

\begin{aligned} f (1) & = B \\ f (2) & = W \\ f (3) & = W \\ f (4) & = W \end{aligned}

🔗

and

σ = (12) (34) .

Then

\tilde{σ} (f) = f \circ σ

sends vertex

2

B

and the remaining vertices to

W .

The set of all such

\tilde{σ}

is a permutation group

\tilde{G}

on the set of possible colorings. Let

\tilde{X}

denote the set of all possible colorings; that is,

\tilde{X}

is the set of all possible maps from

X

Y .

Now we must compute the number of

\tilde{G}

-equivalence classes.

${\tilde{X}}_{(1)} = \tilde{X}$ since the identity fixes every possible coloring. $| \tilde{X} | = 2^{4} = 16 .$
${\tilde{X}}_{(1 2 3 4)}$ consists of all $f \in \tilde{X}$ such that $f$ is unchanged by the permutation $(1 2 3 4) .$ In this case $f (1) = f (2) = f (3) = f (4),$ so that all values of $f$ must be the same; that is, either $f (x) = B$ or $f (x) = W$ for every vertex $x$ of the square. So $| {\tilde{X}}_{(1 2 3 4)} | = 2 .$
$| {\tilde{X}}_{(1 4 3 2)} | = 2 .$
For ${\tilde{X}}_{(1 3) (2 4)},$ $f (1) = f (3)$ and $f (2) = f (4) .$ Thus, $| {\tilde{X}}_{(1 3) (2 4)} | = 2^{2} = 4 .$
$| {\tilde{X}}_{(1 2) (3 4)} | = 4 .$
$| {\tilde{X}}_{(1 4) (2 3)} | = 4 .$
For ${\tilde{X}}_{(1 3)},$ $f (1) = f (3)$ and the other corners can be of any color; hence, $| {\tilde{X}}_{(1 3)} | = 2^{3} = 8 .$
$| {\tilde{X}}_{(2 4)} | = 8 .$

🔗

By Burnside’s Theorem, we can conclude that there are exactly

\frac{1}{8} (2^{4} + 2^{1} + 2^{2} + 2^{1} + 2^{2} + 2^{2} + 2^{3} + 2^{3}) = 6

🔗

ways to color the vertices of the square.

🔗

Proposition 14.21.

🔗

Let

G

be a permutation group of

X

and

\tilde{X}

the set of functions from

X

Y .

Then

G

induces a group

\tilde{G}

that permutes the elements of

\tilde{X},

where

\tilde{σ} \in \tilde{G}

is defined by

\tilde{σ} (f) = f \circ σ

for

σ \in G

and

f \in \tilde{X} .

Furthermore, if

n

is the number of cycles in the cycle decomposition of

σ,

then

| {\tilde{X}}_{σ} | = | Y |^{n} .

Proof.

Let

σ \in G

and

f \in \tilde{X} .

Since

σ

permutes the elements of

X,

f \circ σ

must also be in

\tilde{X} .

Suppose that

g

is another function from

X

Y

such that

\tilde{σ} (f) = \tilde{σ} (g) .

Then for each

x \in X,

f (σ (x)) = \tilde{σ} (f) (x) = \tilde{σ} (g) (x) = g (σ (x)) .

Since

σ

is a permutation of

X,

every element

x^{'}

X

is the image of some

x

X

under

σ;

hence,

f

and

g

agree on all elements of

X .

Therefore,

f = g

and

\tilde{σ}

is injective. The map

σ \mapsto \tilde{σ}

is onto, since the two sets are the same size.

Suppose that

σ

is a permutation of

X

with cycle decomposition

σ = σ_{1} σ_{2} \dots σ_{n} .

Any

f

{\tilde{X}}_{σ}

must have the same value on each cycle of

σ .

Since there are

n

cycles and

| Y |

possible values for each cycle,

| {\tilde{X}}_{σ} | = | Y |^{n} .

🔗

Example 14.22.

🔗

Let

X = {1, 2, \dots, 7}

and suppose that

Y = {A, B, C} .

g

is the permutation of

X

given by

(1 3) (2 4 5) = (1 3) (2 4 5) (6) (7),

then

n = 4 .

Any

f \in {\tilde{X}}_{g}

must have the same value on each cycle in

g .

There are

| Y | = 3

such choices for any value, so

| {\tilde{X}}_{g} | = 3^{4} = 81 .

🔗

Example 14.23.

🔗

Suppose that we wish to color the vertices of a square using four different colors. By Proposition 14.21, we can immediately decide that there are

\frac{1}{8} (4^{4} + 4^{1} + 4^{2} + 4^{1} + 4^{2} + 4^{2} + 4^{3} + 4^{3}) = 55

🔗

possible ways.

🔗

Subsection Switching Functions

🔗

In switching theory we are concerned with the design of electronic circuits with binary inputs and outputs. The simplest of these circuits is a switching function that has

n

inputs and a single output (Figure 14.24). Large electronic circuits can often be constructed by combining smaller modules of this kind. The inherent problem here is that even for a simple circuit a large number of different switching functions can be constructed. With only four inputs and a single output, we can construct 65,536 different switching functions. However, we can often replace one switching function with another merely by permuting the input leads to the circuit (Figure 14.25).

A function, f, represented by a box with inputs, x1, x2, ..., xn, on the left, and an output f(x1, x2, ..., xn) on the right. — 🔗
Figure 14.24. A switching function of $n$ variables

🔗

We define a switching or Boolean function of

n

variables to be a function from

Z_{2}^{n}

Z_{2} .

Since any switching function can have two possible values for each binary

n

-tuple and there are

2^{n}

binary

n

-tuples,

2^{2^{n}}

switching functions are possible for

n

variables. In general, allowing permutations of the inputs greatly reduces the number of different kinds of modules that are needed to build a large circuit.

The function on the left is represented by a rectangle that has inputs a and b on the left and output f(a, b). — 🔗
Figure 14.25. Switching functions in two variables

The function on the right is represented by a rectangle that has inputs a and b with leads switched on the left and an output f(b, a) on the right. — 🔗
Figure 14.25. Switching functions in two variables

🔗

The possible switching functions with two input variables

a

and

b

are listed in Table 14.26. Two switching functions

f

and

g

are equivalent if

g

can be obtained from

f

by a permutation of the input variables. For example,

g (a, b, c) = f (b, c, a) .

In this case

g \sim f

via the permutation

(a, c, b) .

In the case of switching functions of two variables, the permutation

(a, b)

reduces 16 possible switching functions to 12 equivalent functions since

\begin{aligned} f_{2} & \sim f_{4} \\ f_{3} & \sim f_{5} \\ f_{10} & \sim f_{12} \\ f_{11} & \sim f_{13} . \end{aligned}

🔗

Table 14.26. Switching functions in two variables

Inputs		Outputs
		$f_{0}$	$f_{1}$	$f_{2}$	$f_{3}$	$f_{4}$	$f_{5}$	$f_{6}$	$f_{7}$
$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$
$0$	$1$	$0$	$0$	$0$	$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$0$	$1$	$1$	$0$	$0$	$1$	$1$
$1$	$1$	$0$	$1$	$0$	$1$	$0$	$1$	$0$	$1$
Inputs		Outputs
		$f_{8}$	$f_{9}$	$f_{10}$	$f_{11}$	$f_{12}$	$f_{13}$	$f_{14}$	$f_{15}$
$0$	$0$	$1$	$1$	$1$	$1$	$1$	$1$	$1$	$1$
$0$	$1$	$0$	$0$	$0$	$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$0$	$1$	$1$	$0$	$0$	$1$	$1$
$1$	$1$	$0$	$1$	$0$	$1$	$0$	$1$	$0$	$1$

🔗

For three input variables there are

2^{2^{3}} = 256

possible switching functions; in the case of four variables there are

2^{2^{4}} = 65,536 .

The number of equivalence classes is too large to reasonably calculate directly. It is necessary to employ Burnside’s Theorem.

🔗

Consider a switching function with three possible inputs,

a,

b,

and

c .

As we have mentioned, two switching functions

f

and

g

are equivalent if a permutation of the input variables of

f

gives

g .

It is important to notice that a permutation of the switching functions is not simply a permutation of the input values

{a, b, c} .

A switching function is a set of output values for the inputs

a,

b,

and

c,

so when we consider equivalent switching functions, we are permuting

2^{3}

possible outputs, not just three input values. For example, each binary triple

(a, b, c)

has a specific output associated with it. The permutation

(a c b)

changes outputs as follows:

\begin{aligned} (0, 0, 0) & \mapsto (0, 0, 0) \\ (0, 0, 1) & \mapsto (0, 1, 0) \\ (0, 1, 0) & \mapsto (1, 0, 0) \\ ⋮ \\ (1, 1, 0) & \mapsto (1, 0, 1) \\ (1, 1, 1) & \mapsto (1, 1, 1) . \end{aligned}

🔗

Let

X

be the set of output values for a switching function in

n

variables. Then

| X | = 2^{n} .

We can enumerate these values as follows:

\begin{aligned} (0, \dots, 0, 1) & \mapsto 0 \\ (0, \dots, 1, 0) & \mapsto 1 \\ (0, \dots, 1, 1) & \mapsto 2 \\ ⋮ \\ (1, \dots, 1, 1) & \mapsto 2^{n} - 1 . \end{aligned}

🔗

Now let us consider a circuit with four input variables and a single output. Suppose that we can permute the leads of any circuit according to the following permutation group:

\begin{matrix} (a), (a, c), (b, d), (a, d, c, b), \\ (a, b, c, d), (a, b) (c, d), (a, d) (b, c), (a, c) (b, d) . \end{matrix}

🔗

The permutations of the four possible input variables induce the permutations of the output values in Table 14.27.

🔗

Hence, there are

\frac{1}{8} (2^{16} + 2 \cdot 2^{12} + 2 \cdot 2^{6} + 3 \cdot 2^{10}) = 9616

🔗

possible switching functions of four variables under this group of permutations. This number will be even smaller if we consider the full symmetric group on four letters.

🔗

Table 14.27. Permutations of switching functions in four variables

Group		Number
Permutation	Switching Function Permutation	of Cycles
$(a)$	$(0)$	16
$(a, c)$	$(2, 8) (3, 9) (6, 12) (7, 13)$	12
$(b, d)$	$(1, 4) (3, 6) (9, 12) (11, 14)$	12
$(a, d, c, b)$	$(1, 2, 4, 8) (3, 6.12, 9) (5, 10) (7, 14, 13, 11)$	6
$(a, b, c, d)$	$(1, 8, 4, 2) (3, 9, 12, 6) (5, 10) (7, 11, 13, 14)$	6
$(a, b) (c, d)$	$(1, 2) (4, 8) (5, 10) (6, 9) (7, 11) (13, 14)$	10
$(a, d) (b, c)$	$(1, 8) (2, 4) (3, 12) (5, 10) (7, 14) (11, 13)$	10
$(a, c) (b, d)$	$(1, 4) (2, 8) (3, 12) (6, 9) (7, 13) (11, 14)$	10

🔗

Subsection Historical Note

🔗

William Burnside was born in London in 1852. He attended Cambridge University from 1871 to 1875 and won the Smith’s Prize in his last year. After his graduation he lectured at Cambridge. He was made a member of the Royal Society in 1893. Burnside wrote approximately 150 papers on topics in applied mathematics, differential geometry, and probability, but his most famous contributions were in group theory. Several of Burnside’s conjectures have stimulated research to this day. One such conjecture was that every group of odd order is solvable; that is, for a group

G

of odd order, there exists a sequence of subgroups

G = H_{n} \supset H_{n - 1} \supset \dots \supset H_{1} \supset H_{0} = {e}

🔗

such that

H_{i}

is normal in

H_{i + 1}

and

H_{i + 1} / H_{i}

is abelian. This conjecture was finally proven by W. Feit and J. Thompson in 1963. Burnside’s The Theory of Groups of Finite Order, published in 1897, was one of the first books to treat groups in a modern context as opposed to permutation groups. The second edition, published in 1911, is still a classic.

Prev Top Next