Combinação em simetria
Vamos supor que temos seis vértices idênticos conectados com duas linhas diferentes coloridas em verde e preto.
Quero contar quantas maneiras exclusivas podemos fazer uma partição neste sistema. Por exemplo, se eu quiser fazer partições 1x5,
A maneira mais fácil que podemos imaginar é 6C1 = 6 casos. No entanto, o sistema possui simetria rotacional com um ângulo de 60 graus. Portanto, teremos apenas 2 partições exclusivas. Se ignorarmos ainda mais a ordem da cor, teremos apenas uma partição exclusiva . A partição pode conter apenas um verde e um preto.
Para partições 3x3, torna-se um pouco mais complicado. Primeiro, podemos descobrir que existem um total de 6C3 = 20 partições. Assim que nos livrarmos da contagem dupla, teremos apenas 10 casos.
No entanto, precisamos levar em conta a simetria. Eu sei a resposta fazendo isso manualmente, temos apenas 4 casos únicos. temos (1 (3 verdes e 3 pretos) +3 (Verde + Preto) +3 (3 pretos e um verde) +3 (3 verdes e um preto).
Usando essa regra, fui capaz de contar as soluções exclusivas conforme seguidas
(4 escolha 1) temos 1 caso único
(4 escolha 2) temos 3 caixas exclusivas
(6 escolha 1) temos 1 caso único
(6 escolha 2) temos 4 caixas exclusivas
(6 escolha 3) temos 4 caixas exclusivas
Existe alguma maneira de encontrar a solução de combinação generalizada com a simetria do sistema?
Respostas
Você está pedindo o número de partições de um conjunto (aqui, um hexágono) que são diferentes em relação a algumas simetrias (neste caso, simetria rotacional). Em geral, esta é uma questão importante e bem estudada em matemática. É ótimo que você tenha encontrado este material ao estudar este exemplo em profundidade.
A maneira mais geral de resolver esse problema é usar algo chamado lema de Burnside . Se você quiser aprender mais, deve procurar um livro sobre teoria de grupo.
Para resolver este exemplo específico sistematicamente , podemos usar as idéias do lema de Burnside sem precisar explicitamente do fundo da teoria dos grupos. Por exemplo, vamos reformular sua prova de que há$4$ partições distintas do hexágono em dois conjuntos de três pontos cada.
Você corretamente apontou que há $\binom{6}{3} = 20$ possíveis subconjuntos de tamanho $3$, então há $\binom{6}{3} / 2 = 10$possíveis partições. Para uma partição$P$, deixei $f(P)$ denotam o número de maneiras de diferentes cópias giradas de $P$.
Por exemplo, em sua imagem (copiada abaixo), deixe $P$ ser a partição superior esquerda e $P'$ser a partição superior direita. Então$f(P) = 3$ e $f(P') = 1$.
Considere a lista de todos $10$ partições $P_1, \dots, P_{10}$. Cada partição$P$, é "superestimado" exatamente $f(P)$vezes. Para que cada partição que é diferente em relação à rotação seja contada uma vez, fazemos o seguinte truque. Nós consideramos a soma
$$ \sum_{i=1}^{10} \frac{1}{f(P_i)} .$$
No caso em que estamos procurando partições do hexágono em dois conjuntos de tamanho três, isso se torna a soma
$$ \left( \frac{1}{3} + \frac{1}{3} + \frac{1}{3} \right) + \left( \frac{1}{3} + \frac{1}{3} + \frac{1}{3} \right) + \left( \frac{1}{3} + \frac{1}{3} + \frac{1}{3} \right) + 1 = 4,$$
que é exatamente o que você contou!
Esta fórmula também funciona para o caso em que estamos dividindo o hexágono em um conjunto de tamanhos $1$ e um conjunto de tamanho $5$. Há, há$6$ partições totais, e para cada partição temos $f(P) = 6$(porque cada partição é uma rotação de todas as outras). Então a soma é
$$ \sum_{i=1}^6 \frac{1}{f(P)} = \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} + \frac{1}{6} = 1.$$
Experimente esta fórmula em alguns outros casos se não souber como funciona. Também funciona se você substituir o hexágono por um diferente$n$-gon, por exemplo. A parte difícil se torna o cálculo$f(P)$ para cada partição $P$(e enumerando todas as partições possíveis). Espero que isso responda a sua pergunta.