← Bergeç Arşiv
The Art of Computer Programming serisi · 02.12.2025 · 6 dk okuma

Knuth'un Kitabından Bir Soru

Bölüm II — Yığında Kalan Vagonlar
Yazar: Yasin Aydın
Bilim, bir bilgisayara açıklayacak kadar iyi anladığımız şeydir; sanat ise geri kalan her şeydir. Donald Knuth

Geçen sayıdaki yazımızda Knuth'un The Art of Computer Programming adlı eserinden aldığımız bir soruyu tanıtmıştık ve çözüm üretmiştik. Bu yazımızda da o sorunun gelişmiş bir versiyonunu çözeceğiz.

Problem (II)

Bir demiryolu hattının giriş tarafında, soldan sağa doğru sıralanmış ve 1,2,3,4,\dots,n olarak numaralandırılmış n vagon bulunduğunu düşünelim. Vagonlar yalnızca belirtilen yönlerde hareket edebilir ve birbirlerinin üzerinden atlayamaz. Vagonların çıkışa taşınması stack (yığın) işlemleri kullanılarak gerçekleştirilir:

Bu işlemler sonucunda, 1,2,\dots,n sıralaması yığımda m \le n tane tren kalacak ve giriş bölgesinde hiç tren kalmayacak şekilde kaç farklı şekilde yeniden düzenlenebilir?

Giris ve cikis hatlariyla bir stack (yigin) bolgesini gosteren demiryolu semasi
Giris hatti (Input to stack) sagdan, cikis hatti (Output from stack) soldan bir yigin (Stack) bolgesine baglanir.

İlk soruda m=0 durumunu çözmüştük. Şimdi n=4 ve m=2 için örnek bir sıralama gösterelim. Sırasıyla şu işlemleri yapalım: (a) Vagon 1'i yığına taşı; (b) Vagon 1'i yığından çıkışa taşı; (c) Vagon 2'i yığına taşı; (d) Vagon 3'ü yığına taşı; (e) Vagon 3'ü yığından çıkışa taşı; (f) Vagon 4'ü yığına taşı. Bu işlemler sonucunda 1,2,3,4 vagonları 1,3 olur.

Çözüm

Bu soruyu Donald Knuth'un The Art of Computer Programming adlı eserinde yer alan bir methodla çözeceğiz. Bir önceki yazıda yaptığımız gibi herbir sıralamaya tekabül eden yığın işlemlerini bir string ile eşleyeceğiz. İlk yazıdan hatırlayacağınız üzere push için S ve pop için X harflerini kullanmıştık. Bu soruda da aynı yöntemi uygulayalım. Bu karakter dizisinde toplamda n tane S ve n-m tane X olmalıdır. Ayrıca karakter dizisinin herhangi bir başlangıç parçasında, S sayısı X sayısından büyük ya da eşit olmalıdır. Böyle karakter dizilerinin sayısı bize toplam durum sayısını verir.

Uzunluğu n ve toplam S harfinin sayısı ile X harfinin sayısının farkı m olan ve herhangi bir başlangıç parçasında, S sayısı X sayısından büyük ya da eşit olan karakter dizilerinin sayısı g_{nm} olsun. Bizim aradığımız stringdeki toplam karakter sayısı 2n-m olduğundan aradığımız cevap g_{(2n-m)m} olur. Önce g_{nm}'i bulalım. g_{nm}'i bulmak için öncelikle g_{nm} için bir yineleme bağıntısı bulacağız. Ardından çifte üreteç fonksiyonu kullanarak g_{nm}'in kapalı formülünü bulacağız.

Şimdi g_{(n+1)m}'e bakalım. g_{(n+1)m}, n+1 uzunluğunda ve S harfinin sayısı ile X harfinin farkı m olan karakter dizisi sayısını verir. Böyle karakter dizileri ya X ile biter ya da S ile biter. Buna uygun bir yineleme bağıntısı yazalım. Eğer son karakter X ise ilk n karakterden oluşan karakter dizisinde toplam S sayısındaki fark m+1 olur ve bu başlangıç dizisi gereken koşulu sağlar. Buradan g_{n(m+1)} durumu gelir. Eğer son karakter S ise ilk n karakterden oluşan karakter dizisinde toplam S sayısı ile toplam X sayısı arasındaki fark m-1 olur. Benzer şekilde bu başlangıç dizisi de gereken koşulu sağlar. Buradan da toplam g_{n(m-1)} durumu gelir. Yani,

