← Bergeç Arşiv
The Art of Computer Programming serisi · 09.11.2025 · 3 dk okuma

Knuth'un Kitabından Bir Soru

Bölüm I — Vagon Sıralamaları ve Catalan Sayıları
Yazar: Yasin Aydın

Bu yazımızda, bilgisayar bilimi ile matematiğin buluştuğu ilginç bir soruyu ele alacağız.

Problem

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ı kaç farklı şekilde yeniden düzenlenebilir?1

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.

Örneğin n = 4 için şu işlemleri uygulayalım: (a) Vagon 1'i yığına taşı; (b) Vagon 2'yi yığına taşı; (c) Vagon 2'yi çıkışa taşı; (d) Vagon 3'ü yığına taşı; (e) Vagon 4'ü yığına taşı; (f) Vagon 4'ü çıkışa taşı; (g) Vagon 3'ü çıkışa taşı; (h) Vagon 1'i çıkışa taşı. Bu işlemlerin sonucunda, başlangıçtaki 1234 sıralaması 2431 olarak değişmiştir.

Çözüm

S, girişteki vagonu yığın bölgesine taşımayı, X ise yığın bölgesinden çıkışa taşımayı temsil etsin. Her tren yığına bir kere girecek ve bir kere de çıkacak. Bu yüzden problem, n tane S ve n tane X'ten oluşan bir karakter dizisi olarak tanımlanabilir. Toplam olası karakter dizisi sayısı:

$$\binom{2n}{n} = \frac{(2n)!}{n!\,n!}$$

Ancak bazı diziler anlamsızdır. Anlamlı dizilerde, baştan itibaren alınan her alt dizide S harfi sayısı X harfi sayısından fazla ya da eşit olmalıdır (vagon yığına sokulmadan çıkarılamaz). Bu anlamlı dizilerin her biri çıkıştaki başka bir sıralamaya karşılık gelir.

Şimdi ilk vagonu yığın bölgesine alalım. Bu durumda ya sıradaki vagon yığın bölgesine hareket eder ya da ilk vagon yığın bölgesinden çıkış bölgesine hareket eder. Yani diğer vagonların S-X karakterleri ilk vagona tekabül eden S-X karakterlerinin arasında bulunur ya da ilk vagonun S-X karakterlerinden sonra bulunur. A_n, n tane vagon için toplam olabilecek sıralama sayısı olsun.

Burada (n+1) tane vagonun ilkini kullandık. Geriye n tane vagon için S–X karakteri kaldı. Bu n tane trenin S–X karakterlerinin hepsi, ilk vagonun S–X karakterinin içinde olabilir. Buradan A_n A_0 tane sıralama gelir. n-1 tanesi içeride, 1 tanesi dışarıda olduğu durumda A_{n-1} A_1 tane sıralama gelir. k tane trenin içeride, (n-k) tane trenin dışarıda olduğu durumdan A_k A_{n-k} sıralama gelir. Böyle devam edersek, n > 0 için A_0 = 1 olmak üzere:

$$A_{n+1} = \sum_{i=0}^{n} A_i A_{n-i} \quad \text{ve} \quad A_0 = 1 \tag{1}$$

Bu, Catalan sayılarının özyinelemeli tanımıdır. Şimdi A_n için üreteç fonksiyonu yazalım:

$$F(x) = \sum_{n=0}^{\infty} A_n x^n = 1 + \sum_{n=1}^{\infty} A_n x^n = 1 + \sum_{n=0}^{\infty} A_{n+1} x^{n+1} \tag{2}$$

Denklem (1) kullanıldığında:

$$F(x) = 1 + \sum_{n=0}^{\infty} \left(A_0 A_n + A_1 A_{n-1} + \cdots + A_n A_0\right) x^{n+1} = 1 + x \sum_{n=0}^{\infty} \left(A_0 A_n + A_1 A_{n-1} + \cdots + A_n A_0\right) x^{n}$$

olur.

$$\sum_{n=0}^{\infty} \left(A_0 A_n + A_1 A_{n-1} + \cdots + A_n A_0\right) x^{n} = F(x)^2$$

