Permütasyon ve kombinasyon, sonlu bir topluluktaki nesneleri sıralama ve seçme problemlerini sistemli biçimde çözmeyi sağlar. Permütasyonda seçilen elemanların sırası sonucu değiştirirken kombinasyonda yalnız hangi elemanların seçildiği önemlidir.
Önceki Faktöriyel ve Sayma Yöntemleri yazısında saymanın toplama–çarpma kurallarını ve faktöriyeli inceledik. Bu permütasyon ve kombinasyon anlatımında aynı temel; sıralama, ekip seçme, tekrarlı diziliş ve geometrik sayma problemlerine uygulanacaktır. Sıradaki Olasılık konusu ise mümkün durumlar içinden istenen olayların oranını ele alacaktır.
PERMÜTASYON VE KOMBİNASYON ARASINDAKİ FARK
Önce Sıranın Sonucu Değiştirip Değiştirmediğini Belirleme
Bir problemde aynı elemanlar farklı sıraya yerleştirildiğinde yeni bir sonuç oluşuyorsa permütasyon kullanılır. Başkan ve başkan yardımcısı seçimi, yarış dereceleri, oturma düzeni ve şifre oluşturma bu gruptadır. Aynı elemanların hangi sırayla yazıldığı önem taşımıyorsa kombinasyon kullanılır. Ekip, komisyon, alt küme veya soru seçimi bu türdendir.
| Problem dili | Sıra önemli mi? | Temel yöntem |
|---|---|---|
| Dizme, sıralama, rol verme, derece belirleme | Evet | Permütasyon |
| Seçme, ekip kurma, alt küme oluşturma | Hayır | Kombinasyon |
| Önce seçip sonra görev dağıtma | İkinci aşamada evet | Kombinasyon * permütasyon |
PERMÜTASYONUN TANIMI VE P(n,r)
n Elemandan r Tanesini Seçip Sıralama
n farklı elemandan r tanesinin seçilip sıraya konmasına n’nin r’li permütasyonu denir. İlk yere n, ikinci yere n−1, sonraki yere n−2 seçenek kalır. Bu azalan çarpım faktöriyel yardımıyla P(n,r)=n!/(n−r)! biçiminde yazılır. Burada 0≤r≤n olmalıdır.
Örneğin 9 sporcudan ilk üç dereceyi belirlemek, üç kişilik bir grup seçmek değildir. Birinci, ikinci ve üçüncü dereceler farklı görevlerdir. Bu nedenle P(9,3)=9*8*7 kullanılır. Özel olarak P(n,0)=1, P(n,1)=n ve P(n,n)=n! olur.
B) 224
C) 280
D) 336
E) 420
DÜZ BİR SIRADA TAM SIRALAMA VE BLOK YÖNTEMİ
Birlikte Durması Gereken Elemanları Tek Blok Kabul Etme
n farklı elemanın düz bir sıradaki bütün sıralamaları n! tanedir. Belirli elemanların yan yana bulunması isteniyorsa bu elemanlar önce tek bir blok gibi düşünülür. Blok, diğer elemanlarla birlikte sıralandıktan sonra blok içindeki elemanların kendi sıralamaları ayrıca çarpılır.
Örneğin 7 farklı kitap içinde belirli 3 kitabın yan yana olması istenirse üç kitap bir blok kabul edilir. Blokla birlikte toplam 5 birim 5! biçimde sıralanır; blok içi sıralama 3! olduğundan sonuç 5!*3! olur. İki ayrı grubun kendi içinde yan yana olması durumunda her grup bir bloktur ve her blok içi sıralama ayrı çarpandır.
B) 960
C) 1.200
D) 1.440
E) 2.880
YAN YANA OLMAMA, GÖRECELİ SIRA VE BOŞLUK YÖNTEMİ
Yasak Durumu Tüm Sıralamalardan Çıkarma
Belirli iki kişinin yan yana olmaması isteniyorsa en güvenli yöntem, bütün sıralamalardan bu iki kişinin yan yana olduğu sıralamaları çıkarmaktır. n kişide bütün sıralama n!, belirli iki kişinin yan yana olduğu sıralama ise 2*(n−1)! olduğundan sonuç n!−2*(n−1)! olur.
Bir grubun elemanları birbirine komşu olmamalıysa boşluk yöntemi kullanılır. Önce diğer grup sıralanır; oluşan baş, ara ve son boşluklara ikinci grubun elemanları yerleştirilir. “A, B’nin sağında olsun” gibi yalnız göreceli sıra veren koşullarda ise her A–B sıralamasının bir de B–A karşılığı olduğundan bütün sıralamaların yarısı alınır. “A, B’nin hemen sağında” koşulu ise sabit sıralı bir blok oluşturur.
B) 420
C) 480
D) 540
E) 600
DAİRESEL PERMÜTASYON
Dönmeyle Aynı Kalan Oturuşları Bir Kez Sayma
n farklı kişi yuvarlak bir masa çevresine oturduğunda yalnız dönme yönünden aynı olan düzenler tek sonuç kabul edilir. Bir kişinin yeri sabitlenirse kalan n−1 kişi düz bir sıra gibi yerleştirilebilir. Bu nedenle dairesel permütasyon sayısı (n−1)! olur.
Yuvarlak masa ile kolye veya bileklik soruları aynı değildir. Masada saat yönü ve saat yönünün tersi genellikle farklı oturuşlardır; yalnız dönmeler özdeştir. Kolye ve bileklikte şekil ters çevrilebildiği için yansıyan dizilişler de aynı kabul edilebilir ve koşula göre ikiye bölme gerekebilir. Sorunun nesnesi ve “aynı sayılma” açıklaması mutlaka okunmalıdır.
B) 240
C) 360
D) 720
E) 5.040
TEKRARLI PERMÜTASYON
Özdeş Elemanların Yer Değiştirmesinden Doğan Tekrarları Bölme
Toplam n elemanın içinde aynı türden n₁, n₂, …, nₖ tane özdeş eleman bulunuyorsa bütün elemanlar farklıymış gibi hesaplanan n! değeri, özdeş elemanların kendi aralarındaki sıralama sayısına bölünür:
n!/(n₁!*n₂!*…*nₖ!)
Kelime harflerinin yer değiştirmesi, aynı renkli boncukların sıralanması ve rakamları tekrarlı bir sayının basamaklarının değiştirilmesi bu yöntemin yaygın örnekleridir. Rakam sorusunda sıfır varsa önce bütün dizilişler bulunup başında sıfır olan geçersiz dizilişler çıkarılmalıdır.
| Durum | Toplam eleman | Bölünecek tekrarlar |
|---|---|---|
| ANKARA harfleri | 6 | A harfi için 3! |
| 112233 rakamları | 6 | 2!*2!*2! |
| 4 kırmızı, 3 mavi boncuk | 7 | 4!*3! |
B) 90
C) 120
D) 180
E) 360
EN KISA YOL VE IZGARA PROBLEMLERİ
Aynı Yöndeki Adımları Özdeş Elemanlar Gibi Sayma
Izgara üzerinde yalnız sağa ve yukarı gidilerek en kısa yol izlenecekse bütün yollar aynı sayıda yatay ve düşey adımdan oluşur. Örneğin 5 sağ ve 3 yukarı adım gereken bir yol, beş S ve üç Y harfinin farklı dizilişleri gibidir. Sonuç 8!/(5!*3!) olur.
Belirli bir noktadan geçme koşulunda yol iki parçaya ayrılır ve her parçanın yol sayısı çarpılır. Belirli bir noktadan geçmeme koşulunda ise bütün en kısa yolların sayısından o noktadan geçen yollar çıkarılır. Geri dönüşe veya farklı yönlere izin verilmesi, en kısa yol modelini değiştirebilir; yön kısıtları çizim üzerinden kontrol edilmelidir.
B) 40
C) 48
D) 56
E) 64
KOMBİNASYONUN TANIMI VE TEMEL ÖZELLİKLERİ
n Elemandan Sırasız r Eleman Seçme
n farklı elemandan r tanesinin sırasız seçimine kombinasyon denir. Her r elemanlı seçim kendi içinde r! farklı sıraya sahip olduğundan permütasyon bu değere bölünür:
C(n,r)=n!/[r!*(n−r)!]=P(n,r)/r!
Tamamlayıcı seçim özelliği C(n,r)=C(n,n−r) biçimindedir. Çünkü r elemanı seçmek, geride bırakılacak n−r elemanı belirlemekle aynı sonucu verir. Ayrıca C(n,0)=C(n,n)=1, C(n,1)=n ve bütün alt kümelerin sayısı 2ⁿ olur.
B) 72
C) 84
D) 96
E) 108
ZORUNLU VE YASAK ELEMANLI SEÇİMLER
Koşulu Önce Uygulayıp Kalan Seçimi Yapma
Bir ekipte bulunması zorunlu kişiler önce seçilmiş kabul edilir. Toplam r kişilik ekipte k kişi zorunluysa geriye r−k kişilik seçim kalır. Bulunmaması gereken kişiler ise başlangıçtaki aday havuzundan çıkarılır. “A bulunur, B bulunmaz” koşulunda A sabitlenir, B havuzdan silinir ve kalan yerler uygun kişilerden seçilir.
Önce ekip seçilip sonra ekip içinden lider veya görevli belirlenecekse iki aşama vardır. Örneğin n kişiden r kişilik ekip ve bu ekipten bir lider seçimi C(n,r)*r biçimindedir. Aynı sonuç önce lideri seçip ardından kalan n−1 kişiden r−1 ekip üyesi seçilerek de bulunabilir.
B) 70
C) 84
D) 105
E) 126
EN AZ, EN ÇOK VE TAM OLARAK KOŞULLARI
Birbirini Dışlayan Durumları Ayırıp Sonuçları Toplama
“Tam olarak” koşulu tek bir seçim dağılımı verir. “En az” ve “en çok” koşullarında ise uygun bütün durumlar ayrı ayrı hesaplanıp toplanır. Örneğin 4 kişilik bir ekipte en az 2 kadın isteniyorsa 2 kadın–2 erkek, 3 kadın–1 erkek ve 4 kadın–0 erkek durumları birbirini dışlayan üç ayrı seçenektir.
Bazen tamamlayıcı durum daha kısadır. En az bir belirli tür isteniyorsa bütün ekiplerden o türden hiç bulunmayan ekipler çıkarılabilir. Hangi yöntemin daha kısa olduğu, uygun durum sayısına göre belirlenir; farklı durumların kesişmediğinden emin olunmalıdır.
B) 95
C) 100
D) 105
E) 110
KOMBİNASYONUN GEOMETRİK UYGULAMALARI
Nokta ve Doğru Seçimlerini Şeklin Koşullarına Göre Sayma
Herhangi üçü doğrusal olmayan n noktadan iki nokta seçilerek C(n,2) doğru, üç nokta seçilerek C(n,3) üçgen oluşturulur. Aynı biçimde dört nokta dörtgeni, beş nokta beşgeni belirler. Çember üzerindeki n noktadan seçilen üç nokta bir üçgen, dört nokta bir dörtgen oluşturur.
Doğrusal noktalar varsa her üçlü üçgen oluşturmaz. Önce bütün üçlüler sayılır, sonra aynı doğru üzerindeki üçlüler çıkarılır. Birbirine paralel doğru ailelerinden oluşan şekillerde paralelkenar seçmek için her aileden ikişer doğru seçilir; p ve q doğruluk iki ailede sonuç C(p,2)*C(q,2) olur. Dikdörtgen ızgarada da yatay doğrulardan iki, düşey doğrulardan iki seçim yapılır.
| Geometrik nesne | Seçim | Temel sayı |
|---|---|---|
| Doğru | İki nokta | C(n,2) |
| Üçgen | Doğrusal olmayan üç nokta | C(n,3) |
| Paralelkenar | İki paralel doğru ailesinden ikişer doğru | C(p,2)*C(q,2) |
B) 76
C) 80
D) 84
E) 88
PERMÜTASYON VE KOMBİNASYON TEMEL NOKTALAR
- Aynı elemanlar farklı sıraya geçtiğinde yeni sonuç oluşup oluşmadığını belirlemek gerekir.
- Sıralama varsa P(n,r), yalnız seçim varsa C(n,r) kullanılır.
- Tam sıralamada P(n,n)=n! olduğunu hatırlamak gerekir.
- Yan yana olma koşulunda elemanları blok kabul edin ve blok içini ayrıca sıralamak gerekir.
- Yan yana olmama koşulunda tüm durumlardan yasak durumları çıkarmayı değerlendirmek gerekir.
- Yuvarlak masa için dönmeyle aynı düzenleri bir kez sayarak (n−1)! kullanılır.
- Özdeş elemanlarda tekrar sayıları faktöriyellerine bölün.
- Izgara yollarında aynı yönlü adımları özdeş elemanlar gibi düşünmek gerekir.
- Zorunlu kişileri sabitlemek gerekir, yasak kişileri aday havuzundan çıkarmak gerekir.
- En az ve en çok koşullarında bütün uygun dağılımları ayrı durumlara ayrılır.
- Geometrik seçimlerde doğrusal veya paralel olma kısıtlarını ayrıca kontrol edilir.
Bu permütasyon ve kombinasyon kuralları, bir problemin önce “sıralama mı, seçim mi?” sorusuyla sınıflandırılmasını sağlar.