Элементы комбинаторики

Элементы комбинаторики, теории множеств и математической логики.

Комбинаторика

- это раздел математики, посвященный решению задач выбора и расположения элементов некоторого, как правило, конечного множества в соответствии с заданными правилами.

Множество

- это всякая совокупность элементов произвольного рода, обладающая некоторым общим свойством, образует множество (соединение).

Примеры множеств:

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

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

• Множество, состоящее из n элементов, называется упорядоченным , если каждому элементу этого множества поставлено в соответствие натуральное число от 1 до n таким образом, что различным элементам соответствуют различные натуральные числа.
• Всякое конечное множество можно упорядочить.

Правило суммы

• Пусть некоторый предмет А может быть выбран m способами, а другой предмет В может быть выбран n способами. Тогда имеется m + n возможностей выбрать либо предмет А, либо предмет В.

Правило суммы

В

А

Задача 1

• От сквера Кирова до академгородка можно проехать через Ангарский мост, плотину и новый мост. В первом случае количество дорог равно 2, во втором — 2 , в третьем — 3. Сколькими способами можно добраться от сквера Кирова до академгородка ?

Решение

2+2+3=?

Правило произведения

Пусть некоторый предмет А может быть выбран m способами, а другой предмет В может быть выбран n способами. Тогда имеется m n возможностей выбрать предмет А и предмет В.

Правило произведения

В

и

А



В

А



В

А



В

А

Задача 2

• В киоске продают 5 видов конвертов и 4 вида открыток. Сколькими способами можно купить конверт и открытку?

Решение

5 · 4 = ?

Задача 3

• Сколькими способами можно выбрать гласную и согласную буквы из слова КОНВЕРТ?

Решение

• Гласную можно выбрать двумя способами.
• Согласную — пятью способами.
• Ответ. ____________?

Факториал

• произведение всех натуральных чисел от 1 до n включительно (читается n–факториал).

n! = 1•2•3•…•n

• Замечание: 0! = 1! =1.

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

• Число различных способов, которыми может быть упорядочено данное множество, состоящее из n элементов, называется числом перестановок множества и обозначается P n .

Перестановки без повторений

Размещения

• Число упорядоченных k элементных подмножеств множества из n элементов называется числом размещений из n элементов по k и обозначается

Размещения

Размещения с повторениями

Размещения без повторений

Сочетания

• Если из n элементов составлять группы по m элементов в каждой, не обращая внимания на порядок элементов в группе, то получившиеся при этом комбинации называются сочетаниями без повторений из n элементов по m .

Сочетания

Сочетания без повторений

Сочетания с повторениями

Свойства сочетаний