$$g_{(n+1)m} = g_{n(m+1)} + g_{n(m-1)}, \quad m \ge 0,\ n \ge 0,\ g_{0m} = \delta_{0m} \qquad (1)$$

olur. Burada \delta_{0m} işareti Kronocker deltası olarak adlandırılır ve m=0 ise değeri 1, değilse değeri 0'dır. Dikkat ederseniz n-m çift sayı olmalı. Eğer n-m çift değilse g_{nm}=0 olur. Şimdi üreteç fonksiyonunu yazalım.

$$G(x,z) = \sum_{m=0}^{\infty}\sum_{n=0}^{\infty} g_{nm}z^n x^m \qquad (2)$$

Ayrıca

$$g(z) = G(0,z) \qquad (3)$$

olarak tanımlayalım. İleriki adımlarda g(z)'yi de kullanacağız. (1) ilişkisini kullanmak için birtakım seri işlemleri yapalım.

$$G(x,z) = \sum_{m=0}^{\infty} \left( g_{0m} + \sum_{n=1}^{\infty} g_{nm}z^n \right) x^m = \sum_{m=0}^{\infty} \left( g_{0m} + \sum_{n=0}^{\infty} g_{(n+1)m}z^{n+1} \right) x^m$$
$$= \sum_{m=0}^{\infty} g_{0m}x^m + \sum_{m=0}^{\infty}\sum_{n=0}^{\infty} g_{(n+1)m}z^{n+1}x^m$$

olur. (1)'den dolayı

$$\sum_{m=0}^{\infty} g_{0m}x^m = 1$$

Yani

$$G(x,z) = 1 + \sum_{m=0}^{\infty}\sum_{n=0}^{\infty} g_{(n+1)m}z^{n+1}x^m \qquad (4)$$

olur. Şimdi (1)'deki yineleme bağıntısını kullanalım.

$$G(x,z) = 1 + \sum_{m=0}^{\infty}\sum_{n=0}^{\infty} \left( g_{n(m-1)} + g_{n(m+1)} \right) z^{n+1}x^m \qquad (5)$$

olur. Seri işlemleri yapmaya devam edelim.

$$G(x,z) = 1 + z\left( \sum_{n=0}^{\infty}\sum_{m=0}^{\infty} \left( g_{n(m-1)} + g_{n(m+1)} \right) x^m z^n \right)$$
$$= 1 + z\left( \sum_{n=0}^{\infty}\sum_{m=0}^{\infty} g_{n(m-1)}z^n x^m + \sum_{n=0}^{\infty}\sum_{m=0}^{\infty} g_{n(m+1)}x^m z^n \right)$$

olur. g_{n(-1)}=0 olduğundan ilk toplamda m'i 1'den başlatabiliriz. Yani

$$G(x,z) = 1 + z\left( \sum_{n=0}^{\infty}\sum_{m=1}^{\infty} g_{n(m-1)}x^m z^n + \sum_{n=0}^{\infty}\sum_{m=0}^{\infty} g_{n(m+1)}x^m z^n \right)$$

olur. Seri işlemleri yapmaya devam edelim.

