5.7. Размещения с повторениями

Задача формулируется следующим образом. Имеются пред­меты п различных видов a₁,a₂,…,a_n . Из них составляют всевоз­можные расстановки длины k. Например, a₂a₁a₃a₃a₄a₃a₂a₁- расстановка длины 8. Такие расстановки называются размещения­ми с повторениями из п по k (элементы одного вида могут повто­ряться). Найдем общее число расстановок, среди которых две расстановки считаются различными, если они отличаются друг от друга или видом входящих в них предметов, или порядком этих предметов. При составлении указанных расстановок длины k на каждое место можно поставить предмет любого вида. Рас­смотрим множества X₁,X₂,…,X_k такие, что Х₁ = Х₂ = ... = X_k = { a₁,a₂,…,a_n } . Тогда все размещения с повторениями составят мно­жество . По правилу прямого произведения по­лучаем, что общее число размещений с повторениями из п по k равно .

Пример:

Найти количество всех пятизначных чисел.

Решение: Введем пять множеств: А₂ = А₃ = А₄ = А₅ = {0, 1,..., 9}, А₁ = {1, 2,..., 9}. Тогда все пятизначные числа составят прямое произведение указанных множеств А₁ А₂ А₃ А₄ А₅. Соглас­но правилу прямого произведения, количество элементов в мно­жестве А₁ А₂ А₃ А₄ А₅ равно 9*10*10*10*10 =90000.

5.8. Размещения без повторений

Имеются п различных предметов a₁,a₂,…,a_n. Сколько из них можно составить расстановок длины k? Две расстановки счита­ются различными, если они отличаются видом входящих в них элементов или порядком их в расстановке. Такие расстановки называются размещениями без повторений, а их число обо­значают . При составлении данных расстановок на первое место можно поставить любой из имеющихся п предметов. На второе место теперь можно поставить только любой из п - 1 оставшихся. И, наконец, на k-e место - любой из п - k + 1 оставшихся предметов. По правилу прямого произведения по­лучаем, что общее число размещений без повторений из п по k равно А: =n(n-1)...(n-k+1)= =n!/(n-k)!. Напомним, что п! = п(п -1)...1 и 0! = 1.

Пример:

В хоккейном турнире участвуют 17 команд. Разыгры­ваются золотые, серебряные и бронзовые медали. Сколькими способами могут быть распределены медали?

Решение: 17 команд претендуют на 3 места. Тогда тройку при­зеров можно выбрать способами = 17*16*15 = 4080.

5.9. Комбинации элементов с повторениями

Пусть имеем неупорядоченное n-элементное множество А, элементы которо­го разбиты на n классов (в каждом классе находится по одному элементу), которые будут называться типами элементов. Комбинацией из n элементов по m элементов с повторениями называется m-элементное подмножество множества А, каждый элемент которого принадлежит одному из n типов. Со­вокупность таких комбинаций называют комбинациями из n элементов по m.

Теорема.

Количество различных комбинаций из n элементов по т элементов с повторениями равно

Доказательство.

"Закодируем" каждую комбинацию следующим образом. Если комбинация включает k₁ элементов первого типа, то записываем подряд k₁ единиц, ставим нуль. После него ставим подряд k₂ единиц, если комбина­ция включает k₂ элементов другого типа и т. д. Например, если А = {a, b, c, d}, то комбинациям по два элемента с повторениями соответствуют пары {а, а}, {а b}, {а, с}, {а, d}, {b, b}, {b, с}, {c ,d}, {c, c}, {c, d}, {d, d}, а их "кодами" будут соответственно

11000, 10100, 10010, 10001, ..., 00011.

Нетрудно убедиться, что между "кодами" и комбинациями существует взаимно однозначное соответствие. Таким образом, каждой комбинации из n элементов по т соответствует последовательность из т единиц и n - 1 нулей (в рассмотренном примере n = 4, т = 2). Следовательно, число всех комбинаций из n элементов по т с повторениями равно числу последовательно­стей, состоящих из т единиц и n - 1 нулей, т. е. .

Теорема доказана.

Пример:

Сколько целых неотрицательных решений имеет уравнение

x₁+x₂+…+x_n=m?

Решение:

