3. Размещения
Если из данного множества предметов мы будем выбирать некоторое подмножество, то его будем называть выборкой. Выборки бывают упорядоченные и неупорядоченные. В упорядоченной выборке существенен порядок, в котором следуют ее элементы, другими словами, изменив порядок элементов, мы получим другую выборку. Например, из цифр 1, 2, 3, 4, 5 составляем трехзначные числа 123, 431, 524, ...и т.д. Это упорядоченные трехэлементные выборки, ведь 123 и 132 - разные числа. Другой пример: из 20 учащихся класса будем выбирать двух дежурных. Любая пара дежурных представляет собой неупорядоченную двухэлементную выборку, так как порядок их выбора не важен.
Определение.
Размещениями из n элементов по m (m
n)
называются упорядоченные m -элементные
выборки из данных n элементов. Из
определения следует, что размещения
отличаются друг от друга либо самими
элементами, либо их порядком.
Число размещений
из n по m обозначается
Чтобы
вывести формулу числа размещений,
заметим, что первый элемент в выборку
мы можем выбрать n способами, второй из
оставшихся n-1 элементов (n-1) способами,
третий - (n-2) способами и так далее, m-й
элемент можно выбрать n-(m-1) = n-m+1 способами.
По правилу произведения получим:
(1.1)
Это и есть формула
для вычисления числа размещений. Найдем,
например, число размещений из 7 по 3.
Здесь n = 7, n - m +1 =5. Значит,
Заметим, что верхний индекс 3 показывает, сколько сомножителей надо взять в произведение. Приведем еще несколько примеров:
Пример 3.1. Составить все из трех букв А, В, С по две буквы.
Решение. Это
будут: АВ, АС, ВС, ВА, СА, СВ. Проверим по
формуле:
Их
действительно 6 штук. Отметим, что АВ и
ВА - разные размещения.
Пример 3.2. На пяти карточках написаны числа 1, 2, 3, 4, 5. Сколько различных трехзначных чисел можно из них составить?
Решение. Трехзначные числа представляют собой трехэлементные выборки из пяти цифр, причем, выборки упорядоченные, поскольку порядок цифр в числе существенен. Значит, этих чисел будет столько, сколько существует из пяти элементов по 3.
Ответ: 60 чисел.
Часто формулы комбинаторики записывают с помощью факториалов. Произведение всех последовательных натуральных чисел от 1 до n обозначается n! (читается: эн-факториал).
n! = 1 · 2 · 3 · ... · n.
Эту Формулу можно теперь преобразовать следующим образом. Умножим и разделим правую часть этой формулы на выражение
(n-m)! = 1 · 2 · 3 · ... ·(n-m).
Тогда получится:
(1.2)
вычислим например,
по этой формуле:
Мы видим, что здесь приходится еще
сокращать дробь, поэтому для вычисления
числа с конкретными значениями m и n
первая формула предпочтительнее.
Условились считать, что 0! =1.
4. Перестановки
Определение. Перестановками из n элементов называются размещения из n элементов по n. Из определения следует, что в данном случае в упорядоченную выборку входят все n элементов и отличаться выборки могут только порядком. Поэтому все перестановки имеют один и тот же состав и отличаются только порядком элементов. Число перестановок из n элементов обозначается Рn. Подставляя в формулу (1.1) или (1.2) m = n, получим формулу для вычисления числа перестановок из n элементов:
(1.3)
Приведем несколько примеров использования этой формулы.
Р5 = 5! = 1· 2 ·3 · 4 ·5 = 120; Р2 = 2! = 1· 2 = 2; Р1 = 1! = 1.
Пример 4.1. Составить все размещения из трех букв А, В, С.
Решение. АВС, АСВ, ВАС, ВСА, СВА, САВ. Проверим по формуле:
Р3 = 1·2·3 = 6.
Пример 4.2. Сколькими способами можно расставить 7 книг на книжной полке? Решение. Каждая расстановка будет отличаться от другой порядком следования книг. Поэтому это будут перестановки из семи элементов.
Р7 = 7! = 1·2·3·4·5·6·7= 5040.
Ответ: 5040 способами.
Пример 4.3. Сколько шестизначных чисел можно составить из цифр 0, 1, 2, 3, 4, 5 так, чтобы цифры в числе не повторялись?
Решение. Из данных шести цифр можно составить Р6 = 6! = 720 перестановок. Но числа, начинающиеся на нуль, не являются шестизначными. Такие числа отличаются друг от друга перестановкой пяти остальных цифр, значит, их будет Р5 = 120. Поэтому шестизначных чисел будет 720 - 120 = 600.
Ответ: 600 чисел.