Permütasyon

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:


Burada dikkat edilmesi gereken nokta P = I olmadığı müddetçe P TL nin alt üçgensel yapıda olmayacağıdır.

Permütasyonun özellikleri ve örnekler:

Tanım : n elemanlı bir A kümesinin birbirinden farklı r, (r £ n) elemanının herbir sıralanışına A kümesinin r li bir permütasyonu denir. n = r olması durumunda sıralı n lilerin herbirine A kümesinin bir permütasyonu denir.
n elemanlı bir A kümesinin r li permütasyonlarının sayısı P(n , r) biçiminde gösterilir.

Teorem : P(n,r) = dir. [özel olarak P(n, n) = n! dir.]

Örnek: olur.

Örnek 2: dır.

Örnek 3: A={a, b, c} olduğuna göre, A nın 2 li permütasyonlarının sayısını bulunuz.

A nın 2 li permütasyonlarının sayısı 6 dır.Bunlar:
(a, b), (a, c), (b, a), (b, c), (c, a), (c, b) dir.

Teorem: E örnek uzayında iki olay ve A ve B olsun. A nın E ye göre tümleyeni A' olduğuna göre,

P(Ø) = 0
P Ì ise, P ( A )£ P( B )
P(A') =1-P( A )
P(AÈB) = P( A ) + P( B ) - P(A ÇB) dir.

Örnek :

Örnek: 5 farklı kitap, 5 kitap konabilen bir kaba kaç değişik biçimde dizlir?
5 5! 5!
P(5,5) = = = = 120 dir.

2. Faktöriyel kavramı:

n Î olmak üzere 1den n ye kadar doğal sayıların çapımına n faktöryel denir ve n! ile gösterilir.
n! ise
n! = n(n-1)(n-2)...1 dir.

0! = 1 , 1! = 1 dir n faktöryelini sorularda kullanabilmek için değişik yazılımlarınıda bilmek gerekir.

Örnek : 5! i değişik biçimlerde yazınız.
5! = 5.4.3.2.1 5! = 5.4.3.2!
5! = 5.4.3! 5! = 5.4!

Örnek : (n-1)! i değişik biçimlerde yazınız.
(n-1)! = (n-1)(n-2)(n-3)!
(n-1)! = (n-1)(n-2)! gibi

3. Genel çarpma kuralı:

Bir işlem a yoldan, bununla ilişkili başka bir işlemde b yoldan yapılabiliyorsa bu iki işlem birlikte a.b yoldan yapılabilir.

Örnek : A = {1,2,3,4,5,6,7} kümesinin alt elemanlarıyla kaç tane rakamları birbirinden farklı üç basamaklı 350 den büyük sayı yazılabilir?
İki tablo çizerek çözelim.
4 6 5
4 6 5
+

(4,5,6,7) (3) (5,6,7)

4. Olasılık:

Tanım : İhitmal, raslantı ya da kesin olmayan olaylarla uğraşır.Raslantı; sonucu önceden bilinmeyen, gerçekleşmesi şansa bağlı olan olaydır.Örneğin bir parayı havaya attığımızda yazı mı yoksa tura mı geleceğini deney yapmadan bilemeyiz.


Örnek :
Deney : Bir zarın havaya atılması.
Çıkanlar : 1, 2, 3, 4, 5, 6
Örnek Uzay : E={1,2,3,4,5,6}
A olayı : Zarın üst yüzüne 5 gelmesi.
B olayı : Zarın üst yüzüne 5 gelmemesi.
C olayı : Zarın üst yüzüne 3 gelmesi.
İmkansız Olay : Zarın üst yüzüne 7 gelmesi.
Kesin Olay : Zarın üst yüzüne 7’den küçük bir sayma sayısının gelmesi.
Zıt Olaylar : A ve B olayları
Ayrık Olaylar : A ve C olayları

Bir olayın ihtimali :

Evrensel kümeyi “E”, bir olayı “A” ve A olayının ihtimalinide P( A ) ile gösterirsek :

ile gösterilir.Diğer ihtimal hesaplarıda bu ifadeye dayanır.
Bir olayın ihtimali sıfır ile 1 arasında bir sayıdır. 0 ≤ P( A ) ≤ 1 dir
a. P( A ) = 0 ise A olayının gerçekleşmesi mümkün değil demektir.
b. P ( A ) = 1 ise A olayı kesinlikle gerçekleşecek demektir. (Bir zarın 7’den küçük bir sayma sayısının gelmesi.)
P ( A ) + PA´) = 1, yani bir olay olur veya olmaz demektir.Bu ifadeyi, P ( A ) = 1 - P(A´) şeklindede düşünebiliriz.
Örnek uzayda gerçekleştirilen olayların ihtimalleri toplamı 1 dir.
A1,A2,A3,..., An olayları için
P(A1) + P(A2) + P(A3) + ... + P(An) = 1 olur.

