Tübitak Lise Takım Seçme 1995 Soru 2

[Lokman Gökçe]

$n$ pozitif bir tamsayı olmak üzere $\sigma (j)\ge j$ koşulunu sağlayan tam olarak iki $j$ nin bulunduğu $\sigma : \lbrace 1,2,\ldots ,n\rbrace \to \lbrace 1,2,\ldots ,n\rbrace $ permütasyonlarının sayısını bulunuz.

[Lokman Gökçe]

Çözüm (Lokman GÖKÇE):
 
Öncelikle $\sigma (2) \neq 1$ durumuyla ilgilenelim.

$\sigma (2) \neq 1$ ise $\sigma (2) \geq 2$ olur. Ayrıca açıkça $\sigma (1) \geq 1$ olduğundan aranan özellikteki iki $j$ değeri $1$ ve $2$ olmuş olur. O halde  $\sigma (1),\sigma (2) $ değerlerinden biri $n$ e eşit olmak zorundadır. Böyle olmasa $\sigma (x) = n $ denklemini sağlayan $x$ sayısı aranan özellikteki 3. bir $j$ sayısı olmuş olur ki bu bir çelişkidir.

$\sigma (1),\sigma (2) \in \{ n-1, n \}$ olsun. $2$ seçim yapılabilir. $\sigma (3) \in \{ 1, 2 \}$ olup $2$ seçim vardır. $\sigma (4) \in \{ 1, 2, 3 \}$ olup $2$ seçim vardır... $\sigma (n-1) \in \{ 1, 2, \dots n-2 \}$ olup $2$ seçim vardır.  $\sigma (n) $ için $1$ tek seçim kalır. Çarpma prensibiyle $2^{n-2}$ farklı fonksiyon yazabiliriz.

$\sigma (1),\sigma (2) \in \{ n-2, n \}$ olsun. Bu durumda da benzer işlemlerle $2^{n-3}$ farklı fonksiyon yazabiliriz.

Benzer işlemlere devam ederek sondan önceki adımda $\sigma (1),\sigma (2) \in \{ 2, n \}$ olup $2$ seçim vardır. $\sigma (3)=1$ olmak zorundadır. Bundan sonraki değerlerde $\sigma (4)=3$, ... , $\sigma (n)=n-1$ elde edilir. Tek türlü seçim vardır. Çarpma prensibiyle $1 \cdot 2 = 2$ fonksiyon yazabiliriz.

Son adımda ise $\sigma (1),\sigma (2) \in \{ 1, n \}$ olsun. $\sigma (1)=1$ ve $\sigma (2)=n$ olmak zorundadır. $\sigma (3)=2$, ..., $\sigma (n)=n-1$ olacağından yalnız $1$ fonksiyon vardır.

Tüm bu değerlerin toplamını hesaplayalım:

$ 2^{n-2} + 2^{n-3} + \dots + 2^1 +1 = 2^{n-1}-1$ elde edilir.

Şimdi de $\sigma (2)=1$ durumuna bakalım.

Başlangıç olarak $\sigma (1), \sigma (3) \in \{ 2, n \}$ olsun. $\sigma (1)=2$, $ \sigma (3)=n$ tek yolla belirlenebilir. Diğer elemanların görüntüleri için $\sigma (2)=1$, $\sigma (4)=2$, ... , $\sigma (n)=n-1$ olması gerekir. Yani bu halde $1$ fonksiyon yazılabilir. $\sigma (1), \sigma (3) \in \{ 3, n \}$ durumlarını hesaplayalım. $2$ fonksiyon yazılabilir. $\sigma (1), \sigma (3) \in \{ 4, n \}$ durumlarını hesaplayalım. $2^2$ fonksiyon yazılabilir...vs son adımda $2^{n-3}$ ve toplamda ise $2^{n-2}-1$ fonksiyon vardır.

$\sigma (1), \sigma (4) \in \{ 3, n \}$ durumlarını hesaplayalım. $1$ fonksiyon yazılabilir. $\sigma (1), \sigma (4) \in \{ 4, n \}$ durumlarını hesaplayalım. $2$ fonksiyon yazılabilir.  son adımda $2^{n-4}$ fonksiyon yazılabilir...vs toplamda $2^{n-3} -1 $ fonksiyon vardır.

Bu tür alt durumları inceleyerek toplamda $2^{n-1} -1$ fonksiyon yazılabileceğini göstereceğiz. (Bu kısımda küçük bir hata yapıyorum ama henüz göremedim. ispatın son adımlarını daha sonra detaylandıracağım)

Sonuç olarak genel toplam $2^{n-1} -1 + 2^{n-1} - 1 = 2^n - 2$ olmalıdır.

[geo]

Her permütasyon, tek bir şekilde başkaları ile kesişmeyen çevrimlerin bir çarpımı olarak yazılabilir ve her çevrimde en az bir $j$ için $\sigma(j) \geq j$ olacaktır (yani, çevrimin en küçük elemanı). Bu nedenle $\sigma$ yalnızca bir veya iki çevrim içerebilir.

Eğer $\sigma$ iki çevrim içeriyorsa, her biri elemanlarını en büyükten başlayarak azalan sırayla içermelidir. Bu durumda, $\{1, \ldots, n\}$'yi iki boş olmayan kümeye ayırmanın yollarının sayısı, basitçe $2^{n-1}-1$'dir.

Şimdi, $\sigma$'nın bir çevrim içerdiğini düşünelim. Bu çevrim, $1$'e kadar azalan bir eleman dizisi ile başlar ve ardından bir $k>1$'e kadar azalan bir dizi içerir. Elemanlar $2, \ldots, k-1$'in ilk dizide yer alması gerektiğinden, $k+1, \ldots, n$ elemanlarını ilk veya ikinci diziyi seçmek dışında başka seçenek yoktur. Bu durumda $2^{n-k}$ tane permütasyon elde edilir. $k$ her biri için $2, \ldots, n$ olabileceğinden, toplamda $1+\cdots+2^{n-2}=2^{n-1}-1$ adet bir çevrim içeren permütasyon elde edilir.

Bu nedenle toplamda $2\left(2^{n-1}-1\right)=2^n-2$ adet permütasyon bulunur.

Kaynak: Mathematical Contests 1995-1996 Olympiad Problems and Solutions from around the World, 1997, Syf 124-125.