$$G(x,z) = 1 + z\left( \sum_{n=0}^{\infty}\sum_{m=1}^{\infty} g_{n(m-1)}x^m z^n + \sum_{n=0}^{\infty}\sum_{m=1}^{\infty} g_{nm}x^{m-1} z^n \right)$$
$$= 1 + z\left( \sum_{n=0}^{\infty}\sum_{m=0}^{\infty} g_{nm}x^{m+1} z^n + \sum_{n=0}^{\infty}\sum_{m=1}^{\infty} g_{nm}x^{m-1} z^n \right)$$
$$= 1 + z\left( x\sum_{n=0}^{\infty}\sum_{m=0}^{\infty} g_{nm}x^{m} z^n + \frac{1}{x}\sum_{n=0}^{\infty}\sum_{m=1}^{\infty} g_{nm}x^{m} z^n \right)$$
$$= 1 + z\left( x\sum_{n=0}^{\infty}\sum_{m=0}^{\infty} g_{nm}x^{m} z^n + \frac{1}{x}\left( \sum_{n=0}^{\infty}\sum_{m=0}^{\infty} g_{nm}x^{m} z^n + \sum_{n=0}^{\infty} g_{n0}z^n - \sum_{n=0}^{\infty} g_{n0}z^n \right) \right)$$
$$= 1 + z\left( x\sum_{n=0}^{\infty}\sum_{m=0}^{\infty} g_{nm}x^{m} z^n + \frac{1}{x}\left( \sum_{n=0}^{\infty}\sum_{m=0}^{\infty} g_{nm}x^{m} z^n - \sum_{n=0}^{\infty} g_{n0}z^n \right) \right)$$

(2) ve (3)'ten

$$G(x,z) = 1 + z\left[ xG(x,z) + \frac{1}{x}\left( G(x,z) - g(z) \right) \right] \qquad (6)$$

olur. Biraz düzenlersek

$$G(x,z) = \frac{zg(z)-x}{z(x^2+1)-x} \qquad (7)$$

olarak buluruz. Şimdi G(x,z)'nin paydasını z(1-r_1(z)x)(1-r_2(z)x) olacak şekilde çarpanlarına ayıralım. Bu durumda

$$r_1(z) = \frac{1}{2z}\left(1+\sqrt{1-4z^2}\right), \quad r_2(z) = \frac{1}{2z}\left(1-\sqrt{1-4z^2}\right) \qquad (8)$$

olarak buluruz. Dikkat edeceğiniz üzere r_1(z)+r_2(z) = \frac{1}{z} ve r_1(z)r_2(z) = 1. Şimdi g(z)=G(0,z)'yi bulalım. İlk yazımızda a_n = g_{(2n)0} için üreteç fonksiyonunu

$$A(z) = \sum_{n=0}^{\infty} a_n z^n = \frac{1}{2z}\left(1-\sqrt{1-4z}\right) = \sum_{n=0}^{\infty} g_{(2n)0}z^n \qquad (9)$$

olarak bulmuştuk. Bunu kullanarak g(z) fonksiyonunu bulacağız. Bilindiği üzere \forall k \in \mathbb{N} için g_{(2k+1)0}=0. (9)'daki eşitlikte z yerine z^2 yazarsak g(z)'yi bulmuş oluruz çünkü g(z)'nin tek sayı indeksli katsayıları 0. Yani

$$g(z) = A(z^2) = \frac{1}{2z^2}\left(1-\sqrt{1-4z^2}\right) \qquad (10)$$

olur. (8)'den ve (10)'dan

$$g(z) = \frac{r_2(z)}{z} \quad \text{ve} \quad r_2(z) = zg(z) \qquad (11)$$

olduğu görülür. G(x,z)'yi hesaplamaya devam edelim. (7)'den

$$G(x,z) = \frac{r_2(z)-x}{z(1-r_1(z)x)(1-r_2(z)x)}$$

buluruz. r_1(z)r_2(z)=1 olduğundan

$$G(x,z) = \frac{r_1(z)r_2(z)(r_2(z)-x)}{z(1-r_1(z)x)(1-r_2(z)x)}$$
$$= \frac{r_2(z)(1-r_1(z)x)}{z(1-r_1(z)x)(1-r_2(z)x)} \quad \text{gerekli sadeleştirmeleri yaparsak}$$
$$= \frac{r_2(z)}{z(1-r_2(z)x)}$$

olarak buluruz. Şimdi geometrik seri açılımı yaparak

$$G(x,z) = \sum_{n=0}^{\infty} (r_2(z))^{n+1}x^n z^{-1} \qquad (12)$$

