Kombinatoryal modelleme - Combinatorial modelling - Wikipedia

Kombinatoryal modelleme bir problemi yeniden formüle etmek için uygun bir matematiksel model belirlememizi sağlayan süreçtir. Bu kombinatoryal modeller, kombinatorik teori, problemi çözmek için gerekli işlemler.

Örtülü kombinatoryal modeller

Basit kombinatoryal problemler, tek bir kombinatoryal işlem uygulanarak çözülebilen problemlerdir (varyasyonlar, permütasyonlar, kombinasyonlar, ...). Bu sorunlar, örtük kombinatoryal modeller adı verilen üç farklı modelde sınıflandırılabilir.

Seçimi

Bir seçim problemi bir örnek seçmeyi gerektirir k bir dizi öğeden n elementler. Nesnelerin seçilme sırasının önemli olup olmadığını ve bir nesnenin birden fazla seçilip seçilemeyeceğini bilmek gerekir. Bu tablo, modelin seçimlerin her biri için farklı örnek sayısını elde etmek için sağladığı işlemleri gösterir:

Tekrarlama

izin verilmedi

Tekrarlama

izin verildi

Sipariş verildi

örneklem

Sipariş edilmedi

örneklem

Örnekler

1.- Bir partide 50 kişi var. Herkes bir kez elini sıkar. Eller toplamda ne sıklıkla sallanıyor?Yapmamız gereken, tüm olası parti misafir çiftlerinin sayısını hesaplamaktır, yani 50 misafirden 2 kişiden oluşan bir örneklemdir. ve . İki kişinin sırası ne olursa olsun bir çift aynı olacaktır. Bir el sıkışma iki farklı kişi tarafından yapılmalıdır (tekrar yok). Bu nedenle, tekrarlamaya izin verilmeyen 50 öğelik bir setten 2 öğeden oluşan sıralı bir örnek seçmek gerekir. Doğru operasyonu seçmek için bilmemiz gereken tek şey bu ve sonuç:

2.- Maalesef dört basamaklı kilidinizin kodunu hatırlayamıyorsunuz. Sadece bir rakamı birden fazla kullanmadığınızı bilirsiniz. Kaç farklı yolu denemeniz gerekiyor?10 basamaktan oluşan (10 tabanı) 4 basamaklı bir örnek seçmemiz gerekir, bu nedenle ve . Doğru numarayı elde etmek için rakamların belirli bir şekilde sıralanması gerekir, bu nedenle sıralı bir örnek seçmek istiyoruz. Açıklamada belirtildiği gibi, hiçbir rakam birden fazla seçilmedi, bu nedenle örneğimizde tekrarlanan rakamlar olmayacak. Bu nedenle, tekrara izin verilmeyen 10 öğeden oluşan bir setten 4 öğeden oluşan sıralı bir örnek seçmek gerekir. Doğru operasyonu seçmek için bilmemiz gereken tek şey bu ve sonuç:

3.- Bir çocuk, doğum günü partisi için arkadaşlarına vermek üzere 20 davetiye almak istiyor. Mağazada 3 çeşit kart var ve hepsini seviyor. 20 kartı kaç şekilde satın alabilir? 3 tip kart setinden 20 davetiye kartından örnek seçilmesi gerekmektedir. ve . Farklı türdeki davetiyeleri seçtiğiniz sıra önemli değildir. Bir kart türü birden fazla seçilmesi gerektiğinden, davetiye kartlarımızda tekrarlar olacaktır. Bu nedenle, 20 öğeden oluşan sırasız bir örnek seçmek istiyoruz () 3 öğeden oluşan bir setten (), tekrara izin verilir. Doğru operasyonu seçmek için bilmemiz gereken tek şey bu ve sonuç:

Dağıtım

