Спирина, М.С. Дискретная математика

рованном первом) останется л - 1 способов, для третьего (при фиксированных втором и первом элементах) найдется л - 2 спо­ соба и т.д. Для последнего элемента останется единственный ва­ риант (единственное оставшееся место). Необходимо учесть варианты и для первого, и для второго, и для л-го элемента, поэтому количество вариантов надо перемно­ жить. Тогда Рп= л ( л - 1)(л —2) ... 1. Такое произведение кратко записывается л! (читается «л-фак- ториал»). Формула для числа перестановок имеет вид Р„ = л!. Например, из цифр 3, 5, 7, 9 можно составить 4! кортежей, так как л = 4, то Р4 = 4! = 4 • 3 • 2 • 1 = 24, т.е. существует 24 различных четырехзначных числа, составленных из этих цифр: 5379, 7359, 9357, ... . Очевидно, Р„ = л! = пР„ _ ,. Такая формула называется рекур­ рентной и дает возможность подсчитывать число перестановок во множестве л + 1 элемента через перестановки во множестве л элементов. Заметим, что /*, = 1!, а Р0 = 0! = 1. Если множество содержит один элемент, то и вариант составления кортежей тоже един­ ственный, но если во множестве нет элементов, то это тоже един­ ственный вариант: «кортеж длины О». Размещения (без повторений). Упорядоченное подмножество т элементов (кортеж), составленное из всего множества, содержа­ щего л элементов, называется размещением (без повторения). Чис­ ло таких размещений обозначается АЦ1 (от фр. arrangement — раз­ мещение). Число всех кортежей длины т подсчитаем с помощью переста­ новок из всех л элементов (л!), без тех кортежей, которые не вошли в кортеж длины т. Таких «лишних» кортежей длиной л - т насчитывается (л - т)\. Поскольку порядок в «лишнем» подмно­ жестве не зависит от «нужного», действует правило произведения. Поэтому формула размещений (без повторений) примет вид Задача 3. Сколькими способами из различных нечетных цифр можно составить различные трехзначные числа? Решение. Нечетных цифр пять: 1, 3, 5, 7, 9. Тогда количество различных трехзначных чисел найдем по формуле Л53 = Ц = 60. Сочетания без повторений. Сочетания во множестве из л эле­ ментов отличаются от размещений тем, что в подмножестве, со­ стоящем из т элементов, в размещениях порядок определен, а в сочетаниях — не важен. Поэтому сочетаниями из л элементов по т называется неупо­ рядоченное подмножество (выборка), состоящее из т элементов, 48