Processing math: 31%
Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
1 beğenilme 0 beğenilmeme
1.6k 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?

Lisans Matematik kategorisinde (691 puan) tarafından 
tarafından düzenlendi | 1.6k kez görüntülendi

Permütasyon grupları (Sn) 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)}:1kn} ler {1,2,,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.

σ2=id olacak atomorfizmalari bulmamiz yeterli. 

Burada elbet de nokta sabitleyenler de var. Ornegin iki nokta sabitliyorsa bunu n2 hesabi ile cikarabiliriz.

2 Cevaplar

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

n çift bir doğal sayı olsun.

{1,2,,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.

(6.3k puan) tarafından 
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.


(6.3k puan) tarafından 
tarafından düzenlendi
20,333 soru
21,889 cevap
73,623 yorum
3,046,440 kullanıcı