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:
- Push: Giriş kısmının en önündeki vagonu yığın bölgesine hareket ettir.
- Pop: Yığının en önündeki vagonu çıkışa doğru hareket ettir.
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?
İ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,
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.
Ayrıca
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.
olur. (1)'den dolayı
Yani
olur. Şimdi (1)'deki yineleme bağıntısını kullanalım.
olur. Seri işlemleri yapmaya devam edelim.
olur. g_{n(-1)}=0 olduğundan ilk toplamda m'i 1'den başlatabiliriz. Yani
olur. Seri işlemleri yapmaya devam edelim.
(2) ve (3)'ten
olur. Biraz düzenlersek
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
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
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
olur. (8)'den ve (10)'dan
olduğu görülür. G(x,z)'yi hesaplamaya devam edelim. (7)'den
buluruz. r_1(z)r_2(z)=1 olduğundan
olarak buluruz. Şimdi geometrik seri açılımı yaparak
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
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.
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.
olur. Şimdi
k üzerine rasyonel fonksiyon olarak varsayıp kısmi kesirlerine ayıralım. Yani
şartını sağlayan A ve B'yi bulalım. Bu A ve B aşağıdaki gibidir:
eşitliğini yerine yerleştirelim.
Burada Genelleştirilmiş Convolution Teoremi'ni kullanacağız.
Önsav (Genelleştirilmiş Convolution Teoremi). n \in \mathbb{Z} olmak üzere
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.
(18)'i kullanalım.
Böylece teorem r+1 için kanıtlanmış oldu. ∎
Şimdi G(x,z)'ye geri dönelim.
kullanarak G(x,z)'yi bulalım.
eşitliğini yerine yazalım.
olarak bulunur. Yani
olur. n'i m ile m'i \frac{n-m}{2} ile değiştirisek
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.
olarak buluruz. Yani n tren m tanesi yığında kalacak şekilde ve giriş boş kalacak biçimde
şekilde çıkışta sıralanabilir.
Kaynakça
- Knuth, Donald E. The Art of Computer Programming, Vol. 1, 3rd ed., Addison-Wesley, 1997.
Yorumlar
Beğenmek ya da yorum yazmak için GitHub hesabıyla giriş yapmanız gerekir.