Harflerin Sıralaması{Çözüldü}

[senior]

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ı.

[Ferhat GÖLBOL]

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

[senior]

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

[Lokman Gökçe]

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

[senior]

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.

[senior]

İ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.