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






(


m
2


)





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



G
=

S

m




{\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 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:
[102031] döngü tipi:
[112130] döngü tipi:
[132030] döngü tipi:
Bu değerler, Pólya'nın sayma teoreminde yerine konulduğunda
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:
[10203041] döngü tipi:
[11203140] döngü tipi:
[10223040] döngü tipi:
[12213040] döngü tipi:
[14203040] döngü tipi:
Bu değerler, Pólya'nın sayma teoreminde yerine konulduğunda
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


{\textstyle f(t)=1+t}

 olarak yazılabilir.
Üç köşeli basit çizgeler için, 






(


3
2


)



=
3


{\textstyle {\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:
Böylece, istenen üretim fonksiyonu aşağıdaki gibi elde edilebilir:
Dört köşeli basit çizgeler için ise 






(


4
2


)



=
6


{\textstyle {\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:
Böylelikle,
olduğu sonucuna varılabilir.