Дискретная математика — теория счета

В повседневной жизни очень часто нужно выяснить количество всех возможных результатов для серии событий. Например, каким образом можно выбрать коллегию судей в составе 6 мужчин и 4 женщин из 50 мужчин и 38 женщин? Сколько различных 10-буквенных номеров PAN можно сгенерировать таким образом, чтобы первые пять букв были заглавными, следующие четыре — цифрами, а последняя — снова заглавной. Для решения этих задач используется математическая теория счета. Подсчет в основном охватывает фундаментальное правило подсчета, правило перестановки и правило комбинации.

Правила суммы и продукта

Правило суммы и правило продукта используются для разделения сложных задач подсчета на простые задачи.

• Правило суммы — если последовательность задач $T_1, T_2, \ dots, T_m$ может быть выполнена способами $w_1, w_2, \ dots w_m$ соответственно (условие состоит в том, что никакие задачи не могут быть выполнены одновременно), тогда Количество способов выполнить одну из этих задач: $w_1 + w_2 + \ dots + w_m$. Если мы рассмотрим две задачи A и B, которые не пересекаются (то есть $A \ cap B = \ emptyset$), то математически $ | A \ cup B | = | A | + | B | $

• Правило продукта — если последовательность задач $T_1, T_2, \ dots, T_m$ может быть выполнена способами $w_1, w_2, \ dots w_m$ соответственно, и каждая задача прибывает после возникновения предыдущей задачи, то есть $w_1 \ times w_2 \ times \ dots \ times w_m$ способы выполнения задач. Математически, если задача B появляется после задачи A, то $ | A \ times B | = | A | \ times | B | $

Правило суммы — если последовательность задач $T_1, T_2, \ dots, T_m$ может быть выполнена способами $w_1, w_2, \ dots w_m$ соответственно (условие состоит в том, что никакие задачи не могут быть выполнены одновременно), тогда Количество способов выполнить одну из этих задач: $w_1 + w_2 + \ dots + w_m$. Если мы рассмотрим две задачи A и B, которые не пересекаются (то есть $A \ cap B = \ emptyset$), то математически $ | A \ cup B | = | A | + | B | $

Правило продукта — если последовательность задач $T_1, T_2, \ dots, T_m$ может быть выполнена способами $w_1, w_2, \ dots w_m$ соответственно, и каждая задача прибывает после возникновения предыдущей задачи, то есть $w_1 \ times w_2 \ times \ dots \ times w_m$ способы выполнения задач. Математически, если задача B появляется после задачи A, то $ | A \ times B | = | A | \ times | B | $

пример

Вопрос — Мальчик живет в X и хочет пойти в школу в Z. Из своего дома X он должен сначала добраться до Y, а затем от Y до Z. Он может пройти X до Y на 3 автобусных маршрутах или 2 железнодорожных маршрутах. Оттуда он может выбрать либо 4 автобусных маршрута, либо 5 железнодорожных маршрутов, чтобы добраться до Z. Сколько путей можно пройти от X до Z?

Решение — От X до Y он может пойти путями $3 + 2 = 5$ (Rule of Sum). После этого он может перейти от Y к Z путями $4 + 5 = 9$ (Rule of Sum). Следовательно, от X до Z он может идти в $5 \ times 9 = 45$ (правило продукта).

Перестановки

Перестановка — это расположение некоторых элементов, в которых порядок имеет значение. Другими словами, Перестановка — это упорядоченная комбинация элементов.

Примеры

• Из множества S = {x, y, z}, взяв по два за раз, все перестановки имеют вид —

  $xy, yx, xz, zx, yz, zy$.

• Мы должны сформировать перестановку трехзначных чисел из набора чисел $S = \ lbrace 1, 2, 3 \ rbrace$. Различные трехзначные числа будут сформированы, когда мы организуем цифры. Перестановка будет = 123, 132, 213, 231, 312, 321

Из множества S = {x, y, z}, взяв по два за раз, все перестановки имеют вид —

$xy, yx, xz, zx, yz, zy$.

Мы должны сформировать перестановку трехзначных чисел из набора чисел $S = \ lbrace 1, 2, 3 \ rbrace$. Различные трехзначные числа будут сформированы, когда мы организуем цифры. Перестановка будет = 123, 132, 213, 231, 312, 321

Количество перестановок

Количество перестановок ‘n’ разных вещей, взятых ‘r’ за один раз, обозначается как $n_ {P_ {r}}$

$$n_ {P_ {r}} = \ frac {n!} {(n - r)!}$$

где $ n! = 1.2.3. \ dots (n — 1) .n $

Доказательство — пусть будет «n» разных элементов.

