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.

## 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 *C<sub>n</sub>* 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 *D<sub>n</sub>* 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), *Y<sup>X</sup>* olsun. Bu durumda *G* grubu, *Y<sup>X</sup>* kümesinin üzerinde davranır. Pólya'nın sayma teoremi, aşağıdaki formülle *G* grubunun *Y<sup>X</sup>* 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}\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 *f<sub>w</sub>* 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}\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<sub>k</sub>(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<sup>X</sup>* kümesi üzerindeki davranışının bir yörüngesidir. φ ∈ *Y<sup>X</sup>* 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}\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 *Y<sup>X</sup>* 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 *S<sub>m</sub>* grubunun eşlenik sınıflarının incelenmesi gerekir. Örneğin, *m* = 3 alındığında *S<sub>3</sub>* 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.

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 *f<sub>0</sub>* = 1 ve *f<sub>1</sub>* = 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 *S<sub>3</sub>* 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 *S<sub>4</sub>* 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 *C<sub>n</sub>* olsun. Birbirinden farklı, *n* uzunluğundaki *k'lı kolyelerin* sayısını *N<sub>k</sub>(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 *g<sup>z</sup>* elemanının derecesi, |*g<sup>z</sup>*| = *x* olarak verilirse *e = g<sup>n</sup>* olmak üzere *g<sup>xz</sup>* *= 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 *N<sub>n,k</sub>(t*1, *t*2, ...*)* 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 *g<sup>z</sup>* 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 &#x3C; *i* ≤ *k* aralığındaki her *i* tam sayısı için *r<sub>i</sub>* ifadesi bir rengi temsil etmek üzere *Y =* {*r<sub>1</sub>, r<sub>2</sub>, ..., r<sub>k</sub>*} 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 *f<sub>w</sub>* = 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}\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 *D<sub>n</sub>* olsun. Birbirinden farklı, *n* uzunluğundaki *k'lı bileziklerin* sayısını *B<sub>k</sub>(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<sub>n</sub>* 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 *s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>n</sub>* elemanları ile gösterelim. Bu durumda *G* grubunu, *a<sup>0</sup> = e* olmak üzere *G* = ({*e, a, a<sup>2</sup>, ..., a<sup>n</sup>, s<sub>1</sub>, s<sub>2</sub>, ..., s<sub>n</sub>*}, \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 *B<sub>n,k</sub>(t<sub>1</sub>, t<sub>2</sub>, ...)* ile gösterelim. Bir önceki bölümde belirtildiği üzere, *z* ∈ \mathbb{Z} olmak üzere *G* grubunun bir *a<sup>z</sup>* 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 =* {*r<sub>1</sub>, r<sub>2</sub>, ..., r<sub>k</sub>*} 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 *f<sub>w</sub>* = 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}\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, *S<sub>3</sub>* 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 *t<sub>n</sub>* 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}\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).

*Y<sup>X</sup>* 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 *Y<sup>X</sup>* kümesi üzerindeki davranışına uygulandığında m = |Y| olmak üzere,

: \left |Y^X/G \right | = \frac{1}\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}\sum_{g \in G} \left|(Y^X)_{\omega}^g\right|

olur. Bu durumda,

: F(t_1, t_2, \ldots) = \frac{1}\sum_{g \in G, \omega} t^{\omega} \left|(Y^X)_{\omega}^g\right|

yazılabilir.

*Y<sup>X</sup>* 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^, t_2^, t_3^, \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^, t_2^, t_3^,\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}\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.