Lema de Burnside / Teorema da enumeração de Pólya

Lema de Burnside

O lema de Burnside foi formulado e comprovado por Burnside em 1897, mas historicamente já tinha sido descoberto em 1887 por Frobenius, e até mesmo antes em 1845 por Cauchy. Portanto, as vezes ele é chamado de lema de Cauchy-Frobenius.

O lema de Burnside nos permite contar o número de classes de equivalência em conjuntos, baseado na simetria interna.

Objetos e representações

Temos que distinguir claramente o número de objetos e o número de representações.

Representações diferentes podem corresponder aos mesmos objetos, mas é claro que qualquer representação corresponde exatamente a um objeto. Consequentemente, o conjunto de todas as representações é dividido em classes de equivalência. Nossa tarefa é calcular o número de objetos ou, equivalentemente, o número de classes de equivalência. O exemplo a seguir tornará a diferença entre objeto e representação mais clara.

Coloração de árvores binárias

Suppose we have the following problem. Suponha que tenhamos o seguinte problema. Temos que contar o número de maneiras de colorir uma árvore binária enraizada com $n$ vértices with two colors, com duas cores, onde em cada vértice não distinguimos entre os filhos esquerdo e direito.

Aqui, o conjunto de objetos é o conjunto de diferentes colorações da árvore.

Agora, definimos o conjunto de representações. Uma representação de uma coloração é uma função $f(v)$, que atribui a cada vértice uma cor (aqui usamos as "cores" $0$ e $1$). O conjunto de representações é o conjunto que contém todas as funções possíveis desse tipo, e seu tamanho é igual a $2^n$.

Ao mesmo tempo, introduzimos uma partição desse conjunto em classes de equivalência.

Por exemplo, suponha que $n = 3$, e a árvore consiste da raiz $1$ e seus dois filhos $2$ e $3$. Então, as seguintes funções $f_1$ e $f_2$ são consideradas equivalentes. $$\begin{array}{ll}f_1(1) = 0 & f_2(1) = 0\\ f_1(2) = 1 & f_2(2) = 0\\ f_1(3) = 0 & f_2(3) = 1 \end{array}$$

Permutações invariantes

Por que essas duas funções $f_1$ e $f_2$ pertencem à mesma classe de equivalência? Intuitivamente, isso é compreensível - podemos reorganizar os filhos do vértice $1$, $2$ e $3$, e, após essa transformação da função $f_1$, ela irá coincidir com $f_2$.

Mas formalmente isso significa que existe uma permutação invariável $\pi$ (ou seja, uma permutação que não altera o objeto em si, mas apenas sua representação), de modo que: $$f_2 \pi \equiv f_1$$

Assim, a partir da definição de objetos, podemos encontrar todas as permutações invariantes, ou seja, todas as permutações que não alteram o objeto ao aplicar a permutação à representação. Em seguida, podemos verificar se duas funções $f_1$ e $f_2$ são equivalentes (ou seja, se correspondem ao mesmo objeto) checando a condição $f_2 \pi \equiv f_1$ para cada permutação invariante (ou equivalentemente $f_1 \pi \equiv f_2$). Se pelo menos uma permutação for encontrada, para a qual condição for satisfeita, então $f_1$ e $f_2$ são equivalentes, caso contrário, não serão equivalentes.

Encontrar todas essas permutações invariantes com relação à definição do objeto é uma etapa fundamental para a aplicação do lema de Burnside e do teorema de enumeração de Pólya. É claro que essas permutações invariantes dependem do problema específico, e sua descoberta é um processo puramente heurístico baseado em considerações intuitivas. No entanto, na maioria dos problemas, é suficiente encontrar manualmente várias permutações "básicas", com as quais todas as outras permutações podem ser geradas (elas podem ser válidas na resposta para o problema e essa parte do trabalho pode ser transferida para um computador).

Não é difícil entender que permutações invariantes formam um grupo, uma vez que o produto (composição) de permutações invariantes é novamente uma permutação invariável. Denotamos o grupo de permutações invariantes como $G$.

A declaração do lema

