Düzensiz Diziliş

[Lokman Gökçe]

Alan 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ş 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)}\ 0
\qquad\textbf{b)}\ \dfrac{1}{3}
\qquad\textbf{c)}\ \dfrac{2}{2e+1}
\qquad\textbf{d)}\ \dfrac{1}{e}
\qquad\textbf{e)}\ \dfrac{2}{2e-1}
$

[Lokman Gökçe]

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