Bu düzen, Bozuk Düzen!

Question

Matematik ÖABT (öğretmenlik alan bilgisi testi) sınavına uygun düzeyde bir problem sunalım:

$A=\{ 1,2, \dots , n\}$ kümesi üzerinde tanımlı tüm permütasyon fonksiyonlarının kümesi $S$ olsun.  Bir $$ f = \left(\begin{array}{cccccc} 1 & 2 & 3 & \cdots  & n \\ f(1) & f(2) & f(3) & \cdots   & f(n) \end{array} \right) $$ permütasyon fonksiyonunda her bir $a \in A$ için $f(a) \neq a$ oluyorsa $f$ ye bir düzensiz diziliş (bozuk düzen) diyoruz. $ n$ nin büyük değerlerinde, $S$ kümesinden rastgele seçilen bir $f$ permütasyon fonksiyonunun düzensiz diziliş olma olasılığı aşağıdakilerden hangisine daha yakındır? ($e$, doğal logaritma tabanını göstermektedir).

$ \textbf{a)}\ \dfrac{e}{2\pi} \qquad\textbf{b)}\ \dfrac{1}{\pi} \qquad\textbf{c)}\ \dfrac{2}{2e+1} \qquad\textbf{d)}\ \dfrac{1}{e} \qquad\textbf{e)}\ \dfrac{2}{2e-1} $

Comments

Cevap muhtemelen $1/e$. Bakininiz sapka problemi. Dearangment hat problem.

---

Tahmininiz doğru Ökkeş bey, teşekkürler. Uğraşmak isteyenler için bir süre çözümü girmeyeceğim. Daha sonra, duruma göre detaylı çözümü verebiliriz.

Answer 1

Yanıt: $\boxed{D}$

Düzensiz diziliş oluşturan permütasyon fonksiyonlarının sayısını $D_n$ ile gösterelim. $S$ kümesi üzerindeki permütasyon fonksiyonlarının sayısı $S_n=n!$ dir. Bir elemanın kendisi ile eşleştiği durumları çıkaralım. bunlar $\dbinom {n}{1}(n-1)!=\dfrac{n!}{1!}$ dir. Sonra iki elemanın kendisi ile eşleştiği durumları tekrar ekleyelim. Bu iki elemanı $\dbinom{n}{2}$ yolla belirleriz. Kalan $n-2$ eleman ile $(n-2)!$ tane permütasyon yazılabildiğinden $\dbinom{n}{2}(n-2)! = \dfrac{n!}{2!}$ durum oluşur. Bu şekilde devam edilerek içerme dışarma prensibi uygulanırsa 

$$D_n =n! - \dfrac{n!}{1!} + \dfrac{n!}{2!} - \cdots + (-1)^n \dfrac{n!}{n!}$$

olur.

$$D_n = n! \left ( 1 - \dfrac{1}{1!} + \dfrac{1}{2!} - \cdots + (-1)^n \dfrac{1}{n!} \right ) $$

biçiminde yazabiliriz. İstenen olasılığı $p$ ile gösterirsek $p=\dfrac{D_n}{S_n}$ olup $p= \left ( 1 - \dfrac{1}{1!} + \dfrac{1}{2!} - \cdots + (-1)^n \dfrac{1}{n!} \right )$ bulunur. $n$ nin çok büyük değerlerinde $p=\dfrac{D_n}{S_n}$ oranının hangi sayıya yaklaşacağını bulmak istiyorsak $n \to \infty $ için limiti hesaplamalıyız.

Diğer taraftan her $x$ gerçel sayısı için $e^x$ fonksiyonunun

$$e^x = 1 + \dfrac{x}{1!} + \dfrac{x^2}{2!} + \cdots + \dfrac{x^n}{n!} + \cdots $$

biçiminde Taylor serisine açılabildiğini biliyoruz. Özel olarak $x=-1$ için $e^{-1} = 1 - \dfrac{1}{1!} + \dfrac{1}{2!} + \cdots + (-1)^n\dfrac{1}{n!} + \cdots $ olduğundan