Bir dağıtım probleminde yer alması gerekir k içine nesneler n kutular veya alıcılar. Modelin sağladığı operasyonlar arasından doğru operasyonu seçebilmek için bilinmesi gerekenler:

  • Nesnelerin ayırt edilebilir olup olmadığı.
  • Kutuların ayırt edilebilir olup olmadığı.
  • Nesnelerin bir kutuya yerleştirilme sırası önemliyse.
  • Dağıtımın karşılaması gereken koşullar. Buna bağlı olarak dağıtım şu şekilde olabilir:
    1. Enjeksiyon dağılımı: her kutuda en fazla 1 nesne bulunmalıdır ()
    2. Süpürge dağılımı: her kutuda en az 1 nesne bulunmalıdır ()
    3. Bijektif dağıtım: her kutu tam olarak 1 nesne olmalıdır ()
    4. Kısıtlama olmaksızın dağıtım

Aşağıdaki tablo, modelin, dağıtımların her biri için nesneleri dağıtmanın farklı yollarının sayısını elde etmek için sağladığı işlemleri gösterir:

Dağılımı k içine nesneler n kutuları
Sırasız dağıtımSıralı dağıtım
Ayırt edilebilir nesnelerAyırt edilemeyen nesnelerAyırt edilebilir nesneler
Ayırt edilebilir kutularAyırt edilemeyen kutularAyırt edilebilir kutularAyırt edilemeyen kutularAyırt edilebilir kutularAyırt edilemeyen kutular
Hiç

dağıtım

Enjeksiyon

dağıtım

Surjective

dağıtım

Bijective

dağıtım

İkinci türden Stirling sayıları
Tam sayının bölüm sayısı k içine n parçalar
Lah sayıları (üçüncü türün Stirling sayıları)

Örnekler

1.- Bir matematik öğretmeni, öğrencileri arasında 3 öğrenci vermek zorundadır. Bunlardan 7'si 'üstün' bir not aldı, bu yüzden onları almaya adaylar. Hibeleri kaç şekilde dağıtabilir?Diyelim ki 3 öğrenci, öğrenciler olan 7 kutuya dağıtılması gereken nesneler. Nesneler özdeş öğrenci oldukları için ayırt edilemezler. Kutular, farklı öğrenciler oldukları için ayırt edilebilir. Her öğrencilik farklı bir öğrenciye verilmelidir, bu nedenle her kutuda en fazla 1 nesne bulunmalıdır. Ayrıca, nesnelerin bir kutuya yerleştirilme sırası önemli değildir çünkü her kutuda birden fazla olamaz. Yani, 3 ayırt edilemeyen nesnenin sıralı olmayan bir enjeksiyon dağılımıdır () 7 ayırt edilebilir kutuya (). Doğru operasyonu seçmek için bilmemiz gereken tek şey bu ve sonuç:

2.- 8 arkadaş grubu tatillerini geçirmek için 5 odalı bir yazlık kiralar. Odalar aynıysa ve kimse boş olamazsa, kulübede kaç şekilde dağıtılabilir?Arkadaşların, odalar olan 5 kutuya dağıtılması gereken nesneler olduğunu düşünelim. Nesneler farklı insanlar olduğu için ayırt edilebilirler. Aynı odalar oldukları için kutular ayırt edilemez. Bunu sırasız bir dağıtım olarak düşünebiliriz, çünkü herkesin odalara yerleştirildiği sıranın önemi yoktur. Hiçbir oda boş olamaz, bu nedenle her kutuda en az 1 nesne bulunmalıdır. Bu nedenle, 8 ayırt edilebilir nesnenin () 5 ayırt edilemez kutuya (). Doğru operasyonu seçmek için bilmemiz gereken tek şey bu ve sonuç:

