Ten artykuł skupi się na specjalnej sekcji matematyki zwanej kombinatoryką. Wzory, zasady, przykłady rozwiązywania problemów – to wszystko znajdziesz tutaj czytając artykuł do samego końca.
Co to za sekcja? Kombinatoryka zajmuje się kwestią liczenia dowolnych obiektów. Ale w tym przypadku przedmiotami nie są śliwki, gruszki czy jabłka, ale coś innego. Kombinatoryka pomaga nam znaleźć prawdopodobieństwo zdarzenia. Na przykład, kiedy grasz w karty, jakie jest prawdopodobieństwo, że przeciwnik ma kartę atutową? Albo taki przykład - jakie jest prawdopodobieństwo, że z woreczka dwudziestu piłek dostaniesz dokładnie biały? Do tego rodzaju zadań musimy znać przynajmniej podstawy tej sekcji matematyki.
Konfiguracje kombinatoryczne
Rozważając kwestię podstawowych pojęć i formuł kombinatoryki, nie możemy nie zwrócić uwagi na konfiguracje kombinatoryczne. Służą nie tylko do formułowania, ale także do rozwiązywania różnych problemów kombinatorycznych. Przykładami takich modeli są:
- miejsce docelowe;
- permutacja;
- kombinacja;
- skład liczb;
- podziel numer.
O pierwszych trzech omówimy bardziej szczegółowo później, ale w tej sekcji zwrócimy uwagę na kompozycję i podział. Kiedy mówią o składzie pewnej liczby (powiedzmy a), mają na myśli przedstawienie liczby a jako uporządkowanej sumy niektórych liczb dodatnich. A podział to nieuporządkowana suma.
Sekcje
Zanim przejdziemy bezpośrednio do wzorów kombinatoryki i rozpatrzenia problemów, warto zwrócić uwagę na fakt, że kombinatoryka, podobnie jak inne działy matematyki, ma swoje podrozdziały. Należą do nich:
- enumerative;
- strukturalne;
- ekstremalne;
- Teoria Ramseya;
- probabilistyczne;
- topologiczna;
- nieskończony.
W pierwszym przypadku mówimy o kombinatoryce enumeratywnej, problemy dotyczą wyliczania lub liczenia różnych konfiguracji, które tworzą elementy zbiorów. Z reguły na te zestawy nakładane są pewne ograniczenia (rozróżnialność, nierozróżnialność, możliwość powtórzenia itp.). A liczbę tych konfiguracji oblicza się zgodnie z zasadą dodawania lub mnożenia, o czym porozmawiamy nieco później. Kombinatoryka strukturalna obejmuje teorie grafów i matroidów. Przykładem ekstremalnego problemu kombinatorycznego jest największy wymiar grafu, który spełnia następujące własności… W czwartym akapicie wspomnieliśmy o teorii Ramseya, która bada obecność regularnych struktur w losowych konfiguracjach. probabilistycznykombinatoryka jest w stanie odpowiedzieć na pytanie - jakie jest prawdopodobieństwo, że dany zbiór ma określoną właściwość. Jak można się domyślić, topologiczna kombinatoryka stosuje metody w topologii. I wreszcie punkt siódmy - kombinatoryka nieskończoności bada zastosowanie metod kombinatoryki do zbiorów nieskończonych.
Reguła dodawania
Wśród formuł kombinatoryki można znaleźć dość proste, znane nam od dawna. Przykładem jest reguła sumy. Załóżmy, że dane są nam dwa działania (C i E), jeśli wzajemnie się wykluczają, działanie C można wykonać na kilka sposobów (na przykład a), a działanie E można wykonać na sposoby b, a następnie dowolny z nich (C lub E) można to zrobić w sposób a + b.
Teoretycznie jest to dość trudne do zrozumienia, postaramy się przekazać cały punkt na prostym przykładzie. Przyjmijmy średnią liczbę uczniów w jednej klasie - powiedzmy, że jest to dwudziestu pięciu. Wśród nich jest piętnaście dziewczynek i dziesięciu chłopców. Do klasy przydzielany jest codziennie jeden uczestnik. Na ile sposobów można dziś przydzielić uczestnika zajęć? Rozwiązanie problemu jest dość proste, uciekniemy się do zasady dodawania. Tekst zadania nie mówi, że dyżurować mogą tylko chłopcy lub tylko dziewczynki. Dlatego może to być dowolna z piętnastu dziewcząt lub którykolwiek z dziesięciu chłopców. Stosując zasadę sumy, otrzymujemy dość prosty przykład, z którym uczeń szkoły podstawowej bez problemu sobie poradzi: 15 + 10. Po przeliczeniu otrzymujemy odpowiedź: dwadzieścia pięć. Oznacza to, że jest tylko dwadzieścia pięć sposobówprzypisz klasę służby na dziś.
Zasada mnożenia
Zasada mnożenia należy również do podstawowych formuł kombinatoryki. Zacznijmy od teorii. Załóżmy, że musimy wykonać kilka czynności (a): pierwsza czynność jest wykonywana na 1 sposoby, druga - na 2 sposoby, trzecia - na 3 sposoby i tak dalej, aż ostatnia czynność zostanie wykonana na sposoby sa. Wtedy wszystkie te działania (których mamy w sumie) można wykonać na N sposobów. Jak obliczyć nieznane N? Pomoże nam w tym formuła: N \u003d c1c2c3…ca.
Ponownie, teoretycznie nic nie jest jasne, przejdźmy do prostego przykładu zastosowania zasady mnożenia. Weźmy tę samą klasę dwudziestu pięciu osób, w której uczy się piętnaście dziewcząt i dziesięciu chłopców. Tylko tym razem musimy wybrać dwóch opiekunów. Mogą to być albo tylko chłopcy lub dziewczynki, albo chłopiec z dziewczyną. Zwracamy się do elementarnego rozwiązania problemu. Wybieramy pierwszego opiekuna, jak ustaliliśmy w ostatnim akapicie, otrzymujemy dwadzieścia pięć możliwych opcji. Drugą osobą na służbie może być dowolna z pozostałych osób. Mieliśmy dwudziestu pięciu uczniów, wybraliśmy jednego, co oznacza, że każda z pozostałych dwudziestu czterech osób może być drugą na dyżurze. Na koniec stosujemy zasadę mnożenia i stwierdzamy, że dwóch asystentów można wybrać na sześćset sposobów. Otrzymaliśmy tę liczbę, mnożąc dwadzieścia pięć i dwadzieścia cztery.
Zamień
Teraz rozważymy jeszcze jedną formułę kombinatoryczną. W tej części artykułu myPorozmawiajmy o permutacjach. Rozważ problem natychmiast na przykładzie. Weźmy kule bilardowe, mamy ich n-tą liczbę. Musimy obliczyć: ile jest możliwości ułożenia ich w rzędzie, czyli złożenie uporządkowanego zestawu.
Zacznijmy, jeśli nie mamy piłek, to również nie mamy opcji rozmieszczenia. A jeśli mamy jedną kulę, to układ też jest taki sam (matematycznie można to zapisać w następujący sposób: Р1=1). Dwie kule można ułożyć na dwa różne sposoby: 1, 2 i 2, 1. Zatem P2=2. Trzy kule można ułożyć na sześć sposobów (P3=6): 1, 2, 3; 1, 3, 2; 2, 1, 3; 2, 3, 1; 3, 2, 1; 3, 1, 2. A jeśli nie ma trzech takich piłek, ale dziesięć czy piętnaście? Wymienienie wszystkich możliwych opcji jest bardzo długie, wtedy z pomocą przychodzi nam kombinatoryka. Formuła permutacji pomoże nam znaleźć odpowiedź na nasze pytanie. Pn=nP(n-1). Jeśli spróbujemy uprościć wzór, otrzymamy: Pn=n (n - 1) … 21. I to jest iloczyn pierwszych liczb naturalnych. Taka liczba nazywana jest silnią i oznaczana jako n!
Rozważmy problem. Przywódca każdego ranka buduje swój oddział w linii (dwadzieścia osób). W oddziale jest trzech najlepszych przyjaciół - Kostia, Sasha i Lesha. Jakie jest prawdopodobieństwo, że będą obok siebie? Aby znaleźć odpowiedź na pytanie, musisz podzielić prawdopodobieństwo „dobrego” wyniku przez całkowitą liczbę wyników. Całkowita liczba permutacji to 20!=2,5 tryliona. Jak policzyć liczbę „dobrych” wyników? Załóżmy, że Kostia, Sasha i Lesha to jeden superman. Wtedy myMamy tylko osiemnaście przedmiotów. Liczba permutacji w tym przypadku wynosi 18=6,5 biliarda. Dzięki temu Kostya, Sasha i Lesha mogą dowolnie poruszać się między sobą w swojej niepodzielnej trójce, a to jeszcze 3!=6 opcji. Mamy więc w sumie 18 „dobrych” konstelacji!3! Musimy tylko znaleźć pożądane prawdopodobieństwo: (18!3!) / 20! Czyli około 0,016. Po przeliczeniu na wartość procentową okazuje się, że wynosi tylko 1,6%.
Zakwaterowanie
Teraz rozważymy kolejną bardzo ważną i niezbędną formułę kombinatoryczną. Zakwaterowanie to nasz kolejny problem, który proponujemy rozważyć w tej części artykułu. Będziemy się bardziej skomplikować. Załóżmy, że chcemy rozważyć możliwe permutacje, tylko nie z całego zbioru (n), ale z mniejszego (m). Oznacza to, że rozważamy permutacje n elementów przez m.
Podstawowe formuły kombinatoryki powinny być nie tylko zapamiętane, ale także zrozumiane. Nawet pomimo tego, że stają się bardziej skomplikowane, ponieważ mamy nie jeden parametr, a dwa. Załóżmy, że m \u003d 1, następnie A \u003d 1, m \u003d 2, a następnie A \u003d n(n - 1). Jeśli jeszcze bardziej uprościmy formułę i przejdziemy do notacji za pomocą silni, otrzymamy dość zwięzłą formułę: A \u003d n! / (n - m)!
Kombinacja
Rozważyliśmy prawie wszystkie podstawowe formuły kombinatoryki z przykładami. Przejdźmy teraz do ostatniego etapu rozważania podstawowego kursu kombinatoryki - poznania kombinacji. Teraz wybierzemy m pozycji z n, które mamy, natomiast wybierzemy je wszystkie na wszystkie możliwe sposoby. Czym zatem różni się to od zakwaterowania? Nie będziemyrozważ porządek. Ten nieuporządkowany zestaw będzie kombinacją.
Natychmiast wprowadź notację: C. Z n bierzemy rozmieszczenie m kulek. Przestajemy zwracać uwagę na porządek i otrzymujemy powtarzające się kombinacje. Aby otrzymać liczbę kombinacji, musimy liczbę rozmieszczeń podzielić przez m! (m silnia). To znaczy C \u003d A / m! Tak więc istnieje kilka sposobów wyboru spośród n kulek, w przybliżeniu równych liczbie wybrać prawie wszystko. Jest na to logiczne wyrażenie: wybranie małej ilości jest równoznaczne z wyrzuceniem prawie wszystkiego. Należy również wspomnieć w tym miejscu, że maksymalną liczbę kombinacji można osiągnąć, próbując wybrać połowę elementów.
Jak wybrać formułę do rozwiązania problemu?
Przeanalizowaliśmy szczegółowo podstawowe formuły kombinatoryki: rozmieszczenie, permutację i kombinację. Teraz naszym zadaniem jest ułatwienie wyboru niezbędnej formuły rozwiązania problemu w kombinatoryce. Możesz użyć następującego, dość prostego schematu:
- Zadaj sobie pytanie: czy kolejność elementów jest uwzględniona w tekście problemu?
- Jeśli odpowiedź brzmi „nie”, użyj formuły kombinacji (C=n! / (m!(n - m)!)).
- Jeśli odpowiedź brzmi „nie”, musisz odpowiedzieć na jeszcze jedno pytanie: czy wszystkie elementy są zawarte w kombinacji?
- Jeśli odpowiedź brzmi tak, użyj wzoru permutacji (P=n!).
- Jeśli odpowiedź brzmi „nie”, użyj wzoru alokacji (A=n! / (n - m)!).
Przykład
Rozważyliśmy elementy kombinatoryki, formuły i kilka innych zagadnień. Przejdźmy teraz dobiorąc pod uwagę prawdziwy problem. Wyobraź sobie, że masz przed sobą kiwi, pomarańczę i banana.
Pytanie pierwsze: na ile sposobów można je zmienić? Aby to zrobić, używamy wzoru permutacji: P=3!=6 sposobów.
Pytanie drugie: na ile sposobów można wybrać jeden owoc? Jest to oczywiste, mamy tylko trzy opcje - wybierz kiwi, pomarańczę lub banana, ale stosujemy formułę kombinacyjną: C \u003d 3! / (2!1!)=3.
Pytanie trzecie: na ile sposobów można wybrać dwa owoce? Jakie mamy opcje? Kiwi i pomarańcza; kiwi i banan; pomarańcza i banan. Oznacza to trzy opcje, ale łatwo to sprawdzić za pomocą wzoru kombinacji: C \u003d 3! / (1!2!)=3
Pytanie czwarte: na ile sposobów można wybrać trzy owoce? Jak widać, jest tylko jeden sposób, aby wybrać trzy owoce: weź kiwi, pomarańczę i banana. C=3! / (0!3!)=1.
Pytanie piąte: na ile sposobów możesz wybrać przynajmniej jeden owoc? Ten warunek oznacza, że możemy wziąć jeden, dwa lub wszystkie trzy owoce. Dlatego dodajemy C1 + C2 + C3=3 + 3 + 1=7. Oznacza to, że mamy siedem sposobów na pobranie przynajmniej jednego owocu ze stołu.