olarak buluruz. r_2(z)'nin seri açılımını bulalım. Bir önceki yazımızdaki yaptığımız gibi genelleştirilmiş binom açılımı kullanacağız. Bazı ara işlemleri atlayarak

$$r_2(z) = \sum_{n=0}^{\infty} \frac{1}{2n+1}\binom{2n+1}{n}z^{2n+1} \qquad (13)$$

buluruz. Şimdi G(x,z)'yi bulmak için (r_2(z))^{n+1}'i hesaplamamız gerekiyor. Bunun için z^2 yerine \omega yazalım. r_2(z) = zf(\omega) olacak şekilde f(\omega) tanımlayalım. G(x,z)'yi bir kenara bırakıp bir süre f(\omega)'ya odaklanalım.

Tanım.
$$A_k(x,t) = \binom{x-kt}{k}\frac{x}{x-kt}, \quad x \neq kt \qquad (14)$$
şartını sağlayan n. dereceden bir polinom olarak tanımlansın. Gördüğünüz üzere
$$f(\omega) = \sum_{k=0}^{\infty} A_k(1,-2)\omega^k \qquad (15)$$
olur.
Teorem. r \in \mathbb{N} olmak üzere
$$(f(\omega))^r = \sum_{k=0}^{\infty} A_k(r,-2)\omega^k \qquad (16)$$
olur.
Kanıt.

r üzerine tümevarımla kanıtlayalım. f(\omega)'nın tanımından r=1 için doğru. Şimdi teoremin r için doğru olduğunu varsayıp r+1 için kanıtlayalım.

$$(f(\omega))^{r+1} = f(\omega)(f(\omega))^r = f(\omega)\sum_{k=0}^{\infty} A_k(r,-2)\omega^k$$
$$= \left(\sum_{k=0}^{\infty} A_k(1,-2)\omega^k\right)\left(\sum_{k=0}^{\infty} A_k(r,-2)\omega^k\right)$$
$$= \sum_{n=0}^{\infty}\sum_{k=0}^{n} A_k(1,-2)A_{n-k}(r,-2)\omega^n$$
$$= \sum_{n=0}^{\infty}\sum_{k=0}^{n} \binom{1+2k}{k}\binom{r+2(n-k)}{n-k} \frac{r}{(1+2k)(r+2(n-k))}\omega^n$$

olur. Şimdi

$$\frac{1}{(1+2k)(r+2(n-k))}$$

k üzerine rasyonel fonksiyon olarak varsayıp kısmi kesirlerine ayıralım. Yani

$$\frac{1}{(1+2k)(r+2(n-k))} = \frac{A}{1+2k} + \frac{B}{r+2(n-k)}$$

şartını sağlayan A ve B'yi bulalım. Bu A ve B aşağıdaki gibidir:

$$A = B = \frac{1}{1+r+2n}$$
$$\frac{1}{(1+2k)(r+2(n-k))} = \frac{1}{r+2n+1}\left(\frac{1}{1+2k} + \frac{1}{r+2(n-k)}\right)$$

eşitliğini yerine yerleştirelim.

$$(f(\omega))^{r+1} = \sum_{n=0}^{\infty} \frac{1}{1+r+2n}\sum_{k=0}^{n}\binom{1+2k}{k}\binom{r+2(n-k)}{n-k}\left(\frac{r}{1+2k}+\frac{r}{r+2(n-k)}\right)\omega^n \qquad (17)$$

Burada Genelleştirilmiş Convolution Teoremi'ni kullanacağız.

Önsav (Genelleştirilmiş Convolution Teoremi). n \in \mathbb{Z} olmak üzere

$$\sum_{k \ge 0} \binom{r-tk}{k}\binom{s-t(n-k)}{n-k}\frac{r}{r-tk} = \binom{r+s-tn}{n} \qquad (18)$$

eşitliği sağlanır.

Bu önsavı kanıtlamadan kullanacağız. Teoremimize geri dönelim. (17)'deki toplamı ikiye ayıralım ve ikinci toplamda k yerine n-k ve n-k yerine k yazalım. Bu işlem sonucu değiştirmez. Daha sonra önsavı kullanalım.

