- •Содержание
- •Понятие комбинаторной задачи
- •История возникновения и развития комбинаторики
- •Конечные множества
- •Операции над множествами
- •Декартово произведение множеств а и в
- •Задачи для самостоятельного решения
- •Нахождение числа всех подмножеств данного множества
- •Понятие факториала
- •Задания для самостоятельного решения
- •Правила суммы и произведения
- •Задачи для самостоятельного решения
- •Вопросы для самопроверки
- •Виды соединений без повторений
- •Перестановки без повторений
- •Задачи для самостоятельного решения
- •Размещения без повторений
- •Задачи для самостоятельного решения
- •Сочетания без повторений
- •Свойства чисел c
- •Задачи для самостоятельного решения
- •Вопросы для самопроверки
- •Виды соединений с повторениями Сочетания и размещения с повторениями
- •Перестановки с повторениями
- •Задачи для самостоятельного решения
- •Бином Ньютона
- •Задачи для самостоятельного решения
- •Вопросы для самопроверки
- •Контрольные вопросы
- •Примеры решения некоторых комбинаторных задач
- •Задачи для самостоятельного решения
- •Примеры решения некоторых комбинаторных задач
- •Задачи для самостоятельного решения
- •Примеры решения некоторых комбинаторных задач
- •Задачи для самостоятельного решения
- •Примеры решения некоторых комбинаторных задач
- •Задачи для самостоятельного решения
- •Формула включений и исключений
- •Примеры решения некоторых комбинаторных задач
- •Задачи для самостоятельного решения по курсу «Комбинаторика»
Вопросы для самопроверки
1. Что изучает раздел математики комбинаторика?
2. Какие задачи называют комбинаторными?
3. Докажите следующие утверждения.
а) Для любых множеств А и В справедливо равенство:
B=(A B) (B \ A).
б) Для произвольных множеств А и В справедливо равенство:
(A B) (B \ A)=.
в) Для любых множеств А и В справедливо: число элементов разности множеств В и А равно разности числа элементов множества В и числа элементов пересечения множества А и множества В.
4. Чему равно число элементов объединения двух непересекающихся множеств?
5. Чему равно число элементов объединения двух множеств?
6. Что означает запись п!?
7. Найдите число п! для п = 5; 6.
8. Может ли краткая десятичная запись числа п! оканчиваться ровно пятью нулями?
9. Сколько подмножеств имеет трехэлементное множество? Сколько подмножеств имеет пятиэлементное множество? Сколько подмножеств имеет п-элементное множество?
Виды соединений без повторений
Большинство комбинаторных задач связано с операциями над конечными множествами. Рассмотрим некоторые из них.
Упорядочение конечного множества. Эта операция приводит к понятию перестановки из n элементов и к задаче определения числа всех возможных перестановок из n элементов.
Выбор подмножеств некоторого конечного множества. Это приводит к понятию сочетания и к задаче определения числа всех возможных сочетаний из n – элементов по k – элементов.
Выбор упорядоченных подмножеств некоторого конечного множества. Это приводит к понятию размещения и к задаче определения числа всех возможных размещений из n – элементов по k – элементов.
Научное обоснование теории сочетаний и перестановок дал в 1666 году немецкий учёный В. Лейбниц (1646–1716) в своей работе «Размышления о комбинаторном искусстве».
Перестановки без повторений
Четыре горе – музыканта из баcни Крылова долго пересаживались с места на место. В ходе этого творческого поиска осёл внёс предложение: «Мы, верно, уж поладим, коль рядом сядем». Попробовали – не помогло. Но в ряд можно сесть разными способами. Определим число всевозможных вариантов расположения четырёх музыкантов в ряд. Обозначим музыкантов следующим образом: А – Мартышка, В – Осёл, С – Козёл, Д – Мишка. Тогда варианты расположения будут такими:
АВСД, АВДС, АДВС, АДСВ, АСДВ, АСВД,
САВД, САДВ, СДАВ, СДВА, СВДА, СВАД,
ВСАД, ВСДА, ВДСА, ВДАС, ВАСД, ВАДС,
ДВАС, ДВСА, ДАВС, ДАСВ, ДСАВ, ДСВА.
Итого 24 варианта. Если говорить математическим языком, то мы составляем кортежи длины 4 из различных элементов четырёхэлементного множества.14
Определение. Упорядоченные подмножества длины n, составленные из элементов n-элементного множества, называют перестановками без повторений.
Число всех таких перестановок обозначают символом Р.
Теорема 6. Число различных перестановок из n элементов равно произведению последовательных натуральных чисел от 1 до n включительно, то есть Р=1 ∙2 ∙ 3 ∙ … ∙n=n!
При упорядочении n – элементного множества, какой-то элемент получит номер 1, какой-то номер 2 и так далее, какой-то из элементов получит номер n. Номер 1 может получить любой из элементов множества. Значит, выбор первого элемента можно осуществить n способами. Вторым может быть любой из оставшихся элементов, а значит, его можно выбрать (n – 1) способами. Третий элемент можно выбрать (n – 2) способами и т.д. Наконец, предпоследний можно выбрать двумя способами, а последний элемент только одним способом. По правилу произведения получаем, что общее число всевозможных перестановок из n элементов определяется по формуле: Р=n ∙ (n – 1) ∙ (n – 2) ∙ … ∙ 2 ∙ 1=n!
Теорема 6 доказана.
Задача 1. Сколько слов (не обязательно имеющих смысл) можно получить из букв слова «апельсин»?
Решение. Речь идет об упорядочении множества содержащего восемь элементов. Эта операция приводит к определению числа всех возможных перестановок из 8 элементов, то есть о вычислении Р8.
Р8=8!=1 2 3 4 5 6 7 8=40320 (перестановок).
Из этих комбинаций только одна – «спаниель» – является осмысленным словом русского языка, все остальные представляют собой бессмысленный набор букв15.
Ответ: 40320 перестановок.
Задача 2. Сколько различных пятизначных чисел можно записать с помощью цифр 1, 2, 3, 4, 5, если ни одна цифра в записи числа не повторяется?
Решение. Так как, для записи пятизначного числа необходимо использовать 5 цифр, то речь идет об упорядочении множества содержащего пять элементов. Найдём число всевозможных перестановок из пяти цифр:
Р=5!=1=120(чисел).
Ответ: 120 чисел.
Задача 3. Сколько различных пятизначных чисел можно записать с помощью цифр 0, 1, 2, 3, 4, если ни одна цифра в записи числа не повторяется?
Решение. Как и предыдущей задаче, найдём число всевозможных перестановок из 5 цифр: Р=5!.
Однако, если цифра 0 займет первое место, число станет четырехзначным, таких чисел Р=4!. Следовательно, искомое число Р–Р=5! – 4!=120 – 24=96 (чисел).
Ответ: 96 чисел.