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. For a deeper understanding I recommend reading "groups" in https://web.evanchen.cc/napkin.html

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