3.- Şu anda 4 kasiyerin çalıştığı süpermarkette 12 kişi alışveriş yapıyor. Kasalara kaç farklı şekilde dağıtılabilirler?İnsanların kutulara dağıtılması gereken nesneler olduğunu düşünelim. İnsanlar ve kasalar farklı olduğundan nesneler ve kutular ayırt edilebilir. Nesnelerin kutulara yerleştirilme sırası önemlidir, çünkü onlar sıraya giren insanlardır. Açıklamada herhangi bir kısıtlama belirtilmiyor. Dolayısıyla, 12 ayırt edilebilir nesnenin kısıtlaması olmayan sıralı bir dağıtımdır () 4 ayırt edilebilir kutuya (). Doğru operasyonu seçmek için bilmemiz gereken tek şey bu ve sonuç:

Bölüm

Bir bölüm problemi, bir dizi k içine elemanlar n alt kümeler. Her kutudaki nesneleri, dağıtılacak nesneler kümesinin alt kümeleri olarak kabul edebileceğimiz için, bu model dağıtım modeli ile ilgilidir. Bu nedenle, daha önce açıklanan 24 dağıtımın her biri, alt kümelere göre eşleşen bir tür bölüme sahiptir. Böylelikle, bir bölme problemi, onu bir dağıtım modeline dönüştürerek ve dağıtım modelinin sağladığı karşılık gelen işlemi uygulayarak çözülebilir (önceki tablo). Bu yöntemi takip ederek, seti bölmenin olası yollarının sayısını alacağız. Bu iki model arasındaki ilişki aşağıdaki tabloda açıklanmıştır:

DağıtımBölüm
Sipariş verildiSıralı elemanların alt kümeleri
Sipariş edilmediSırasız elemanların alt kümeleri
Ayırt edilebilir nesnelerAyırt edilebilir unsurlar
Ayırt edilemeyen nesnelerAyırt edilemeyen öğeler
Ayırt edilebilir kutularSipariş edilen bölümler
Ayırt edilemeyen kutularSırasız bölümler
Enjeksiyon dağılımı1 öğeli alt kümeler veya boş olanlar
Surjektif dağılımBoş alt küme yok
Bijektif dağılımTam olarak 1 elementin alt kümeleri
Kısıtlama yok1 veya daha fazla öğenin alt kümeleri veya boş olanlar

Bu ilişki, dağıtım modeli tarafından sağlanan tabloyu, bir dizi bölmenin farklı yollarını bilmek için kullanılabilecek yeni bir tabloya dönüştürmemizi sağlar. k içine elemanlar n alt kümeler:

Bir kümenin bölümü k içine elemanlar n alt kümeler
Sırasız öğeler,
Ayırt edilebilir unsurlarAyırt edilemeyen öğelerAyırt edilebilir unsurlar
Sıralı alt kümelerSırasız alt kümelerSıralı alt kümelerSırasız alt kümelerSıralı alt kümelerSırasız alt kümeler
Herhangi bir alt küme
Boş veya 1 öğeli alt kümeler
Boş alt küme yok
1 öğenin alt kümeleri

Örnekler

1.- 3 sınıf arkadaşından oluşan bir grup 8 farklı matematik konusu hakkında tez yapmak zorundadır. Yapmak için işi kaç şekilde bölebilirler?8 konu setini 3 alt gruba bölmemiz gerekiyor. Bu alt kümeler, her öğrencinin üzerinde çalışacağı konular olacaktır. Setteki öğeler (konular) ayırt edilebilir. Bölümler sıralanmalıdır çünkü her biri farklı bir öğrenciye karşılık gelir, ancak her alt kümenin içindeki konuların sıralanması gerekmez çünkü her öğrenci tez üzerinde çalışırken hangi sırayı takip edeceğine karar verebilir. Açıklama, alt kümelerin herhangi bir kısıtlamasından bahsetmez. Bu nedenle, 8 öğelik bir kümeyi bölmek gerekir () 3 sıralı alt kümeye () sıralı olmayan elemanlar. Doğru operasyonu seçmek için bilmemiz gereken tek şey bu ve sonuç:

Ayrıca bakınız

Kaynaklar