$$\sum_{n=0}^{\infty} \frac{1}{1+r+2n}\sum_{k=0}^{n}\binom{1+2k}{k}\binom{r+2(n-k)}{n-k}\left(\frac{r}{1+2k}+\frac{r}{r+2(n-k)}\right)\omega^n$$
$$= \sum_{n=0}^{\infty} \frac{r}{1+r+2n}\sum_{k=0}^{n}\binom{1+2k}{k}\binom{r+2(n-k)}{n-k}\frac{1}{1+2k}\omega^n$$
$$+ \sum_{n=0}^{\infty} \frac{1}{1+r+2n}\sum_{k=0}^{n}\binom{1+2k}{k}\binom{r+2(n-k)}{n-k}\frac{r}{r+2(n-k)}\omega^n$$

(18)'i kullanalım.

$$= \sum_{n=0}^{\infty}\left(\frac{r}{1+r+2n}\binom{1+r+2n}{n} + \frac{1}{1+r+2n}\binom{1+r+2n}{n}\right)\omega^n$$
$$= \sum_{n=0}^{\infty}\frac{r+1}{1+r+2n}\binom{r+2n+1}{n}\omega^n = \sum_{n=0}^{\infty} A_n(r+1,-2)\omega^n$$

Böylece teorem r+1 için kanıtlanmış oldu. ∎

Şimdi G(x,z)'ye geri dönelim.

$$G(x,z) = \sum_{n=0}^{\infty} (r_2(z))^{n+1}x^n z^{-1} \quad \text{ve} \quad r_2(z) = zf(z^2)$$

kullanarak G(x,z)'yi bulalım.

$$(f(z^2))^{n+1} = \sum_{m=0}^{\infty} A_m(n+1,-2)z^{2m}$$

eşitliğini yerine yazalım.

$$G(x,z) = \sum_{n=0}^{\infty}\sum_{m=0}^{\infty} A_m(n+1,-2)x^m z^{2m+n} = \sum_{n=0}^{\infty}\sum_{m=0}^{\infty} \binom{n+1+2m}{m}\frac{n+1}{n+1+2m}x^n z^{2m+n}$$

olarak bulunur. Yani

$$g_{(2m+n)n} = \binom{n+1+2m}{m}\frac{n+1}{n+1+2m} \qquad (19)$$

olur. n'i m ile m'i \frac{n-m}{2} ile değiştirisek

$$g_{nm} = \binom{n+1}{\frac{n-m}{2}}\frac{m+1}{n+1} \qquad (20)$$

olarak buluruz. Eğer n-m pozitif çift bir tam sayı değilse g_{nm}=0'dır. Şimdi aradığımız durum sayısı olan g_{(2n-m)m}'i hesaplayalım.

$$g_{(2n-m)m} = \binom{2n-m+1}{n-m}\frac{m+1}{2n-m+1} \qquad (21)$$

olarak buluruz. Yani n tren m tanesi yığında kalacak şekilde ve giriş boş kalacak biçimde

$$g_{(2n-m)m} = \binom{2n-m+1}{n-m}\frac{m+1}{2n-m+1} \qquad (22)$$

şekilde çıkışta sıralanabilir.

Kaynakça

  1. Knuth, Donald E. The Art of Computer Programming, Vol. 1, 3rd ed., Addison-Wesley, 1997.

Okumaya devam

Knuth’un Kitabından Bir Soru dizisi · 2 / 3

← Önceki: Knuth’un Kitabından Bir Soru (I)

Sonraki: Knuth’un Kitabından Bir Soru (III) →

Konular: Kombinatorik

Bunları da okuyun

  1. Enigma Bölüm 1: Matematiksel Ön Hazırlık · 05.02.2026
  2. Mel’in Hikayesi · 18.11.2026
  3. Enigma Bölüm 3: Enigmanın Çözülmesi · 07.02.2026

Yorumlar

Beğenmek ya da yorum yazmak için GitHub hesabıyla giriş yapmanız gerekir.