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

Перестановками из n элементов называются различные упорядочения множества  X .
Из этого определения следует, что две перестановки отличаются только порядком элементов и их можно рассматривать как частный случай размещений.
Формула: Число различных перестановок без повторений вычисляется по формуле

$$P_n=n!=n \cdot (n-1) \cdot (n-2) \cdot ...\cdot 2 \cdot 1$$

Заметим, что в любую перестановку входят все элементы множества Х, причём ровно по одному разу. То есть перестановки одна от другой отличаются только порядком следования элементов и могут получиться одна из другой перестановкой элементов (отсюда и название).

 Пример. Сколькими способами можно разместить на полке 5 книг?

Решение. Способов размещения книг на полке существует столько, сколько существует различных перестановок из пяти элементов: $P_5=5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$ способов.

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

Задачи:

1. Сколькими способами могут встать в очередь в билетную кассу: 1) 3 человека; 2) 5 человек?

Решение.

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

Категория: Комбинаторика | Просмотров: 60 | Добавил: Admin | Дата: 07.11.2018 | Комментарии (0)

Правило суммы. Если объект Х можно выбрать n способами, а объект Y можно выбрать m способами, причём эти способы выбора несовместны, то объект «Х или Y» можно выбрать n+m способами.

Несовместность способов выбора означает, что ни один способ выбора объекта Х не совпадает ни с одним способом выбора объекта Y.

Пример 1. Сколькими разными способами можно заказать напиток в кафе, где есть 8 видов сока и 5 видов минеральной воды?

Решение. Напиток – это или сок (объект Х), или минеральная вода (объект Y). Сок можно выбрать 8-ю разными способами, минеральную воду – 5-ю, причем способы выбора несовместны. Тогда по правилу суммы напиток (объект «Х или Y») можно выбрать 8+5=13-ю способами.

Пример 2. Пусть есть колода карт (36 листов). Объект Х – карта червовой масти – может быть выбран 9-ю разными способами. Объект Y – туз – может быть выбран 4-мя разными способами. Сколькими способами может быть выбран объект «Х или Y» – «червовая карта или туз»?

Решение. В этом примере правило суммы не работает, так как способы выбора объектов X и Y совместны: один из способов выбора объекта X совпадает с одним из способов выбора объекта Y (выбор червового туза – это и способ выбора объекта X, и способ выбора объекта Y).

Задача решается перебором подходящих карт: червовых карт 9 и ещё 3 туза (один уже учтён). Значит, червовую карту или туз ... Смотреть решение »

Категория: Комбинаторика | Просмотров: 40 | Добавил: Admin | Дата: 07.11.2018 | Комментарии (0)

Правило произведения: Если объект А может быть выбран из совокупности объектов $n$ способами и посла каждого такого выбора объект В может быть выбран $m$ способами, то пара объектов (А,В) в указанном порядке может быть выбрана $n \cdot m$ способами.

Пример. Сколько можно составить пятизначных чисел так, чтобы любые две соседние цифры были различны? ► Первую цифру можно выбрать 9-ю способами, вторую – 9-ю способами и т.д., следовательно, всего цифр можно составить $9\cdot9\cdot9\cdot9\cdot9=9^5$ способами (правило произведения).

 

Правило произведения в общем виде: Обозначим через $N$ число способов, которыми можно заполнить строчку $x_1,x_2 ,...,x_n$, если для выбора элемента $x_j$ существует $n_j$ вариантов $j=1,2,...,k$

Тогда

$$N=n_1\cdot n_2 \cdot ... \cdot n_k$$

Это правило иногда используется, когда речь идет о выборах элементов из $n$ элементов заданного множества, причем, выбор происходит без возвращения. В этом случае $n_1=n,n_2=n-1,...n_k=n-k$

Рассмотрим пример такой ситуации.

 

Задача 1.  Вам надо позвонить пятерым своим друзьям. Сколько имеется способов выстроить очередность этих звонков? Решение. Первый Ваш звонок может быть адресован любому из Ваших 5 друзей, второй – любому из 4 оставшихся друзей, которым вы еще не позвонили и т. д. Поэтому задача решается с помощью приведенной выше формулы при

... Смотреть решение »
Категория: Комбинаторика | Просмотров: 51 | Добавил: Admin | Дата: 07.11.2018 | Комментарии (0)

1 2 3 ... 13 14 »
close