Tekrarlı ve dairesel permütasyon

DEDE kelimesinin harflerini kaç farklı biçimde sıralayabiliriz? Dört harf olduğu için ilk akla gelen cevap 4! = 24'tür. Ama harfleri tek tek yazınca bir tuhaflık görülür: iki D'nin ve iki E'nin yerlerini değiştirmek yeni bir kelime üretmez. "DEDE" yazılışı, D'leri kendi aralarında ve E'leri kendi aralarında yer değiştirdiğimiz dört dizilişin hepsinde aynı görünür. Bu yüzden gerçek sayı 24/4 = 6'dır: DDEE, DEDE, DEED, EDDE, EDED ve EEDD. Benzer bir durum yuvarlak masada da yaşanır. Dört arkadaş bir masanın etrafına oturduğunda herkes bir koltuk sağa kaysa kimsenin komşusu değişmez; bu oturuşlar aynı sayılır. Bir önceki derste farklı nesneleri bir sıraya dizdik. Bu derste aynı nesnelerin bulunduğu sıralamaları, yani tekrarlı permütasyonu, bir ızgarada en kısa yolların sayısını ve bir çember etrafındaki sıralamaları, yani dairesel permütasyonu işliyoruz.

• Aynı nesneler içeren dizilişlerin sayısını n!/(n₁! · n₂! · …) formülüyle bulursun.
• Kelime ve rakam problemlerinde tekrarlı permütasyonu uygular, sıfırın başa gelmediği durumları ayırırsın.
• Izgarada yalnızca sağa ve yukarı gidilen en kısa yolların sayısını tekrarlı permütasyonla hesaplarsın.
• Yuvarlak masa ve anahtarlık problemlerinde dairesel permütasyonu, yan yana olma ve dönüşümlü oturma koşullarıyla birlikte kullanırsın.

Tekrarlı permütasyon

n nesnenin n₁ tanesi aynı türden, n₂ tanesi başka bir aynı türden ve böyle devam ediyorsa farklı dizilişlerin sayısı n!/(n₁! · n₂! · …)'dir. Formülün mantığı kancadaki gibidir: nesneler farklıymış gibi n! diziliş sayılır, sonra aynı nesnelerin kendi aralarındaki yer değiştirmeleri yeni diziliş üretmediği için her grubun faktöriyeline bölünür. Bir kez görünen nesneler için bölen 1! = 1 olduğundan onlar formülde yazılmaz.

ANNE kelimesinde dört harf vardır ve iki N aynıdır; farklı dizilişler 4!/2! = 12'dir. Formülü uygularken ilk iş harfleri saymak ve her harfin kaç kez geçtiğini bir liste hâlinde yazmaktır. Türkçe kelimelerde büyük İ ile I'nın, Ö ile O'nun farklı harfler olduğunu unutmamak gerekir.

Rakam problemleri

Aynı rakamlar içeren rakam kümeleriyle sayı yazılırken de tekrarlı permütasyon kullanılır. Kümede 0 varsa, 0'ın başa geldiği dizilişler sayı belirtmez; bu dizilişler ayrıca sayılıp toplamdan çıkarılır. 0 başa sabitlendiğinde kalan rakamların tekrarlı permütasyonu, çıkarılacak miktarı verir. Sayının belirli bir rakamla başlaması ya da bitmesi isteniyorsa o rakam yerine konur ve kalan rakamların tekrarlı permütasyonu sayılır.

Izgarada en kısa yollar

Bir ızgara üzerinde A noktasından B noktasına yalnızca sağa ve yukarı giderek ulaşmak isteyen biri, örneğin 2 adım sağa ve 2 adım yukarı gitmek zorundaysa, her yol bu dört adımın bir sıralamasıdır: SSYY, SYSY ve benzerleri. Bu, iki S ve iki Y harfinin tekrarlı permütasyonudur: 4!/(2! · 2!) = 6. Genel olarak m adım sağa ve n adım yukarı gidilen en kısa yolların sayısı (m + n)!/(m! · n!)'dir. Yol belirli bir ara noktadan geçmek zorundaysa yolculuk iki parçaya ayrılır ve parçaların yol sayıları çarpılır. Belirli bir noktadan geçmemesi isteniyorsa tümleyen kullanılır: bütün yollardan o noktadan geçenler çıkarılır. Izgara sorularında önce kaç adım sağa, kaç adım yukarı gidilmesi gerektiğini saymak, formülü doğru kurmanın tek ön koşuludur.

Dairesel permütasyon

n farklı nesne bir çemberin etrafına dizildiğinde, bütün nesnelerin aynı yöne kaydırıldığı dizilişler birbirinden ayırt edilemez. Bu yüzden bir nesnenin yeri sabit kabul edilir ve kalan n − 1 nesne sıralanır: dairesel permütasyon sayısı (n − 1)!'dir. 4 kişi yuvarlak bir masaya 3! = 6 farklı biçimde oturur. Bunu görmek için masadaki bir kişiyi referans alıp diğerlerinin ona göre nerede oturduğuna bakmak yeterlidir.

