8 elemanlı bir kümeden 3 elemanlı bir kümeye tanımlanabilen örten fonksiyon sayısı kaç tanedir?

Question

http://www.matkafasi.com/13616/kombinasyon sorusuna ek olsun

Answer 1

Toplam fonksiyon sayısı $3^8$. Şimdi örten olmayan fonksiyon sayısını çıkaralım. 3 elemandan birini seçip, 8 elemandan hiçbirini o elemana götürmeyelim. Öyleyse $3\times 2^8$ tane örten olmayan fonksiyon varmış gibi duruyor. Fakat fazladan çıkardığımız $3\times 1$ tane örten olmayan fonksiyon var (8 elemanın birden karşı kümeden tek elemana gittiği durum). Bunları da geri eklediğimiz zaman $$3^8-3\times 2^8+3$$ buluyoruz. Genel olarak da $n$ elemanlı bir kümeden $m$ elemanlı bir kümeye giden örten fonksiyon sayısını bulurken içerme-dışarma prensibini kullanarak $$m^n-m\times (m-1)^n+C(m,2)\times (m-2)^n-...$$ şeklinde bulabiliriz.

Comments

Sayın Riemann'ın son yazdığını şöyle formülleştirmek mümkün.

$\sum_{k=0}^{m}(-1)^k. \binom{m}{k}.(m-k)^n$ 

Answer 2

Diğer soru ile ilişkili olarak çözecek olursak da, 8 elamanlı bir kümeyi hiçi biri boş olmayan 3 e alt kümeye 966 farklı şekilde ayırmıştık örten fonksiyon sayısıda 966.3!=5796 olur.