Bu makale matematiğin kombinatorik adı verilen özel bir bölümüne odaklanacak. Formüller, kurallar, problem çözme örnekleri - tüm bunları makaleyi sonuna kadar okuyarak burada bulabilirsiniz.
Peki, bu bölüm nedir? Kombinatorik, herhangi bir nesneyi sayma sorunuyla ilgilenir. Ancak bu durumda nesneler erik, armut veya elma değil, başka bir şeydir. Kombinatorik, bir olayın olasılığını bulmamıza yardımcı olur. Örneğin, kağıt oynarken rakibin koz kartı olma olasılığı nedir? Veya böyle bir örnek - yirmi bilyelik bir torbadan tam olarak beyaz çıkma olasılığınız nedir? Bu tür görevler için en azından matematiğin bu bölümünün temellerini bilmemiz gerekiyor.
Kombinatoryal konfigürasyonlar
Birleştiricilerin temel kavramları ve formülleri konusunu göz önüne aldığımızda, kombinatoryal konfigürasyonlara dikkat etmekten başka bir şey yapamayız. Sadece formülasyon için değil, aynı zamanda çeşitli kombinatoryal problemlerin çözümü için de kullanılırlar. Bu tür modellere örnekler:
- yerleştirme;
- permütasyon;
- kombinasyon;
- sayı bileşimi;
- ayrık sayı.
İlk üçünden daha sonra daha detaylı bahsedeceğiz ama bu bölümde kompozisyon ve bölmeye dikkat edeceğiz. Belirli bir sayının bileşimi hakkında konuştuklarında (örneğin, a), a sayısının bazı pozitif sayıların sıralı toplamı olarak temsilini kastediyorlar. Bölünme ise sırasız bir toplamdır.
Bölümler
Doğrudan kombinatorik formüllerine ve problemlerin ele alınmasına geçmeden önce, matematiğin diğer bölümleri gibi kombinatoriğin de kendi alt bölümlerine sahip olduğuna dikkat etmekte fayda var. Bunlar şunları içerir:
- sayısal;
- yapısal;
- aşırı;
- Ramsey teorisi;
- olasılık;
- topolojik;
- sonsuz.
İlk durumda, numaralandırma kombinatoriklerinden bahsediyoruz, problemler kümelerin elemanları tarafından oluşturulan farklı konfigürasyonların numaralandırılmasını veya sayılmasını ele alıyor. Kural olarak, bu kümelere bazı kısıtlamalar getirilir (ayırt edilebilirlik, ayırt edilemezlik, tekrarlama imkanı vb.). Ve bu konfigürasyonların sayısı, biraz sonra konuşacağımız toplama veya çarpma kuralı kullanılarak hesaplanır. Yapısal kombinatorikler, grafik ve matroid teorilerini içerir. Aşağıdaki özellikleri sağlayan bir grafiğin en büyük boyutunun ne olduğu ekstrem kombinatorik problemine bir örnektir… Dördüncü paragrafta, rastgele konfigürasyonlarda düzenli yapıların varlığını inceleyen Ramsey teorisinden bahsetmiştik. olasılıksalkombinatorik, soruyu cevaplayabilir - belirli bir kümenin belirli bir özelliğe sahip olma olasılığı nedir. Tahmin edebileceğiniz gibi, topolojik kombinatorik, topolojide yöntemler uygular. Ve son olarak, yedinci nokta - sonsuz kombinatorik, kombinatorik yöntemlerin sonsuz kümelere uygulanmasını inceler.
Toplama kuralı
Birleştirici formüller arasında, uzun zamandır aşina olduğumuz oldukça basit formüller bulunabilir. Bir örnek, toplam kuralıdır. Bize iki eylem (C ve E) verildiğini varsayalım, eğer bunlar birbirini dışlıyorlarsa, C eylemi birkaç yolla yapılabilir (örneğin, a) ve E eylemi b-yollarında yapılabilir, sonra bunlardan herhangi biri (C) veya E) a + b yollarıyla yapılabilir.
Teoride bunu anlamak oldukça zor, basit bir örnekle tüm konuyu aktarmaya çalışacağız. Bir sınıftaki ortalama öğrenci sayısını alalım - diyelim ki yirmi beş. Aralarında on beş kız ve on erkek var. Her gün sınıfa bir görevli atanır. Bugün bir sınıf görevlisi atamanın kaç yolu var? Sorunun çözümü oldukça basit, toplama kuralına başvuracağız. Görevin metni sadece erkek veya sadece kızların görev yapabileceğini söylemiyor. Bu nedenle, on beş kızdan herhangi biri veya on erkekten herhangi biri olabilir. Toplam kuralını uygulayarak, bir ilkokul öğrencisinin kolayca başa çıkabileceği oldukça basit bir örnek alıyoruz: 15 + 10. Hesapladıktan sonra cevabı alıyoruz: yirmi beş. Yani, sadece yirmi beş yol varbugün için bir görev sınıfı atayın.
Çarpma kuralı
Çarpma kuralı, kombinatoriklerin temel formüllerine de aittir. Teoriyle başlayalım. Birkaç eylem gerçekleştirmemiz gerektiğini varsayalım (a): ilk eylem 1 şekilde gerçekleştirilir, ikincisi - 2 şekilde, üçüncüsü - 3 şekilde ve böylece son a-eylem sa yollarla gerçekleştirilene kadar. O zaman tüm bu eylemler (bunların toplamı elimizde) N yolla gerçekleştirilebilir. Bilinmeyen N nasıl hesaplanır? Formül bize bu konuda yardımcı olacaktır: N \u003d c1c2c3…ca.
Yine, teoride hiçbir şey net değil, hadi çarpma kuralının uygulanmasıyla ilgili basit bir örneğe geçelim. On beş kız ve on erkeğin okuduğu yirmi beş kişilik aynı sınıfı ele alalım. Sadece bu sefer iki görevli seçmemiz gerekiyor. Sadece erkek veya kız ya da bir kızla birlikte bir erkek olabilirler. Sorunun temel çözümüne dönüyoruz. İlk görevliyi seçiyoruz, son paragrafta kararlaştırdığımız gibi, yirmi beş olası seçenek elde ediyoruz. Görevdeki ikinci kişi, kalan kişilerden herhangi biri olabilir. Yirmi beş öğrencimiz vardı, birini seçtik, yani kalan yirmi dört kişiden herhangi biri ikinci görevli olabilir. Son olarak, çarpma kuralını uygularız ve iki görevlinin altı yüz şekilde seçilebileceğini buluruz. Bu sayıyı yirmi beş ile yirmi dördü çarparak elde ettik.
Takas
Şimdi bir kombinatorik formül daha ele alacağız. Yazının bu bölümünde bizPermütasyonlardan bahsedelim. Sorunu hemen bir örnekle düşünün. Bilardo toplarını ele alalım, n'inci numaramız var. Hesaplamamız gerekiyor: bunları bir satırda düzenlemek, yani sıralı bir küme oluşturmak için kaç seçenek var.
Başlayalım, topumuz yoksa yerleştirme seçeneğimiz de sıfır. Ve eğer bir topumuz varsa, o zaman düzenleme de aynıdır (matematiksel olarak, bu şu şekilde yazılabilir: Р1=1). İki top iki farklı şekilde yerleştirilebilir: 1, 2 ve 2, 1. Dolayısıyla, Р2=2. Üç top altı şekilde düzenlenebilir (P3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. Ve böyle üç top yoksa on mu on beş mi? Tüm olası seçenekleri listelemek çok uzun, ardından kombinatorik yardımımıza geliyor. Permütasyon formülü, sorumuzun cevabını bulmamıza yardımcı olacaktır. Pn=nP(n-1). Formülü sadeleştirmeye çalışırsak, şunu elde ederiz: Pn=n (n - 1) … 21. Ve bu ilk doğal sayıların ürünüdür. Böyle bir sayı faktöriyel olarak adlandırılır ve n! olarak gösterilir.
Problemi ele alalım. Lider her sabah müfrezesini bir sıra halinde kurar (yirmi kişi). Müfrezede en iyi üç arkadaş var - Kostya, Sasha ve Lesha. yan yana olma olasılığı kaçtır? Sorunun cevabını bulmak için “iyi” bir sonuç olasılığını toplam sonuç sayısına bölmeniz gerekir. Toplam permütasyon sayısı 20'dir!=2.5 kentilyon. "İyi" sonuçların sayısı nasıl sayılır? Diyelim ki Kostya, Sasha ve Lesha bir süpermen. Sonra bizSadece on sekiz deneğimiz var. Bu durumda permütasyon sayısı 18=6.5 katrilyondur. Bütün bunlarla, Kostya, Sasha ve Lesha, bölünmez üçlülerinde kendi aralarında keyfi olarak hareket edebilirler ve bu 3 tane daha!=6 seçenek. Yani toplamda 18 “iyi” takımyıldızımız var!3! Sadece istenen olasılığı bulmamız gerekiyor: (18!3!) / 20! Bu, yaklaşık olarak 0.016'dır. Yüzdeye dönüştürülürse, yalnızca %1.6 olduğu ortaya çıkar.
Konaklama
Şimdi başka bir çok önemli ve gerekli kombinatorik formülünü ele alacağız. Konaklama, makalenin bu bölümünde göz önünde bulundurmanızı önerdiğimiz bir sonraki sayımız. Daha karmaşık hale geleceğiz. Tüm kümeden (n) değil, daha küçük bir kümeden (m) olası permütasyonları dikkate almak istediğimizi varsayalım. Yani, n öğenin permütasyonlarını m. ile ele alıyoruz.
Birleştiricilerin temel formülleri sadece ezberlenmemeli, aynı zamanda anlaşılmalıdır. Daha karmaşık hale gelmelerine rağmen, bir parametremiz değil, iki parametremiz olduğu için. Diyelim ki m \u003d 1, sonra A \u003d 1, m \u003d 2, sonra A \u003d n(n - 1). Formülü daha da basitleştirirsek ve faktöriyelleri kullanarak gösterime geçersek, oldukça özlü bir formül elde ederiz: A \u003d n! / (n - m)!
Kombinasyon
Birleştiricilerin neredeyse tüm temel formüllerini örneklerle inceledik. Şimdi, kombinatoriğin temel seyrini düşünmenin son aşamasına geçelim - kombinasyonu tanıma. Şimdi elimizdeki n'den m tane öğe seçeceğiz ve hepsini mümkün olan her şekilde seçeceğiz. O halde bunun konaklamadan ne farkı var? Yapmayacağızsipariş düşünün. Bu sırasız küme bir kombinasyon olacaktır.
Hemen şu notasyonu tanıtın: C. n'den m topların yerleşimlerini alıyoruz. Siparişe dikkat etmeyi bırakıp tekrar eden kombinasyonlar alıyoruz. Kombinasyon sayısını elde etmek için yerleşim sayısını m'ye bölmemiz gerekiyor! (m faktöriyel). Yani, C \u003d A / m! Bu nedenle, n top arasından seçim yapmanın birkaç yolu vardır, bu, hemen hemen her şeyi kaç tane seçeceğinize yaklaşık olarak eşittir. Bunun mantıklı bir ifadesi var: Biraz seçmek, neredeyse her şeyi atmakla aynı şeydir. Öğelerin yarısını seçmeye çalışırken maksimum kombinasyon sayısına ulaşılabileceğini de bu noktada belirtmekte fayda var.
Bir sorunu çözmek için bir formül nasıl seçilir?
Birleştiricilerin temel formüllerini ayrıntılı olarak inceledik: yerleştirme, permütasyon ve kombinasyon. Şimdi görevimiz, sorunu kombinatorikte çözmek için gerekli formülün seçimini kolaylaştırmaktır. Aşağıdaki oldukça basit şemayı kullanabilirsiniz:
- Kendinize sorun: Problemin metninde öğelerin sırası dikkate alınıyor mu?
- Cevap hayır ise, kombinasyon formülünü kullanın (C=n! / (m!(n - m)!)).
- Cevap hayır ise, o zaman bir soruyu daha cevaplamanız gerekir: Kombinasyonda tüm unsurlar var mı?
- Cevap evet ise, permütasyon formülünü kullanın (P=n!).
- Cevap hayır ise, tahsis formülünü kullanın (A=n! / (n - m)!).
Örnek
Birleştiricilerin, formüllerin ve diğer bazı konuların unsurlarını düşündük. şimdi devam edelimgerçek bir sorun göz önüne alındığında. Önünüzde bir kivi, bir portakal ve bir muz olduğunu hayal edin.
Birinci soru: Kaç şekilde yeniden düzenlenebilirler? Bunu yapmak için permütasyon formülünü kullanıyoruz: P=3!=6 yol.
İkinci soru: bir meyve kaç farklı şekilde seçilebilir? Bu açıktır, sadece üç seçeneğimiz var - kivi, portakal veya muz seçin, ancak kombinasyon formülünü uyguluyoruz: C \u003d 3! / (2!1!)=3.
Üçüncü soru: iki meyve kaç farklı şekilde seçilebilir? Hangi seçeneklerimiz var? kivi ve portakal; kivi ve muz; portakal ve muz. Yani, üç seçenek, ancak kombinasyon formülünü kullanarak bunu kontrol etmek kolaydır: C \u003d 3! / (1!2!)=3
Dördüncü soru: Üç meyve kaç farklı şekilde seçilebilir? Gördüğünüz gibi, üç meyve seçmenin tek bir yolu var: bir kivi, bir portakal ve bir muz alın. C=3! / (0!3!)=1.
Beşinci soru: En az bir meyveyi kaç farklı şekilde seçebilirsiniz? Bu koşul, bir, iki veya üç meyveyi de alabileceğimiz anlamına gelir. Bu nedenle C1 + C2 + C3=3 + 3 + 1=7'yi ekliyoruz. Yani masadan en az bir meyve almanın yedi yolu var.