Örnek :
Hilesiz bir zar atıldığında, zarın 3 geme olasılığı nedir?
Çözüm :
Zar artıldığında örnek uzay : E={1,2,3,4,5,6}
Ve olay : A={3} dür.

P ( A ) = = olur.
S ( E ) 6

Örnek :
Hilesiz bir zar atıldığında üst yüze tek sayı gelme ihtimali kaçtır?
Çözüm :
Zarın atılmasındaki tüm durumların sayısı 6 dır.İstenilenler 1 veya 3 veya 5 olduğu için, istenilen durum sayısı 3 dür.

P(tek sayı gelme) = = olur.
2
Örnek : 3 para aynı anda masaya atılıyor.Üste gelen yüzlerinin;
a. en az ikisinin yazı gelmesi,
b. birinci paranın yazı gelmesi,
c. her üç paranın aynı olması ihtimali kaçtır?

Çözüm :
Üç paranın atılması deneyinde tüm çıkanların kümesi ,
E = {YYY,YYT,YTY,YTT,TYY,TTY,TYT,TTT} dir.

a. A olayı en az iki yazı gelme olayı A ise,
A={YYY,YYT,YTY,TYY} olur.
P ( A ) = 4 = 1

b. 1.paranın yazı gelmesi olayı B ise
B={YYY,YYT,YTY,YTT} dir.
P( B ) = 4 = 1 dir.

c. Her üç paranın aynı gelme olayı C ise C={YYY,TTT} olduğundan,
P( C ) = 2 = 1

Geçmiş yıllarda çıkmış sorular :

Soru 1: 1 ifadesi aşağıdakilerden hangisine eşittir? (1995 FL)

4! 1! 4! 3!
A) B) C) D)

Çözüm:
4! 4! 1!

Cevap : A

Soru 2: Bir kutudaki 20 kalemden 11’i sağlam, geri kalanıda kırıktır.Kutuya geri atmamak şartıyla arka arkaya çekilen iki kaleminde kırık olma olasılığı nedir? (1995 FL)

A) 9 B) 7 C) 11 D) 18

Çözüm :

20 kalemden 11’i sağlam 9’u kırıktır.
P ( A ) = s ( A ) ve çekilen kalemler kutuya geri atılmadığından;

Çekilen 1. kalemin kırık olma olasılığı 9 ,

Çekilen 2. kalemin kırık gelme olasılığı 8 dur.Buradan;

P ( A ) = 9 8 18
* = olur.
Cevap : D

Soru 3: Bir rafta 5 tane matematik, 2 tane edebiyat ve 3 tane tarih kitabı vardır.Aynı tür kitaplar birbirinden ayrılmamak üzere, kaç değişik şekilde yanyana sıralanabilir? (1996 FL)
A) 30 B)90 C)1440 D)8640

Çözüm :
Aynı tür kitaplar birbirinden ayrılamayacağından;
5 Matematik kitabı = 5! şeklinde
2 Edebiyat kitabı = 2! şeklinde
3 Tarih kitabı = 3! Şeklinde sıralanır.

MMMM EE TTT

Burada Matematik, Edebiyat ve Tarih kitapları birer kitap gibi düşünülür; böyle olunca; 3! Şeklinde de bunlar sıralanır. Öyleyse;

3! . (5! . 2! . 3!) = 8640 olur. Cevap : D

Soru 4: Bir torbada 6 kırmızı, 4 mavi, 5 yeşil top vardır.Torbadan rastgele çekilen 1 topun yeşil olmaması olasılığı kaçtır? (1997 FL)

A) 1 B) 1 C) 2 D) 3

Çözüm :
P ( A ) = s ( A ) ve P ( A ) + P(A’)

P ( Y ) = 5 = 1
P ( Y ) + P(Y’) = 1 olduğundan;

1
P(Y’) = 1 P(Y’) = 1- 1 = 2 olur. Cevap : C

Soru 5: n bir doğal sayı olmak üzere;

(n-1)! + n! + (n+1)! işleminin sonucu aşağıdakilerden hangisine eşittir? (1997 FL)


A) n+1 B) 2n C) n+1 D) n-1

Çözüm :
= (n-1)! + n . (n-1)! + (n+1) . n . (n-1)!

= (n-1)! [1 + n + (n + 1)! . n] = 1 + n + n + n

= n + 2n + 1 = (n + 1)

= n + 1 olur. Cevap : A

Soru 6: P(n;4) = 5P(n;3) ise, n’in değeri kaçtır? (1997 FL)

A) 3 B) 4 C) 8 D) 10

Çözüm :
n! = 5. n!

1! = 5 1 = 5

n-3 = 5 n = 8 olur. Cevap : C