Matematyka dyskretna - teoria liczenia
W życiu codziennym niejednokrotnie trzeba poznać liczbę wszystkich możliwych wyników serii wydarzeń. Na przykład, na ile sposobów można wybrać komisję sędziowską składającą się z 6 mężczyzn i 4 kobiet spośród 50 mężczyzn i 38 kobiet? Ile różnych 10-literowych numerów PAN można wygenerować w taki sposób, że pierwsze pięć liter to wielkie litery, następne cztery to cyfry, a ostatnia jest znowu wielką literą. Do rozwiązania tych problemów stosuje się matematyczną teorię liczenia.Counting obejmuje głównie podstawową regułę liczenia, regułę permutacji i regułę kombinacji.
Zasady dotyczące sum i produktów
Plik Rule of Sum i Rule of Product służą do rozkładania trudnych problemów liczenia na proste problemy.
The Rule of Sum- Jeśli sekwencja zadań $ T_1, T_2, \ dots, T_m $ może być wykonana odpowiednio w $ w_1, w_2, \ dots w_m $ (pod warunkiem, że żadne zadania nie mogą być wykonywane jednocześnie), to liczba sposobów jedno z tych zadań to $ w_1 + w_2 + \ dots + w_m $. Jeśli weźmiemy pod uwagę dwa zadania A i B, które są rozłączne (tj. $ A \ cap B = \ emptyset $), to matematycznie $ | A \ cup B | = | A | + | B | $
The Rule of Product- Jeśli sekwencja zadań $ T_1, T_2, \ dots, T_m $ może być wykonana odpowiednio na sposoby $ w_1, w_2, \ dots w_m $ i każde zadanie przychodzi po wystąpieniu poprzedniego zadania, to jest $ w_1 \ times w_2 \ times \ dots \ times w_m $ sposoby wykonywania zadań. Matematycznie, jeśli zadanie B pojawia się po zadaniu A, to $ | A \ razy B | = | A | \ times | B | $
Przykład
Question- Chłopiec mieszka w X i chce iść do szkoły w Z. Ze swojego domu X musi najpierw dotrzeć do Y, a następnie Y do Z. Może jechać od X do Y 3 liniami autobusowymi lub 2 trasami kolejowymi. Stamtąd może wybrać 4 linie autobusowe lub 5 tras pociągów, aby dotrzeć do Z. Ile jest sposobów, aby przejść z X do Z?
Solution- Od X do Y, może przejść 3 $ + 2 = 5 $ sposobów (zasada sumy). Następnie może przejść od Y do Z w 4 $ + 5 = 9 $ sposobów (reguła sumy). Stąd od X do Z może iść 5 $ \ times 9 = 45 $ drogami (zasada iloczynu).
Permutacje
ZA permutationto układ niektórych elementów, w których liczy się kolejność. Innymi słowy, permutacja jest uporządkowaną kombinacją elementów.
Przykłady
Ze zbioru S = {x, y, z}, biorąc po dwa naraz, wszystkie permutacje są -
$ xy, yx, xz, zx, yz, zy $.
Musimy utworzyć permutację trzycyfrowych liczb ze zbioru liczb $ S = \ lbrace 1, 2, 3 \ rbrace $. Po ułożeniu cyfr zostaną utworzone różne liczby trzycyfrowe. Permutacja wyniesie = 123, 132, 213, 231, 312, 321
Liczba permutacji
Liczba permutacji „n” różnych rzeczy wykonywanych jednocześnie „r” jest oznaczona przez $ n_ {P_ {r}} $
$$ n_ {P_ {r}} = \ frac {n!} {(n - r)!} $$
gdzie $ n! = 1,2,3. \ dots (n - 1). n $
Proof - Niech będzie „n” różnych elementów.
Istnieje wiele sposobów na zajęcie pierwszego miejsca. Po wypełnieniu pierwszego miejsca (n-1) zostaje liczba elementów. Stąd jest (n-1) sposobów na zajęcie drugiego miejsca. Po wypełnieniu pierwszego i drugiego miejsca zostaje (n-2) liczba elementów. Stąd jest (n-2) sposoby na zajęcie trzeciego miejsca. Możemy teraz uogólnić liczbę sposobów wypełnienia r-tego miejsca jako [n - (r – 1)] = n – r + 1
Więc w sumie nie. sposobów na zapełnienie miejsca od pierwszego do r-tego miejsca -
$ n_ {P_ {r}} = n (n-1) (n-2) ..... (nr + 1) $
$ = [n (n-1) (n-2) ... (nr + 1)] [(nr) (nr-1) \ dots 3.2.1] / [(nr) (nr-1) \ dots 3.2.1] $
W związku z tym,
$ n_ {P_ {r}} = n! / (nr)! $
Kilka ważnych wzorów permutacji
Jeśli istnieje n elementów, z których $ a_1 $ jest podobnego rodzaju, $ a_2 $ są podobne do innego rodzaju; $ a_3 $ są podobne do trzeciego rodzaju i tak dalej, a $ a_r $ są $ r ^ {th} $ rodzaju, gdzie $ (a_1 + a_2 + ... a_r) = n $.
Wówczas liczba permutacji tych n obiektów wynosi = $ n! / [(a_1! (a_2!) \ dots (a_r!)] $.
Liczba permutacji n różnych elementów przyjmujących jednocześnie n elementów = $ n_ {P_n} = n! $
Liczba permutacji n odmiennych elementów przyjmujących r elementów naraz, gdy x poszczególnych rzeczy zawsze zajmuje określone miejsca = $ n-x_ {p_ {rx}} $
Liczba permutacji n różnych elementów, gdy r określone rzeczy zawsze się łączą, wynosi - $ r! (n − r + 1)! $
Liczba permutacji n różnych elementów, gdy r określone rzeczy nigdy się nie łączą, wynosi - $ n! - [r! (n − r + 1)!] $
Liczba permutacji cyklicznych n różnych elementów przyjmowanych w czasie x elementów = $ ^ np_ {x} / x $
Liczba permutacji cyklicznych n różnych rzeczy = $ ^ np_ {n} / n $
Trochę problemów
Problem 1 - Z zestawu 6 różnych kart, na ile sposobów możemy to permutować?
Solution- Ponieważ bierzemy jednocześnie 6 kart z talii 6 kart, permutacja będzie wynosić $ ^ 6P_ {6} = 6! = 720 $
Problem 2 - Na ile sposobów można ułożyć litery słowa „CZYTELNIK”?
Solution - Słowo „CZYTNIK” składa się z 6 liter (2 E, 1 A, 1D i 2R.).
Permutacja wyniesie $ = 6! / \: [(2!) (1!) (1!) (2!)] = 180. $
Problem 3 - W jaki sposób można ułożyć litery słowa „POMARAŃCZOWY”, aby spółgłoski zajmowały tylko pozycje parzyste?
Solution- W słowie „POMARAŃCZOWY” są 3 samogłoski i 3 spółgłoski. Liczba sposobów ułożenia spółgłosek między sobą $ = ^ 3P_ {3} = 3! = 6 $. Pozostałe 3 wolne miejsca zostaną wypełnione 3 samogłoskami w $ ^ 3P_ {3} = 3! = 6 $ sposobów. Stąd całkowita liczba permutacji wynosi 6 $ \ razy 6 = 36 $
Kombinacje
ZA combination to wybór pewnych elementów, w których kolejność nie ma znaczenia.
Liczba wszystkich kombinacji n rzeczy branych na raz r to -
$$ ^ nC_ {{r}} = \ frac {n! } {r! (nr)! } $$
Problem 1
Znajdź liczbę podzbiorów zbioru $ \ lbrace1, 2, 3, 4, 5, 6 \ rbrace $ posiadającego 3 elementy.
Solution
Kardynalność zestawu wynosi 6 i do wyboru mamy 3 elementy z zestawu. Tutaj kolejność nie ma znaczenia. Stąd liczba podzbiorów będzie wynosić $ ^ 6C_ {3} = 20 $.
Problem 2
W pokoju jest 6 mężczyzn i 5 kobiet. Na ile sposobów możemy wybrać z pokoju 3 mężczyzn i 2 kobiety?
Solution
Liczba sposobów wyboru 3 mężczyzn spośród 6 mężczyzn to $ ^ 6C_ {3} $, a liczba sposobów wyboru 2 kobiet z 5 kobiet to $ ^ 5C_ {2} $
Stąd całkowita liczba sposobów wynosi - $ ^ 6C_ {3} \ times ^ 5C_ {2} = 20 \ times 10 = 200 $
Problem 3
Na ile sposobów możesz wybrać 3 różne grupy po 3 uczniów spośród łącznie 9 uczniów?
Solution
Ponumerujmy grupy jako 1, 2 i 3
Do wyboru 3 studentów na 1 st grupy, liczba sposobów - $ ^ 9C_ {3} $
Liczba sposobów wyboru 3 studentów do 2 nd grupy po wybraniu 1st grupę - $ ^ 6C_ {3} $
Liczba sposobów wyboru 3 studentów na 3 -ciej grupy po wybraniu 1 st i 2 nd Group - $ ^ 3C_ {3} $
Stąd całkowita liczba sposobów $ = ^ 9C_ {3} \ times ^ 6C_ {3} \ times ^ 3C_ {3} = 84 \ times 20 \ times 1 = 1680 $
Tożsamość Pascala
Tożsamość Pascala, po raz pierwszy wyprowadzona przez Blaise'a Pascala w XVII wieku, stwierdza, że liczba sposobów wyboru k elementów z n elementów jest równa sumie sposobów wyboru (k-1) elementów z (n-1) elementów oraz liczbę sposobów wyboru elementów z n-1 elementów.
Matematycznie dla dowolnych dodatnich liczb całkowitych k i n: $ ^ nC_ {k} = ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k} $
Proof -
$$ ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k} $$
$ = \ frac {(n-1)! } {(k-1)! (nk)! } + \ frac {(n-1)! } {k! (nk-1)! } $
$ = (n-1)! (\ frac {k} {k! (nk)!} + \ frac {nk} {k! (nk)!}) $
$ = (n-1)! \ frac {n} {k! (nk)! } $
$ = \ frac {n! } {k! (nk)! } $
$ = n_ {C_ {k}} $
Zasada gołębnika
W 1834 roku niemiecki matematyk Peter Gustav Lejeune Dirichlet sformułował zasadę, którą nazwał zasadą szuflady. Teraz jest znana jako zasada szufladkowania.
Pigeonhole Principlestwierdza, że jeśli jest mniej dołków niż całkowita liczba gołębi, a każdy gołąb jest umieszczony w gołębniku, to musi istnieć co najmniej jeden dołek z więcej niż jednym gołębiem. Jeśli n gołębi jest umieszczonych w m przegródkach, gdzie n> m, jest dołek z więcej niż jednym gołębiem.
Przykłady
Dziesięciu mężczyzn jest w pokoju i biorą udział w uściskach dłoni. Jeśli każda osoba przynajmniej raz poda sobie rękę i żaden mężczyzna nie podaje ręki temu samemu więcej niż jeden raz, to dwóch mężczyzn brało udział w tej samej liczbie uścisków dłoni.
W klasie liczącej 30 osób muszą być co najmniej dwie osoby, których imiona zaczynają się tym samym alfabetem.
Zasada włączenia-wykluczenia
Plik Inclusion-exclusion principleoblicza liczbę kardynalną sumy wielu nierozłącznych zbiorów. Dla dwóch zbiorów A i B zasada mówi:
$ | A \ filiżanka B | = | A | + | B | - | A \ czapka B | $
Dla trzech zestawów A, B i C zasada stanowi:
$ | A \ filiżanka B \ filiżanka C | = | A | + | B | + | C | - | A \ czapka B | - | A \ czapka C | - | B \ czapka C | + | A \ czapka B \ czapka C | $
Uogólniona formuła -
$ | \ bigcup_ {i = 1} ^ {n} A_i | = \ sum \ limits_ {1 \ leq i <j <k \ leq n} | A_i \ cap A_j | + \ sum \ limits_ {1 \ leq i < j <k \ leq n} | A_i \ cap A_j \ cap A_k | - \ dots + (- 1) ^ {\ pi-1} | A_1 \ cap \ dots \ cap A_2 | $
Problem 1
Ile liczb całkowitych od 1 do 50 to wielokrotności 2 lub 3, ale nie obu?
Solution
Od 1 do 100 są liczby 50/2 = 25 $, które są wielokrotnościami 2.
Istnieją liczby 50 $ / 3 = 16 $, które są wielokrotnościami 3.
Istnieją liczby 50 $ / 6 = 8 $, które są wielokrotnościami 2 i 3.
A więc $ | A | = 25 $, $ | B | = 16 $ i $ | A \ cap B | = 8 $.
$ | A \ filiżanka B | = | A | + | B | - | A \ czapka B | = 25 + 16 - 8 = 33 $
Problem 2
W grupie 50 uczniów 24 osoby lubią zimne napoje, a 36 - gorące napoje, a każdy uczeń lubi przynajmniej jeden z dwóch napojów. Ilu lubi kawę i herbatę?
Solution
Niech X będzie grupą uczniów lubiących zimne napoje, a Y grupą osób lubiących gorące napoje.
Więc $ | X \ miseczka Y | = 50 $, $ | X | = 24 $, $ | Y | = 36 $
$ | X \ cap Y | = | X | + | Y | - | X \ miseczka Y | = 24 + 36 - 50 = 60 - 50 = 10 $
Dlatego jest 10 uczniów, którzy lubią zarówno herbatę, jak i kawę.