Imagine you have a set of elements $$$S$$$. $$$x, y \in S$$$ are equivalent if you can get from one to another by performing some operations $$$G$$$. You must count the number of non-equivalent things in the set. Turns out this is a lot easier if the operation has some special properties.

Let $$$G$$$ be the set of operations. We define $$$gx$$$ for $$$g \in G$$$ and $$$x \in S$$$ as the element that is the operation $$$g$$$ on the element $$$x$$$.

Let's define our set of operation $$$G$$$ as a "group action" if the following is satisfied.

• Every operation is invertible. For $$$x, y \in S$$$ and $$$g \in G$$$, if $$$gx = y$$$, then $$$x = g^{-1}y$$$.
• Given 2 operations, the operation of them one after other is another operation in our set. For $$$g_1, g_2 \in G$$$, there exists $$$g_3 \in G$$$ such that $$$g_3 = g_2g_1$$$

A more intuitive way to define this would be, that the graph of operations is undirected set of cliques, where an edge $$$(x, y)$$$ denotes that $$$gx = y$$$ for some $$$g$$$ (Notice invertibility guarantees this is a symmetric statement). If 2 elements are equal, its possible to get from one of them to another in one operation. Cyclic shifts of an array is one example of such a set of operations, as we will see later.

Now we need the number of connected components in this graph, which is the same as the number of non equivalent elements.

Each clique is a just a set of some equivalent copies, let's say $$$k$$$ copies. If we weigh each node by $$$1/k$$$. Then each clique will contribute exactly one to our sum. So we get the sum

This is just sum $$$1 / k$$$ over all elements. Summing over elements is a bit easier, but still, finding the size of the set seems hard.

Let us look at the number of solutions for $$$gx = y$$$. Let $$$g_{xy}$$$ be one of the solutions. Then $$$g_{xy}^{-1}gx = x$$$. So the number of solutions to $$$gx = y$$$ is same as the number of solutions for $$$gx = x$$$. Invertibility implies that there is bijection between the solutions of $$$gx = x$$$ and $$$gx = y$$$ using $$$g_{xy}$$$.

That means for each $$$x, y \in S$$$ where $$$x, y$$$ are equivalent, there is an equal number of solutions to $$$gx = y$$$. Let's imagine the size of clique is $$$k$$$ and the number of solutions to $$$gx = y$$$ is $$$s$$$ for each $$$y$$$. Then $$$ks = |G|$$$, because each $$$g$$$ is solution to some equation. So instead of using $$$1/k$$$ we use $$$s/|G|$$$ instead.

Ok we're getting somewhere. Using this in the above equation, we get

Notice that this is just the number of pairs $$$(g, x)$$$ such that $$$gx = x$$$. We can choose to iterate over $$$g$$$ instead.

And we've finally reached the long awaited burnside lemma. In many cases iterating over $$$g$$$ is easier like in the following problem.

Count the number of arrays $$$A$$$ of size $$$n$$$ with entries in $$$[1, m]$$$, where 2 arrays are considered equal, if they differ only by a cyclic shift. https://cses.fi/problemset/task/2209

Let's first take a step back, and reprove burnside's lemma on this explicit case. For a given cyclic array, let $$$k$$$ be the smallest $$$k$$$ such that $$$a_i = a_{i+k}$$$. Then this array is the concatenation of $$$a[1 : k]$$$, $$$n/k$$$ times. So there are $$$k$$$ equivalent arrays in $$$S$$$, and $$$n/k$$$ cyclic shifts that equal itself, as you would expect from the proof above. So each array should be counted $$$\frac{1}{k} = \frac{n/k}{n}$$$ times. $$$n/k$$$ is the number of cyclic shifts of this array such that the array equals itself. From here you can verify the burnside's lemma counts each element the correct number of times.

$$$G$$$ is the set of cyclic shifts of an array of size $$$n$$$, and $$$S$$$ is the $$$m^n$$$ arrays of size $$$n$$$ with entries in $$$[1, m]$$$. The number of arrays such that its $$$k$$$th cyclic shift is equal to itself is $$$m^{\gcd(k, n)}$$$. Therefore using burnside's lemma we get the answer