Question

$\{ 1,2, ..., n \}$ kümesinin ardışık sayı içermeyen $k$ elemanlı kaç altkümesi vardır?

Comments

Ben $k$'lısını sormuştum! Nasıl olduğunu cevap olarak güzelce yazarsanız herkes faydalanır.

---

Bu güzel soruya sizin cevabınızı bekliyoruz Salih Hoca.

Answer 1

$\{1,2,\dots, n\}$ kümesinden $k$ tane eleman seçmeyi $n$ uzunlukta bir diziye tam $k$ tanesine $1$ gelecek şekilde $0$ ya da $1$ yazmak olarak görebiliriz. Mesela $n=6$ ve $k=3$ iken $\{1,3,5\}$ alt kümesini $101010$ dizisi olarak gösterebiliriz.

Bu yüzden soru şuna denktir: İçerisinde $k$ tane 1 olan ve hiçbir 1'in yanyana olmadığı kaç tane $n$ uzunlukta $0-1$ dizisi vardır?

Elimizde $n$ tane boş kutu var, bunlardan tam $k$ tanesine $1$ yazacağız. Yanyana iki kutuya $1$ yazamayacağımız için, her $1$'in yanında $0$ olmalı. Yani $1$'ler aslında tek başına değil, $10$ şeklinde bir ikili. Elimizde böyle $k$ tane ikili var, bunların herbirisi en sondaki kutu hariç iki kutuyu dolduracak. O yüzden bunları yerleştirecek toplam $n-k+1$ tane yer var. Demek ki bunları $\binom{n-k+1}{k}$ farklı şekilde seçebilirim.