Olasılıkta Beklenen değer = Ortalama. Yani Çılgın hocamızın bahsettiği toplamı hesaplamamız lazım bir şekilde, yani sonucu gerçekten n e bağlı olmadan 1
. Farklı bir yaklaşım ile biraz olasılık teorisi kullanarak çok kısa bir çözüm mümkün. Ama klasik yoldan yani beklenen değerin tanımından da bunu ispatlamak mümkün. Ben öncelikle ekstra bir bilgi gerektirmeyen çözümü paylaşacağım buraya, yani klasik yolu.
Soruyu n için çözüyorum.
X : Kendi kalemini alan kişilerin sayısı olsun. Ortalama kendi kalemini alanların sayısına E(X) (Expected Value) diyelim. O zaman
$E(X) = 0.P(X = 0) + 1 . P(X = 1) + ... + nP(X = n)$
$c(k)$: $n$ kişiye kalemlerini kaç farklı şekilde verelim ki $k$ kişi kendi kalemini alsın. O zaman olasılığı aşağıdaki gibi yazabiliriz.
$P(X = k) = c(k)/n!$
İçerme-Dışarma ile $c(k)$ ları hesaplayabiliriz. Özetle şöyle: mesela $c(0)$ için toplamda $n!$ dağılımdan herhangi bir 1 kişinin kendi kalemini aldığı dağılımları çıkartabiliriz. Yani $n! - \dbinom{n}{1}(n-1)!$ Burada bir kişi seçip ona kendi kalemini veriyoruz, mesela A kişisi, sonra geri kalanları $(n-1)!$ şekilde sıralarken aslında başkalarına da kendi kalemini veriyor olabiliriz. Mesela B kişisine de kendi kalemini vermiş olduğumuz dağılımlar da bu $(n-1)!$ içerisindedir. Ama ilk başta B kişisini seçip ona kendi kalemini vermiş olsaydık ve sonra geri kalanları $(n-1)!$ şekilde sıralasaydık bu sefer de A kişisine kendi kalemini verdiğimiz durumlar tekrar saymış olacaktık. Yani A ve B kişilerine kendi kalemlerini verdiğimiz durumlar ikişer defa saydık aslında. O zaman fazladan çıkarma yaptık demektir. Yani bu ikisine kendi kalemlerini verdiğimiz durumları tekrar eklememiz gerekiyor. (Zaten şu durumda toplam 0
) O zaman $c(k) = n! - \dbinom{n}{1}(n-1)! + \dbinom{n}{2}(n-2)!$ olur. Bu durumda da bir başka C kişisini düşünürsek ikili durumları tekrar eklerken A ve C yi ve B ve C yi tekrar ekliyoruz. Ama A, B ve C nin kendi kalemlerini aldığı durumları iki defa eklemiş olduk, bunu çıkarmamız lazım. Bunu böyle devam ettirirsek $c(0)$ aşağıdaki gibi olur.
$c(0) = n! - \dbinom{n}{1}(n-1)! + \dbinom{n}{2}(n-2)! - \dbinom{n}{3}(n-3)! + ... + (-1)^n \dbinom{n}{n}(n-n)! = n! - n! + \dfrac{n!}{2!} - \dfrac{n!}{3!} ... + (-1)^n \dfrac{n!}{n!} = n! \left(1 - \dfrac{1}{1!} + \dfrac{1}{2!} - \dfrac{1}{3!} + \dfrac{1}{4!} ... + (-1)^n \dfrac{1}{n!}\right)$
$\left(1 - \dfrac{1}{1!} + \dfrac{1}{2!} - \dfrac{1}{3!} + \dfrac{1}{4!} ... + (-1)^n \dfrac{1}{n!}\right)$ kısmına $f(n)$ diyelim. O zaman $c(0) = n! f(n)$
Benzer şekilde c(1) i hesaplayalım. c(1), tam olarak bir kişinin kendi kalemini aldığı durumların sayısı idi. Bu durumda 1 kişi seçelim, ona kendi kalemini verelim ve geri kalan n-1 kişi için hiç kimsenin kendi kalemini alamadığı durumları sayalım. Bunu demin yaptığımız gibi yaparsak
$c(1) = \dbinom{n}{1}(n-1)!f(n-1)$ eder. Benzer şekilde
$c(2) = \dbinom{n}{2}(n-2)!f(n-2) = \dfrac{n! f(n-2)}{2!}$
...
$c(k) = \dfrac{n! f(n-k)}{k!}$
Beklenen değeri hatırlayalım.
$E[X] = 0.P(X = 0) + 1 . P(X = 1) + ... + nP(X = n) = 0.\dfrac{c(0)}{n!} + 1 . \dfrac{c(1)}{n!} + ... + n \dfrac{c(n)}{n!} = \dfrac{1}{n!} \left(c(1) + 2c(2) + 3c(3) + (n-2)c(n-2) + (n-1)c(n-1) + nc(n)\right)$
$E[X] = \dfrac{1}{n!} \left(n! f(n-1) + 2\dfrac{n! f(n-2)}{2!} + 3\dfrac{n! f(n-3)}{3!} + ... + (n-2)\dfrac{n! f(2)}{(n-2)!} + n\right) = f(n-1) + f(n-2) + \dfrac{f(n-3)}{2!} + ... + \dfrac{f(2)}{(n-3)!} + \dfrac{1}{(n-1)!}$
Bunu açık yazarsak
$E[X] = \left( \dfrac{1}{2!} - \dfrac{1}{3!} ... + (-1)^{n-1} \dfrac{1}{(n-1)!} \right) + \left( \dfrac{1}{2!} - \dfrac{1}{3!} ... + (-1)^{n-2} \dfrac{1}{(n-2)!} \right) + \dfrac{1}{2!}\left( \dfrac{1}{2!} - \dfrac{1}{3!} ... + (-1)^{n-3} \dfrac{1}{(n-3)!} \right) + \dfrac{1}{3!}\left( \dfrac{1}{2!} - \dfrac{1}{3!} ... + (-1)^{n-4} \dfrac{1}{(n-4)!} \right) + ... + \dfrac{1}{(n-3)!}\left(\dfrac{1}{2!}\right) + \dfrac{1}{(n-1)!}$
$n = 3$ için $E[X]$ i hesaplayalım, buna $E[X, 3]$ diyelim.
$E[X, 3] = \dfrac{1}{2!} + \dfrac{1}{(3-1)!} = 1$ Benzer şekilde E[X,4], E[X,5] de açık şekilde yazılabilir.
$E[X, 4] = \left(\dfrac{1}{2!} - \dfrac{1}{3!}\right) + \left(\dfrac{1}{2!}\right) + \dfrac{1}{3!}$
Burada $E[X,4]$ $E[X,3]$ cinsinden her parantez içerisine eklenen terimleri hesaba katarak yazılabilir. Yani
$E[X,4] = E[X, 3] - \dfrac{1}{3!} + \dfrac{1}{2!} - \dfrac{1}{2!} + \dfrac{1}{3!} = E[X, 3] = 1$
Aynı şekilde $E[X, 5]$ de $E[X, 4]$ ün parantez içlerine eklenen terimler $E[X,4]$ yanına ayrıca eklenerek ve $E[X, 4]$ ün son terimi çıkarılıp yerine $E[X,5]$ in son terimi yazılarak oluşturulabiir.
$E[X, 5] = \left(\dfrac{1}{2!} - \dfrac{1}{3!} + \dfrac{1}{4!}\right) + \left(\dfrac{1}{2!} - \dfrac{1}{3!}\right) + \dfrac{1}{2!}\left( \dfrac{1}{2!} \right) + \dfrac{1}{4!} = E[X, 4] + \dfrac{1}{4!} - \dfrac{1}{3!} + \dfrac{1}{2!}\left( \dfrac{1}{2!} \right) - \dfrac{1}{3!} + \dfrac{1}{4!} = E[X,4] = E[X,3] = 1$
$E[X, 6] = E[X, 5] + \left(-\dfrac{1}{5!} + \dfrac{1}{4!} - \dfrac{1}{2!}\dfrac{1}{3!} + \dfrac{1}{3!}\dfrac{1}{2!} - \dfrac{1}{4!} + \dfrac{1}{5!}\right) = E[X,5] = 1$
Eklenen terimleri dikkatlice incelersek genelleme yapabiliriz:
$E[X, k+1] = E[X, k] + (-1)^{k}\left(\dfrac{1}{k!} - \dfrac{1}{(k-1)!} + \dfrac{1}{2!}\dfrac{1}{(k-2)!} ... + (-1)^{k-2}\dfrac{1}{(k-2)!}\dfrac{1}{2!} + (-1)^{k-1}\dfrac{1}{(k-1)!} + (-1)^k\dfrac{1}{k!} \right)$
$E[X,k]$ yanındaki terimi dikkatlice incelersek (terime A diyelim)
$A = \left(\dfrac{1}{k!} - \dfrac{1}{(k-1)!} + \dfrac{1}{2!}\dfrac{1}{(k-2)!} ... + (-1)^{k-2}\dfrac{1}{(k-2)!}\dfrac{1}{2!} + (-1)^{k-1}\dfrac{1}{(k-1)!} + (-1)^k\dfrac{1}{k!} \right) = \dfrac{1}{k!} \left(\dfrac{k!}{k!} - \dfrac{k!}{(k-1)!} +\dfrac{k!}{2!(k-2)!} ... + (-1)^{k-2}\dfrac{k!}{(k-2)!2!} + (-1)^{k-1}\dfrac{k!}{(k-1)!} + (-1)^k\dfrac{k!}{k!} \right)$
$A = \dfrac{1}{k!} \left( \dbinom{k}{0} - \dbinom{k}{1} + \dbinom{k}{2} ... (-1)^{k-2}\dbinom{k}{k-2} + (-1)^{k-1} \dbinom{k}{k-1} + (-1)^k \dbinom{k}{k}\right) = (1-1)^k = 0$
Yani $A = 0$, bu durumda $E[X,k+1] = E[X, k]$ olmaktadır.
Yani herhangi bir n için cevap 1.
