Упражнения

4. Абонент забыл две последние цифры номера телефона и набирает их наудачу. Каково наибольшее возможное число безуспешных попыток абонента?

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

6. В колоде 36 карт. Наудачу вынимают 3 карты. Каково число всех возможных комбинаций? Сколько троек содержат по крайней мере один туз? Сколько тро­ек содержат только один туз? Сколько раз попадется комбинация дама—семерка—туз?

§3. Размещения, перестановки, сочетания

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

Пример 1. Пять бойцов сержанта Сбруева

В отделении сержанта Сбруева проходят службу 5 новобранцев: Белкин, Пенкин, Фенькин, Свечкин и Овечкин. В свободное от нарядов время сержант обучает их, как рассчитаться по порядку. По команде «В одну шеренгу становись!» солдаты выстраиваются справа от Сбруева и по команде «По порядку номеров рассчитайсь!» производят расчет: «первый-второй-третий-четвертый-пятый». После этого сержант перестраивает но­вобранцев по-новому и расчет повторяется. Сколько раз может Сбруев повторить это упражнение, используя только разные способы построения солдат?

Решение. Договоримся указывать порядок расположения солдат первыми буквами их фамилий. Например, комбинация ПСОФБ означает, что первым является Пенкин, вторым — Свечкин и т.д. Все комбинации от­личаются одна от другой порядком букв и называются перестановками из пяти букв. Нам нужно найти число всех таких перестановок. Сначала мы выведем общую формулу, а потом закончим обсуждение примера.

Пусть дано множество из n элементнов. Занумеруем все элементы каким-нибудь способом от 1 до n (в случае с новобранцами п = 5). Ясно, что занумеровать можно многими способами.

Определение. Перестановкой из п элементов называется всякий способ нумерации этих элементов.*

* Более подробно о перестановках будет сказано в гл. VIII «Математические структуры».

Теорема 2. Число всех различных перестановок из п элементов равно n!

Доказательство. Всякую перестановку из п элементов можно получить с помощью п действий: первое дей­ствие — выбор первого элемента, второе действие — вы­бор второго элемента, и т.д., наконец, n-е действие — выбор элемента с номером п.

Первый элемент можно выбрать п различными способами; второй выбирается из оставшихся n – 1 элемен­тов, поэтому число всех способов выполнения второго действия будет n – 1. После выбора второго элемента их останется п – 2, следовательно, число способов, которы­ми можно выполнить третье действие, будет п – 2. Та­ким образом, число способов, которыми выполняется очередное действие, будет на единицу меньше предыду­щего. Следовательно, четвертое действие можно выпол­нить (п – 2) способами, пятое — (п – 4) способами и т.д., наконец, последнее действие — одним способом.

По правилу умножения (теорема 1) число всех способов выполнения действий, т.е. число всех перестано­вок, равно п(п – 1)(п – 2) • ... • 1 = n!. Теорема доказана.

Число всех перестановок из n элементов обозначают P_n. Согласно теореме 1 его можно найти по формуле

Рп = n!. (4)

Например, в случае с новобранцами (n = 5) мы получим P₅ = 5! = 120.