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.Pólya'nın sayma teoremi, sembolik kombinatorik ve kombinatoryal türler teorisi bağlamında da çeşitli uygulama alanlarına sahiptir.X, sonlu bir küme ve G, X kümesinin permütasyonlarının grubu (ya da X kümesi üzerinde davranan sonlu bir simetri grubu) olsun. Bu durumda X kümesi, sonlu sayıda boncuktan oluşan bir yığını temsil edebilir ve G, bu boncukların permütasyonlarından oluşan bir grup olabilir. Örneğin, X kümesi bir daire etrafındaki n adet boncuktan oluşan bir kolye ise bu küme üzerinde dönme simetrisi önem taşır. Bu nedenle G, döngüsel grup Cn olur. Benzer şekilde, X kümesi bir daire etrafındaki n adet boncuktan oluşan bir bilezik ise bu küme üzerinde dönme ve yansıma simetrisi önem taşır. Bu nedenle G, dihedral grup Dn olur. Bunun dışında, Y'nin sonlu sayıda renkten (boncukların renkleri) oluşan bir küme olduğunu varsayalım. Bu boncukların renkli düzenlemelerinin kümesi (başka bir deyişle,  biçimindeki fonksiyonların kümesi), YX olsun. Bu durumda G grubu, YX kümesinin üzerinde davranır. Pólya'nın sayma teoremi, aşağıdaki formülle G grubunun YX kümesi üzerindeki davranışının yörünge sayısını hesaplayarak boncukların renkli düzenlemelerinin sayısını verir:(, kullanılan renklerin sayısı ve c(g), G grubunun bir g elemanının X'in permütasyonu olarak değerlendirilmesi durumunda bulundurduğu döngü sayısıdır).Teoremin daha genel ve daha önemli olan versiyonunda, kullanılan renkler bir ya da daha fazla şekilde ağırlıklandırılır ve renklerden oluşan kümenin sonlu katsayılara sahip bir üretim fonksiyonuna sahip olması şartıyla sonsuz sayıda renk kullanılabilir. Kullanılan renklere verilen ağırlık değerlerinin sayısı, kümenin üretim fonksiyonunun değişken sayısını belirler. Tek değişkenli durumda,fonksiyonu, her w ≥ 0 tam sayısı için ağırlık değeri w olan fw adet renk bulunmak üzere renk kümesinin üretim fonksiyonu olur. Çok değişkenli durumda ise her rengin ağırlığı, doğal sayılardan oluşan bir vektördür. Bu şekildeki her  vektörü için ağırlık değeri  olan  adet renk bulunmak üzere(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).X kümesinin elemanı olan boncukların renkli bir düzenlemesi, G grubunun YX kümesi üzerindeki davranışının bir yörüngesidir. φ ∈ YX fonksiyonu, bu yörüngenin temsilci bir elemanı olmak üzere bu biçimdeki bir düzenlemenin ağırlığı, her x ∈ X elemanı için φ(x) renklerinin ağırlıklarının toplamı olarak tanımlanır. Teorem, boncukların renkli düzenlemelerinin ağırlıklarına göre sayısını veren üretim fonksiyonunun aşağıdaki bağıntı ile verildiğini belirtir:Bu bağıntıyı daha önce verilen basitleştirilmiş versiyona indirgemek için, m adet rengin kullanıldığını ve her birinin ağırlığının 0 olduğunu kabul edebiliriz. O hâlde, f(t) = m vePó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.X, küpün yüzlerinden oluşan bir küme, Y, m farklı renkten oluşan bir küme ve G, küpün dönme simetrilerinden oluşan bir grup olsun. Teoremin bahsedilen probleme uygulanabilmesi için G grubunun her bir elemanının X kümesinin bir permütasyonu olarak değerlendirilmesi durumunda bulundurduğu döngü sayısı hesaplanmalıdır. Bu doğrultuda, G grubunun 24 elemanı aşağıdaki gibi beş gruba ayrılabilir:Bu şekilde yalnızca bir permütasyon bulunur ve döngü sayısı, e birim elemanı göstermek üzere,  olarak verilir.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, küpü bir öncekine benzer şekilde hareket ettirir. Bu şekilde üç permütasyon bulunur ve döngü sayıları,  olarak verilir.Bu permütasyonlar, cisim köşegeni etrafında küpü döndürür. Bu şekilde sekiz 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.Bir simetrik grup elemanının döngü sayısı, o elemanın bulunduğu eşlenik sınıfına bağlıdır. Bu nedenle eşyapılı olmayan m köşeli basit çizgelerin sayısını bulmak için, verilen m değerine göre Sm grubunun eşlenik sınıflarının incelenmesi gerekir. Örneğin, m = 3 alındığında S3 grubunun elemanları aşağıdaki gibi incelenebilir: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 bir permütasyon bulunur ve bu permütasyon bütün kenarları sabit tutar. Bu nedenle bu permütasyonun döngü sayısı 3 olur.adet eşyapılı olmayan m köşeli basit çizge olduğu sonucu elde edilir. Bu eşyapı sınıfları, sağda gösterilmiştir.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.Bu şekilde bir permütasyon bulunur ve bu permütasyon bütün kenarları sabit tutar. Bu nedenle bu permütasyonun döngü sayısı 6 olur.adet eşyapılı olmayan m köşeli basit çizge olduğu sonucu elde edilir. Bu eşyapı sınıfları, sağda gösterilmiştir.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.Üç köşeli basit çizgeler için,  kenardan oluşan X kümesi üzerinde davranan S3 grubunun döngü indeksi, yukarıdaki inceleme göz önünde bulundurularak şu şekilde ifade edilebilir:Dört köşeli basit çizgeler için ise  kenardan oluşan X kümesi üzerinde davranan S4 grubunun döngü indeksi, yukarıdaki inceleme göz önünde bulundurularak şu şekilde ifade edilebilir: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.X, n adet boncuktan oluşan bir küme; Y, k farklı renkten oluşan bir küme ve G, döngüsel grup Cn olsun. Birbirinden farklı, n uzunluğundaki k'lı kolyelerin sayısını Nk(n) ile gösterelim. Bu değerin hesaplanması için Pólya'nın sayma teoreminin ağırlıksız versiyonu kullanılabilir. Bunun için, G grubunun her bir elemanının X kümesinin bir permütasyonu olarak değerlendirilmesi durumunda bulundurduğu döngü sayısının hesaplanması gerekir. G grubu, üretici elemanı da kullanılarak G = ⟨g⟩ biçiminde ifade edilebilir. z ∈  olmak üzere G grubunun bir gz elemanının derecesi, |gz| = x olarak verilirse e = gn olmak üzere gxz = e olur. Bu durumda  olur. O hâlde,yazılabilir. Bu koşulu sağlayan en küçük x pozitif tam sayısı,  olacaktır. Bu nedenle  olur. G grubunun her bir elemanı, n elemanlı X kümesinin bir permütasyonu olarak değerlendirileceği için, grubun üretici elemanı olan g'nin n elemanlı bir döngüsel permütasyon olması gerekir. Bu noktadan hareketle,  olarak bulunur. Böylece,Bu sonuçtan daha kullanışlı bir bağıntının elde edilmesi için, z ∈ {0, 1, ..., n-1} olmak üzere  denkleminin çözümlerinin sayısı hesaplanmalıdır. Bu ifade,  denklemi ile aynı anlama gelmektedir. Buradan, denklemin çözüm sayısının  olduğu anlaşılır (, Euler'in fi fonksiyonunu göstermektedir.). Buna göre,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.Bunun dışında, 1 < i ≤ k aralığındaki her i tam sayısı için ri ifadesi bir rengi temsil etmek üzere Y = {r1, r2, ..., rk} yazılabilir. Bu kümenin her bir elemanı için,       olmak üzere  biçiminde bir ağırlık değeri tanımlandığında elde edilecek olan üretim fonksiyonu, oluşabilecek kolyelerin sayısını renklerin kullanım sayısına göre gruplandırır. Bu durumda, her ağırlık değeri (w) için fw = 1 olur. Buna göre,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).Bir önceki bölümde belirtildiği üzere, z ∈  olmak üzere  olur. Yansıma simetrisini gösteren elemanlar için ise simetri eksenlerinin düzgün çokgene ait köşe ve kenarları birbirine bağlama durumuna göre aşağıdaki eşitlik geçerli olur:Kolyelerde olduğu gibi bileziklerde de bu yolla ulaşılan bir bağıntı, yalnızca kullanılan boncuk ve renk sayısının bilindiği durumlarda istenen sonucu verir. Renkli boncuklardan oluşan her bir çoklu kümeden kaç farklı bilezik oluşturulabileceğini gösteren bir üretim fonksiyonunun elde edilmesi için Pólya'nın sayma teoreminin ağırlıklı versiyonu kullanılmalıdır. Bu fonksiyonu Bn,k(t1, t2, ...) ile gösterelim. Bir önceki bölümde belirtildiği üzere, z ∈  olmak üzere G grubunun bir az 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. Yansıma simetrisini gösteren elemanların bulundurduğu döngüler ise ya bir ya da iki elemanlı olacaktır. Bu durumda aşağıdaki eşitlik geçerli olur:Kullanılan renklerin ağırlıklandırılması, kolyelerdekine benzer şekilde gerçekleştirilebilir:       olmak üzere Y = {r1, r2, ..., rk} kümesinin her bir elemanı için  olsun. Bu durumda, her ağırlık değeri (w) için fw = 1 olur. Buna göre,Çizge kuramında bir köklü ağaç, bir köşesi kök olarak belirlenmiş bir ağaç olarak tanımlanır. Üçlü ağaç ise, her bir köşesi tam olarak üç adet alt köşeye sahip olan (düğüm) ya da hiçbir alt köşeye sahip olmayan (yaprak) ağaçların ismidir. Pólya'nın sayma teoremi, belli bir düğüm sayısına sahip kaç adet eşyapılı olmayan köklü üçlü ağaç oluşturulabileceğini hesaplamada kullanılabilir. Bir köklü ağaç, başka bir köklü ağacın düğümlerinin alt köşelerinin dizilimlerinin değiştirilmesiyle elde edilebiliyorsa bu iki ağaç eşyapılı olur. Buna göre, köklü bir üçlü ağacın bir düğümünün alt köşeleri üzerinde davranan grup, S3 simetrik grubu olur. Bu grubun döngü indeksi,Bir köklü üçlü ağaç, ya bir yaprak ya da her biri yine bir köklü üçlü ağaç olan üç adet alt köşesi bulunan bir düğüm olarak değerlendirilebilir. Pólya'nın sayma teoremi, köklü üçlü ağaçların bu özyinelemeli yapısını fonksiyonel bir eşitliğe çevirir. Bunun için, bir köklü üçlü ağacın ağırlık değerini bu ağacın düğümlerinin sayısı olarak tanımlayalım. Eşyapılı olmayan köklü üçlü ağaçların sayısını düğümlerinin sayısına göre veren üretim fonksiyonu, F(t) olsun. Bir düğümün sahip olduğu üç alt köşeyi, düğüm sayısı ile ağırlıklandırılmış köklü üçlü ağaçlar ile "boyadığımızda" yeni bir köklü üçlü ağaç elde ederiz. Bu nedenle, renk kümesinin üretim fonksiyonu  olur. Bu durumda Pólya'nın sayma teoremi,ifadesini köklü üçlü ağaçların üretim fonksiyonu olarak verir. Ancak bu işlem sırasında ağacın kökü hesaba katılmadığı için bu fonksiyon ile üretilen bir köklü üçlü ağacın ağırlık değeri, olması gerekenden bir eksik bulunur. Bu nedenle,olur. Bu ifade, n düğümlü köklü üçlü ağaçların sayısını veren tn dizisi için a, b ve c sayıları negatif olmayan tam sayılar olmak üzere aşağıda verilen özyinelemeli bağıntıya denktir:Teoremin ağırlıksız versiyonunun ispatı, bir küme üzerindeki bir grup davranışının yörünge sayısını veren Burnside önsavı kullanılarak yapılabilir. Burnside önsavı, bir X kümesinin üzerinde davranan bir G grubu için aşağıdaki biçimde ifade edilebilir:YX kümesinin bir elemanının X kümesinin bir permütasyonu tarafından sabitlenmesi için, aynı döngüdeki her bir elemanın aynı renge sahip olması gerekir. Bu nedenle,olur. Burnside önsavı, bu bilgi de kullanılarak G grubunun YX kümesi üzerindeki davranışına uygulandığında  olmak üzere,Teoremin ağırlıklı versiyonunun ispatında, f ve F üretim fonksiyonları aşağıdaki gibi ifade edilecektir:Bir  ağırlık vektörü için  değerinin hesaplanmasında Burnside önsavı kullanılabilir.  kümesi, ağırlığı  olan renkli düzenlemelerin kümesi olmak üzere,YX kümesinin bir elemanının X kümesinin bir permütasyonu tarafından sabitlenmesi için, aynı döngüdeki her bir elemanın aynı renge sahip olması gerekir. Bu nedenle, bir g ∈ G elemanının her bir döngüsü (q) için yapılabilecek boyamaları ağırlığına göre veren üretim fonksiyonuChyzak, F (1997). Enumerating alcohols and other classes of chemical molecules, an example of Pólya theory.Zenil, H.; Pavlyk, O. (2011). Applying the Pólya-Burnside Enumeration Theorem . The Wolfram Demonstrations Project.