Есть n способов заполнить первое место. После заполнения первого места (n-1) количество элементов осталось. Следовательно, есть (n-1) способов занять второе место. После заполнения первого и второго места, (n-2) количество элементов осталось. Следовательно, есть (n-2) способы занять третье место. Теперь мы можем обобщить количество способов занять r-е место следующим образом: [n — (r – 1)] = n – r + 1

Итак, итого нет. способов пополнения с первого места до r-го места —

$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]$

Следовательно,

$ n_ {P_ {r}} = n! / (номер)! $

Некоторые важные формулы перестановки

• Если существует n элементов, из которых $a_1$ похожи в некотором роде, $a_2$ похожи на другие; $a_3$ похожи на третий тип и т. д., а $a_r$ — на $r ^ {th}$, где $(a_1 + a_2 + ... a_r) = n$.

  Тогда число перестановок этих n объектов равно = $ n! / [(a_1! (a_2!) \ dots (a_r!)] $.

• Количество перестановок из n различных элементов, принимающих n элементов за раз = $n_ {P_n} = n!$

• Количество перестановок из n разнородных элементов, занимающих r элементов за один раз, когда x конкретных вещей всегда занимают определенные места = $n-x_ {p_ {rx}}$

• Число перестановок n разнородных элементов, когда r указанных вещей всегда собираются вместе, равно — $ r! (П-р + 1)! $

• Число перестановок n разнородных элементов, когда r указанных вещей никогда не объединяются, составляет — $ n! — [r! (П-г + 1)!] $

• Количество циклических перестановок n различных элементов, взятых по x элементам за раз = npx/x$^ np_ {x} / x$

• Количество циклических перестановок из n разных вещей = npn/n$^ np_ {n} / n$

Если существует n элементов, из которых $a_1$ похожи в некотором роде, $a_2$ похожи на другие; $a_3$ похожи на третий тип и т. д., а $a_r$ — на $r ^ {th}$, где $(a_1 + a_2 + ... a_r) = n$.

Тогда число перестановок этих n объектов равно = $ n! / [(a_1! (a_2!) \ dots (a_r!)] $.

Количество перестановок из n различных элементов, принимающих n элементов за раз = $n_ {P_n} = n!$

Количество перестановок из n разнородных элементов, занимающих r элементов за один раз, когда x конкретных вещей всегда занимают определенные места = $n-x_ {p_ {rx}}$

Число перестановок n разнородных элементов, когда r указанных вещей всегда собираются вместе, равно — $ r! (П-р + 1)! $

Число перестановок n разнородных элементов, когда r указанных вещей никогда не объединяются, составляет — $ n! — [r! (П-г + 1)!] $

Количество циклических перестановок n различных элементов, взятых по x элементам за раз = npx/x$^ np_ {x} / x$

Количество циклических перестановок из n разных вещей = npn/n$^ np_ {n} / n$

Некоторые проблемы

Задача 1 — Сколько способов мы можем переставить из 6 разных карт?

Решение — Поскольку мы берем 6 карт одновременно из колоды из 6 карт, перестановка будет $ ^ 6P_ {6} = 6! = 720 $

Задача 2 — Как можно расположить буквы слова «ЧИТАТЕЛЬ»?

Решение — В слове «ЧИТАТЕЛЬ» есть слово из 6 букв (2 E, 1 A, 1D и 2R.).

Перестановка будет $ = 6! / \: [(2!) (1!) (1!) (2!)] = 180. $

Задача 3. Каким образом можно расположить буквы слова «ОРАНЖЕВЫЙ» так, чтобы согласные занимали только четные позиции?

Решение — в слове «ОРАНЖЕВЫЙ» 3 гласных и 3 согласных. Количество способов расположения согласных между собой $ = ^ 3P_ {3} = 3! = 6 $ Оставшиеся 3 вакантных места будут заполнены 3 гласными в $ ^ 3P_ {3} = 3! = 6 $ способов. Следовательно, общее число перестановок составляет $6 \ times 6 = 36$

Комбинации

Комбинация — это выбор некоторых заданных элементов, в которых порядок не имеет значения.

Количество всех комбинаций из n вещей, взятых по r, составляет —

$$ ^ nC_ {{r}} = \ frac {n! } {r! (nr)! } $$

Проблема 1

Найдите число подмножеств множества $\ lbrace1, 2, 3, 4, 5, 6 \ rbrace$, содержащего 3 элемента.

Решение

Мощность набора составляет 6, и мы должны выбрать 3 элемента из набора. Здесь порядок не имеет значения. Следовательно, количество подмножеств будет 6C3=20$^ 6C_ {3} = 20$.

Проблема 2

В комнате 6 мужчин и 5 женщин. Во сколько способов мы можем выбрать 3 мужчин и 2 женщин из комнаты?

Решение

Количество способов выбрать 3 женщин из 6 мужчин составляет 6C3$^ 6C_ {3}$, а количество способов выбрать 2 женщин из 5 женщин — 5C2$^ 5C_ {2}$

Следовательно, общее количество способов составляет — 6C3 times5C2=20 times10=200$^ 6C_ {3} \ times ^ 5C_ {2} = 20 \ times 10 = 200$

Проблема 3

Сколько способов вы можете выбрать 3 отдельные группы из 3 студентов из общего количества 9 студентов?

Решение

Давайте нумеруем группы как 1, 2 и 3

Для выбора 3 учеников для 1- ^й группы, количество способов — 9C3$^ 9C_ {3}$

Количество способов выбора 3 учеников для 2- ^й группы после выбора 1-й группы — 6C3$^ 6C_ {3}$

Количество способов выбора 3 учеников для 3- ^й группы после выбора 1- ^й и 2- ^й группы — 3C3$^ 3C_ {3}$

Следовательно, общее количество способов $= ^ 9C_ {3} \ times ^ 6C_ {3} \ times ^ 3C_ {3} = 84 \ times 20 \ times 1 = 1680$

Личность Паскаля

Идентичность Паскаля, впервые полученная Блезом Паскалем в 17 веке, гласит, что количество способов выбора k элементов из n элементов равно сумме количества способов выбора (k-1) элементов из (n-1) элементов. и количество способов выбора элементов из n-1 элементов.

Математически для любых натуральных чисел k и n: nCk=n−1Ck−1+n−1Ck$^ nC_ {k} = ^ n {^ -} ^ 1C_ {k-1} + ^ n {^ -} ^ 1 {C_k}$

Доказательство —

n−1Ck−1+n−1Ck $$^ 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}}$

