İleri sayma: tekrarlı seçim, binom teoremi ve yineleme bağıntıları

Geçen hafta tekrar olmayan seçimleri saydık. Bu hafta tekrara izin veriyoruz, binom teoremini görüyoruz ve bir problemi yineleme bağıntısına (recurrence relation) çevirmeyi öğreniyoruz. Final konusu. Bir sonraki hafta (doğrusal yinelemeleri çözme) bunun devamı. Altın kurallar:

1. Dört kutulu tablo: sıra önemli mi, tekrar var mı? Dört formülden birini seç.
2. Tekrarlı kombinasyon = yıldız ve çubuk (stars and bars). $r$ yıldız, $n - 1$ çubuk.
3. Binom katsayısını bulurken içerideki sayıları ve işareti de üsse al.
4. Yineleme kurarken son adıma bak ve başlangıç koşullarını (initial conditions) mutlaka yaz.

Dört formül tablosu

$n$ türden $r$ tane seçiyorsun:

Örnek (sıra önemli, tekrar var): 26 harfle 5 uzunluklu kelime, harfler tekrar edebilir: $26^5 = 11881376$.

Tekrarlı kombinasyon: yıldız ve çubuk

Örnek. Fırında 4 tür poğaça var, 6 tane alacaksın. Her türden istediğin kadar alabilirsin, sıra önemsiz. Kaç farklı alışveriş?

Bir alışverişi 6 yıldız ve türleri ayıran 3 çubukla yaz:

**|*||***    ->  tur1: 2, tur2: 1, tur3: 0, tur4: 3
|******||    ->  tur1: 0, tur2: 6, tur3: 0, tur4: 0

Her alışveriş, 9 karakterlik dizide 3 çubuğun yerini seçmeye karşılık gelir (birebir eşleme, bijection):

$C(6 + 4 - 1, 3) = C(9, 3) = C(9, 6) = 84.$

Denklem çözümü sayma

$x_1 + x_2 + x_3 = 11$ denkleminin negatif olmayan tam sayı çözümleri: 11 yıldız, 2 çubuk, $C(13, 2) = 78$.

Her $x_i \ge 1$ olsun istenirse: önce her kutuya 1 koy, geriye 8 kalır. $y_1 + y_2 + y_3 = 8$, $C(10, 2) = 45$.

Aynı model: 8 özdeş topu 4 farklı kutuya dağıtmak $C(8 + 3, 3) = C(11, 3) = 165$ yol.

Bir örnek daha: 10 özdeş şekeri 3 çocuğa, her çocuk en az 2 alacak şekilde dağıt. Önce her çocuğa 2 ver ($3 \cdot 2 = 6$ şeker gitti), kalan 4 şeker serbest: $y_1 + y_2 + y_3 = 4$, $C(4 + 2, 2) = C(6, 2) = 15$ yol. Alt sınırlı her soru bu iki adımla biter: önce zorunlu payı dağıt, sonra kalanı yıldız-çubukla say.

TUZAK · nesne özdeş mi, farklı mı? Yıldız-çubuk sadece özdeş nesneler (aynı topa, aynı tür poğaçalar) için çalışır. 8 farklı topu 4 kutuya atıyorsan her top 4 kutudan birini seçer: $4^8$.

Tekrarlı harfli kelimeler

$n$ nesneden $n_1$ tanesi bir tür, $n_2$ tanesi başka tür, … ise farklı dizilişlerin sayısı

$\frac{n!}{n_1!\, n_2! \cdots n_k!}.$

BANANA: 6 harf, A üç kez, N iki kez, B bir kez. $\frac{6!}{3!\,2!\,1!} = \frac{720}{12} = 60$. Neden bölüyoruz? Üç A’nın kendi arasında yer değiştirmesi ($3!$) aynı kelimeyi verir, o tekrarları atıyoruz (bölme kuralı).

Binom teoremi (binomial theorem)

$(x + y)^n = \sum_{j=0}^{n} \binom{n}{j} x^{n-j} y^j.$

Sezgi: $(x+y)(x+y)\cdots(x+y)$ çarpımında her parantezden ya $x$ ya $y$ seçersin. $x^{n-j}y^j$ teriminin kaç kez çıktığı = $n$ parantezden $y$‘yi seçeceğin $j$ tanesini seçme sayısı = $\binom{n}{j}$.

Örnek: $(x + y)^4 = x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + y^4$. Katsayılar 1, 4, 6, 4, 1.

Çözümlü örnek. $(2x - y)^7$ açılımında $x^3y^4$ katsayısı.

