Burnside Lemması: "Kaç Farklı Kolye Yapabilirim?" Sorusunun Cevabı

Basit bir soru

Elinizde 6 boncuk olsun: 3 kırmızı, 3 mavi. Bunları yuvarlak bir kolyede sıralamak istiyorsunuz. Kaç farklı kolye yapabilirsiniz?

İlk düşünce: 6 yeri 3 kırmızı + 3 mavi şekilde doldurmanın yolu $\binom{6}{3} = 20$'dir. Ama dikkat — kolye dönebilir! Saat yönünde bir çentik döndürüğümüzde aynı görünüyorsa, bu aynı kolyedir. Hatta ters çevirebilirsek (yansıma) daha da az farklı kolye kalır.

Doğru cevap 20 değil. Peki kaç?

Burnside lemması cevap verir.

Grup eylemi dili

Matematiksel olarak: bir nesne kümesi $X$ var (örneğimizde 20 boyama), bir grup $G$ bu küme üzerinde eylem yapıyor (kolyeyi 6 farklı açıyla döndürmek, yani $G = \mathbb{Z}/6\mathbb{Z}$). İki boyama, biri diğerinden grup elemanıyla elde edilebiliyorsa aynı yörüngede sayılır.

Gerçek soru: kaç yörünge var?

Burnside (Cauchy-Frobenius) lemması

Lemma:

$\text{Yörünge sayısı} = \frac{1}{|G|} \sum_{g \in G} |X^g|$

Burada $X^g$, grup elemanı $g$ tarafından sabitlenen (yani $g$ uygulayınca değişmeyen) $X$ elemanlarının kümesidir. Lemma yaklaşık olarak şöyle der: yörünge sayısı, grup elemanlarının sabit nokta sayılarının ortalamasıdır.

İsim tarihsel bir hatadır: lemma aslında Cauchy (1845) ve Frobenius (1887) tarafından bulundu; William Burnside 1897 grup teorisi kitabında onları doğru atıf yapmadan kullandığı için adı yapıştı. Yine de "Burnside lemması" terimi en yaygın.

6 boncuklu kolye örneği

$X$ = 6 yerli kırmızı/mavi boyamalar, $|X| = 2^6 = 64$. Ama 3 kırmızı + 3 mavi kısıtıyla $\binom{6}{3} = 20$. Sadelik için tüm $2^6 = 64$ boyamayı düşünelim — yani her renk dağılımı mümkün.

$G = \mathbb{Z}/6$, dönme grubu. Elemanlar: $r^0, r^1, r^2, r^3, r^4, r^5$ (0°, 60°, 120°, 180°, 240°, 300°).

Her biri için sabit boyama sayısını sayalım:

• $r^0$ (özdeşlik): tüm 64 boyama sabit. $|X^{r^0}| = 64$.
• $r^1$ (60°): boyama sabit kalması için tüm 6 yer aynı renk olmalı. 2 boyama: hep kırmızı veya hep mavi. $|X^{r^1}| = 2$.
• $r^2$ (120°): 6 yer 2 yörüngeye ayrılır (her biri 3 elemanlı). Her yörünge tek renk; toplam $2^2 = 4$.
• $r^3$ (180°): 6 yer 3 yörüngeye ayrılır (her biri 2 elemanlı). $2^3 = 8$.
• $r^4$ (240°): $r^2$ ile aynı yapıda, $4$.
• $r^5$ (300°): $r^1$ ile aynı yapıda, $2$.

Toplam: $64 + 2 + 4 + 8 + 4 + 2 = 84$. Yörünge sayısı:

$\frac{84}{6} = 14$

14 farklı kolye (dönmeyle ayırdığımızda; tüm renk dağılımları için).

Sadece "3 kırmızı + 3 mavi" kısıtıyla yapsaydık benzer sayma daha az çıkar — sayma alıştırması okuyucuya kalsın.

Neden çalışıyor? (kısa)

Kanıtın özü: çift-sayma. $(x, g)$ çiftlerini iki şekilde sayın — $x$'in stabilizatörüne göre ve $g$'nin sabit kümesine göre. Yörünge-stabilizatör teoremi ($|\text{yörünge}(x)| \cdot |\text{Stab}(x)| = |G|$) ile birleştirilince formül çıkar.

Uygulamalar

1. Kolye, bilezik, mozaik desenleri: Yansımayı eklersek grup dihedral $D_n$ olur, formül aynı.
2. Rubik küpün renklendirmeleri: 6 yüzlü küpün 6 farklı renkle boyanmasının kaç gerçekten farklı yolu vardır? Küpün simetri grubu (24 dönme). Burnside ile cevap $\frac{6!}{24} = 30$.
3. Kimya — moleküler izomerler: Aynı atomları içeren ama uzayda farklı yerleşen molekülleri sayma.
4. Bilgisayar bilimi: İzomorf graf sayma; tasarım enumerasyonu.
5. Polya enumerasyon teoremi: Burnside'ın renk-ağırlıklı genellemesi; her renk farklı sayıda kullanılmak istenirse cevap verir.

Polya enumerasyonu — bir kademe ileri

George Pólya 1937'de Burnside'ı döngü indeksi ile genişletti. Grubun her elemanı için bir polinom yazıp tek formülde çözer:

$P_G(z_1, z_2, \ldots) = \frac{1}{|G|} \sum_{g \in G} z_1^{c_1(g)} z_2^{c_2(g)} \cdots$

Burada $c_k(g)$, $g$'nin $k$ uzunluklu döngü sayısıdır. Her $z_k$'ya $(x_1^k + x_2^k + \cdots)$ yerleştirip katsayı okursanız, istediğiniz renk dağılımı için yörünge sayısını alırsınız.

Kimya tarihinde Pólya bu yöntemi izomer sayma için kullandı; sonuçlar deneysel verilerle birebir tutuştu — matematiğin "tahmin ettiren" gücünün başka bir gösterisi.

Sonuç

Burnside lemması basit görünüşlü ama derin: simetriyi sayma, sayma yoluyla simetri anlama. Lise düzeyinde anlatılabilen tek satırı, modern kombinatorik, fiziksel kimya ve kodlama teorisinde her gün kullanılan bir araç.

Grup teorisinin neden "soyut" olmadığını gösteren en güzel örneklerden biri.