Принцип голубиных отверстий

В 1834 году немецкий математик Питер Густав Лежен Дирихле сформулировал принцип, который он назвал принципом ящика. Теперь это известно как принцип «голубиного отверстия».

Принцип «Голубиная лунка» гласит, что если голубиных отверстий меньше, чем общее число голубей, и каждый голубь помещается в голубиную лунку, то должна быть как минимум одна лунка голубя с более чем одним голубем. Если n голубей помещают в m голубых отверстий, где n> m, то есть отверстие с более чем одним голубем.

Примеры

• Десять человек находятся в комнате, и они принимают участие в рукопожатиях. Если каждый человек пожимает руку хотя бы один раз, и никто не жмет руку одного и того же человека более одного раза, то два человека приняли участие в одинаковом количестве рукопожатий.

• В классе из 30 человек должно быть не менее двух человек, имена которых начинаются с одинакового алфавита.

Десять человек находятся в комнате, и они принимают участие в рукопожатиях. Если каждый человек пожимает руку хотя бы один раз, и никто не жмет руку одного и того же человека более одного раза, то два человека приняли участие в одинаковом количестве рукопожатий.

В классе из 30 человек должно быть не менее двух человек, имена которых начинаются с одинакового алфавита.

Принцип включения-исключения

Принцип включения-исключения вычисляет кардинальное число объединения нескольких непересекающихся множеств. Для двух множеств A и B принцип гласит:

$ | A \ cup B | = | A | + | B | — | A \ cap B | $

Для трех наборов A, B и C принцип гласит:

$ | A \ чашка B \ чашка C | = | A | + | B | + | C | — | A \ cap B | — | A \ cap C | — | B \ cap C | + | A \ cap B \ cap C | $

Обобщенная формула —

$| \ bigcup_ {i = 1} ^ {n} A_i | = \ sum \ limit_ {1 \ leq i <j <k \ leq n} | A_i \ cap A_j | + \ sum \ limit_ {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 |$

Проблема 1

Сколько целых чисел от 1 до 50 кратно 2 или 3, но не оба?

Решение

От 1 до 100 чисел $50/2 = 25$, кратных 2.

Есть $50/3 = 16$ чисел, которые кратны 3.

Есть $50/6 = 8$ чисел, которые кратны 2 и 3.

Итак, $| A | = 25$, $| B | = 16$ и $| A \ cap B | = 8$.

$ | A \ cup B | = | A | + | B | — | A \ cap B | = 25 + 16 — 8 = 33 $

Проблема 2

В группе из 50 учеников 24 любят холодные напитки, а 36 — горячие напитки, и каждому ученику нравится по крайней мере один из двух напитков. Кто любит кофе и чай?

Решение

Пусть X — группа студентов, которые любят холодные напитки, а Y — группа людей, которые любят горячие напитки.

Итак, $ | X \ чашка Y | = 50 $,$ | X | = 24 $,$ | Y | = 36 $

$ | X \ cap Y | = | X | + | Y | — | X \ чашка Y | = 24 + 36 — 50 = 60 — 50 = 10 $

Следовательно, есть 10 студентов, которые любят чай и кофе.