Схема выбора с возвращением

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

Пусть а и b – элементы конечного множества.

Правило 1 (сложения). Если элемент а может быть выбран способами, а элемент b – способами, причем первые и вторые способы не пересекаются, то любой из элементов (а или b) можно выбрать способами.

Правило 2 (умножения). Если элемент а может быть выбран способами, а элемент b – способами, то оба элемента (а и b) в указанном порядке можно выбрать способами.

Схема выбора без возвращений

Пусть дано множество, состоящее из n различных элементов.

Размещением из n элементов по m элементов называется любое упорядоченное подмножество данного множества, содержащее m элементов.

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

Перестановкой из n элементов называется размещение из n элементов по n элементов. Число перестановок из n элементов обозначается .

Сочетанием из n элементов по m называется любое подмножество данного множества, которое содержит m элементов.

Два сочетания различны, если они отличаются хотя бы одним элементом, и обозначаются .

Схема выбора с возвращением

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

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

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

Формулы для вычислений приведены в таблице (первая строка без повторений, вторая с повторениями).

	Размещения	Перестановки	Сочетания

Пример 1. В ящике 100 деталей. Известно, что 50 из них – 1 сорта, 20 –
2-го, остальные – 3-го сорта. Сколько существует способов извлечения из ящика одной детали 1-го или 2 -го сорта?

Решение. Деталь 1-го сорта может быть извлечена способами, 2-го сорта – способами. По правилу суммы существует = 70 спо­собов извлечения одной детали первого или второго сорта.

Пример 2. Порядок вступления 12 участников конкурса определяется жребием. Сколько различных вариантов жеребьевки при этом возможно?

Решение. Каждый вариант отличается только порядком участников, т.е. перестановкой

Пример 3. Сколькими способами можно переставить буквы в слове ЛИМПОПО?

Решение. Букв всего 7, но среди них 2 буквы О и 2 буквы П, поэтому вычисляем по формуле перестановок с повторениями

Пример 4. В магазине есть 7 видов тортов. Сколькими способами можно составить набор, содержащий три торта?

Решение. Имеем выборку с повторением из 7 элементов по 3, причем важен только состав.

Пример 5. Пять человек вошли в лифт на 1-м этаже девятиэтажного дома. Сколькими способами пассажиры могут выйти из лифта на нужных этажах?

Решение. Каждый из 5 пассажиров может выйти на любом из 8 этажей. Имеем выборку с повторением, где важен и порядок и состав. Итак,

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

Решение. Имеем выборку без повторения из 10 элементов по 7, в которой важен только состав. То есть

.

Поиск по сайту: