Kapsama-Dışlama Prensibi
Kapsama-dışlama prensibi, kümelerin birleşiminin büyüklüğünü, kesişimlerinin büyüklüklerini dönüşümlü olarak ekleyip çıkararak saymaktadır.
Tanım
Sonlu kümelerin birleşiminin kardinalitesinin, tüm boş olmayan alt koleksiyonlar üzerinden alınan tüm kesişimlerinin kardinalitelerinin dönüşümlü toplamına eşit olduğunu belirten bir sayma özdeşliğidir.
Kapsam
Bu konu, kapsama-dışlama formülünü ve yasaklanmış özellikler listesinden kaçınan nesneleri saymaya yönelik uygulamalarını sunmaktadır: permütasyonlar (derangements), örten fonksiyonlar (surjections), Euler'in totient fonksiyonu ve belirli bir sayıya göre asal olan tam sayıların sayısı. Ayrıca, prensibi daha geniş bir cebirsel bağlama yerleştiren elek bakış açısını ve kısmi sıralı kümeler üzerindeki Mobius fonksiyonu genellemesini tanıtmaktadır.
Temel sorular
- Birkaç çakışan koşuldan en az birini kaç eleman sağlamaktadır?
- Yasaklanmış özellikler kümesinin tamamından kaçınan nesneler nasıl sayılabilir?
- Permütasyonlar (derangements) ve örten fonksiyon (surjection) sayıları bu prensipten nasıl türetilmektedir?
- Bir kısmi sıralı küme (poset) üzerindeki Mobius fonksiyonu, kapsama-dışlama prensibini nasıl genelleştirmektedir?
Anahtar kavramlar
- Çakışan kümelerin birleşimi
- Elek yöntemi
- Kapsama-dışlama yoluyla permütasyonlar (derangements)
- Örten fonksiyonları sayma
- Euler'in totient fonksiyonu
- Kısmi sıralı kümeler (posetler) üzerindeki Mobius fonksiyonu
Temel kuramlar
- Kapsama-dışlama formülü
- A_1'den A_n'ye kadar olan kümelerin birleşiminin kardinalitesi, tekli küme büyüklüklerinin toplamı eksi ikili kesişimler artı üçlü kesişimler şeklinde devam ederek, paylaşılan elemanların fazla sayılmasını sistematik olarak düzeltmektedir.
- Kısmi sıralı kümeler (posetler) üzerinde Mobius tersinimi
- Stanley'nin kısmi sıralı küme (poset) teorik genellemesi, kapsama-dışlamanın dönüşümlü işaretlerini kısmi sıralı bir kümenin Mobius fonksiyonu ile değiştirerek, prensibi sayı teorik ve kafes teorik tersinim formülleriyle birleştirmektedir.
Klinik önem
Elek fikri, sayı teorisine (Eratosthenes eleği ve analitik elekler), olasılığa (birleşim olasılıklarını sınırlayan Bonferroni eşitsizlikleri) ve çakışan hata modlarına sahip sistemlerin güvenilirlik analizine genelleştirilmektedir.
Tarihçe
Özünde de Moivre ve Sylvester tarafından ifade edilen prensip, 1964 yılında Rota tarafından kısmi sıralı kümeler üzerindeki Mobius fonksiyonlarının genel bir teorisi içine yerleştirilmiş olup, modern kombinatoriğin önemli bir dönüm noktasıdır.
Öne çıkan isimler
- Abraham de Moivre
- Gian-Carlo Rota
İlgili konular
Temel eserler
- stanley2011
Sıkça sorulan sorular
- İşaretler neden dönüşümlüdür?
- Kümelerin birkaçında bulunan elemanlar çok fazla kez eklenmektedir; ikili kesişimlerin çıkarılması aşırı düzeltmeye yol açar, bu nedenle üçlü kesişimler tekrar eklenerek, her elemanı tam olarak bir kez sayan dönüşümlü bir örüntü oluşturulmaktadır.
- Mobius fonksiyonu ile bağlantısı nedir?
- Kapsama-dışlama, alt kümelerin Boole kafesi üzerindeki Mobius tersiniminin özel bir durumudur; burada Mobius fonksiyonu artı veya eksi bir değerlerini almaktadır.