Genel terim: C(7, j) (2x)^(7-j) (-y)^j
x^3 y^4 icin j = 4
C(7, 4) * 2^3 * (-1)^4 = 35 * 8 * 1 = 280

İki önemli sonuç:

$\sum_{k=0}^{n}\binom{n}{k} = 2^n \quad (x = y = 1), \qquad \sum_{k=0}^{n}(-1)^k\binom{n}{k} = 0 \quad (x = 1,\ y = -1,\ n \ge 1).$

Örnek: $\binom{5}{0} + \dots + \binom{5}{5} = 1 + 5 + 10 + 10 + 5 + 1 = 32 = 2^5$.

Pascal özdeşliği ve kombinatorik ispat

$\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k}.$

Kombinatorik ispat (combinatorial proof): iki tarafın da aynı şeyi saydığını göster.

Proof. Let S be a set with n + 1 elements and fix one element a in S.
The left side counts the k-element subsets of S.
Such a subset either contains a or does not.
- If it contains a, choose the other k - 1 elements from the
  remaining n elements: C(n, k-1) ways.
- If it does not contain a, choose all k elements from the
  remaining n elements: C(n, k) ways.
By the sum rule the total is C(n, k-1) + C(n, k). ∎

Kontrol: $\binom{6}{2} = 15$, $\binom{5}{1} + \binom{5}{2} = 5 + 10 = 15$. Pascal üçgeninde her sayı üstündeki iki sayının toplamıdır.

Permütasyon üretme: sözlük sırası

Sözlük sırasında (lexicographic order) $a_1 a_2 \dots a_n$‘den sonra gelen permütasyon:

1. Sağdan sola ilerle, $a_j < a_{j+1}$ olan ilk $j$‘yi bul.
2. $a_j$‘nin sağındakiler arasından $a_j$‘den büyük en küçük sayıyı bul, $a_j$ ile yer değiştir.
3. $j$ konumunun sağını artan sıraya diz.

362541
Sagdan: 4 > 1, 5 > 4, 2 < 5  ->  a_j = 2
2'nin sagi: 5 4 1, 2'den buyuk en kucuk = 4
Degistir: 364521
4'un sagini artan diz: 1 2 5  ->  364125

Yineleme bağıntıları (recurrence relations)

Yineleme bağıntısı, dizinin $a_n$ terimini önceki terimlerle ifade eder. Başlangıç koşulları olmadan dizi belirlenmez.

Örnek 1 (faiz). 1000 TL yıllık %5 faizle: $P_n = 1.05\,P_{n-1}$, $P_0 = 1000$. Üç yıl sonra $P_3 = 1000 \cdot 1.05^3 = 1157.625$.

Örnek 2 (Hanoi kuleleri, Tower of Hanoi). $n$ diski taşımak için: üstteki $n-1$ diski yardımcı çubuğa taşı ($H_{n-1}$), en büyüğü taşı (1), $n-1$ diski üstüne taşı ($H_{n-1}$):

$H_n = 2H_{n-1} + 1, \qquad H_1 = 1.$

İterasyonla $1, 3, 7, 15, 31, 63$: tahmin $H_n = 2^n - 1$. Tümevarımla ispatı (hafta 3’ün şablonu):

Claim. H_n = 2^n - 1 for all integers n >= 1.
Basis step. n = 1: H_1 = 1 and 2^1 - 1 = 1. True.
Inductive step. Assume H_k = 2^k - 1 for some k >= 1 (IH).
Then H_(k+1) = 2 H_k + 1 = 2(2^k - 1) + 1 = 2^(k+1) - 2 + 1 = 2^(k+1) - 1.
So the claim holds for k + 1.
By mathematical induction, H_n = 2^n - 1 for all n >= 1. ∎

Örnek 3 (bit dizileri). $a_n$: $n$ uzunluklu, iki ardışık 0 içermeyen bit dizilerinin sayısı. Son bite bak:

• Son bit 1: önü geçerli herhangi bir $n-1$ uzunluk dizi, $a_{n-1}$.
• Son bit 0: ondan önceki bit 1 olmak zorunda, önü geçerli $n-2$ uzunluk dizi, $a_{n-2}$.

$a_n = a_{n-1} + a_{n-2}, \qquad a_1 = 2,\ a_2 = 3.$

Değerler $2, 3, 5, 8, 13, 21$: Fibonacci dizisi kaydırılmış haliyle.

İPUCU · “son adıma bak” tarifi. Yineleme kurarken dizinin son elemanına (son bit, son taşınan disk, son basamak) göre durumlara ayır. Her durumda kalan kısım daha kısa bir aynı problemdir. Durumları topla.

Sık yapılan hatalar