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

1 beğenilme 0 beğenilmeme
105 kez görüntülendi

$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?

4, Kasım, 2016 Lisans Matematik kategorisinde Cagan Ozdemir (672 puan) tarafından  soruldu
4, Kasım, 2016 Cagan Ozdemir tarafından düzenlendi

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.

2 Cevaplar

1 beğenilme 0 beğenilmeme
 
En İyi Cevap

$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.

5, Kasım, 2016 DoganDonmez (3,534 puan) tarafından  cevaplandı
5, Kasım, 2016 Cagan Ozdemir tarafından seçilmiş
0 beğenilme 0 beğenilmeme

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.


5, Kasım, 2016 DoganDonmez (3,534 puan) tarafından  cevaplandı
12, Kasım, 2016 DoganDonmez tarafından düzenlendi
...