permütasyon

permütasyon


.A. FAKTÖRİYEL1 den n ye kadar olan sayma sayılarının çarpımına n faktöriyel denir ve n! biçiminde gösterilir.0! = 1 olarak tanımlanır.1! = 12! = 1 . 2 = 23! = 1 . 2 . 3 = 64! = 1 . 2 . 3 . 4 = 245! = 1 . 2 . 3 . 4 . 5 = 1206! = 1 . 2 . 3 . 4 . 5 . 6 = 720...................................................n! = 1 . 2 . 3 . ... . (n – 1) . n* · 5! = 5 . 4 . 3! 5! = 5 . 4! şeklinde de yazılabilir.· n! = n . (n – 1) . (n – 2)! n! = n . (n – 1)! şeklinde de yazılabilir.· (3n – 1)! = (3n – 1) . (3n – 2)! (3n – 1)! = (3n – 1) . (3n – 2) . (3n – 3)! şeklinde de yazılabilir.* * B. GENEL ÇARPMA KURALIİki işlemden birincisi m yolla yapılabiliyorsa ve ilk işlem bu m yoldan birisiyle yapıldıktan sonra ikinci işlem n yolla yapılabiliyorsa bu iki işlem birlikte m . n yolla yapılabilir.* * Örnek 1**A şehrinden B şehrine 4 farklı yol ve B şehrinden C şehrine 5 farklı yol vardır. B şehrine uğramak koşuluyla, A şehrinden C şehrine kaç değişik yolla gidilebilir?*A) 10******************* B) 12******************* C) 15******************* D) 20* ÇözümA şehrinden B şehrine gidiş 4 farklı yolla ve B şehrinden C şehrine gidiş 5 farklı yolla yapılabileceği için; A şehrinden C şehrine gidiş 4 . 5 = 20farklı yolla yapılabilir.Cevap D***C. PERMÜTASYON (SIRALAMA)1. Tanımr ve n sayma sayısı ve r £ n olmak üzere, n elemanlı bir kümenin r elemanlı sıralı r lilerine bu kümenin r li permütasyonları denir.n elemanlı kümenin r li permütasyonlarının sayısı :dır. Biz formülün sadeleştirilmiş halini kullanacağız.**Örnek 2*· P(n, n) = n! · P(n, 1) = n· P(n, n – 1) = n! dir.**D. ÇEMBERSEL (DÖNEL) PERMÜTASYONn tane farklı elemanın dönel (dairesel) sıralanmasına, n elemanın dairesel sıralaması denir.n elemanın dairesel sıralamalarının sayısı :(n – 1)! dir. PERMUTASYON MATRİSLERİGauss eliminasyonu yaparken bazı satır veya sütun takasları yapmamız gerekebilmektedir. Yaptığımız takas işlemlerini matris türünden ifade etmek istersek bunu bize permütasyon matrisleri sağlayacaktır. Satır veya sütun takaslarını göstermek için kullandığımız permütasyonlara takas permütasyonları adını vereceğiz.Bir n x n permütasyon matrisi, satırları farklı şekilde düzenlenmiş birim matristen ibarettir. Böyle bir matrisin her satırında ve her sütununda sıfırdan farklı bir eleman olacaktır ve bu elemanların da tümü “1” dir. Ancak böyle bir permütasyon matrisini bilgi işlem sistemimizde açık matris ifadesi olarak saklamak yerine, k = 1,...,n , ‘1’ in hangi sütunda bulunduğunu gösteren sütun indisi olmak üzere, p(k) olarak göstermek daha uygun olacaktır. (Aynı şekilde k, ‘1’ in satır indisi olarak ta alınabilir)Örnek:P , 3 x 3 ‘lük bir permütasyon matrisidir. Herhangi bir 3 x 3 ‘lük A matrisini soldan P matrisi ile çarpmak A’nın 2 ve 3’üncü satırlarını takas etmek anlamına gelecektir:A matrisini sağdan P ile çarpmak ta aynı sonucu verecektir. Permütasyon matrislerinin Gauss Eliminasyonu ile ilgili iki yararlı özelliği mevcuttur:1. Eğer k1 , ..., kn 1’den n’e kadar olan tamsayıların permütasyonu ve permütasyon matrisi P = ( pij ) ‘de olarak tanımlanmış ise PA, A matrisinin satırlarını permüte eder, yani şöyle bir matris elde ederiz:2. Eğer P bir permütasyon matrisi ise P -1 mevcuttur ve P -1 = P T gerçeklenir. Gauss eliminasyonu için gerekli olan satır takaslarını önceden bildiğimiz takdirde, başta elimizde bulunan denklemleri satır takası gerekmeyecek sırada yazmamız mümkündür. Yani sistemdeki denklemlerin satır takası olmaksızın Gauss eliminasyonu yapılabilecek bir sıralanışı mevcuttur. Bu da herhangi bir singular olmayan A matrisi için,olacak biçimde bir P permütasyonunun varlığını gerektirir. PA matrisi de, PA = LUşeklinde faktorize edilebildiğinden dolayı P -1 = P T özelliğini kullanarak şu sonuca varabiliriz:A = P –1LU = (P TL )UBurada dikkat edilmesi gereken nokta P = I olmadığı müddetçe P TL nin alt üçgensel yapıda olmayacağıdır.