Geomania.Org Forumları
Fantezi Cebir => Kombinatorik => Konuyu başlatan: Lokman Gökçe - Mart 03, 2012, 08:46:41 ös
-
n tane a ve n tane b harfimiz var. Öyle bir dizilim yapalım ki bu dizilimde seçilen herhangi bir harfin solundaki a ların sayısı daima > b lerin sayısı olsun. Bu şekilde kaç farklı dizilim yapılabilir? (Cevabı n türünden olmalı)
n = 2 durumu için örnek verelim:
aabb ve abab şeklinde 2 tane dizilim vardır.
abab istenen özelliğe sahiptir şöyle: abab dizisinde ilk sıradaki a harfi seçilirse bunun solunda 0 tane a ve 0 tane b vardır. abab dizisinde 2. sıradaki b harfi seçilirse bunun solunda 1 tane a, 0 tane b vardır. abab dizisinde 3 sıradaki a seçilirse bu harfin solunda 1 tane a, 1 tane b vardır. abab dizisindeki son b seçilirse bunun solunda 2 tane a, 1 tane b vardır. Daima a ların sayısı, b lerin sayısından büyük ya da b lerin sayısına eşit oldu.
-
Lokman hocam hemen koymuşsun soruyu:)
-
n x n biçiminde sol alt köşesi orijin olan bir kare düşünelim. A harfi x eksenine paralel (sağa doğru) bir birimlik hareketi, B harfi de y-eksenine paralel (yukarı doğru) bir birimlik hareketi gösterecek biçimde sol alt köşeden sağ üst köşeye birim karelerin kenarı üzerinden gidilebilecek en kısa yol sayısı ile harlerin dizilim sayısı eşittir.
İstediğimiz koşula uygun yolların, y=x+1 doğrusunun kare içinde kalan parçasını kesmemesi gerekir. Tersten düşünüp istenmeyen durumları sayalım:
y=x+1 doğrusunun kare içinde kalan parçası (n-1) x (n-1) lik karenin köşegenidir. Bu doğrunun kesebilmek için köşeleri (0,0), (0,1), (n-1,0) ve (n-1,n) olan dik yamuksal bölgede hareket edilmelidir.
Şimdi can alıcı yaklaşım geliyor. Bu bölgenin y = x + 1 doğrusuna göre simetrisini alalım. Böylece hareketlerin de simetrisini almış olacağız.
Elimizde (n+1) x (n-1) lik bir dikdörtgen oluşacaktır. Simetriden önceki hareketlerin başlangıç noktası (0,0) noktası, simetri sonrası (-1,1) noktası olacaktır. Böylece n + 1 sağ hareket (A harfi) ve n -1 yukarı hareket (B harfi) ile y = x+1 doğrusunu kesmek zorunda olan en kısa hareketler elde edilir.
O halde istenilen cevap C(2n,n) - C(2n,n-1) bulunur.
-
sen de hemen çözmüşsün soruyu Barış hocam. Olmaz ki ! :D
Lokman hocam hemen koymuşsun soruyu:)
-
n x n biçiminde sol alt köşesi orijin olan bir kare düşünelim. A harfi x eksenine paralel (sağa doğru) bir birimlik hareketi, B harfi de y-eksenine paralel (yukarı doğru) bir birimlik hareketi gösterecek biçimde sol alt köşeden sağ üst köşeye birim karelerin kenarı üzerinden gidilebilecek en kısa yol sayısı ile harlerin dizilim sayısı eşittir.
İstediğimiz koşula uygun yolların, y=x+1 doğrusunun kare içinde kalan parçasını kesmemesi gerekir. Tersten düşünüp istenmeyen durumları sayalım:
y=x+1 doğrusunun kare içinde kalan parçası (n-1) x (n-1) lik karenin köşegenidir. Bu doğrunun kesebilmek için köşeleri (0,0), (0,1), (n-1,0) ve (n-1,n) olan dik yamuksal bölgede hareket edilmelidir.
Şimdi can alıcı yaklaşım geliyor. Bu bölgenin y = x + 1 doğrusuna göre simetrisini alalım. Böylece hareketlerin de simetrisini almış olacağız.
Elimizde (n+1) x (n-1) lik bir dikdörtgen oluşacaktır. Simetriden önceki hareketlerin başlangıç noktası (0,0) noktası, simetri sonrası (-1,1) noktası olacaktır. Böylece n + 1 sağ hareket (A harfi) ve n -1 yukarı hareket (B harfi) ile y = x+1 doğrusunu kesmek zorunda olan en kısa hareketler elde edilir.
O halde istenilen cevap C(2n,n) - C(2n,n-1) bulunur.
Not: Elde ettiğimiz bu sayılara "Catalan Sayıları" denir.