Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
0 beğenilme 0 beğenilmeme
1.5k kez görüntülendi

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

Lisans Matematik kategorisinde (2.6k puan) tarafından  | 1.5k kez görüntülendi

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.

1 cevap

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

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.

(2.6k puan) tarafından 
tarafından seçilmiş
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.

20,282 soru
21,821 cevap
73,503 yorum
2,522,509 kullanıcı