Pólya'nın sayma teoremi

Pólya'nın sayma teoremi (Redfield – Pólya teoremi olarak da bilinir), bir küme üzerindeki bir grup davranışının yörünge sayısını veren Burnside önsavını izleyen ve genelleştiren bir kombinatorik teoremidir. Teorem; ilk olarak 1927 yılında J. Howard Redfield tarafından yayımlanmış, 1937'de ise teoremin ortaya çıkardığı sonuçları birçok sayma problemine, özellikle kimyasal bileşiklerin sayımına uygulayarak büyük ölçüde yaygınlaştıran George Pólya tarafından yeniden keşfedilmiştir.

(n, X kümesinin eleman sayısı ve ck(g), G grubunun bir g elemanının X'in permütasyonu olarak değerlendirilmesi durumunda bulundurduğu k elemanlı döngü sayısıdır).

Pólya'nın sayma teoreminin çizge kuramında ağaçlara ve kimyada açık halkalı moleküllere uygulanması sırasında, "boncukların" renkli bir düzenlemesi aslında bu yolla elde edilen düzenlemelerin bir düzenlemesi olarak kabul edilir. Böylece, renk kümesinin üretim fonksiyonu olan f, "renkli" düzenlemelerin üretim fonksiyonu olan F fonksiyonundan türetilir ve Pólya'nın sayma teoremi, özyinelemeli bir formül hâline gelir.

Verilen m değişik renk kullanılarak bir küpün yüzleri boyanıyor. Küpün istenildiği kadar ve istenen istikametlerde döndürülmesiyle elde edilen herhangi iki boyama özdeş kabul edildiğinde bu boyama işleminin kaç farklı biçimde gerçekleştirilebileceğinin hesaplanması için Pólya'nın sayma teoreminin ağırlıksız versiyonu kullanılabilir.

Bu permütasyonlar, seçilen bir yüzeyin ve onun karşısında bulunan yüzeyin merkezinden geçen bir eksen etrafında küpü döndürür. Bu şekilde altı permütasyon bulunur ve döngü sayıları, olarak verilir.

Bu permütasyonlar, birbirine paralel olup aynı yüzeyde bulunmayan iki kenarın orta noktalarını birleştiren bir eksen etrafında küpü döndürür. Bu şekilde altı permütasyon bulunur ve döngü sayıları, olarak verilir.

Çizge kuramında bir basit çizge, herhangi bir döngüsü veya aynı iki köşeyi birleştiren birden fazla kenarı bulunmayan bir yönsüz çizge olarak tanımlanır. Belirli bir sayıda bulunan köşeler birleştirilerek eşyapılı olmayan kaç adet basit çizge oluşturulabileceğinin hesaplanması için Pólya'nın sayma teoreminin ağırlıksız versiyonu kullanılabilir.

Bir basit çizgeyi, kenarların renkli bir düzenlemesi olarak yorumlamak mümkündür. m adet köşeden oluşan bir basit çizge için X, çizilebilecek adet kenardan oluşan bir küme, Y = {siyah, beyaz} kümesi ise bu kenarların görünüp görünmeyeceğini belirleyen bir renk kümesi olsun. simetrik grubu, X kümesinin üzerinde davranır: G kümesinin elemanı olan bir φ permütasyonu, {a, b} biçimindeki bir kenarı {φ(a), φ(b)} kenarına dönüştürür. Buna göre, m kenarlı basit çizgelerden oluşan bir eşyapı sınıfı, G grubunun YX kümesi üzerindeki davranışının bir yörüngesi olur. Bu grubun her bir elemanının X kümesinin bir permütasyonu olarak değerlendirilmesi durumunda bulundurduğu döngü sayısı teoremde yerine konulduğunda istenen sonuca ulaşılır.

Bu şekilde iki permütasyon bulunur ve bu permütasyonlar, X kümesinin her bir elemanını bir diğerine dönüştürebilir. Bu nedenle bu permütasyonların döngü sayısı 1 olur.

Bu şekilde üç permütasyon bulunur ve bu permütasyonlar, kenarlardan birini sabit tutarken diğerlerini birbirine dönüştürür. Bu nedenle bu permütasyonların döngü sayısı 2 olur.

Bu şekilde 6 permütasyon bulunur ve bu permütasyonlar, X kümesinin elemanlarını biri dört elemanlı, diğeri iki elemanlı olan iki farklı döngüye ayırır. Bu nedenle bu permütasyonların döngü sayısı 2 olur.

Bu şekilde 8 permütasyon bulunur ve bu permütasyonlar, X kümesinin elemanlarını üç elemanlı iki farklı döngüye ayırır. Bu nedenle bu permütasyonların döngü sayısı 2 olur.

Bu şekilde 3 permütasyon bulunur ve bu permütasyonlar, kenarlardan iki tanesini sabit tutarken diğer kenarları iki elemanlı iki farklı döngüye ayırır. Bu nedenle bu permütasyonların döngü sayısı 4 olur.

Bu şekilde 6 permütasyon bulunur ve bu permütasyonlar, kenarlardan iki tanesini sabit tutarken diğer kenarları iki elemanlı iki farklı döngüye ayırır. Bu nedenle bu permütasyonların döngü sayısı 4 olur.

Eşyapılı olmayan basit çizgelerin sayısı incelenirken Pólya'nın sayma teoreminin ağırlıklı versiyonu da kullanılabilir. Böylece, söz konusu çizgeleri kenar sayısına göre sınıflandıran bir üretim fonksiyonu elde edilebilir. Bunun için, siyah renge boyanan (görünen) bir kenarın ağırlığının 1, beyaz renge boyanan (görünmeyen) bir kenarın ağırlığının ise 0 olduğunu söyleyebiliriz. Bu durumda bir çizgenin kenar sayısı, o çizgeye karşılık gelen renkli düzenlemenin ağırlığına eşit olur. Ayrıca, verilen ağırlık değerleri için f0 = 1 ve f1 = 1 olur. Bu durumda renk kümesinin üretim fonksiyonu, olarak yazılabilir.

Kombinatorikte, n uzunluğunda bir k'lı kolye, k elemanlı bir alfabe ile oluşturulan n karakterli dizelerin her bir döngüsel ötelemesinin bir diğerine denk kabul edilmesiyle oluşan bir denklik sınıfı olarak tanımlanır. Bu denklik sınıfları, k farklı renkle boyanabilen n adet boncuğun bir çember etrafına dizilmesiyle oluşan yapıları temsil eder. Bu tanımdan yola çıkılarak bir kolye, bir döngüsel grubun n karakterli dizeler üzerindeki davranışının bir yörüngesi olarak kabul edilebilir.

Bu bağıntı yoluyla, kullanılan boncuk ve renk sayısı bilinen bir kolyenin kaç farklı şekilde oluşturulabileceğini hesaplamak mümkündür. Fakat hangi rengin kaç defa kullanıldığının bilindiği durumlarda Pólya'nın sayma teoreminin ağırlıklı versiyonu kullanılarak renkli boncuklardan oluşan her bir çoklu küme için kaç farklı kolye oluşturulabileceğini gösteren bir üretim fonksiyonunun elde edilmesi gerekir. Bu fonksiyonu Nn,k(t1, t2, ...) ile gösterelim. Yukarıda belirtildiği üzere, G = ⟨g⟩ ve z ∈ olmak üzere olur. G grubunun bir gz elemanı, aynı zamanda X kümesinin bir permütasyonu olduğu için durumunda ve x tam sayısının bundan farklı herhangi bir değeri için olur.

Kombinatorikte, n uzunluğunda bir k'lı bilezik, k elemanlı bir alfabe ile oluşturulan n karakterli dizelerin her bir döngüsel ötelemesinin ve yansımasının bir diğerine denk kabul edilmesiyle oluşan bir denklik sınıfı olarak tanımlanır (Bu durumda her bir dize, tersten yazılmış hâli ile aynı denklik sınıfında bulunur). Bu denklik sınıfları, kolyelerin temsil ettiği yapıların belli bir eksen etrafındaki yansımalarının birbirine denk kabul edilmesiyle somutlaştırılabilir. Bu tanımdan yola çıkılarak bir bilezik, bir dihedral grubun n karakterli dizeler üzerindeki davranışının bir yörüngesi olarak kabul edilebilir.

X, n adet boncuktan oluşan bir küme; Y, k farklı renkten oluşan bir küme ve G, dihedral grup Dn olsun. Birbirinden farklı, n uzunluğundaki k'lı bileziklerin sayısını Bk(n) ile gösterelim. Bu değerin hesaplanması için, kolyelerde de olduğu gibi, Pólya'nın sayma teoreminin ağırlıksız versiyonu kullanılabilir. G = Dn grubu, n kenarlı bir düzgün çokgene ait n adet dönme simetrisi ve n adet yansıma simetrisinden oluşmaktadır. Bu çokgenin saat yönünde derecelik bir dönüşünü, a elemanı ile gösterelim. Benzer şekilde, çokgenin her bir yansıma simetrisini s1, s2, ..., sn elemanları ile gösterelim. Bu durumda G grubunu, a0 = e olmak üzere G = ({e, a, a2, ..., an, s1, s2, ..., sn}, ) biçiminde ifade edebiliriz (, fonksiyonların bileşke işlemini göstermektedir).