Pólya'nın sayma teoremi
Örnekler > 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 ∈ 




Z



{\textstyle \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
∣
x
z


{\textstyle n\mid xz}

 olur. O hâlde,
yazılabilir. Bu koşulu sağlayan en küçük x pozitif tam sayısı, 





n

e
b
o
b
(
n
,
z
)





{\textstyle {\frac {n}{ebob(n,z)}}}

 olacaktır. Bu nedenle 




|


g

z



|

=


n

e
b
o
b
(
n
,
z
)





{\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 döngüsel permütasyon olması gerekir. Bu noktadan hareketle, 



c
(

g

z


)
=
e
b
o
b
(
n
,
z
)


{\textstyle c(g^{z})=ebob(n,z)}

 olarak bulunur. Böylece,
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
=
e
b
o
b
(
n
,
z
)


{\textstyle d=ebob(n,z)}

 denkleminin çözümlerinin sayısı hesaplanmalıdır. Bu ifade, 



e
b
o
b
(


n
d


,


z
d


)
=
1


{\textstyle ebob({\frac {n}{d}},{\frac {z}{d}})=1}

 denklemi ile aynı anlama gelmektedir. Buradan, denklemin çözüm sayısının 



φ
(


n
d


)


{\textstyle \varphi ({\frac {n}{d}})}

 olduğu anlaşılır ( \varphi , Euler'in fi fonksiyonunu göstermektedir.). Buna göre,
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 ∈ 




Z



{\textstyle \mathbb {Z} }

 olmak üzere 



c
(

g

z


)
=
e
b
o
b
(
n
,
z
)


{\textstyle 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
=


n

e
b
o
b
(
n
,
z
)





{\textstyle x={\frac {n}{ebob(n,z)}}}

 durumunda 




c

x


(

g

z


)
=
e
b
o
b
(
n
,
z
)


{\textstyle 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


{\textstyle 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, 





a


1


=
(
1
,
0
,
⋯
,
0
)
,


{\textstyle \mathbf {a} _{1}=(1,0,\cdots ,0),}

 





a


2


=
(
0
,
1
,
0
,
⋯
,
0
)
,


{\textstyle \mathbf {a} _{2}=(0,1,0,\cdots ,0),}

 



…
,


{\textstyle \ldots ,}

 





a


k


=
(
0
,
⋯
,
0
,
1
)


{\textstyle \mathbf {a} _{k}=(0,\cdots ,0,1)}

 olmak üzere 



w
(

r

i


)
=


a


i




{\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 fw = 1 olur. Buna göre,
yazılabilir. Böylece, istenen üretim fonksiyonu aşağıdaki gibi elde edilebilir: