Eğer $X$ bir kümeyse, $X$’in permütasyonlarından (yani $X$’ten $X$’e giden birebir ve örten fonksiyonlardan) oluşan Sym $X$ kümesi bileşke işlemi altında bir gruptur. Bunu ilk yazılarımızdan birinde görmüştük. Simetrik grup adı verilen bu gruplar matematikte çok önemlidir ve elbette $X$’in sonlu olduğu durumlar daha da önemlidir.
Eğer $X$ ve $Y$ arasında bir eşleme varsa, kümeler kuramı açısından $X$ ile $Y$ arasında fazla bir fark yoktur; dolayısıyla, fonksiyonlar da kümeler kuramının nesneleri olduğundan, bu durumda Sym $X$ ile Sym $Y$ arasında da fazla bir fark yoktur; birini anlamak demek diğerini de anlamak demektir. (İlerde iki grup arasında pek bir fark olmadığını belirtmek için, matematiksel olarak tanımlayacağımız “izomorfik” sıfatını kullanacağız.) Demek ki $|X| = n$ ise, Sym $X$ grubunu anlamakla
$$ \text{Sym}\; {1, 2, \dots, n}$$
grubunu anlamak aynı şeydir. Sym ${1, 2, \dots, n}$ yerine Sym $n$, bazen de $S_n$ yazılır.
Bu yazıda Sym $n$ grubuyla haşır neşir olacağız.
- Sym n Grubunun Eleman Sayısı. $n$ kadın ve $n$ erkek kaç farklı biçimde (her kadına bir erkek ve her erkeğe bir kadın düşecek biçimde) eşleştirilebilir? Sorunun (kolay olan) yanıtını bulmak için kadınları numaralandıralım. Birinci kadını $n$ erkekten biriyle eşleştireceğiz. İkinci kadını geri kalan $n – 1$ erkekten biriyle, üçüncü kadını geri kalan $n – 2$ erkekten biriyle eşleştireceğiz ve bunu böylece devam ettireceğiz. Anlaşılacağı gibi, toplam $n!$ farklı kadın-erkek eşlemesi vardır. Bu $n!$ sayısı, elbette, $n$ elemanlı herhangi bir kümeden $n$ elemanlı herhangi bir kümeye giden eşleme sayısıdır. Gördüğümüz üzere, Sym $n$’nin tam $n!$ tane elemanı vardır.
- Sym n’nin Elemanlarının Yazılımı. Önce Sym $n$ kümesinin elemanlarını inceleyelim, sonra
modern matematik gereği, kümeye bir bütün olarak bakarız. Bir örnekle başlayalım.
Sym 7’nin aşağıdaki permütasyonunu ele alalım.
Tanım kümesini üst sırada, değer kümesini alt sırada gösterdik. Permütasyon aslında şunu yapıyor:
$$1 \mapsto 3$$
$$2 \mapsto 5$$
$$3 \mapsto 4$$
$$4 \mapsto 6$$
$$5 \mapsto 2$$
$$6 \mapsto 1$$
$$7 \mapsto 7$$
Bu permütasyonu daha sade olarak şöyle yazabiliriz:
$$ \bigg( \begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 3 & 5 & 4 & 6 & 2 & 1 & 7 \end{matrix} \bigg) $$
Üst sıra tanım kümesinin elemanlarını, alt sıra da değer kümesinin elemanlarını simgeler. 5’in hemen altında 2 olması, bu permütasyonun 5’teki değerinin 2 olduğunu söyler, yani,
$$f = \bigg( \begin{matrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 3 & 5 & 4 & 6 & 2 & 1 & 7 \end{matrix} \bigg) $$
ise,
$$f(1) = 3,$$
$$f(2) = 5,$$
$$f(3) = 4,$$
$$f(4) = 5,$$
$$f(5) = 2,$$
$$f(6) = 1,$$
$$f(7) = 7$$
olur.
Yukarıdakinden daha sade, dolayısıyla daha kullanışlı bir yazılım vardır. Örneğimizdeki permütasyona bakalım.
Yukardaki üç nedenden dolayı bu permütasyon (1 3 4 6)(2 5)(7)
olarak gösterilir. Buradaki her sayının imgesi hemen sağındaki sayıdır, ama eğer sayı parantezin
sonundaysa, o zaman o sayının imgesi, bulunduğu parantezin ilk sayısıdır.
Her bir paranteze döngü adı verilir.
(1 3 4 6)(2 5)(7)
permütasyonunda 3 döngü vardır.
(1 3 4 6) ve (2 5) döngüleri ayrıktır. Ama
(1 3 4 6) ve (2 5 6)
döngüleri ayrık değildirler, 6 ortak elemandır.
Sym $n$’nin her elemanı, yukarıdaki yöntemle, ayrık döngülerin çarpımı olarak yazılabilir.
Örneğin Sym 7’nin
(1 2 7)(3 4 5 6)
permütasyonunun resmi aşağıdadır. Görüldüğü gibi, (1 2 7) döngüsü nedeniyle 1 sağındaki 2’ye, 2 sağındaki 7’ye, 7 de ta en baştaki 1’e gidiyor.
Döngüyle gösterilen permütasyonlarda her sayı hemen sağındaki sayıya gider. Sağında sayı
olmayan sayılar, bulundukları döngünün (parantezin) en başına giderler. Sym 7’nin her elemanı (ki $7! = 5040$ tane elemanı vardır) böyle ayrık döngüler biçiminde yazılabilir.
Yalnız dikkat edilmesi gereken bir nokta var:
Bu yazılımla,
(1 2 7)(3 4 5 6)
ile
(3 4 5 6)(1 2 7)
permütasyonları da birbirine eşittir. Aynı biçimde,
(1 2 7)(3 4 5 6) = (2 7 1)(3 4 5 6)
$\qquad \qquad$ = (3 4 5 6)(2 7 1)
$\qquad \qquad$ = (4 5 6 3)(2 7 1)
$\qquad \qquad$ = (5 6 3 4)(7 1 2)
gibi eşitlikler geçerlidir. Genel olarak (1 5 9 3 6) gibi bir döngüyü yazmaya döngüdeki herhangi bir elemandan başlayabiliriz:
(1 5 9 3 6) = (5 9 3 6 1) = (9 3 6 1 5)= (3 6 1 5 9) = (6 1 5 9 3).
Ama döngünün en küçük sayısından başlamak bir
gelenektir.
Sym 4’ün 4! yani 24 elemanını bu yazılımla
yazabiliriz:
(1)(2)(3)(4)
(1 2)(3)(4), (1 3)(2)(4), (1 4)(2)(3), (1)(2 3)(4),
(1)(2 4)(3), (1)(2)(3 4)
(1 2)(3 4), (1 3)(2 4), (1 4)(2 3)
(1 2 3)(4), (1 2 4)(3),(1 3 4)(2), (1)(2 3 4)
(1 3 2)(4), (1 4 2)(3), (1 4 3)(2), (1)(2 4 3)
(1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2),
(1 4 2 3), (1 4 3 2).
Yazılımı biraz daha sadeleştirebiliriz. Eğer $n$’nin kaç olduğunu önceden biliyorsak tek elemanlı döngüleri yazmasak da olur. Örneğin
(1 3 4 6)(2 5)(7)
yerine daha basit olarak
(1 3 4 6)(2 5)
yazabiliriz. Bunun gibi
(1 2 3)(4 5)(6)(7)
yerine
(1 2 3)(4 5)
yazalım. Ama o zaman (1)(2)(3)(4)(5)(6)(7) yerine
ne yazacağız? Onun yerine de $Id_7$ yazalım. Eğer 7
umurumuzda değilse, $Id_7$ yerine sadece Id yazalım.
Bu daha basit yazılımla, Sym 4’ün 24 elemanı aşağıdaki gibi yazılır.
$Id_4$
(1 2), (1 3), (1 4), (2 3), (2 4), (3 4)
(1 2)(3 4), (1 3)(2 4), (1 4)(2 3)
(1 2 3), (1 2 4), (1 3 4), (2 3 4)
(1 3 2), (1 4 2),(1 4 3), (2 4 3)
(1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2),
(1 4 2 3), (1 4 3 2).
Bu yazılımın bir tehlikesi var. O da şu: Bu yazılımla (1 3 4 6)(2 5) elemanı Sym 6’nın da,
Sym 7’nin de, Sym 8’in de elemanı olabilir. Hatta hatta Sym $\mathbb{N}$’nin de bir elemanı olabilir. Nasıl anlayacağız hangisinin elemanı olduğunu? Konunun gelişinden… Biraz dikkat etmek gerekir sadece.
Bu yazılımın tehlikesi yanında bir avantajı vardır: Bu yazılım sayesinde, örneğin, Sym 6’yı rahatlıkla Sym 9’un altkümesi olarak görebiliriz. Nitekim Sym 6’nın her elemanı, Sym 9’un 7, 8 ve 9’u sabitleyen bir elemanı olarak görülebilir.
Örnekler
Örnek 1. İskambil kâğıtlarını 1’den 52’ye kadar numaralandıralım ve 1 en üstte, 52 en altta
olmak üzere sıraya dizelim. Bu numaralar aslında kâğıtların üstten başlayarak sıraları. Desteyi tam ortadan 26’şar kâğıtlık iki küçük desteye bölelim. Destelerden birinde 1’den 26’ya kadar olan kâğıtlar (sol deste), diğerinde 27’den 52’ye kadar olan kâğıtlar (sağ deste) var. Şimdi iki desteyi o bilinen fiyakalı biçimde karalım.
Sağ destenin son kâğıdı olan 52 numara gene
en alta gelsin. Sol destenin sonuncu kâğıdı olan 26
numara sondan bir önceki kâğıt olsun.
Kâğıtları bu yöntemle bir sağdan bir soldan kararsak, birinci destenin ilk kâğıdı (1 yani) en üste gelir, ikinci destenin ilk kâğıdı (27 yani) ikinci kâğıt olur. Sonra 2 numaralı kâğıt, sonra 28 numaralı kâğıt, sonra 3 numaralı kâğıt gelir ve bu böyle devam eder. Karmadan önceki destenin
kâğıtları nasıl değişmiştir? 1 numaralı kâğıt gene en baştadır, gene 1 numaradır diyelim. Dolayısıyla (1) döngüsü oluşmuştur. Ama 2 numaralı kâğıt karmadan sonra 3’üncü sıraya gelmiştir, yani 3 numaralı kâğıt olmuştur. 3 numara ise 5 numara olmuştur. Genel olarak, ilk destedeki 1 ile 26 arasındaki $n$ numaralı kâğıt yeni destede $2n – 1$ numaralı kâğıt olmuşlardır. Öte yandan 27 numaralı kâğıt 2 numaralı kâğıt, 28 numaralı kâğıt 4 numaralı kâğıt olmuştur. Genel olarak ikinci destedeki 27 ile 52 arasında olan n numaralı kâğıt yeni destede $2(n-26)$ numaralı kâğıt olmuştur. Dönüşümü şöyle gösterebiliriz:
$$ f(n) = \left\{ \begin{array}{ll} 2n-1 \quad \text{eğer}\; 1 \geq n \geq 26 \quad \text{ise} \\ 2(n-26) \quad \text{eğer}\; 27\geq n \geq 52 \quad \text{ise} \end{array} \right\} $$
Bu dönüşümü (permütasyonu) öğrendiğimizbiçimde yazarsak (tek satıra sığmayan),
(1)(2 3 5 9 17 33 14 27)(4 7 13 25 49 46 40 28)
(6 11 21 41 30 8 15 29)(10 19 37 22 43 34 16 31)
(12 23 45 38 24 47 42 32)(18 35)(20 39 26 51 50
48 44 36)(52)
permütasyonunu elde ederiz.
Örnek 2. Sym $\mathbb{N}$ grubunun elemanlarını da bu yöntemle yazabiliriz, en azından formülü olan permütasyonlarını. Örneğin $(0 1)(2 3)(4 5)\dots$ permütasyonu çift sayılara 1 ekler, tek sayılardan 1 çıkarır. $(0 1)(2 3 4)(5 6 7 8)\dots$ bir başka örnek. Ama dikkat $(0 1 2 3 \dots)$ bir permütasyonun gösterimi değildir çünkü 0’a giden eleman yok, yani fonksiyon örten değil.
$\mathbb{Z}$’den $\mathbb{Z}$’ye giden ve $f(n)=n+1$ formülüyle tanımlanan eşleşmeyi ele alalım. Kümeler kuramı açısından $\mathbb{Z}$ ile $\mathbb{N}$ arasında bir fark yoktur, çünkü her ikisi de sayılabilir sonsuzluktadır. $\mathbb{Z}$’den $\mathbb{N}$’ye giden bir $g$ eşlemesi bulalım. O zaman $g \circ f \circ g^{-1} \in \text{Sym} \mathbb{N}\;$ olur. $g$ olarak mesela,
$$ g(n) = \left\{ \begin{array}{ll} 2n \quad \text{eğer}\; n \geq 0 \quad \text{ise} \\ -2n-1 \quad \text{eğer}\; n \leq 0 \quad \text{ise} \end{array} \right \} $$
olabilir. Bu durumda kolayca kontrol edilebileceği üzere $g \circ f \circ g^{-1} = (\dots 5 3 1 0 2 4 6 \dots )\;$ olur.
Alıştırmalar
- Aşağıda gösterilen permütasyonların en kısa yazılımını bulun.
- $f$ ve $g$ aşağıda (bu sırayla) gösterilen permütasyonlar olsun. $f \circ g$ ve $g \circ f$ permütasyonlarını bulun.
- Aşağıda gösterilen permütasyonların en kısa yazılımını bulun
- Aşağıdaki $f$ ve $g$ permütasyonları için $f \circ g$ permütasyonunu bulun ve bu permütasyonu en kısa gösterimiyle yazın.
Hangi durumda $f \circ g = g \circ f$ olur?k 1’de karmaya sağ destenin son kâğıdı en alta gelecek biçimde değil de, sol destenin en son kâğıdı en alta gelecek biçimde başlasaydık hangi permütasyonu elde ederdik?
- Bileşke. Sym $X$’ten iki elemanın bileşkesinin yine Sym $X$’tedir elbette. Sym $n$ gruplarında ve hatta Sym \mathbb{N} grubunda, elemanların bileşkesini almanın kolay bir yöntemi vardır.
Örnekler
Örnek 3. Sym 7’den iki eleman alıp bunların bileşkesini bulalım. Diyelim, (1 2 3)(4 5) ile (1 4 7 2)(3 6 5) elemanlarını aldık. Bu iki elemanın $(1 2 3)(4 5) \circ (1 4 7 2)(3 6 5)$ bileşkesini bulalım:
En soldan başlayıp okları takip edersek (yani ortadaki kademeyi resimden atarsak),
buluruz. Bu permütasyon da (1 5)(3 6 4 7) olarak yazılır. Demek ki (1 2 3)(4 5) $\circ$ (1 4 7 2)(3 6 5) = (1 5)(3 6 4 7) olur. Bu eşitliği yukardaki zahmetli şekilleri çizmeden de bulabiliriz. Şöyle yaparız: Bileşkeyi bulmak için önce 1’in imgesini bulalım.
(1 yazarak hesaplara başlayalım. (1 4 7 2)(3 6 5) permütasyonu 1’i 4’e götürüyor. Bir sonraki (1 2 3)(4 5) permütasyonu da 4’ü 5’e götürüyor. Demek ki bulmak istediğimiz bileşke 1’i 5’e götürüyor. Bu yüzden 1’in yanına 5 yazalım: (1 5
fiimdi 5’in bileşke altında akıbetini bulmalıyız. (1 4 7 2)(3 6 5) permütasyonu 5’i 3’e götürüyor. Bir sonraki (1 2 3)(4 5) permütasyon da 3’ü 1’e götürüyor. Demek ki bulmak istediğimiz bileşke 5’i 1’e götürüyor. Hesaplara başladığımız 1 sayısına geri döndük. Açtığımız parantezi kapatalım: (1 5)
Şimdi nereye gittiğini bilmediğimiz ilk sayı olan 2’nin akıbetini öğrenelim. Yeni bir parantez açıp sağına 2 yazalım: (1 5)(2
(1 4 7 2)(3 6 5) permütasyonu 2’yi 1’e götürüyor. Bir sonraki (1 2 3)(4 5) permütasyonu da 1’i 2’ye götürüyor. Demek ki bulmak istediğimiz bileşke 2’yi 2’ye götürüyor. Paranteze başladığımız 2 sayısına çabuk geri döndük. Parantezi hemen kapatalım: (1 5)(2)
Akıbetini bilmediğimiz bir sonraki sayı 3. Önce (1 5)(2)(3 yazalım.
(1 4 7 2)(3 6 5) permütasyonu 3’ü 6’ya götürüyor. Bir sonraki (1 2 3)(4 5) permütasyon da 6’yı 6’ya götürüyor. Demek ki bulmak istediğimiz bileşke 3’ü 6’ya götürüyor. Bu yüzden 3’ün yanına 5 yazalım: (1 5)(2)(3 6
6’nın nereye gittiğini bulmalıyız. (1 4 7 2)(3 6 5) permütasyonu 6’yı 5’e götürüyor. Bir sonraki (1 2 3)(4 5) permütasyonu da 5’i 4’e götürüyor. Demek ki bulmak istediğimiz bileşke 6’yı 4’e götürüyor. Bu yüzden 6’nın yanına 4 yazalım: (1 5)(2)(3 6 4
Bakalım 4 nereye gidiyor. Diğer tüm sayıları kullandığımız için 4’ün ya 3’e ya da 7’ye gitmesi gerektiğini biliyoruz. Bulalım: (1 4 7 2)(3 6 5) permütasyonu 4’ü 7’ye götürüyor. Bir sonraki (1 2 3)(4 5) permütasyonu da 7’yi 7’ye götürüyor. Demek ki bulmak istediğimiz bileşke 4’ü 7’ye götürüyor. Bu yüzden 4’ün yanına 7 yazalım: (1 5)(2)(3 6 4 7
7’nin bileşke altında nereye gittiğini bulmalıyız. 7’nin 3’ten başka gidecek yeri kalmadı ama biz gene de yukarıdaki yöntemi uygulayalım: (1 4 7 2)(3 6 5) permütasyonu 7’yi 2’ye götürüyor. Bir sonraki (1 2 3)(4 5) permütasyonu da 2’yi 3’e götürüyor. Demek ki bulmak istediğimiz bileşke 7’yi gerçekten 3’e götürüyor. Paranteze başladığımız 3 sayısına geri döndük. Açtığımız parantezi kapatalım: (1 5)(2)(3 6 4 7).
Kontrol edilmemiş başka sayı kalmadığından, (1 2 3)(4 5) $\circ$ (1 4 7 2)(3 6 5) = (1 5)(2)(3 6 4 7) eşitliğine ulaşırız. (2) parantezini yazmadığımızdan, aynen yukardaki gibi (1 2 3)(4 5) $\circ$ (1 4 7 2)(3 6 5) = (1 5)(3 6 4 7) buluruz.
Örnek 4. Tabii ikiden fazla permütasyonun da bileşkesini alabiliriz. Örneğin, (1 3 5) $\circ$ (2 3 6) $\circ$ (1 2 6) = (1 5)(2)(3 6).
Alıştırmalar
6. Eğer $f \in \text{Sym}\; \mathbb{N}$ ise Soc $f = \{n \in \mathbb{N}: f(n) \neq n\}$ olsun. Soc $f$’ye $f$’nin kaidesi (İngilizcesi socle) adı verilir. $\text{Sym}^{<ω}\; \mathbb{N} = \{f \in \text{Sym}\; \mathbb{N}: \text{Soc}\;f\; \text{sonlu}\}$ olsun. $\text{Sym}^{<ω}\; \mathbb{N}$ kümesinin bileşke altında kapalı olduğunu ve bileşke işlemiyle birlikte bir grup olduğunu gösterin.
Son olarak (1 2 3)(4 5) permütasyonunun (1 2 3) ile (4 5) permütasyonunun bileşkesi olduğuna dikkat edelim, yani (1 2 3) $\circ$ (4 5) = (1 2 3)(4 5). Bu iki permütasyon birbiriyle yer değiştirir: (1 2 3)(4 5) = (4 5)(1 2 3); çünkü (1 2 3) ile (4 5) permütasyonlarının değiştirdiği elemanlar kümesi (yani bu permütasyonların kaideleri) sırasıyla {1, 2, 3} ve {4, 5} kümeleridir ve bu kümeler ayrık kümelerdir.
- Elemanların Tersi. Her permütasyonun bir tersi vardır: Eğer bir permütasyon $x$’i $y$’ye götürüyorsa, bu permütasyonun tersi $y$’yi $x$’e götürür.
Örneğin $f$ = (1 2 3 4)(5 6 7 8 9) permütasyonun tersi $g$ = (1 4 3 2)(5 9 8 7 6) permüstasyonudur. Örneğin $f$ permütasyonu 1’i 2’ye götürdüğünden, $g$ permüstasyonu 2’yi 1’e götürür; $f$ permütasyonu 4’ü 1’e götürdüğünden, $g$ permütasyonu 1’i 4’e götürür. $f$ ne yapıyorsa, $g$ tam tersini yapar.
$f$’nin tersi $f^{-1}$ olarak yazılır.
Ayrık döngüler halinde yazılmış bir permütasyonun tersini gene ayrık döngüler halinde yazmak
çok kolaydır: her döngünün ilk elemanını sabitleyip geri kalan elemanları tersten sıralayarak yazmak yeter. Yukarda olduğu gibi. Bir örnek daha: $[(1 4 7 3)(2 5 8)(6 9)]^{-1} = (1 3 7 4)(2 8 5)(6 9).$ Bazı elemanlar kendi kendilerinin tersidir. Örneğin, (1 2), (1 3)(2 5) gibi elemanların tersleri kendileridir.
- Elemanların Dereceleri. Eğer $f$ bir permütasyonsa (hatta bir kümeden kendisine giden herhangi bir fonksiyonsa), $f$’nin kendisiyle bileşkesini alabiliriz, yani $f \circ f$ bileşkesini bulabiliriz. Bu bileşke $f^2$ olarak yazılır. (Ama $f$’nin değerlerinin karelerini alma fonksiyonuyla karıştırılmasın.) $f$’nin kendisiyle 3 defa da bileşkesini alabiliriz. Bu yeni
permütasyon $f^3$ olarak gösterilir. Bunu böyle devam ederek $f^n$ bileşkesini alabiliriz. $f^0 = \text{Id}$ ve $f^1 = f$ anlamına gelirler.
Örnekler
Örnek 5. $f$ = (1 2 3 4)(5 6 7) olsun. $f$’nin kuvvetlerini teker teker yazalım:
Görüldüğü üzere tam 12’nci kuvvette Id buluyoruz, daha önce değil. Bu durumda $f$’nin derecesinin (ya da mertebesinin) 12 olduğu söylenir. Bu listeyi devam ettirirsek, pek farklı bir şey bulmayız: $f^{13} = f,\; f^{14} = f^2,\; f^{15} = f^3,$ yukarıdaki liste kendini yeniler. Örneğin, $f^{142} = f^{10} =$ (1 3)(2 4)(5 6 7) olur.
Örnek 6. Yukardaki örnekte iki döngü vardı: (1234) döngüsü ve (567) döngüsü. Kolayca görüleceği üzere birinci döngünün derecesi 4, ikincisinin ise 3. Çarpımın derecesi ise 4 × 3 = 12 ama her zaman böyle olmaz. Örneğin, $f$ = (1 2 3 4 5 6 7 8 9 10)(11 12) ise $f$’nin derecesi 10 × 2 = 20 değil 10 olur. Aynı şekilde $f$ = (1 2 3 4 5 6)(7 8 9 10) permütasyonunun derecesi 6 × 4 = 24 değil 12 olur.
Örnek 7. $k$ uzunluğunda bir döngünün derecesi tam $k$’dır.
Örnek 8. Genel olarak $k_1, \dots, k_r$ uzunluğunda ayrık $r$ döngüden oluşan bir permüstasyonun derecesi ekok$(k_1, \dots, k_r)$ olur.
Örnek 9. Id derecesi 1 olan yegâne elemandır.
Örnek 10. Sym 5’in derecesi 2 olan elemanlarını yazalım:
(1 2), (1 3), (1 4), (1 5), (2 3) (2 4) (2 5)
(3 4) (3 5) (4 5),
(1 2)(3 4), (1 2)(3 5), (1 2)(4 5), (1 3)(2 4),
(1 3)(2 5), (1 3)(4 5),
(1 4)(2 3), (1 4)(2 5), (1 4)(3 5), (1 5)(2 3),
(1 5)(2 4), (1 4)(3 5).
Sym $n$’nin bir $f$ elemanının derecesi, $f^d$ kuvvetinin özdeşlik fonksiyonu olduğu en küçük pozitif $d$ doğal sayısıdır. Bu durumda $f \circ f^{d-1} = f^d =$ Id eşitliğinden dolayı $f^{-1} = f^{d-1}$ olur. Genel olarak eğer $f^n =$ Id ise $f^{-1} = f^{n-1}$ olur.
(1 2), (1 3)(2 5) gibi elemanların dereceleri 2’dir. Derecesi 2 olan her elemanın döngüleri 2
uzunluğundadır. Nitekim eğer $f^2 =$ Id ise ve $f(a) \neq a$ ise, $(a, f(a))$ döngüsü mutlaka $f$’de yer almalıdır. Elbette derecesi 2 olan elemanlar kendi kendilerinin tersidir ve kendi kendisinin tersi olan her elemanın derecesi 2’dir.
Alıştırmalar
- Sym 6’nın kaç tane derecesi 2 olan elemanı vardır?
- Sym 7’nin kaç tane derecesi 3 olan elemanı vardır?
- Sym 8’in kaç tane derecesi 4 olan elemanı vardır?
- Sym 9’un kaç tane derecesi 6 olan elemanı vardır?
- $n = 1,\dots, 20$ için Sym $n$’nin elemanlarının maksimum derecelerini bulun.
- Örnek 1’deki karmayı kaç defa yaparsak artlar eski haline gelir?
- Aynı soru Alıştırma 5’teki karma için.
- Yukardaki iki soruda destedeki kâğıt sayısı (çift kalmak üzere) değişse yanıt ne olur?
- $f^n = f^m$ = Id ise $d = \text{ebob}(n, m)$ için $f^d =$ Id olduğunu kanıtlayın.
- $f$’nin derecesi $d$ olsun. Eğer bir $n \in \mathbb{N}$ için $f^n = Id$ ise $d$’nin $n$’yi böldüğünü kanıtlayın.
- $g \in \text{Sym}\; n$ ise $g^{n!} =$ Idn eşitliğini kanıtlayın.
- Makaslar. (1 2), (3 5) gibi sadece iki elemanın yerlerini değiştiren permütasyonlara transpozisyon adı verilir. Türkçe karşılığı olarak makas terimini öneriyoruz. Makasların derecesi 2’dir elbette. Ama derecesi 2 olan her eleman bir makas değildir, örneğin (1 2)(3 5) permütasyonunun derecesi 2 olmasına rağmen bir makas değildir. Öte yandan, (1 2)(3 5)(4 7) gibi, derecesi 2 olan her eleman ayrık makasların çarpımı olarak yazılabilir.
Makasların önemi şuradan gelmektedir: Her eleman makasların bileşkesi olarak yazılabilir. Örneğin
(1 2) $\circ$ (2 3) = (1 2 3)
(1 2) $\circ$ (2 3) $\circ$ (3 4) = (1 2 3 4)
(1 2) $\circ$ (2 3) $\circ$ (3 4) $\circ$ (4 5) = (1 2 3 4 5).
Bir başka örnek:
(1 2 5 6)(3 8 4) = (1 2) o (2 5) o (5 6) o (3 8) o (8 4).
(1 a) türünden makaslara temel makas diyelim. Sym $n$’de tam $n -1$ tane temel makas vardır:
(1 2), $\dots,$ (1 $n$).
İlginç ve yararlı bir gözlem:
(1 a) o (1 b) o (1 a) = (a b)
olduğundan, bir önceki paragrafa göre, Sym $n$’nin
her elemanı temel makasların bileşkesi olarak yazılabilir. Örneğin,
(1 2 3 4) = (1 2) o (2 3) o (3 4) = (1 2) o (1 2) o (1 3) o (1 2) o (1 3) o (1 4) o (1 3)
= (1 3) o (1 2) o (1 3) o (1 4) o (1 3)
olur. (1 2), (2, 3), (3 4) gibi ardışık sayılardan oluşan makaslara ardışık makaslar adı verelim.
(1 3) = (2 3) o (1 2) o (2 3)
(1 4) = (3 4) o (2 3) o (1 2) o (2 3) o (3 4)
(1 5) = (4 5) o (3 4) o (2 3) o (1 2) o (2 3) o (3 4) o (4 5)
gibi eşitlikler sayesinde, bir önceki paragraftan dolayı, Sym $n$’nin her elemanının ardışık makasların bileşkesi olarak yazılabileceği görülür.
Ayrıca, doğruluğu kolayca kontrol edilebilen
(1 2 $\dots n$) o (1 2) o (1 2 $\dots n)^{-1}$ = (2 3)
(1 2 $\dots n$) o (2 3) o (1 2 $\dots n)^{-1}$ = (3 4)
gibi eşitlikler sayesinde, bir önceki paragraftan dolayı Sym $n$’nin her elemanının
(1 2 $\dots n$), (1 2), ve (1 2 $\dots n)^{-1}$
permütasyonlarının çarpımı olarak yazıldığı görülür.
Kanıtladıklarımızı yazalım:
Teorem 1. Sym $n$’nin her elemanı makaslar / temel makaslar / ardışık makaslar cinsinden yazılabilir. Sym $n$’nin her elemanı $(1 2 \dots n)$ ve $(1 2)$ permütasyonları cinsinden de yazılır.
Kanıt: Çünkü (1 2 $\dots n)^{–1}$ = (1 2 $\dots n)^{n–1}.$
Bundan böyle bileşke için $o$ işaretini kullanamayacağız. Örneğin (1 2) o (2 3) yerine (1 2)(2 3) yazacağız. (1 2) o (3 4) = (1 2)(3 4) eşitliğinden dolayı bu yeni yazılım herhangi bir karışıklığa neden olmayacak. Sık sık bileşke yerine çarpım dediğimiz de olacak.
- Eşleniklik. Sym 9’da, örneğin
(1 2)(3 4 5)(6 7 8)
ile
(2 9)(3 7 6)(4 5 8)
elemanları aynı tiptendirler, çünkü her ikisinde de her $k$ için uzunluğu $k$ olan her ayrık döngüden aynı sayıda vardır. Sym 9’un elemanlarının tiplerini sıralayalım:
Id0 tipi
(1 2) tipi
(1 2 3) tipi
(1 2)(3 4) tipi
(1 2 3 4) tipi
(1 2)(3 4 5) tipi
(1 2 3 4 5) tipi
(1 2)(3 4)(5 6) tipi
(1 2)(3 4 5 6) tipi
(1 2 3)(4 5 6) tipi
(1 2 3 4 5 6) tipi
(1 2)(3 4)(5 6 7) tipi
(1 2)(3 4 5 6 7) tipi
(1 2 3)(4 5 6 7) tipi
(1 2 3 4 5 6 7) tipi
(1 2)(3 4)(5 6)(7 8) tipi
(1 2)(3 4)(5 6 7 8) tipi
(1 2)(3 4 5)(6 7 8) tipi
(1 2)(3 4 5 6 7 8) tipi
(1 2 3)(4 5 6 7 8) tipi
(1 2 3 4)(5 6 7 8) tipi
(1 2)(3 4)(5 6)(7 8 9) tipi
(1 2)(3 4)(5 6 7 8 9) tipi
(1 2)(3 4 5)(6 7 8 9) tipi
(1 2 3)(4 5 6)(7 8 9) tipi
(1 2 3)(4 5 6 7 8 9) tipi
(1 2 3 4)(5 6 7 8 9) tipi
(1 2 3 4 5 6 7 8 9) tipi
Her birinden kaç tane olduğunu ileride bulacağız. Bu paragrafta amacımız aynı tipten iki eleman
arasında grup teorisi açısından nasıl bir ilişki olduğunu irdelemek.
Örnek olarak aynı tipten olan
$f$ = (1 2)(3 4)(5 6 7 8 9)
permütasyonuyla
$g$ = (1 5)(2 8)(3 7 9 6 4)
permütasyonuna bakalım. Birincisinde sayıların
adlarını değiştirirsek, mesela
1 yerine 1
2 yerine 5
3 yerine 2
4 yerine 8
5 yerine 3
6 yerine 7
7 yerine 9 8 yerine 6
9 yerine 4
yazarsak ikincisini buluruz.
$g$ = (1 5)(2 8)(3 7 9 6 4) = (8 2)(1 5)(7 9 6 4 3)
olduğundan, şöyle de yapabilirdik:
1 yerine 8
2 yerine 2
3 yerine 1
4 yerine 5
5 yerine 7
6 yerine 9
7 yerine 6
8 yerine 4
9 yerine 3
de yazabilirdik. Bu “yerine yazmanın” ne demek
olduğunu görelim. İkinci yer değişikliğini ele alarak,
$h$ = (1 8 4 5 7 6 9 3)
yazalım ve $hfh^{-1}$ elemanına bakalım. (Bileşke için $o$ yazmıyoruz artık.)
$hfh^{-1}$ = (1 8 4 5 7 6 9 3)(1 2)(3 4)(5 6 7 8 9)(1 3 9 6 7 5 4 8)
= (1 5)(2 8)(3 7 9 6 4) = $g$
buluruz. Yani
$hfh^{-1} = g$
olur. Ve elbette soldaki $h$’leri sağ tarafa atarak ve
$k = h^{-1}$ tanımını yaparsak,
$kgk^{-1} = f$
buluruz. Eğer Sym $n$’nin $f$ ve $g$ elemanlarının tipleri aynıysa, bir $h ∈ \text{Sym}\; n$ için,
$hfh^{-1} = g$
olur. Bu eşitliği sağlayan birden çok $h ∈ $ Sym $n$ vardır ama en az bir tane vardır.
Teorem 2. Eğer Sym $n$’nin $f$ ve $g$ elemanlarının tipi aynıysa, o zaman bir h ∈ Sym n için
hƒh-1 = g
olur. Bunun tersi de doğrudur: Eğer bir $h ∈ \text{Sym}\; n$ için $hfh^{-1} = g$ oluyorsa o zaman $f$ ve $g$’nin tipleri aynıdır.
Kanıt: Birinci kısmın kanıtının nasıl olması gerektiği teoremden önce yazılanlardan belli.
İkinci önermeyi kanıtlayalım. Diyelim $f$’nin içinde uzunluğu $k$ ile başlayan bir döngü var. Bu döngünün $(1 2 \dots k)$ döngüsü olduğunu varsaymak bize bir şey kaybettirmez. Öyle yapalım. Şimdi
$g(h(1)) = (hfh^{-1})(h(1)) = h(f(1)) = h(2)$
olur. Ayrıca
$g(h(2)) = (hfh^{-1})(h(2)) = h(f(2)) = h(3)$
olur. Bunu $h(k)$’ya kadar devam ettiririz, her $i = 1, 2, \dots, k – 1$ için $g(h(i)) = h(i + 1)$ buluruz. $k$ için ise,
$g(h(k)) = (hfh^{-1})(h(k)) = h(f(k)) = h(1)$
bulunur. Yani $f$’nin $(1 2 \dots k)$ döngüsü, $g$’de
$(h(1)\; h(2)\; \dots\; h(k))$
döngüsüne dönüşmüştür. Her döngü için aynı şey olduğundan kanıtımız tamamlanmıştır.
- Hangi Tipten Kaç Eleman Var? Sym $n$ ile biraz daha haşır neşir olmak için biraz hesap yapalım. Bu ve bundan sonraki bölüm, Sym $n$’nin anlaşılması için ya da grup teorisi için illa okunması gereken bölümler değildir. Konuyla daha aşina olmak isteyenlere önerilir ama.
Sym $n$’de “tipi” aynı olan elemanların sayısını hesaplayalım.
Örneğin (1 2) gibi ikili döngü biçiminde yazılabilen kaç eleman vardır? Eğer n = 4 ise 6 tane vardır: (1 2), (1 3), (1 4), (2 3), (2 4), (3 4).
Eğer $n = 5$ ise, 10 tane vardır:
(1 2), (1 3), (1 4), (1 5), (2 3),
(2 4), (2 5), (3 4), (3 5), (4 5).
Genel olarak bu tip elemanlardan $n$’nin ikilisi
kadar, yani
$$ \binom{n}{2} = \frac{n(n-1)}{2}$$
tane vardır.
Ya (1 2 3) gibi yazılabilen kaç eleman vardır?
$$\binom{n}{3}$$
tane değil. Çünkü seçtiğimiz her üçlü için iki ayrı seçeneğimiz var. Örneğin, 1, 2, 3 seçilmişse, bu
sayılarla elde edeceğimiz (1 2 3) ve (1 3 2) gibi iki ayrı permütasyon var. Bu tipten toplam
$$\binom{n}{3}\times 2$$
tane eleman vardır. $n = 5$ olsun ve bu 20 elemanın
her birini yazalım:
(1 2 3), (1 2 4), (1 2 5), (1 3 4), (1 3 5), (1 4 5),
(2 3 4), (2 3 5), (2 4 5), (3 4 5),
(1 3 2), (1 4 2), (1 5 2), (1 4 3), (1 5 3), (1 5 4),
(2 4 3), (2 5 3), (2 5 4), (3 5 4).
Ya (12)(34) tipinden? Birinci çift için
$$\binom{n}{2}$$
seçenek var. İkinci çift için
$$\binom{n-2}{2}$$
tane seçenek vardır. Ancak bu iki sayıyı çarparsak yanlış sonuç buluruz. Çünkü böyle yaparsak (12)(34) ve (34)(12)’yi sanki iki ayrı elemanmış gibi iki kez sayarız. Çarpımı ikiye bölmek gerekir. Sonuç olarak, (12)(34) tipinden
$$\frac{\binom{n}{2} \binom{n-2}{2}}{2} $$
tane eleman vardır. Gene $n = 5$ için bu 15 elemanın
hepsini teker teker yazalım:
(1 2)(3 4), (1 2)(3 5), (1 2)(4 5),
(1 3)(2 4), (1 3)(2 5), (1 3)(4 5),
(1 4)(2 3), (1 4)(2 5), (1 4)(3 5),
(1 5)(2 3), (1 5)(2 4), (1 5)(3 4),
(2 3)(4 5), (2 4)(3 5), (2 5)(3 4).
Aynı tipten olan elemanlara eşlenik denir. Eşlenik elemanlardan oluşan kümeye de eşleniklik
sınıfı denir.
Aşağıdaki tabloda $n = 2, \dots, 8$ için, $S_n$’de her eşlenik sınıfında kaç eleman olduğunu hesapladık. Her sütunun altında bulduğumuz sayıları toplayarak, toplamın $n!$ olup olmadığını kontrol ettik. Böylece yaptığımız hesapların sağlamasını yapmış olduk. (Gene de hata olabilir! Yanlışa tahammülü olmayan okur kendi başına hesaplamalıdır bu sayıları.)
Örneğin tipi, (1 2)(3 4)(5 6) elemanının tipiyle aynı olan eleman sayısını bulmak için,
$$\binom{n}{2} \binom{n-2}{2} \binom{n-4}{2}$$
sayısını $3!$’e bölmek zorundayız, aksi halde, örneğin, hepsi birbirine eşit olan
(1 2)(3 4)(5 6), (1 2)(5 6)(3 4), (3 4)(1 2)(5 6),
(3 4)(5 6)(1 2), (5 6)(1 2)(3 4), (5 6)(3 4)(1 2)
permütasyonların hepsini ayrı ayrı saymış olurduk.
Bunun gibi, $n ≥ 22$ için, Sym $n$’de, tipi
(1 2)(3 4)(5 6)(7 8)(9 10)(11 12 13)(14 15 16)
(17 18 19)(20 21 22)
olan elemanlardan tam,
$$ \frac{\binom{n}{2} \binom{n-2}{2} \binom{n-4}{2} \binom{n-6}{2} \binom{n-8}{2} \binom{n-10}{2} \binom{n-13}{2} \binom{n-16}{2} \binom{n-19}{2} 2^4}{5! \times 4!}$$
tane vardır; paydaki ilk beş ve son dört terim sadeleşir ve geriye,
$$ \frac{n!}{(n-22)! \times (5!2^5) \times (4!3^4)}$$( )
kalır. Bir sonraki teoremi okuduğunuzda bu sayının anlamını daha iyi anlaşılacak.
Teorem 3. $f ∈ S_n$ olsun. $k_i, f$’de $i$ uzunluğundaki döngülerin sayısı olsun. (Demek ki \sum ik_i = n.) O zaman, $f$’nin eşleniklik sınıfının eleman sayısı,
$$\frac{n!}{(k_1!1^{k_1}) (k_2!2^{k_2}) \dots (k_n!n^{k_n})} $$
olur.
Kanıt: Önce döngülerimizin parantezlerini hazırlayalım.
(_)(_)…(_)(_ _)… (_ _)(_ _ _)(_ _ _)…(_ _ _)…
Burada $k_1$ tane 1 sayılık parantez, $k_2$ tane 2 sayılık parantez, $…, k_n$ tane $n$ sayılık parantez var. (En uzun döngünün uzunluğu ancak $n$ olabilir.) Sayı konulabilecek toplam $n$ tane yuva var. Önce $n$ tane sayıyı her biçimde bu parantezlere (her parantezin kabul ettiği kadar) yerleştirelim. Bunu elbette $n!$ değişik biçimde yapabiliriz. Ama bu $n!$ yerleştirmenin bazıları $S_n$’nin aynı elemanını verir. Kaç tanesinin aynı elemanı verdiğini bulup bu sayıya bölelim. İçinde $i$ tane sayı yerleştirilebilen bir parantezi alalım. Bu parantezin içindeki sayıları $i$ değişik biçimde yerleştirirsek $S_n$’nin aynı elemanını elde ederiz. Örneğin,
(1 2 3 4 5), (2 3 4 5 1), (3 4 5 1 2), (4 5 1 2 3),
(5 1 2 3 4)
yerleştirmeleri aynı permütasyonu verir. Bu parantezlerden tam ki tane olduğundan, sayıları bulundukları parantezlerden çıkarmadan iki tane farklı yerleştirmenin aynı permütasyonu verdiğini buluruz. Öte yandan bu parantezlerin de yerlerini değiştirebiliriz. Örneğin,
(1 2)(3 4)(5 6), (1 2)(5 6)(3 4), (3 4)(1 2)(5 6),
(3 4)(5 6)(1 2), (5 6)(1 2)(3 4), (5 6)(3 4)(1 2)
yerleştirmelerinin hepsi aynı permütasyonu verir. $i$ uzunluğundaki $k_i$ parantezi $k_i!$ farklı biçimde yerleştirebiliriz. Demek ki sadece $i$ uzunluğundaki parantezlere yapılan $i^{k_i} \cdot k_i!$ tane farklı yerleştirme aynı permütasyonu verir. Bunları
$i = 1, 2, \dots, n$
için çarparsak, toplam
$(1^{k_1} ⋅ k_1!) (2^{k_2} ⋅ k_2!) \dots (i^{k_i} ⋅ k_i!) \dots (n^{k_n} ⋅ k_n!) $
farklı yerleştirmenin aynı permütasyonu vereceğinibuluruz. Demek ki bu tipteki eleman sayısını bulmak için, toplam yerleştirme sayısı olan $n!$ sayısını bu sayıya bölmeliyiz.
Önceki sayfadaki listede Sym $n$’de en fazla eleman olan eşleniklik sınıflarını koyu harflerle, Id
permütasyonu dışında, en az eleman olan sınıfları da altı çizili olarak gösterdik.
Belli ki, eğer $n ≥ 5$ ise en az (12) tipinde eleman var.
Ve gene belli ki Sym $n$’de en kalabalık sınıf
$(1 2 \dots n-1)$
sınıfı. Bu sınıfın $n(n – 2)!$ tane, yani
$$\frac{n!}{(n-1)}$$
tane elemanı var. Bir başka deyişle, her $n – 1$ elemandan biri bu tipten (yani bu eşleniklik sınıfında). En az elemanlı eşlenik sınıfının (1 2)’nin eşleniklik sınıfı olduğunu birazdan kanıtlayacağız. (1 2 $\dots\; n – 1$) elemanının sınıfının en kalabalık olduğu da doğru ama bu olgunun bu kitaba alacak kadar kolay bir kanıtını bilmiyorum. Meraklı okur Matematik Dünyası dergisinin 2003-II sayısının 103’üncü sayfasındaki Özer Çözer’in kanıtını okuyabilir. Zaten o kadar da ilginç bir soru değil!
- Eşlenik Sınıfı Sayısı. Her eşleniklik sınıfının sayısını bulduk. Peki Sym $n$’de kaç tane eşleniklik sınıfı var? Birkaç sayfa önce eşleniklik sınıflarını ve dolayısıyla kaç tane olduklarını $n = 8$’e kadar teker teker bulduk. Biraz daha ileri gidelim.
Sym $n$’deki eşleniklik sınıfı sayısı aslında $n$ sayısının parçalanış sayısına eşittir. Örneğin, eğer $n= 6$ ise, $n$’nin parçalanışlarıyla eşleniklik sınıfları
arasında şöyle bir eşleme vardır:
6 = 1 + 1 + 1 + 1 + 1 + 1 Id sınıfı
6 = 2 + 1 + 1 + 1 + 1 (1 2) sınıfı
6 = 3 + 1 + 1 + 1 (1 2 3) sınıfı
6 = 2 + 2 + 1 + 1 (1 2)(3 4) sınıfı
6 = 4 + 1 + 1 (1 2 3 4) sınıfı
6 = 3 + 2 + 1 (1 2 3)(4 5) sınıfı
6 = 5 + 1 (1 2 3 4 5) sınıfı
6 = 2 + 2 + 2 (1 2)(3 4)(5 6) sınıfı
6 = 4 + 2 (1 2 3 4)(5 6) sınıfı
6 = 3 + 3 (1 2 3)(4 5 6) sınıfı
6 = 6 (1 2 3 4 5 6) sınıfı
Bir doğal sayının parçalanış sayısı, o sayıyı (sıra gözetmeden) doğal sayıların toplamı olarak kaç
türlü yazılabileceğidir. Dolayısıyla 6’nın parçalanış sayısı yukarda görüldüğü gibi 11’dir, Sym 6’nın
eşleniklik sınıfı sayısına eşittir. Genel olarak, Sym n’nin eşleniklik sınıfı sayısı n’nin parçalanış sayısına eşittir. İlk birkaç sayı için liste aşağıda:
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 15 |
| sınıf sayısı | 1 | 2 | 3 | 5 | 7 | 11 | 15 | 22 | 30 | 42 | 56 | 77 | 101 | 135 |
Bugün bile üzerine pek çok araştırmalar yapılan parçalanış sayısı konusuna daha fazla girmeyeceğiz.
Teorem 4. Eğer $n ≥ 4$ ise, (1 2)’nin eşleniklik sınıfı, Id’in sınıfı dışında, Sym $n$’nin en az elemanlı eşleniklik sınıfıdır.
Kanıt. Id ≠ f ∈ Sym $n$ olsun. $f$’nin eşleniklik sınıfının eleman sayısını [ƒ] olarak gösterelim. ƒ’yi ayrık döngülerine ayırıp, uzunluğu $r$ olan döngülerini, adına $f_r$ diyeceğimiz bir elemanda toparlayalım. Örneğin $f$ = (1 2)(3 4)(5 6 7 8) ise $f_2$ = (1 2)(3 4), $f_3$ = Id, $f_4$ = (5 6 7 8).
Demek ki her $f_r$ uzunluğu $r$ olan ayrık döngülerin çarpımı ve $f$, bu $f_r$’lerin çarpımı. Eğer $f$ ve $g$ permütasyonları aynı tiptelerse, yani aynı eşleniklik sınıfındalarsa, elbette $f_r$ ve $g_r$ de aynı eşleniklik sınıfındadırlar. Ve $f_r$ ile aynı eşleniklik sınıfında olan her eleman mutlaka $f$ ile aynı eşleniklik sınıfında olan bir elemanda belirir, hatta muhtemelen 1’den fazla kez belirir. Örneğin yukardaki örnekteki $f_2$ ile aynı eşleniklik sınıfında olan (1 3)(2 5) elemanı, $f$’ye eşlenik olan (1 3)(2 5)(4 6 7 8) elemanında belirir. Eğer $f_r \neq$ Id ise, [$f_r$] ≤ [$f$] eşitsizliği bu yüzden bariz. Demek ki [(1 2)] ≤ [$f_r$]eşitsizliğini kanıtlamak yeterli.
Bundan böyle, $f$, herbirinin uzunluğu $r$ olan $k$ ayrık döngünün çarpımı olsun. Demek ki
$k_r ≤ n.$
Ayrıca $2 ≤ r$. Bu bilgiler daha sonra gerekecek. Şimdi $g$ = (1 2 $\dots$ r) olsun. Önce
[$g$] ≤ [$f$]
eşitsizliğini kanıtlayacağız. Her iki sayıyı da açık
açık bulabiliriz:
$$[g] = \binom{n}{r}(r-1)! $$
$$[f] = \binom{n}{r} \binom{n-r}{r} \dots \binom{n-kr +r}{r} \frac{((r-1)!)^k}{k!} $$
(Teorem 3’ü de kullanabilirdik.) Bundan sonra
[$g$] ≤ [$f$]
eşitsizliğini $k$ ve $n$ üzerine tümevarımla kanıtlamak, biraz meşakkatli olsa da çok zor değil; okura bırakıyoruz. Demek ki
[(12)] ≤ [$g$]
eşitsizliğini, yani
$$\binom{n}{2} \neq \binom{n}{r}(r-1)! $$
eşitsizliğini kanıtlamamız gerekiyor. Bu da meşakkatli belki ama kolay. Ufak tefek ayrıntıları saymazsak teorem böylece kanıtlanmıştır.
Alıştırmalar
- (Bu soru IMO 1987 yarışmasında sorulmuştur).
$P_ (k ) = | \{ f : S_n : f\; \text{tam}\; k\; \text{eleman sabitliyor} \} |$
olsun.
$\sum_{k=0}^n kP_n(k) =
eşitliğini kanıtlayın. - Her $i$ = 1, $\dots, n$-1 için $σ_i = (i, i+1) ∈ \text{Sym}\; n$ olsun. Sym $n$’nin her elemanının sonlu tane $σ_i$’nin çarpımı olduğunu kanıtlayın. Her $i$ ve $j$ = 1, $\dots, n$ – 1 için ya
$(σ_i o σ_j)^1$ = Id,
ya
$(σ_i o σ_j)^2$ = Id,
ya da
$(σ_i o σ_j)^3 = Id
olmalı. Kanıtlayın. - Her $i$ = 2, $\dots, n$ için \tau_i = (1, i) ∈ \text{Sym}\; n$ olsun. Sym $n$’nin her elemanının sonlu tane $\tau_i$’nin çarpımı olduğunu kanıtlayın.
- Sym $\mathbb{N}$’nin her elemanının $f^2 = g^2$ eşitliklerini sağlayan iki $f$ ve $g$ permütasyonu için $f o g$ olarak yazıldığını kanıtlayın.
