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.Riedel, M. R. (2020). "Pólya’s enumeration theorem and the symbolic method". Stuttgart Üniversitesi. == Basitleştirilmiş, ağırlıksız versiyon == 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, X \to Y 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: : \left |Y^X/G \right | = \frac{1}{|G|}\sum_{g \in G} m^{c(g)} (m=|Y|, 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). == Tam, ağırlıklı versiyon == 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, : f(t) = f_0 + f_1 t + f_2 t^2 + \cdots 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 \mathbf{a} = (w_1, w_2, \ldots) vektörü için ağırlık değeri \mathbf{a} olan f_\mathbf{a} adet renk bulunmak üzere : f(t_1, t_2, \ldots) = \sum_{w_1, w_2, \ldots \in \mathbb{N}} f_{\mathbf{a}} t_1^{w_1} t_2^{w_2}\cdots fonksiyonu, renk kümesinin üretim fonksiyonu olur. Teorem, döngü indeksi olarak adlandırılan çok değişkenli başka bir fonksiyon daha kullanır: : Z_G(t_1,t_2,\ldots,t_n) = \frac{1}{|G|}\sum_{g \in G} t_1^{c_1(g)} t_2^{c_2(g)} \cdots t_n^{c_n(g)} (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)Jin, J. (2018). "Analysis and Applications of Burnside's Lemma". Massachusetts Institute of Technology. . 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: : F(t) = Z_G(f(t),f(t^2),f(t^3),\ldots,f(t^n)). Çok değişkenli durumda ise teorem, aşağıdaki gibi ifade edilebilir: : F(t_1,t_2,\ldots) = Z_G(f(t_1,t_2,\ldots),f(t_1^2,t_2^2,\ldots),f(t_1^3,t_2^3,\ldots),\ldots,f(t_1^n,t_2^n,\ldots)). 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 ve : \left |Y^X/G \right | =F(0)= Z_G(m,m,\ldots,m) = \frac{1}{|G|}\sum_{g \in G} m^{c(g)}. 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. == Örnekler == === Renkli küpler === 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: * Birim eleman: : Bu şekilde yalnızca bir permütasyon bulunur ve döngü sayısı, e birim elemanı göstermek üzere, c(e) = 6 olarak verilir. * Yüzeylerin 90 derecelik dönme hareketleri: : 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ı, c(g) = 3 olarak verilir. * Yüzeylerin 180 derecelik dönme hareketleri: : Bu permütasyonlar, küpü bir öncekine benzer şekilde hareket ettirir. Bu şekilde üç permütasyon bulunur ve döngü sayıları, c(g) = 4 olarak verilir. * Köşelerin 120 derecelik dönme hareketleri: : 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ı, c(g) = 2 olarak verilir. * Kenarların 180 derecelik dönme hareketleri: : 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ı, c(g) = 3 olarak verilir. Bu değerler, Pólya'nın sayma teoreminde yerine konulduğunda : \left |Y^X/G \right | = \frac{1}{24}\left(m^6+ 3m^4 + 12m^3 + 8m^2\right) farklı boyamanın gerçekleştirilebileceği sonucuna ulaşılır. === Eşyapılı olmayan basit çizgeler === Ç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 \binom{m}2 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. G = S_m 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. küçükresim|Üç köşeli tüm basit çizgeler küçükresim|Eşyapılı olmayan üç köşeli basit çizgeler 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: * döngü tipi: : 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. * döngü tipi: : 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. * döngü tipi: : 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. Bu değerler, Pólya'nın sayma teoreminde yerine konulduğunda : \left |Y^X/G \right | = \frac{1}{6}(2\cdot2^1 + 3\cdot2^2 + 2^3) = 4 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. küçükresim|Eşyapılı olmayan dört köşeli basit çizgeler Benzer işlemler, m = 4 değeri için de tekrarlanabilir: * döngü tipi: : 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. * döngü tipi: : 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. * döngü tipi: : 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. * döngü tipi: : 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. * döngü tipi: : 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. Bu değerler, Pólya'nın sayma teoreminde yerine konulduğunda : \left |Y^X/G \right | = \frac{1}{24}(6\cdot2^2 + 8\cdot2^2 + 3\cdot2^4 + 6\cdot2^4 + 2^6) = 11 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, f(t)=1+t olarak yazılabilir. Üç köşeli basit çizgeler için, \binom{3}2 = 3 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: : Z_G(t_1,t_2,t_3) = \frac{1}{6} \left(t_1^3 + 3 t_1 t_2 + 2 t_3\right) Böylece, istenen üretim fonksiyonu aşağıdaki gibi elde edilebilir: : \begin{align} F(t) &= Z_G\left(t+1,t^2+1,t^3+1\right) \\\ &= \frac{1}{6}\left((t+1)^3 + 3 (t+1) (t^2+1) + 2 (t^3+1)\right) \\\ &= t^3+t^2+t+1. \end{align} Dört köşeli basit çizgeler için ise \binom{4}2 = 6 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: : Z_G(t_1,t_2,t_3,t_4) = \frac{1}{24}\left(t_1^6 + 9 t_1^2 t_2^2 + 8 t_3^2 + 6 t_2 t_4\right) Böylelikle, : \begin{align} F(t) &= Z_G \left(t+1,t^2+1,t^3+1,t^4+1\right) \\\ &= \frac{1}{24}\left((t+1)^6 + 9 (t+1)^2 (t^2+1)^2 + 8 (t^3+1)^2 + 6 (t^2+1) (t^4+1)\right) \\\ &= t^6 + t^5 + 2 t^4 + 3 t^3 + 2 t^2 + t + 1 \end{align} olduğu sonucuna varılabilir. === Kolye ve bilezikler === ==== Kolyeler ==== 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 ∈ \mathbb{Z} olmak üzere G grubunun bir gz elemanının derecesi, |gz| = x olarak verilirse e = gn olmak üzere gxz = e olur. Bu durumda n \mid xz olur. O hâlde, : xz \equiv 0 \pmod n, : x(\frac{z}{ebob(n,z)}) \equiv 0 \pmod \frac{n}{ebob(n,z)} yazılabilir. Bu koşulu sağlayan en küçük x pozitif tam sayısı, \frac{n}{ebob(n,z)} olacaktır. Bu nedenle |g^z| = \frac{n}{ebob(n,z)} 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, c(g^z) = ebob(n,z) olarak bulunur. Böylece, : \left |Y^X/G \right | = \frac{1}{n}\sum_{z=0}^{n-1} k^{ebob(n,z)} eşitliği elde edilir. Bu sonuçtan daha kullanışlı bir bağıntının elde edilmesi için, z ∈ {0, 1, ..., n-1} olmak üzere d = ebob(n,z) denkleminin çözümlerinin sayısı hesaplanmalıdır. Bu ifade, ebob(\frac{n}{d}, \frac{z}{d}) = 1 denklemi ile aynı anlama gelmektedir. Buradan, denklemin çözüm sayısının \varphi(\frac{n}{d}) olduğu anlaşılır (\varphi, Euler'in fi fonksiyonunu göstermektedir.). Buna göre, : N_k(n)=\frac{1}{n}\sum_{d\mid n}\varphi(\frac{n}{d})k^d=\frac{1}{n}\sum_{d\mid n}\varphi(d)k^\frac{n}{d} olduğu sonucuna varılabilir. 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 ∈ \mathbb{Z} olmak üzere c(g^z) = ebob(n,z) olur. G grubunun bir gz elemanı, aynı zamanda X kümesinin bir permütasyonu olduğu için x = \frac{n}{ebob(n,z)} durumunda c_x(g^z) = ebob(n,z) ve x tam sayısının bundan farklı herhangi bir değeri için c_x(g^z) = 0 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, \mathbf{a}_1=(1,0,\cdots,0), \mathbf{a}_2=(0,1,0,\cdots,0), \ldots, \mathbf{a}_k=(0,\cdots,0,1) olmak üzere w(r_i)=\mathbf{a}_i 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, : f(t_1, t_2, \ldots) = t_1 + t_2 + \cdots yazılabilir. Böylece, istenen üretim fonksiyonu aşağıdaki gibi elde edilebilir: : \begin{align} N_{n,k}(t_1, t_2, \ldots) &= Z_G((t_1+t_2+\cdots), (t_1^2+t_2^2+\cdots), \ldots, (t_1^n+t_2^n+\cdots))\\\ &= \frac{1}{|G|}\sum_{g \in G} (t_1+t_2+\cdots)^{c_1(g)} (t_1^2+t_2^2+\cdots)^{c_2(g)} \cdots (t_1^n+t_2^n+\cdots)^{c_n(g)}\\\ &= \frac{1}{n}\sum_{z=0}^{n-1} (t_1+t_2+\cdots)^{c_1(g^z)} (t_1^2+t_2^2+\cdots)^{c_2(g^z)} \cdots (t_1^n+t_2^n+\cdots)^{c_n(g^z)}\\\ &= \frac{1}{n}\sum_{d\mid n} (t_1^{\frac{n}{d}}+t_2^{\frac{n}{d}}+\cdots)^d \varphi(\frac{n}{d})\\\ &= \frac{1}{n}\sum_{d\mid n} (t_1^d+t_2^d+\cdots)^{\frac{n}{d}} \varphi(d). \end{align} ==== Bilezikler ==== 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}, \circ) biçiminde ifade edebiliriz (\circ, fonksiyonların bileşke işlemini göstermektedir). Bir önceki bölümde belirtildiği üzere, z ∈ \mathbb{Z} olmak üzere c(a^z) = ebob(n,z) 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: : c(s_z) = \begin{cases} (n+1)/2 & n \text{ tek ise} \\\ n/2 & n \text{ çift ve } z \text{ tek ise} \\\ (n+2)/2 & n \text{ çift ve } z \text{ çift ise} \end{cases} Böylelikle, şu sonuca ulaşılabilir: : \begin{align} \left |Y^X/G \right | &= \frac{1}{2n}\left(\sum_{z=0}^{n-1} k^{ebob(n,z)} + \sum_{z=1}^{n} k^{c(s_z)}\right) \\\ &= \frac{1}{2} N_k(n) + \frac{1}{2n}\sum_{z=1}^{n} k^{c(s_z)}, \end{align} dolayısıyla : B_k(n) = \begin{cases} \tfrac12 N_k(n) + \tfrac14 (k+1)k^\frac{n}{2} & n\text{ çift ise} \\\\[10px] \tfrac12 N_k(n) + \tfrac12 k^\frac{n+1}{2} & n\text{ tek ise.} \end{cases} 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 ∈ \mathbb{Z} olmak üzere G grubunun bir az elemanı, aynı zamanda X kümesinin bir permütasyonu olduğu için x = \frac{n}{ebob(n,z)} durumunda c_x(a^z) = ebob(n,z) ve x tam sayısının bundan farklı herhangi bir değeri için c_x(a^z) = 0 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: : c_x(s_z) = \begin{cases} 1 & n \text{ tek ve } x = 1 \text{ ise} \\\ (n-1)/2 & n \text{ tek ve } x = 2 \text{ ise} \\\ n/2 & n \text{ çift, } z \text{ tek ve } x = 2 \text{ ise} \\\ 2 & n \text{ çift, } z \text{ çift ve } x = 1 \text{ ise} \\\ (n-2)/2 & n \text{ çift, } z \text{ çift ve } x = 2 \text{ ise} \end{cases} Kullanılan renklerin ağırlıklandırılması, kolyelerdekine benzer şekilde gerçekleştirilebilir: \mathbf{a}_1=(1,0,\cdots,0), \mathbf{a}_2=(0,1,0,\cdots,0), \ldots, \mathbf{a}_k=(0,\cdots,0,1) olmak üzere Y = {r1, r2, ..., rk} kümesinin her bir elemanı için w(r_i) = \mathbf{a}_i olsun. Bu durumda, her ağırlık değeri (w) için fw = 1 olur. Buna göre, : f(t_1, t_2, \ldots) = t_1 + t_2 + \cdots yazılabilir. Böylece, istenen üretim fonksiyonu aşağıdaki gibi elde edilebilir: : \begin{align} B_{n,k}(t_1, t_2, \ldots) &= Z_G((t_1+t_2+\cdots), (t_1^2+t_2^2+\cdots), \ldots, (t_1^n+t_2^n+\cdots))\\\ &= \frac{1}{|G|}\sum_{g \in G} (t_1+t_2+\cdots)^{c_1(g)} (t_1^2+t_2^2+\cdots)^{c_2(g)} \cdots (t_1^n+t_2^n+\cdots)^{c_n(g)}\\\ &= \frac{1}{2} N_{n,k}(t_1, t_2, \ldots) + \frac{1}{2n}\sum_{z=1}^{n} (t_1+t_2+\cdots)^{c_1(s_z)} (t_1^2+t_2^2+\cdots)^{c_2(s_z)}, \end{align} dolayısıyla : B_{n,k}(t_1, t_2, \ldots) = \begin{cases} \tfrac12 N_{n,k}(t_1, t_2, \ldots) + \tfrac12 (t_1+t_2+\cdots)(t_1^2+t_2^2+\cdots)^{\frac{n-1}{2}} & n \text{ tek ise} \\\\[10px] \tfrac12 N_{n,k}(t_1, t_2, \ldots) + \tfrac14 \left((t_1+t_2+\cdots)^{2}(t_1^2+t_2^2+\cdots)^{\frac{n-2}{2}} + (t_1^2+t_2^2+\cdots)^{\frac{n}{2}}\right) & n \text{ çift ise.} \end{cases} === Köklü üçlü ağaçlar === Ç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, : Z_{S_3}(t_1,t_2,t_3) = \frac{1}{6} \left(t_1^3 + 3 t_1 t_2 + 2 t_3\right) olarak yazılabilir. 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 f(t) = F(t) olur. Bu durumda Pólya'nın sayma teoremi, :\frac{F(t)^3 + 3 F(t)F(t^2) + 2 F(t^3)}{6} 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, :F(t) = 1 + \frac{t}{6} \cdot \left(F(t)^3 + 3 F(t)F(t^2) + 2 F(t^3)\right) 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: :\begin{align} t_0 &= 1 \\\ t_{n+1} &= \frac{1}{6} \left(\sum_{a+b+c=n} t_a t_b t_c + 3\sum_{a+2b=n} t_a t_b + 2 \sum_{3a=n} t_a \right) \end{align} Bu dizinin ilk birkaç terimi aşağıdaki gibidir: :1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241 == Teoremin ispatı == 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: :|X/G| = \frac{1}{|G|}\sum_{g \in G}|X^g| (X^g, X kümesinin G grubuna ait bir g elemanı tarafından sabitlenen elemanlarından oluşan kümedir)Burnside, W. "On Some Properties of Groups of Odd Order." Proc. London Math. Soc. 33, 162-184, 1900.. 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, : \left|(Y^X)^g\right| = |Y|^{c(g)} olur. Burnside önsavı, bu bilgi de kullanılarak G grubunun YX kümesi üzerindeki davranışına uygulandığında m = |Y| olmak üzere, : \left |Y^X/G \right | = \frac{1}{|G|}\sum_{g \in G} m^{c(g)} sonucuna ulaşılır. Teoremin ağırlıklı versiyonunun ispatında, f ve F üretim fonksiyonları aşağıdaki gibi ifade edilecektir: : \omega = (w_1, w_2, \ldots), bir ağırlık vektörüdür. : f_{\omega}, ağırlığı \omega olan renklerin sayısıdır. : m_{\omega}, ağırlığı \omega olan birbirinden farklı renkli düzenlemelerin sayısıdır. : t^{\omega} = t_1^{w_1} t_2^{w_2} \cdots olarak tanımlanıyor. : f(t_1, t_2, \ldots) = \sum_{w_1, w_2, \ldots \in \mathbb{N}} f_{\omega} t^{\omega}. : F(t_1, t_2, \ldots) = \sum_{w_1, w_2, \ldots \in \mathbb{N}} m_{\omega} t^{\omega}. Bir \omega ağırlık vektörü için m_{\omega} değerinin hesaplanmasında Burnside önsavı kullanılabilir. (Y^X)_{\omega} kümesi, ağırlığı \omega olan renkli düzenlemelerin kümesi olmak üzere, : m_{\omega} = \left|(Y^X)_{\omega}/G\right| = \frac{1}{|G|}\sum_{g \in G} \left|(Y^X)_{\omega}^g\right| olur. Bu durumda, : F(t_1, t_2, \ldots) = \frac{1}{|G|}\sum_{g \in G, \omega} t^{\omega} \left|(Y^X)_{\omega}^g\right| yazılabilir. 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 fonksiyonu :f\left(t_1^{|q|}, t_2^{|q|}, t_3^{|q|}, \ldots \right) = \sum_{w_1, w_2, \ldots \in \mathbb{N}} f_{\omega} t_1^{w_1|q|} t_2^{w_2|q|} \cdots olur. Buna göre, :\begin{align} \sum_{\omega} t^\omega \left|(Y^X)_{\omega}^g\right| &= \prod_{q \text{ döngüsüdür } g} f \left(t_1^{|q|}, t_2^{|q|}, t_3^{|q|},\ldots \right) \\\ &= f(t_1, t_2, \ldots)^{c_1(g)} f \left(t_1^2, t_2^2, \ldots \right)^{c_2(g)} \cdots f \left(t_1^n, t_2^n, \ldots \right)^{c_n(g)} \end{align} eşitliği sağlanır. Böylece, :\begin{align} F(t_1, t_2, \ldots) &= \frac{1}{|G|}\sum_{g \in G} f(t_1, t_2, \ldots)^{c_1(g)} f \left(t_1^2, t_2^2, \ldots \right)^{c_2(g)} \cdots f \left(t_1^n, t_2^n, \ldots \right)^{c_n(g)} \\\ &= Z_G(f(t_1,t_2,\ldots),f(t_1^2,t_2^2,\ldots),f(t_1^3,t_2^3,\ldots),\ldots,f(t_1^n,t_2^n,\ldots)) \end{align} olduğu sonucuna ulaşılır. == Kaynakça == == Dış bağlantılar == * Chyzak, 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. Kategori:Kombinatorik Kategori:Kanıt içeren maddeler