Para a formulação do lema, precisamos de mais uma definição da álgebra. Um ponto fixo $f$ para uma permutação $\pi$ é um elemento invariável sob essa permutação: $f \equiv f \pi$. Por exemplo, os pontos fixos são aquelas funções $f$ que correspondem a cores que não mudam quando a permutação $\pi$ é aplicada a eles (ou seja, elas não mudam no sentido formal da igualdade de funções) . Denotamos por $I(\pi)$ o número de pontos fixos para a permutação $\pi$.

Então, o lema de Burnside: o número de classes de equivalência é igual à soma dos números de pontos fixos em relação a todas as permutações do grupo $G$, dividido pelo tamanho desse grupo: $$|\text{Classes}| = \frac{1}{|G|} \sum_{\pi \in G} I(\pi)$$

Embora o lema de Burnside em si não seja tão conveniente de usar na prática (não fica claro como procurar rapidamente o valor $I(\pi)$, ele revela claramente a essência matemática na qual a idéia de calcular classes de equivalência se baseia.

Prova do lema de Burnside

A prova do lema de Burnside descrito aqui não é importante para as aplicações práticas, portanto pode ser ignorada na primeira leitura.

A prova aqui é a mais simples conhecida, e não usa a teoria de conjuntos. A prova foi publicada por Kenneth P. Bogart em 1991.

Precisamos provar a seguinte declaração: $$|\text{Classes}| \cdot |G| = \sum_{\pi \in G} I(\pi)$$

O valor no lado direito nada mais é do que o número de "pares invariantes" $(f, \pi)$, ou seja, pares nos quais $f \pi \equiv f$. É óbvio que podemos mudar a ordem da soma. Deixamos a soma iterar sobre todos os elementos $f$ e somar sobre os valores $J(f)$ - o número de permutações para as quais $f$ é um ponto fixo. $$|\text{Classes}| \cdot |G| = \sum_{f} J(f)$$

Para provar essa fórmula, comporemos uma tabela com colunas rotuladas com todas as funções $f_i$ e linhas rotuladas com todas as permutações $\pi_j$. E preenchemos as células com $f_i \pi_j$. Se observarmos as colunas nesta tabela como conjuntos, algumas delas coincidirão, e isso significa que as funções correspondentes $f$ para essas colunas também são equivalentes. Assim, o número de colunas diferentes (como conjuntos) é igual ao número de classes. Aliás, do ponto de vista da teoria dos grupos, a coluna rotulada com $f_i$ é a órbita desse elemento. Para elementos equivalentes, as órbitas coincidem e o número de órbitas fornece exatamente o número de classes.

Assim, as colunas da tabela se decompõem em classes de equivalência. Vamos fixar uma classe e examinar as colunas nela. Primeiro, observe que essas colunas podem conter apenas os elementos $f_i$ da classe de equivalência (caso contrário, alguma permutação $\pi_j$ moveu uma das funções para uma classe de equivalência diferente, o que é impossível, pois consideramos apenas permutações invariantes). Em segundo lugar, cada elemento $f_i$ ocorrerá o mesmo número de vezes em cada coluna (isso também decorre do fato de as colunas corresponderem a elementos equivalentes). A partir disso, podemos concluir que todas as colunas da mesma classe de equivalência coincidem entre si como multiconjuntos.

Agora escolha um elemento arbitrário $f$. Por um lado, ocorre em sua coluna exatamente $J(f)$ vezes (por definição). Por outro lado, todas as colunas na mesma classe de equivalência são iguais como multiconjuntos. Portanto, dentro de cada coluna de uma determinada classe de equivalência, qualquer elemento $g$ ocorre exatamente $J(g)$ vezes.

Assim, se arbitrariamente pegarmos uma coluna de cada classe de equivalência e somarmos o número de elementos nelas, obteremos, por um lado, $|\text{Classes}| \cdot |G|$ (simplesmente multiplicando o número de colunas pelo número de linhas), e por outro lado obtemos a soma das quantidades de $J(f)$ para todo $f$ (isso vem de argumentos anteriores): $$|\text{Classes}| \cdot |G| = \sum_{f} J(f)$$

Teorema da enumeração de Pólya

O teorema de enumeração de Pólya é uma generalização do lema de Burnside e também fornece uma ferramenta mais conveniente para encontrar o número de classes de equivalência. Vale ressaltar que esse teorema já foi descoberto antes de Pólya por Redfield em 1927, mas sua publicação passou despercebida pelos matemáticos. Pólya obteve os mesmos resultados independentemente em 1937, e sua publicação foi mais bem sucedida.

Aqui discutimos apenas um caso especial do teorema da enumeração de Pólya, que será muito útil na prática. A fórmula geral do teorema não será discutida.

Denotamos por $C(\pi)$ o número de ciclos na permutação $\pi$. Então, a seguinte fórmula (um caso especial do teorema da enumeração de Pólya) é válida: $$|\text{Classes}| = \frac{1}{|G|} \sum_{\pi \in G} k^{C(\pi)}$$ $k$ é o número de valores que cada elemento de representação pode receber, no caso da coloração de uma árvore binária, isso seria $k = 2$.

Evidência

Essa fórmula é uma conseqüência direta do lema de Burnside. Para obtê-lo, basta encontrar uma expressão explícita para $I(\pi)$, que aparece no lema. Lembre-se de que $I(\pi)$ é o número de pontos fixos na permutação $\pi$.

Assim, consideramos uma permutação $\pi$ e algum elemento $f$. Durante a aplicação de $\pi$, os elementos em $f$ se movem pelos ciclos da permutação. Como o resultado deve obter $f \equiv f \pi$, os elementos tocados por um ciclo devem ser todos iguais. Ao mesmo tempo, diferentes ciclos são independentes. Assim, para cada ciclo de permutação $\pi$ podemos escolher um valor (entre $k$ possíveis) e, assim, obtemos o número de pontos fixos: $$I(\pi) = k^{C(\pi)}$$

Aplicação: colorindo colares

O problema "colares" é um dos problemas combinatórios clássicos. A tarefa é contar o número de colares diferentes de $n$ miçangas(ou seja, dentre um conjunto de colares), cada uma dos quais pode ser pintado com qualquer uma das $k$ cores. Ao comparar dois colares, eles podem ser rotacionados, mas não revertidos completamente (ou seja, é permitido uma mudança cíclica).

Nesse problema, podemos encontrar imediatamente o grupo de permutações invariantes: $$\begin{align} \pi_0 &= 1 2 3 \dots n\\ \pi_1 &= 2 3 \dots n 1\\ \pi_2 &= 3 \dots n 12\\ &\dots\\ \pi_{n-1} &= n 1 2 3\dots\end{align}$$

Vamos encontrar uma fórmula explícita para calcular $C(\pi_i)$. Primeiro, observamos que a permutação $\pi_i$ tem, na $j$-ésima posição, o valor $i + j$ (sobre o módulo $n$). Se verificarmos a estrutura do ciclo para $\pi_i$. Vemos que $1$ vai para $1 + i$, $1 + i$ vai para $1 + 2i$, que vai para $1 + 3i$, etc., até chegarmos a um número no formato $1 + k n$. Definições similares podem ser feitas para os elementos restantes. Portanto, vemos que todos os ciclos têm o mesmo comprimento, ou seja, $\frac{\text{lcm}(i, n)}{i} = \frac{n}{\gcd(i, n)}$. Assim, o número de ciclos em $\pi_i$ será igual a $\gcd(i, n)$.

Substituindo esses valores no teorema da enumeração de Pólya, obtemos a solução: $$\frac{1}{n} \sum_{i=1}^n k^{\gcd(i, n)}$$

Você pode deixar a fórmula assim ou simplificá-la ainda mais. Vamos transferir a soma para que possamos iterar sobre todos os divisores de $n$. Na soma original, haverá muitos termos equivalentes: se $i$ não for um divisor de $n$, esse divisor poderá ser encontrado após calcular o $\gcd/mdc(i, n)$. Portanto, para cada divisor $d ~|~ n$ seu termo $k^{\gcd(d, n)} = k^d$ aparecerá na soma várias vezes, ou seja, a resposta para o problema pode ser reescrita como $$\frac{1}{n} \sum_{d ~|~ n} C_d k^d,$$ onde $C_d$ é o número desses números $i$ com $\gcd(i, n) = d$. Podemos encontrar uma expressão explícita para esse valor. Qualquer um desses números $i$ terá a forma $i = d j$ com $\gcd(j, n / d) = 1$ (caso contrário, $\gcd(i, n) > d$). Portanto, podemos contar o número de $j$ com esse comportamento. A função phi de Euler fornece o resultado $C_d = \phi(n / d)$, e, portanto, obtemos a resposta: $$\frac{1}{n} \sum_{d ~|~ n} \phi\left(\frac{n}{d}\right) k^d$$

Aplicação: Colorindo um toro(uma rosquinha :D )

Muitas vezes, não podemos obter uma fórmula explícita para o número de classes de equivalência. Em muitos problemas, o número de permutações em um grupo pode ser muito grande para cálculos manuais e não é possível calcular analiticamente o número de ciclos neles.

Nesse caso, devemos encontrar manualmente várias permutações "básicas", para que elas possam gerar todo o grupo $G$. Em seguida, podemos escrever um programa que irá gerar todas as permutações do grupo $G$, contar o número de ciclos neles e calcular a resposta com a fórmula.

Considere o exemplo do problema para colorir um toro. Há uma folha de papel quadriculado $n \times m$ ($n < m$), algumas das células são pretas. Em seguida, um cilindro é obtido desta folha colando os dois lados de comprimentos $m$. Em seguida, um toro é obtido do cilindro colando os dois círculos (superior e inferior) sem torcer. A tarefa é calcular o número de toros/rosquinhas de cores diferentes, supondo que não possamos ver as linhas coladas e que o toro possa ser girado e girado.

Novamente, começamos com um pedaço $n \times m$ de papel. Os seguintes tipos de transformações preservam a classe de equivalência: uma mudança cíclica das linhas, uma mudança cíclica das colunas e uma rotação da folha em 180 graus. Também é possível ver que essas transformações podem gerar todo o grupo de transformações invariantes. Se, de alguma forma, numerarmos as células do papel, podemos escrever três permutações $p_1$, $p_2$, $p_3$ correspondentes a esses tipos de transformação.

Em seguida, resta apenas gerar todas as permutações obtidas como um produto. Todas essas permutações terão a forma $p_1^{i_1} p_2^{i_2} p_3^{i_3}$ onde $i_1 = 0 \dots m-1$, $i_2 = 0 \dots n-1$, $i_3 = 0 \dots 1$.

Assim, podemos escrever as implementações para esse problema.

using Permutation = vector<int>;  //boa maneira para lembrar as permutações

void operator*=(Permutation& p, Permutation const& q) {
    Permutation copy = p;
    for (int i = 0; i < p.size(); i++)
        p[i] = copy[q[i]];
}

int count_cycles(Permutation p) {
    int cnt = 0;
    for (int i = 0; i < p.size(); i++) {
        if (p[i] != -1) {
            cnt++;
            for (int j = i; p[j] != -1;) {
                int next = p[j];
                p[j] = -1;
                j = next;
            }
        }
    }
    return cnt;
}

int solve(int n, int m) {
    Permutation p(n*m), p1(n*m), p2(n*m), p3(n*m);
    for (int i = 0; i < n*m; i++) {
        p[i] = i;
        p1[i] = (i % n + 1) % n + i / n * n;
        p2[i] = (i / n + 1) % m * n + i % n;
        p3[i] = (m - 1 - i / n) * n + (n - 1 - i % n);
    }

    set<Permutation> s;
    for (int i1 = 0; i1 < n; i1++) {
        for (int i2 = 0; i2 < m; i2++) {
            for (int i3 = 0; i3 < 2; i3++) {
                s.insert(p);
                p *= p3;
            }
            p *= p2;
        }
        p *= p1;
    }

    int sum = 0;
    for (Permutation const& p : s) {
        sum += 1 << count_cycles(p);
    }
    return sum / s.size();
}