$$\lim_{n \to \infty} \dfrac{D_n}{S_n} = \dfrac{1}{e}$$ olarak hesaplanır.

Comments

Hocam bir elemanın kendisi ile eşleştiği durumları bulurken $\dbinom{n}{1}(n-1)!$ yolunu kullandık $\dbinom{n}{1}$ burada kendisi ile eşleşen elemanlar ,

$(n-1)!$ ise kendisi ile eşleşen bir eleman harici diğer elemanların aralarında sıralamaları ama biz bu $(n-1)!$ sıralamada elemanların kendisi ile eşleştiği durumları neden göz önüne almıyoruz ? aynı soru 2 elemanın kendisi ile eşleştiği durunlarda $(n-2)!$ sayısı içinde geçerli. Cevabınız için şimdiden teşekkürler.

---

Sorduğunuz nokta, içerme dışarma prensibi nin ispatı oluyor. $\dbinom{n}{1}$ ile kendisi ile eşleşen bir elemanı seçiyoruz. Geri kalan $(n-1)$ eleman $(n-1)!$ yolla sıralanıyorlar ve bunlar istenmeyen durumlar oluşturuyor. Örneğin $f(1)=1$ olan bir $f$ permütasyonu $(n-1)!$ yolla oluşturulabilir ve bu istenmeyen bir durumdur. Ayrıca $f(2)=2$ olan bir $f$ permütasyonu da $(n-1)!$ yolla oluşturulabilir ve bu da istenmeyen bir durumdur. Bunları tüm durumdan çıkarıyoruz. $n! - \dbinom{n}{1}(n-1)!$ olur. Ama burada bir yanlışlık olduğunu hissediyorsunuzdur. Çünkü bu farkın değeri $0$ oldu. Açıkça fazla çıkarma yaptık. Neyi fazla çıkardık? $f(1)=1,f(2)=2$ olan bir $f$ permütasyonu hem ilk istenmeyen durumda, hem de ikinci istenmeyen durumda hesapladı. İki defa dışarı atmışız. O halde bunlardan birini  geri alalım. $f(1)=1,f(2)=2$ olan $f$ permütasyonlarının sayısı $(n-2)!$ dir. Bu şekilde iki elemanın doğru yere gittiği $f$ permütasyonlarının sayısı $\dbinom{n}{2}(n-2)!$ olur. Bunları toplama geri alalım. $n! - \dbinom{n}{1}(n-1)! + \dbinom{n}{2}(n-2)!$ oldu. Fakat halen bu hesapta bir sorun var. $f(1)=1, f(2)=2, f(3)=3$ olan $f$ permütasyonları var. $ f(1)=1, f(2)=2$ olanları aldık, $f(1)=1, f(3)=3$ olanları da aldık, $f(2)=2, f(3)=3$ olanları da aldık. Fazla mı aldık ne? $f(1)=1, f(2)=2, f(3)=3$ olan $f$ permütasyonlarını yine dışarı atalım ... 

Bu şekilde devam eden bir süreç devam etmektedir. Bu tür durumların hesabı, doğrudan istenen durum hesabı yaparak pek kolay yapılamıyor. Hata yapmak, eksik/fazla sayma yapmak işten bile değildir. Neyse ki içerme dışarma prensibimiz var ve hatasız hesap yapma imkanı sunuyor bize. Üç küme için

$$|A\cup B \cup C| = |A| + |B| + |C| - |A \cap B | - |B \cap C| - |C\cap A| + |A\cap B \cap C | $$ biçiminde verilen bu teoremin genel haldeki ispatı internette araştırıp bulunabilir.

Dikkatimi çeken üç önemli uygulaması şunlardır:

• Düzensiz dizilişlerin sayısı (yukarıda uyguladık)
• Euler $\phi$ fonksiyonunun formülünün ispatı (burada verildi)
• Örten fonksiyon sayısı (henüz bir bağlantı paylaşmadık sanırım)

Tatlı sert bir örten fonksiyon sayısı probleminin çözümünü şurada video olarak yapmıştım. Yöntemi kavrama bakımından iş görebilir.