Pólya'nın sayma teoremi

Pólya'nın sayma teoremi (Redfield – Pólya teoremi olarak da bilinir), bir küme üzerindeki bir sayısını veren izleyen ve genelleştiren bir kombinatorik teoremidir. Teorem; ilk olarak 1927 yılında 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, ve teorisi bağlamında da çeşitli uygulama alanlarına sahiptir.

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 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 ise bu küme üzerinde dönme simetrisi önem taşır. Bu nedenle G, C_n olur. Benzer şekilde, X kümesi bir daire etrafındaki n adet boncuktan oluşan bir ise bu küme üzerinde dönme ve önem taşır. Bu nedenle G, D_n 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, ${\displaystyle X\to Y}$ biçimindeki fonksiyonların kümesi), Y^X olsun. Bu durumda G grubu, Y^X kümesinin üzerinde davranır. Pólya'nın sayma teoremi, aşağıdaki formülle G grubunun Y^X kümesi üzerindeki davranışının yörünge sayısını hesaplayarak boncukların renkli düzenlemelerinin sayısını verir:

${\displaystyle \left|Y^{X}/G\right|={\frac {1}{|G|}}\sum _{g\in G}m^{c(g)}}$

(${\displaystyle 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 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,

${\displaystyle 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 f_w 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 ${\textstyle \mathbf {a} =(w_{1},w_{2},\ldots )}$ vektörü için ağırlık değeri ${\textstyle \mathbf {a} }$ olan ${\textstyle f_{\mathbf {a} }}$ adet renk bulunmak üzere

${\displaystyle 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, olarak adlandırılan çok değişkenli başka bir fonksiyon daha kullanır:

${\displaystyle 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 c_k(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 Y^X kümesi üzerindeki davranışının bir yörüngesidir. φ ∈ Y^X 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:

${\displaystyle 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:

${\displaystyle 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

${\displaystyle \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, ${\textstyle 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ı, ${\textstyle 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ı, ${\textstyle 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ı, ${\textstyle 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ı, ${\textstyle c(g)=3}$ olarak verilir.

Bu değerler, Pólya'nın sayma teoreminde yerine konulduğunda

${\displaystyle \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 , herhangi bir 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 ${\textstyle {\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. ${\textstyle 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 Y^X 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öşeli tüm basit çizgeler

Eşyapılı olmayan üç köşeli basit çizgeler

Bir simetrik grup elemanının döngü sayısı, o elemanın bulunduğu 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 S_m grubunun eşlenik sınıflarının incelenmesi gerekir. Örneğin, m = 3 alındığında S₃ grubunun elemanları aşağıdaki gibi incelenebilir:

• [1⁰2⁰3¹] :

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.

• [1¹2¹3⁰] 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.

• [1³2⁰3⁰] 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

${\displaystyle \left|Y^{X}/G\right|={\frac {1}{6}}(2\cdot 2^{1}+3\cdot 2^{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.

Eşyapılı olmayan dört köşeli basit çizgeler

Benzer işlemler, m = 4 değeri için de tekrarlanabilir:

• [1⁰2⁰3⁰4¹] 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.

• [1¹2⁰3¹4⁰] 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.

• [1⁰2²3⁰4⁰] 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.

• [1²2¹3⁰4⁰] 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.

• [1⁴2⁰3⁰4⁰] 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

${\displaystyle \left|Y^{X}/G\right|={\frac {1}{24}}(6\cdot 2^{2}+8\cdot 2^{2}+3\cdot 2^{4}+6\cdot 2^{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 f₀ = 1 ve f₁ = 1 olur. Bu durumda renk kümesinin üretim fonksiyonu, ${\textstyle f(t)=1+t}$ olarak yazılabilir.

Üç köşeli basit çizgeler için, ${\textstyle {\binom {3}{2}}=3}$ kenardan oluşan X kümesi üzerinde davranan S₃ grubunun döngü indeksi, yukarıdaki inceleme göz önünde bulundurularak şu şekilde ifade edilebilir:

${\displaystyle Z_{G}(t_{1},t_{2},t_{3})={\frac {1}{6}}\left(t_{1}^{3}+3t_{1}t_{2}+2t_{3}\right)}$

Böylece, istenen üretim fonksiyonu aşağıdaki gibi elde edilebilir:

${\displaystyle {\begin{aligned}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{aligned}}}$

Dört köşeli basit çizgeler için ise ${\textstyle {\binom {4}{2}}=6}$ kenardan oluşan X kümesi üzerinde davranan S₄ grubunun döngü indeksi, yukarıdaki inceleme göz önünde bulundurularak şu şekilde ifade edilebilir:

${\displaystyle Z_{G}(t_{1},t_{2},t_{3},t_{4})={\frac {1}{24}}\left(t_{1}^{6}+9t_{1}^{2}t_{2}^{2}+8t_{3}^{2}+6t_{2}t_{4}\right)}$

Böylelikle,

${\displaystyle {\begin{aligned}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}+2t^{4}+3t^{3}+2t^{2}+t+1\end{aligned}}}$

olduğu sonucuna varılabilir.

Kolye ve bilezikler

Kolyeler

Kombinatorikte, n uzunluğunda bir k'lı kolye, k elemanlı bir ile oluşturulan n karakterli dizelerin her bir bir diğerine denk kabul edilmesiyle oluşan bir 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 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 C_n olsun. Birbirinden farklı, n uzunluğundaki k'lı kolyelerin sayısını N_k(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, da kullanılarak G = ⟨g⟩ biçiminde ifade edilebilir. z ∈ ${\textstyle \mathbb {Z} }$ olmak üzere G grubunun bir g^z elemanının , |g^z| = x olarak verilirse e = gⁿ olmak üzere g^xz = e olur. Bu durumda ${\textstyle n\mid xz}$ olur. O hâlde,

${\displaystyle xz\equiv 0{\pmod {n}},}$

${\displaystyle 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ı, ${\textstyle {\frac {n}{ebob(n,z)}}}$ olacaktır. Bu nedenle ${\textstyle |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 olması gerekir. Bu noktadan hareketle, ${\textstyle c(g^{z})=ebob(n,z)}$ olarak bulunur. Böylece,

${\displaystyle \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 ${\textstyle d=ebob(n,z)}$ denkleminin çözümlerinin sayısı hesaplanmalıdır. Bu ifade, ${\textstyle ebob({\frac {n}{d}},{\frac {z}{d}})=1}$ denklemi ile aynı anlama gelmektedir. Buradan, denklemin çözüm sayısının ${\textstyle \varphi ({\frac {n}{d}})}$ olduğu anlaşılır (${\displaystyle \varphi }$, Euler'in fi fonksiyonunu göstermektedir.). Buna göre,

${\displaystyle 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 N_n,k(t₁, t₂, ...) ile gösterelim. Yukarıda belirtildiği üzere, G = ⟨g⟩ ve z ∈ ${\textstyle \mathbb {Z} }$ olmak üzere ${\textstyle c(g^{z})=ebob(n,z)}$ olur. G grubunun bir g^z elemanı, aynı zamanda X kümesinin bir permütasyonu olduğu için ${\textstyle x={\frac {n}{ebob(n,z)}}}$ durumunda ${\textstyle c_{x}(g^{z})=ebob(n,z)}$ ve x tam sayısının bundan farklı herhangi bir değeri için ${\textstyle c_{x}(g^{z})=0}$ olur.

Bunun dışında, 1 < i ≤ k aralığındaki her i tam sayısı için r_i ifadesi bir rengi temsil etmek üzere Y = {r₁, r₂, ..., r_k} yazılabilir. Bu kümenin her bir elemanı için, ${\textstyle \mathbf {a} _{1}=(1,0,\cdots ,0),}$ ${\textstyle \mathbf {a} _{2}=(0,1,0,\cdots ,0),}$ ${\textstyle \ldots ,}$ ${\textstyle \mathbf {a} _{k}=(0,\cdots ,0,1)}$ olmak üzere ${\textstyle 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 f_w = 1 olur. Buna göre,

${\displaystyle f(t_{1},t_{2},\ldots )=t_{1}+t_{2}+\cdots }$

yazılabilir. Böylece, istenen üretim fonksiyonu aşağıdaki gibi elde edilebilir:

${\displaystyle {\begin{aligned}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{aligned}}}$

Bilezikler

Kombinatorikte, n uzunluğunda bir k'lı bilezik, k elemanlı bir ile oluşturulan n karakterli dizelerin her bir ve yansımasının bir diğerine denk kabul edilmesiyle oluşan bir 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 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 D_n olsun. Birbirinden farklı, n uzunluğundaki k'lı bileziklerin sayısını B_k(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 = D_n grubu, n kenarlı bir düzgün çokgene ait n adet dönme simetrisi ve n adet oluşmaktadır. Bu çokgenin saat yönünde 360/n derecelik bir dönüşünü, a elemanı ile gösterelim. Benzer şekilde, çokgenin her bir yansıma simetrisini s₁, s₂, ..., s_n elemanları ile gösterelim. Bu durumda G grubunu, a⁰ = e olmak üzere G = ({e, a, a², ..., aⁿ, s₁, s₂, ..., s_n}, ${\displaystyle \circ }$) biçiminde ifade edebiliriz (${\displaystyle \circ }$, fonksiyonların bileşke işlemini göstermektedir).

Bir önceki bölümde belirtildiği üzere, z ∈ ${\textstyle \mathbb {Z} }$ olmak üzere ${\textstyle 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:

${\displaystyle 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:

${\displaystyle {\begin{aligned}\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{aligned}}}$

dolayısıyla

${\displaystyle B_{k}(n)={\begin{cases}{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{4}}(k+1)k^{\frac {n}{2}}&n{\text{ çift ise}}\\[10px]{\tfrac {1}{2}}N_{k}(n)+{\tfrac {1}{2}}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 B_n,k(t₁, t₂, ...) ile gösterelim. Bir önceki bölümde belirtildiği üzere, z ∈ ${\textstyle \mathbb {Z} }$ olmak üzere G grubunun bir a^z elemanı, aynı zamanda X kümesinin bir permütasyonu olduğu için ${\textstyle x={\frac {n}{ebob(n,z)}}}$ durumunda ${\textstyle c_{x}(a^{z})=ebob(n,z)}$ ve x tam sayısının bundan farklı herhangi bir değeri için ${\textstyle 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:

${\displaystyle 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: ${\textstyle \mathbf {a} _{1}=(1,0,\cdots ,0),}$ ${\textstyle \mathbf {a} _{2}=(0,1,0,\cdots ,0),}$ ${\textstyle \ldots ,}$ ${\textstyle \mathbf {a} _{k}=(0,\cdots ,0,1)}$ olmak üzere Y = {r₁, r₂, ..., r_k} kümesinin her bir elemanı için ${\textstyle w(r_{i})=\mathbf {a} _{i}}$ olsun. Bu durumda, her ağırlık değeri (w) için f_w = 1 olur. Buna göre,

${\displaystyle f(t_{1},t_{2},\ldots )=t_{1}+t_{2}+\cdots }$

yazılabilir. Böylece, istenen üretim fonksiyonu aşağıdaki gibi elde edilebilir:

${\displaystyle {\begin{aligned}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{aligned}}}$

dolayısıyla

${\displaystyle B_{n,k}(t_{1},t_{2},\ldots )={\begin{cases}{\tfrac {1}{2}}N_{n,k}(t_{1},t_{2},\ldots )+{\tfrac {1}{2}}(t_{1}+t_{2}+\cdots )(t_{1}^{2}+t_{2}^{2}+\cdots )^{\frac {n-1}{2}}&n{\text{ tek ise}}\\[10px]{\tfrac {1}{2}}N_{n,k}(t_{1},t_{2},\ldots )+{\tfrac {1}{4}}\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 , bir köşesi kök olarak belirlenmiş bir olarak tanımlanır. 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, S₃ simetrik grubu olur. Bu grubun döngü indeksi,

${\displaystyle Z_{S_{3}}(t_{1},t_{2},t_{3})={\frac {1}{6}}\left(t_{1}^{3}+3t_{1}t_{2}+2t_{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 ${\textstyle f(t)=F(t)}$ olur. Bu durumda Pólya'nın sayma teoremi,

${\displaystyle {\frac {F(t)^{3}+3F(t)F(t^{2})+2F(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,

${\displaystyle F(t)=1+{\frac {t}{6}}\cdot \left(F(t)^{3}+3F(t)F(t^{2})+2F(t^{3})\right)}$

olur. Bu ifade, n düğümlü köklü üçlü ağaçların sayısını veren t_n 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:

${\displaystyle {\begin{aligned}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{aligned}}}$

Bu dizinin ilk birkaç terimi aşağıdaki gibidir:

1, 1, 1, 2, 4, 8, 17, 39, 89, 211, 507, 1238, 3057, 7639, 19241 (OEIS'de A000598 dizisi)

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 kullanılarak yapılabilir. Burnside önsavı, bir X kümesinin üzerinde davranan bir G grubu için aşağıdaki biçimde ifade edilebilir:

${\displaystyle |X/G|={\frac {1}{|G|}}\sum _{g\in G}|X^{g}|}$

(${\displaystyle X^{g}}$, X kümesinin G grubuna ait bir g elemanı tarafından sabitlenen elemanlarından oluşan kümedir).

Y^X 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,

${\displaystyle \left|(Y^{X})^{g}\right|=|Y|^{c(g)}}$

olur. Burnside önsavı, bu bilgi de kullanılarak G grubunun Y^X kümesi üzerindeki davranışına uygulandığında ${\textstyle m=|Y|}$ olmak üzere,

${\displaystyle \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:

${\displaystyle \omega =(w_{1},w_{2},\ldots )}$, bir ağırlık vektörüdür.

${\displaystyle f_{\omega }}$, ağırlığı ${\displaystyle \omega }$ olan renklerin sayısıdır.

${\displaystyle m_{\omega }}$, ağırlığı ${\displaystyle \omega }$ olan birbirinden farklı renkli düzenlemelerin sayısıdır.

${\displaystyle t^{\omega }=t_{1}^{w_{1}}t_{2}^{w_{2}}\cdots }$ olarak tanımlanıyor.

${\displaystyle f(t_{1},t_{2},\ldots )=\sum _{w_{1},w_{2},\ldots \in \mathbb {N} }f_{\omega }t^{\omega }.}$

${\displaystyle F(t_{1},t_{2},\ldots )=\sum _{w_{1},w_{2},\ldots \in \mathbb {N} }m_{\omega }t^{\omega }.}$

Bir ${\textstyle \omega }$ ağırlık vektörü için ${\displaystyle m_{\omega }}$ değerinin hesaplanmasında Burnside önsavı kullanılabilir. ${\textstyle (Y^{X})_{\omega }}$ kümesi, ağırlığı ${\textstyle \omega }$ olan renkli düzenlemelerin kümesi olmak üzere,

${\displaystyle m_{\omega }=\left|(Y^{X})_{\omega }/G\right|={\frac {1}{|G|}}\sum _{g\in G}\left|(Y^{X})_{\omega }^{g}\right|}$

olur. Bu durumda,

${\displaystyle F(t_{1},t_{2},\ldots )={\frac {1}{|G|}}\sum _{g\in G,\omega }t^{\omega }\left|(Y^{X})_{\omega }^{g}\right|}$

yazılabilir.

Y^X 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

${\displaystyle 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,

${\displaystyle {\begin{aligned}\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{aligned}}}$

eşitliği sağlanır. Böylece,

${\displaystyle {\begin{aligned}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{aligned}}}$

olduğu sonucuna ulaşılır.

Kaynakça

1. ^ ^{a b c} Redfield, J. Howard (1927). "The Theory of Group-Reduced Distributions". . 49 (3): 433-455. doi:10.2307/2370675. JSTOR 2370675. MR 1506633. 
2. ^ ^{a b c d} Pólya, G. (1937). "Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen". . 68 (1): 145-254. doi:10.1007/BF02546665. 
3. ^ Riedel, M. R. (2020). "Pólya’s enumeration theorem and the symbolic method". Stuttgart Üniversitesi. [1] 5 Temmuz 2020 tarihinde Wayback Machine sitesinde .
4. ^ ^{a b} ; Palmer, E. (1967). "The Enumeration Methods of Redfield". . 89 (2): 373-384. doi:10.2307/2373127. JSTOR 2373127. MR 0214487. 
5. ^ (1995), "9.3 The Cycle Index", Applied Combinatorics, New York: Wiley, ss. 365-371, ISBN  
6. ^ Jin, J. (2018). "Analysis and Applications of Burnside's Lemma". Massachusetts Institute of Technology. [2] 5 Temmuz 2020 tarihinde Wayback Machine sitesinde .
7. ^ ^{a b c} Pólya, G.; Read, R. C. (1987). Combinatorial Enumeration of Groups, Graphs, and Chemical Compounds. New York: Springer-Verlag. ISBN . MR 0884155. 
8. ^ Eric W. Weisstein, Simple Graph (MathWorld)
9. ^ ^{a b c d} Eric W. Weisstein, Necklace (MathWorld)
10. ^ Eric W. Weisstein, Rooted Tree (MathWorld)
11. ^ Eric W. Weisstein, Cauchy-Frobenius Lemma (MathWorld)
12. ^ Burnside, W. "On Some Properties of Groups of Odd Order." Proc. London Math. Soc. 33, 162-184, 1900.

Dış bağlantılar

• Chyzak, F (1997). Enumerating alcohols and other classes of chemical molecules, an example of Pólya theory11 Mayıs 2008 tarihinde Wayback Machine sitesinde ..
• Eric W. Weisstein, Polya Enumeration Theorem (MathWorld).
• Zenil, H.; Pavlyk, O. (2011). Applying the Pólya-Burnside Enumeration Theorem 11 Ekim 2019 tarihinde Wayback Machine sitesinde .. .