Geomania.Org Forumları

Fantezi Cebir => Kombinatorik => Konuyu başlatan: senior - Temmuz 27, 2011, 11:49:10 ös

Başlık: Harflerin Sıralaması{Çözüldü}
Gönderen: senior - Temmuz 27, 2011, 11:49:10 ös

A,B,C ve D harflerinden oluşan
 - A ile başlayan ve D ile biten
 - A ve D harflerinin yanyana bulunmayacağı
 - ve herhangi aynı iki harfin yanyana bulunmayacağı kaç farklı 7 harfli kelime yazılabilir?

Soru 4 harf için sorulsa idi cevaplar ABCD, ACBD yani 2 tane olacaktı.

Başlık: Ynt: Harflerin Sıralaması
Gönderen: Ferhat GÖLBOL - Ağustos 06, 2011, 03:49:27 ös

Anlatmak çözmekten daha zor.
İnşallah anlatabilmişimdir...

Başlık: Ynt: Harflerin Sıralaması
Gönderen: senior - Ağustos 07, 2011, 12:03:29 öö

Ferhat, tebrikler. Soru aslında Graf Teori ile de yakından alakalı. Diğer çözümü de yolluyorum.

Başlık: Ynt: Harflerin Sıralaması
Gönderen: Lokman Gökçe - Ağustos 07, 2011, 12:06:24 öö

Matrisi nasıl oluşturduğunu biraz daha açabilir misin Güneş kardeşim. selamlar ... :)

Başlık: Ynt: Harflerin Sıralaması
Gönderen: senior - Ağustos 07, 2011, 12:23:21 öö

Tabi ki :)  Graflarda bitişiklik matrisi şöyle oluşturulur:
Eğer A'dan B'ye gidebiliyorsak matrisin A'dan sorumlu satırı ile B'den sorumlu kolonunun kesiştiği eleman 1 olur.
A'dan sorumlu satır  -> 1. satır
B'den sorumlu kolon -> 2.kolon
Matrisin 1.satır 2.kolonu A'dan B'ye gidebildiğimiz için 1'dir.

Başlık: Ynt: Harflerin Sıralaması
Gönderen: senior - Ağustos 09, 2011, 04:11:44 öö

İstek üzerine Mⁿ'in ne anlama geldiğini biraz açalım.

M, yani bitişiklik matrisi, noktalar arası bağlantıların varlığını gösterir.
Ör: 1.şehirden 2.şehire yol gidiyor(aynı zamanda 2'den de 1'e gitmektedir) ise M₁₂ = M₂₁ = 1'dir.
Bunu şöyle de yorumlayabiliriz: M_ij i ve j şehirleri arasında toplam yol uzunluğu 1 olan bütün yol kombinasyonlarının sayısıdır.

Şimdi, Tümevarım metodu kullanacağız. Mⁿ'nin i. satırı i'den diğer şehirlere toplam yol uzunluğu n olan farklı yolların sayısını göstersin. Bu matrisi M ile çarparsak, (Mⁿ⁺¹)_ij, Mⁿ'in i. satırı ile M'nin j.kolonunun çarpımıdır. Açık olarak aşağıdaki gibi yazılır:

(Mⁿ⁺¹)_ij = (Mⁿ)_i1 x M_1j + (Mⁿ)_i2 x M_2j + ... + (Mⁿ)_in x M_nj

Aslında bu yazılan şey de,
(Mⁿ⁺¹)_ij = i'den 1'e n uzunluğundaki yolların sayısı x 1'den j'ye 1 uzunluğundaki yolların sayısı +
... + i'den n'e n uzunluğundaki yolların sayısı x n'den j'ye 1 uzunluğundaki yolların sayısı 'dır.

Yani, (Mⁿ⁺¹)_ij'de i'den j'ye (n+1) uzunluğundaki yolların sayısı anlamına gelmektedir. n = 1 için zaten doğru olduğunu kanıtladık. Böylece ispat tamamlanmış olur.