Bu eşitliği F(x)'in karesini alarak doğrulayabilirsiniz.

$$F(x) = 1 + x F(x)^2$$

Bu ikinci dereceden denklemdir. Çözümü:

$$F(x) = \frac{1 \pm \sqrt{1-4x}}{2x}$$

F(0) = 1 koşulunu sağlayan kök:

$$F(x) = \frac{1 - \sqrt{1-4x}}{2x}$$

Şimdi Newton'un genelleştirilmiş binom teoremini kullanalım:2

$$(1+x)^{\alpha} = 1 + \frac{\alpha x}{1!} + \frac{\alpha(\alpha-1)x^2}{2!} + \cdots + \frac{\alpha(\alpha-1)\cdots(\alpha-n+1)x^n}{n!} + \cdots$$

\alpha = \tfrac{1}{2} için:

$$(1+x)^{1/2} = 1 + \sum_{n=1}^{\infty} \frac{\tfrac{1}{2}\left(\tfrac{1}{2}-1\right)\cdots\left(\tfrac{1}{2}-n+1\right)}{n!} x^n = 1 + \sum_{n=1}^{\infty} \frac{\tfrac{1}{2}\left(-\tfrac{1}{2}\right)\cdots\left(\tfrac{1}{2}-n+1\right)}{n!} x^n$$

Biraz daha düzenleyerek

$$\begin{aligned} (1+x)^{1/2} &= 1 + \sum_{n=1}^{\infty} (-1)^{n-1} \frac{1 \cdot 3 \cdot \cdots \cdot (2n-3)}{2^n\, n!} x^n \\ &= 1 + \sum_{n=1}^{\infty} (-1)^{n-1} \frac{1 \cdot 2 \cdot 3 \cdot \cdots \cdot (2n-2)}{2^n\, n! \cdot 2 \cdot 4 \cdot \cdots \cdot (2n-2)} x^n = 1 + \sum_{n=1}^{\infty} (-1)^{n-1} \frac{(2n-2)!}{2^n\, n! \cdot 2^{n-1}(n-1)!} x^n \\ &= 1 + \sum_{n=1}^{\infty} (-1)^{n-1} \frac{2(2n-2)!}{4^n\, n!\,(n-1)!} x^n = 1 + \sum_{n=0}^{\infty} (-1)^{n} \frac{2(2n)!}{4^{n+1}\,(n+1)!\,n!} x^{n+1} \end{aligned}$$

x yerine -4x yazarsak:

$$(1-4x)^{1/2} = 1 + \sum_{n=0}^{\infty} (-1)^{n} \cdot \frac{2(2n)!}{4^{n+1}\,(n+1)!\,n!} \cdot (-4x)^{n+1}$$

Dolayısıyla:

$$F(x) = \frac{1 - \sqrt{1-4x}}{2x} = \sum_{n=0}^{\infty} \frac{(2n)!}{(n+1)!\,n!} x^n$$

Yani:

$$A_n = \frac{(2n)!}{(n+1)!\,n!} = \frac{1}{n+1}\binom{2n}{n}$$

Bu sayılara Catalan Sayıları denir.

Kaynakça

  1. Işlak, Ü. Ayrık Matematikte Seçme Konular I. Nesin Yayınevi, 2022.
  2. Knuth, Donald E. The Art of Computer Programming, Vol. 1, 2nd ed., Addison-Wesley, 1973.
  3. Terzioğlu, T. Bir Analizcinin Defterinden Seçtikleri. 3rd ed., Nesin Yayınevi, 2019.

1. Bu problem Donald Knuth'un "The Art of Computer Programming" adlı eserinden alınmıştır.
2. Bu teoremin kanıtını Tosun Terzioğlu'nun "Bir Analizcinin Defterinden Seçtikleri" kitabından okuyabilirsiniz.

Okumaya devam

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

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

Konular: Kombinatorik

Bunları da okuyun

  1. Knuth’un Kitabından Bir Soru (III) · 05.10.2026
  2. Enigma Bölüm 1: Matematiksel Ön Hazırlık · 05.02.2026
  3. Mel’in Hikayesi · 18.11.2026

Yorumlar

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