Sıralama (Permütasyon) ve Faktöriyel

Nesneleri sıraya dizmek veya bir yarışmada kimlerin hangi sırada yer alacağını belirlemek gibi durumlar günlük hayatta sık karşılaşılır; bu tür farklı dizilimler özellikle olasılık hesaplamalarında önemli bir yer tutar.

Faktöriyel Tanımı

n∈ℕ olmak üzere 1'den n'ye kadar olan ardışık tam sayıların çarpımına n faktöriyel denir ve n! ile gösterilir.

$$n! = 1 \cdot 2 \cdot 3 \cdots (n-1) \cdot n$$

0! = 1 olarak kabul edilir. 1!=1, 2!=2, 3!=6, 4!=24, 5!=120, 6!=720'dir. 7!=7·6!=7·6·5! gibi ardışık faktöriyeller arasında bir ilişki kurulabilir.

n Farklı Nesnenin Sıralanması

n farklı nesne düz bir sıraya n! farklı şekilde sıralanabilir. Bu, çarpma yoluyla sayma ilkesinin doğrudan bir sonucudur: 1. sıraya n seçenek, 2. sıraya (n−1) seçenek, ... son sıraya 1 seçenek kalır; çarpım n!'dir.

Örnek: Arda, Berra, Can adlı üç kardeş 3!=6 farklı şekilde yan yana sıralanabilir. 5 farklı kitap bir rafa 5!=120 farklı şekilde sıralanabilir.

Kısıtlı sıralama örneği: 8 kişilik bir ekipte Selim en solda, Seda en sağda sabit olacaksa, geriye kalan 6 kişi 6!=720 farklı şekilde sıralanabilir (uç konumlar sabit, yalnızca ortadaki 6 kişi serbestçe sıralanır).

Örnek — Kombine sıralama: 4 çeşit börek ve 5 çeşit tatlı, ayrı bölmelerde sıralanacak ve bölmeler kendi aralarında da yer değiştirebilecektir: 4!·5!·2 = 24·120·2 = 5760 farklı sıralama.

Bit ve Bayt Örneği (İkili Sistemde Sayma)

4 bitlik bir veri dizilimi, her bite 0 veya 1 gelebileceğinden çarpma yoluyla sayma ile 2·2·2·2=2⁴=16 farklı karakter kümesi oluşturur. Bir bayt (8 bit) ise 2⁸=256 farklı karakter kümesi oluşturur — ASCII'de 7 bit ile 2⁷=128, Genişletilmiş ASCII'de 8 bit ile 2⁸=256 farklı karakter temsil edilebilir.

n Farklı Nesneden r Tanesinin Sıralanması

n tane farklı nesneden r tanesi seçilip sıralandığında (n≥r): 1. konuma n seçenek, 2. konuma (n−1) seçenek, ..., r. konuma (n−r+1) seçenek kalır; toplam sıralama sayısı n·(n−1)·(n−2)···(n−r+1) = n!/(n−r)!'dir.

Örnek — Araç Plakası: Tuna isminin harflerinden (4 farklı harf) ikili gruplar oluştururken 4·3=12 farklı ikili grup elde edilir.

Örnek — Otopark: 7 farklı renkte araba, 4 araçlık bir otoparka 7·6·5·4=840 farklı sıralamada park edebilir.

Özdeş Nesnelerin Sıralanması

Sıralanması gereken n tane elemanın r tanesi özdeş ise, bunların kendi arasında yer değiştirmesi farklı bir sıralama oluşturmaz. Bu durumda sıralama sayısı n!/r! olur.

Örnek — Duvar Süsü: 4 özdeş çiçek desenli ve 2 özdeş nazar boncuğu desenli magnet, 6 bölmeli bir yüzeye 6!/(4!·2!) = (6·5·4!)/(4!·2) = 15 farklı şekilde yerleştirilebilir.

Örnek — Izgara Yol Sayma: Bir mahalle krokisinde A noktasından C noktasına en kısa yoldan gitmek için 5 birim sağa (S), 3 birim yukarı (Y) hareket gerekiyorsa, yol SSSSSYYY diziliminin farklı sıralanışları kadar yol vardır: 8!/(5!·3!) = 56 farklı yol. Araya bir B noktasından (kütüphane) geçme şartı eklenirse, A→B yolu (3 yol) ile B→C yolu (10 yol) çarpılır: 3×10=30 farklı yol.

Özet

• n farklı nesne n! farklı şekilde sıralanabilir; n nesneden r tanesinin sıralanma sayısı n!/(n−r)!'dir — bu formüller çarpma yoluyla saymanın doğrudan bir genellemesidir.
• n nesnenin r tanesi özdeş olduğunda, sıralama sayısı n!/r!'ye düşer, çünkü özdeş nesnelerin kendi aralarındaki yer değişimleri farklı bir dizilim oluşturmaz.
• Izgara (grid) üzerinde en kısa yol sayma problemleri, yön harflerinin (S, Y gibi) özdeş nesneler olarak sıralanması problemine dönüştürülerek n!/(r₁!·r₂!) formülüyle çözülür.