Yuvarlak masada iki arkadaşın komşu oturması isteniyorsa bu ikiliye tek bir koltuk grubu gibi davranılır. Blok ve diğer kişiler çember etrafına dizilir, sonra bloğun içi sıralanır. 4 kişiden iki belirli kişinin yan yana olduğu oturuşlar (3 − 1)! · 2! = 4'tür. Yan yana olmamaları istendiğinde tümleyen kullanılır. Kızlar ve erkekler gibi iki grubun dönüşümlü oturması isteniyorsa önce bir grup çember etrafına oturtulur, sonra öteki grup aradaki boşluklara sıralanır; boşluklar artık birbirinden ayırt edilebilir olduğu için ikinci grup düz sıralama gibi sayılır.

Anahtarlık ve bilezik

Anahtarlık, bilezik ya da kolye gibi ters çevrilebilen nesnelerde bir dizilişin ayna görüntüsü de aynı nesne sayılır. Saat yönünde okunan bir diziliş ters çevrilince saat yönünün tersine okunur ve ikisi ayırt edilemez. Bu yüzden dairesel permütasyon bir kez daha ikiye bölünür: (n − 1)!/2. 4 anahtarlık bir halka 3!/2 = 3 farklı biçimde dizilir. Bu kural yalnızca nesnenin ters çevrilebildiği durumlarda geçerlidir; yuvarlak masadaki kişiler için uygulanmaz, çünkü masa ters çevrilemez.

Neden bölüyoruz?

Tekrarlı ve dairesel permütasyonun ortak fikri, fazla sayılan durumları bölerek ayıklamaktır. Önce bütün nesneler farklıymış ya da bütün koltuklar numaralıymış gibi sayılır. Ardından aynı görünen dizilişlerin kaç kez sayıldığı bulunur ve toplam bu sayıya bölünür. Tekrarlı permütasyonda her diziliş, aynı nesnelerin kendi aralarındaki yer değiştirme sayısı kadar tekrarlanmıştır. Dairesel permütasyonda her oturuş, n farklı dönme ile n kez sayılmıştır; n!'in n'ye bölünmesi (n − 1)!'i verir. Bilezikte buna bir de ters çevirme eklenir ve bölen 2n olur. Bu bakış açısı, formülleri ezberlemek yerine her yeni durumda neye bölüneceğini kendin bulmanı sağlar.

Yuvarlak masada koşullar

Yuvarlak masa sorularında koşullar düz sıralamadakine benzer biçimde ele alınır, tek fark çemberde bir başlangıç noktasının olmamasıdır. Belirli bir kişinin belirli bir koltuğa oturması istendiğinde masa artık simetrik değildir; o kişi yerine konur ve kalanlar düz sıra gibi dizilir. İki kişinin karşılıklı oturması istendiğinde biri oturtulur, öteki tam karşısındaki koltuğa yerleşir ve kalanlar sıralanır. Bu tür koşullar çember simetrisini bozduğu için (n − 1)! formülü doğrudan uygulanmaz; önce sabitlenen kişiler yerleştirilir. Örneğin altı kişilik bir masada iki kişinin karşılıklı oturması istendiğinde biri oturtulunca ötekinin yeri belirlenir ve kalan dört kişi 4! biçimde dizilir.

Soru kökleri

Bu dersin problemleri aynı harfler içeren kelimelerin diziliş sayısını, tekrarlı rakamlarla yazılabilen sayıları, ızgaradaki en kısa yolları, yuvarlak masa oturuşlarını, yan yana olma ve dönüşümlü oturma koşullarını ve anahtarlık ya da bilezik dizilişlerini ister.

Örnek 1 — Tekrarlı harfler

Soru: SEPETE kelimesinin harfleri kaç farklı biçimde sıralanabilir?

• A) 720
• B) 360
• C) 120
• D) 240
• E) 60

Çözüm: Altı harften üçü E'dir; 6!/3! = 120. Cevap: C.

Örnek 2 — Yuvarlak masa

Soru: 8 kişi yuvarlak bir masaya kaç farklı biçimde oturabilir?

• A) 40320
• B) 2520
• C) 720
• D) 5040
• E) 8

Çözüm: Bir kişinin yeri sabitlenir; kalan 7 kişi 7! = 5040 biçimde oturur. Cevap: D.

Örnek 3 — Izgara

Soru: Bir ızgarada 3 adım sağa ve 3 adım yukarı gidilen en kısa yolların sayısı kaçtır?

• A) 20
• B) 12
• C) 720
• D) 36
• E) 15

Çözüm: Üç S ve üç Y harfinin dizilişleri: 6!/(3! · 3!) = 20. Cevap: A.

Örnek 4 — Anahtarlık

Soru: 5 farklı anahtar bir halkaya kaç farklı biçimde dizilebilir?

• A) 24
• B) 120
• C) 60
• D) 5
• E) 12

Çözüm: Dairesel permütasyon 4! = 24'tür; halka ters çevrilebildiği için ikiye bölünür: 12. Cevap: E.

• Tekrar eden harfleri farklı saymak. Aynı harflerin yer değiştirmesi yeni diziliş değildir.
• Tekrarlı rakamlarda 0'ı başa koymak. 0 ile başlayan dizilişler çıkarılır.
• Yuvarlak masada n! yazmak. Dairesel dizilişte bir yer sabitlenir: (n − 1)!.
• Yuvarlak masaya bileziğin kuralını uygulamak. İkiye bölme yalnızca ters çevrilebilen nesneler içindir.
• Dönüşümlü oturmada ikinci grubu da dairesel saymak. İlk grup oturunca boşluklar ayırt edilir hâle gelir.