Основные формулы комбинаторики

Лекция №1.

Формулы комбинаторики.

Рассмотрим некоторое множество, состоящее из n различных элементов. Из элементов этого множества могут быть образованы различные подмножества (комбинации) из k элементов (k ≤ n).

На практике часто применяются следующие формулы комбинаторики:

Определение: Сочетаниями из n различных элементов по k элементов называются такие комбинации из k элементов, которые отличаются друг от друга только составом своих элементов, обозначают .

Число сочетаний из n различных элементов по k элементов вычисляется по формуле:

Если число предметов в совокупности равно n и производится выбор k предметов без возвращения и без учёта порядка, то количество всех элементарных исходов находится по формуле числа сочетаний.

Пример 1.

Найти количество способов заполнения карточки спортлото «6 из 49».

Решение.

В данной задаче эксперимент состоит в том, что случайным образом выбирается 6 чисел из 49 в карточке спортлото. Пространство элементарных исходов здесь образуют различные кортежи из 6 чисел, которые выбирают без учёта порядка из чисел:

1, 2, 3, …, 49.

Количество всех возможных способов (всех элементарных событий) находится по формуле числа сочетаний:

Если число предметов в совокупности равно n и производится выбор k предметов с возвращением (с повторениями) без учёта порядка, то количество всех элементарных исходов будет равно:

Пример 2.

В магазине продается 8 видов онигири. Петя хочет купить 6 штук либо одинаковых, либо разных видов онигири. Сколькими способами Петя может осуществить выбор?

Решение.

В данной задаче число вариантов будет равно числу сочетаний из 8 элементов по 6 с возвращением (с повторениями) без учёта порядка:

Определение: Перестановками из k различных элементов называются такие комбинации из этих элементов, которые отличаются друг от друга только порядком своих элементов, обозначают P_k

Число перестановок из k элементов вычисляется по формуле:

P_k = k!

Пример 3.

Найти количество вариантов выставить 6 людей в ряд для группового фотоснимка.

Решение.

В данной задаче число вариантов будет равно числу перестановок из 6 различных вариантов:

P₆ = 6! = 1∙2∙3∙4∙5∙6 = 720

Если из k переставляемых элементов l повторяются, то число перестановок будет равно:

Пример 4.

Сколько «слов» можно составить, переставляя буквы в слове БАРАБАНЩИК.

Решение:

В данной задаче число вариантов будет равно числу перестановок из 10 различных вариантов, среди которых элемент «Б» повторяется 2 раза, «А» – 3 раза:

=302 400

Определение: Размещениями из n различных элементов по k элементов называются такие комбинации из k элементов, которые отличаются друг от друга либо составом элементов, либо порядком своих элементов, обозначают

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

Если выбор производится k предметов без возвращения и с учётом порядка из совокупности в n предметов, то количество всех элементарных исходов находится по формуле числа размещений.

Пример 5.

В виварии имеются 10 подопытных животных. Найти количество способов выбора по одному животному для трёх различных экспериментов.

Решение.

Число различных вариантов выбора подопытных животных из вивария, содержащего 10 животных, по одному животному для трёх экспериментов будет равно

Если число предметов в совокупности равно n и производится выбор k предметов с возвращением и учётом порядка, то количество всех элементарных исходов будет равно:

Пример 6.

Сколько существует различных шестизначных телефонных номеров?

Решение.

Набор телефонного номера из шести цифр (k=6) можно рассматривать как результат выбора с возвращением и с учѐтом порядка шести цифр из следующих десяти: 0, 1, …, 9 (n =10).

Пространство элементарных исходов в этой задаче образует различные кортежи из шести цифр, например, 210635, 201356, 112345, ….

Всего различных телефонных номеров будет:

= 1 000 000

Очевидно, что из этого количества вариантов нужно убрать вариант номера состоящий из шести нулей. Поэтому, итоговым результатом будет общее количество вариантов телефонных номеров равное 999 999.

Формулы комбинаторики используют при непосредственном вычислении вероятностей.

Правила сложения и умножения в комбинаторике.

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

Пример 7. В группе 30 человек. Необходимо выбрать старосту и профорга. Сколькими способами можно это сделать?

Решение. Старостой может быть выбран любой из 30 учащихся, то есть существует 30 способов выбора старосты. После того, как староста уже выбран, профоргом можно выбрать любого из оставшихся 29 учащихся. Согласно правилу умножения, общее число способов выбора старосты и профорга равно 30 · 29 = 870.

Правило умножения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n₁ способами, второе действие n₂ способами, третье – n₃ способами и так до k-го действия, которое можно выполнить n_k способами, то все k действий вместе могут быть выполнены N = n₁∙n₂∙n₃∙…∙n_k cпособами.

Пример 8. Необходимо составить варианты контрольной работы, каждый из которых должен содержать три задачи. Первая задача выбирается из любого параграфа I главы сборника, вторая – из любого параграфа II главы, а третья – из любого параграфа III главы. Сколько вариантов контрольной работы можно составить, если I и III глава содержат два параграфа, а II глава – три параграфа?

Решение.

Нужно найти число способов выбора трех задач из трех соответствующих глав. Первую задачу можно выбрать двумя способами, так как I глава содержит 2 параграфа. Вторую задачу можно выбрать тремя способами, так как II глава содержит 3 параграфа. Третью задачу можно выбрать двумя способами, так как III глава содержит 2 параграфа. Общее число способов выбора трех задач равно 2·3·2 = 12. Таким образом, можно составить 12 различных вариантов контрольной работы.

Эти правила дают удобный универсальный метод решения многих задач.

Задание.

• Изучить материал лекции.

• Составить схему для применения формул комбинаторики.

• Выучить формулы комбинаторики и их названия.

• Подготовить вопросы по теме лекции.