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ę.