Решения данного уравнения можно интерпретировать так. Если имеем целые неотрицательные числа x₁, x₂, … ,x_n, такие что x₁+x₂+…+x_n=m, то можно составить комбинацию из n элементов по m, взяв x₁ элементов первого типа, x₂ элементов второго типа, ..., x_n элемен­тов n-ого типа. Наоборот, имея комбинацию из n по m элементов, получим решение урав­нения (x₁, x₂, … ,x_n – число элементов первого, второго, и, соответ­ственно, n-ого типа), где все x_i неотрицательные (i = 1, 2, ..., n). Таким об­разом, между множеством всех неотрицательных решений данного уравнения и множеством всех комбинаций из n элементов по m устанавлива­ется взаимно однозначное соответствие. Следовательно, число целых не­отрицательных решений уравнения равно

Например, если x₁+x₂+ x₃+x₄=10, то это уравнение имеет целых неотрицательных решений.

Основное правило комбинаторики:

Задача 1:

Сколькими способами на первенстве мира по футболу могут распределиться медали, если в финальной части играют 24 команды?

Решение. Золотую медаль может получить любая из 24 команд, т. е. имеем 24 возможности. Серебряную медаль может выиграть одна из 23 команд, а бронзовую - одна из 22 команд. По основному правилу комбинаторики общее число способов распределения медалей 24 . 23 . 22 = 12 144.

Задача 2:

Сколько трехзначных чисел можно составить из цифр 0, 1,2,3,4, 5, если:

• Цифры могут повторяться.

Решение. Первой цифрой может быть одна из цифр 1,2,3,4,5, по­скольку 0 не может быть первой цифрой, ибо в таком случае число не будет трехзначным. Если первая цифра выбрана, то вторая может быть выбрана шестью способами, как и третья цифра. Следователь­но, общее число трехзначных цифр 5*6*6 = 180.

• Ни одна из цифр не повторяется дважды.

Решение. Первой цифрой может быть одна из пяти цифр - 1,2, 3, 4, 5. Если первая цифра выбрана, то второй может быть также одна из пяти цифр (тут уже учитывается 0), а третья может быть выбрана четырьмя способами из четырех цифр, что остались. Следовательно, общее количество таких трехзначных чисел 5*5*4 = 100.

• Цифры нечетные и могут повторяться.

Решение. Первой цифрой может быть одна из трех цифр: 1, 3, 5. Второй тоже может быть одна из этих трех цифр. Аналогично и тре­тья цифра может быть выбрана тремя способами. Таким образом, общее количество таких чисел равняется 3*3*3 = 27.

Перестановки:

Задача 3:

Сколькими способами можно расположить на шахматной доске 8 ладей, чтобы они «не били» друг друга?

Решение. Условие «не могли бить» означает, что на каждой го­ризонтали и вертикали может стоять лишь одна ладья. Ввиду это­го, каждому расположению ладей на доске соответствует перестановка . Верхняя строка перестановок – это номера горизонталей, нижняя - вертикалей, пересечение которых определяет положение ладей на доске. Следовательно, число рас­становок равно числу перестановок Р₈ = 8! из 8 элементов.

Число подмножеств данного множества:

Задача 4:

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

Решение. Число игроков волейбольной команды равно шести. Значит, число всех возможных вариантов - это число различных подмножеств, состоящих из шести элементов в множестве из пятнадцати элементов. Следовательно,

.

Размещение элементов множества:

Основная формула:

Задача 5:

Студенту необходимо сдать три экзамена на протяжении семи дней. Сколькими способами это можно сделать?

Решение. Искомое число способов равно количеству трехэлемент­ных упорядоченных подмножеств множества из семи элементов, т. е. существует = 7 * 6 * 5 = 210 способов.

Если известно, что последний экзамен будет сдаваться на седьмой день, то число способов равно З * = 3 * 6 * 5 = 90.

Задача 6:

Сколькими разными способами можно разместить пять студентов в ауди­тории, которая имеет 20 мест?

Решение. Искомое число способов равно числу размещений из 20 элементов по 5 элементов, т. е. = 20 * 19 * 18 * 17 * 16 = 1 860 480.

Задача 7:

Сколько различных слов можно составить:

• В алфавите из восьми букв.

Решение. Всех таких слов будет столько, сколько существует отображений восьмиэлементного множества в множестве из двух элементов, т.е. по теореме 2⁸=256 слов.

• В алфавите из шестнадцати букв.

Решение. В этом алфавите имеем 2¹⁶=65536 слов.

Задача 8:

В хоккейном турнире участвуют 17 команд. Разыгры­ваются золотые, серебряные и бронзовые медали. Сколькими способами могут быть распределены медали?

Решение. 17 команд претендуют на 3 места. Тогда тройку при­зеров можно выбрать способами = 17*16*15 = 4080.