$n$ elemanlı bir kümeden kendisine giden birebir ve örten fonksiyon

Question

$n$ elemanlı bir kümeden kendisine giden, sabit noktası olmayan ve iki kez uygulandığında birim fonksiyonu veren kaç birebir ve örten fonksiyon vardır?

Comments

Permütasyon grupları ($S_n$) ile ilgili bazı basit bilgilerle cevaplanabilir.

İpucu: $\{k,f(k)\}$ ikililerini düşün. $n$ tek ise böyle bir fonksiyon yoktur.

---

Senin dusuncen nedir, Cagan?

---

n tek ise, ya sabit noktası olmak zorunda olur, sabit noktası yoksa da fonksiyon iki elemanın yerini değiştirdiğinden karesi kendisine eşit olamaz. 

Çift n ler için genel bir formul nasıl bulunabilir?

Fazla bir fikrim yok Sercan Hocam, oldukça yazıyorum zaten

---

$\{\{k,f(k)\}:1\leq k\leq n\}$ ler $\{1,2,\ldots,n\}$ kümesinin bir parçalanması (ama her şey iki defa yazılmış) olacak. 

Böyle bir parçalanış kaç şekilde yapılabilir saymayı düşünebiliriz.

---

$\sigma^2=id$ olacak atomorfizmalari bulmamiz yeterli. 

Burada elbet de nokta sabitleyenler de var. Ornegin iki nokta sabitliyorsa bunu $n-2$ hesabi ile cikarabiliriz.

Answer 1

$n$ çift bir doğal sayı olsun.

$\{1,2,\ldots, n\}$ kümesinden iki eleman seçelim. Bunu $\binom{n}{2}$ değişik şekilde yapabiliriz.

Kalan elemanlardan iki eleman daha $\binom{n-2}{2}$  şekilde seçebiliriz.

Bu şekilde devam edersek $\frac n2$ tane 2 elemanlı (ayrık) alt kümeyi (seçme sırası önemsiz oduğundan):

$$\frac{\binom{n}{2}\binom{n-2}{2} \cdots \binom{2}{2}}{\left(\frac n2\right)!}$$

değişik şekilde seçebiliriz. 

Yani $\{1,2,\ldots, n\}$ yi bu kadar değişik şekilde iki elemanlı alt kümelere parçalayabiliriz.

Bu parçalanışların herbiri ($\{k,l\}$ ikilisi bu parçalanışa ait ise $f(k)=l,\ f(l)=k$ olacak şekilde) 

$\{1,2,\ldots,n\}$ kümesinden kendine, tersi kendisine eşit olan, sabit noktası olmayan, 1-1 ve örten bir fonksiyon verir.

Answer 2

Daha kısa bir çözüm de varmış:

$f:\{1,2,\ldots,n\}$ böyle bir fonksiyon olsun.

$f(1)$ için $n-1$ seçeneğimiz var.

$k_1=\min\left(\{1,2,\ldots,n\}\setminus\{1,f(1)\}\right)$ olsun. $f(k_1)$  için $n-3$ seçenek var 

($f(k_1); 1,f(1),\textrm{ ve }k_1$ den farklı olmalı).

Bu şekilde devam edildiğinde, böyle fonksiyonların sayısı($n$ çift ise)

$(n-1)(n-3)\cdots 1$ olmalıdır. (Bu sayı bazan $(n-1)!!$ şeklinde kısaltılır) ($n$ tek ise boyle bir fonksiyon var olmadığı da görülüyor.)

Cagan Ozdemir e odev ($n$  çift ise):

$$\frac{\binom{n}{2}\binom{n-2}{2} \cdots \binom{2}{2}}{\left(\frac n2\right)!}=(n-1)(n-3)\cdots 1$$

 olduğunu göster.