Permütasyonlar ve Kombinasyonlar
Permütasyonlar nesnelerin sıralı düzenlemelerini, kombinasyonlar ise sırasız seçimlerini saymaktadır; birlikte sayma işleminin temel çekirdeğini oluşturmaktadırlar.
Tanım
Bir kümenin permütasyonu, elemanlarının sıralı bir düzenlemesidir (veya kümenin kendisine bir bijeksiyondur); bir kombinasyon ise, bir kümeden belirli sayıda elemanın sırasız seçimidir.
Kapsam
Bu konu, düzenlemelerin (tekrarlı ve tekrarsız), seçimlerin ve bunların bozuk permütasyonlar (derangements), dairesel permütasyonlar ve kısıtlı konumlu permütasyonlar gibi inceliklerinin sayılmasını geliştirmektedir. İnişler (descents), ters çevirmeler (inversions) ve döngü yapısı gibi permütasyon istatistiklerini tanıtmaktadır; bunlar, temel saymayı simetrik grubun daha zengin modern kuramına bağlamaktadır.
Temel sorular
- n farklı nesne kaç farklı şekilde sıralanabilir ve bunlardan r tanesi kaç farklı şekilde sıralanabilir?
- Tekrar ve ayırt edilemezlik, düzenlemelerin sayısını nasıl değiştirmektedir?
- Bozuk permütasyonlar (derangements) nelerdir ve rastgele bir permütasyonun hiçbir elemanı sabit tutmama olasılığı ne sıklıktadır?
- Permütasyonlar üzerindeki hangi istatistikler eş dağılımlıdır?
Anahtar kavramlar
- Faktöriyel ve azalan faktöriyel
- Tekrarlı ve tekrarsız düzenlemeler
- Bozuk permütasyonlar (Derangements)
- Dairesel permütasyonlar
- Ters çevirmeler (Inversions) ve inişler (descents)
- Stirling sayıları
Temel kuramlar
- Permütasyonların döngü ayrışımı
- Her permütasyon, ayrık döngülere benzersiz bir şekilde ayrışmaktadır; permütasyonları döngü tiplerine göre saymak, birinci tür Stirling sayıları tarafından yönetilmekte ve simetrik grubun yapısının temelini oluşturmaktadır.
- Bozuk permütasyon (derangement) sayımı
- Sabit noktası olmayan permütasyonların sayısı, içerme-dışlama prensibi aracılığıyla türetilmekte ve n!/e değerine yaklaşmaktadır; bu da permütasyonların yaklaşık %37'sinin bozuk permütasyon (derangement) olduğu klasik sonucunu vermektedir.
Klinik önem
Permütasyon ve kombinasyon sayıları olasılıkta (eşit olasılıklı sonuçlar), sıralama ve karıştırma algoritmalarında, deneysel tasarımda ve kriptografik anahtar uzaylarında karşımıza çıkmaktadır; bu alanlarda bir düzenleme uzayının boyutu zorluğu ve güvenliği belirlemektedir.
Tarihçe
Permütasyonların kombinatoriği, MacMahon'un 20. yüzyıl başlarındaki kombinatorik analiz üzerine yaptığı çalışmalarla sistemleştirilmiş ve daha sonra permütasyon istatistiklerinin modern kuramı aracılığıyla derinleştirilmiştir.
Öne çıkan isimler
- Percy MacMahon
- Richard P. Stanley
İlgili konular
Temel eserler
- stanley2011
Sıkça sorulan sorular
- n elemanlı bir kümenin kaç permütasyonu vardır?
- n! permütasyonu vardır; bu, n'ye kadar olan tüm pozitif tam sayıların çarpımıdır, çünkü n konumun her biri farklı bir kalan elemanla doldurulmaktadır.
- Bozuk permütasyon (derangement) nedir?
- Bozuk permütasyon (derangement), hiçbir elemanın orijinal konumunda kalmadığı bir permütasyondur; örneğin, hiçbir mektubun kendi zarfına geri dönmediği bir yeniden karıştırma gibi.