По условию задачи, нам необходимо
1, 2, 3, 4, 5, ..., 10, 11, 12.
По условию задачи, нам необходимо из этих 12 чисел выбирать по 5 чисел. Причем эти наборы из пяти чисел могут отличаться не только числами, но и расположением чисел, например, один из наборов будет: {1, 2, 3, 4, 5}; набор, который получается при перестановке этих же чисел {2, 1, 3, 4, 5}, также будет удовлетворять условию задачи.
В самом деле, пусть первый набор будет состоять из следующих предметов: {алгебра, физика, химия, история, литература}; тогда набор, полученный при перестановке хотя бы двух предметов уже даст новое расписание: {физика, алгебра, химия, история, литература}.
Таким образом, наборы из 5 чисел могут отличаться не только самими числами, но и порядком их расположения.
Такие подмножества называются в комбинаторике размещениями.
Определение. Размещением из n
элементов по k называется всякое упорядоченное подмножество данного множества, содержащее k элементов.
О размещениях можно сказать несколько иначе, правда менее строго с математической точки зрения, но более понятно для нас.
Размещением из n
элементов по k называется всякое подмножество данного множества, состоящее из k элементов, которое может отличаться не только элементами, но и порядком их расположения.
Например, из множества M = {1, 2, 3, 4} можно образовать 12 различных размещений, из 4 по 2:
{1, 2} {1, 3} {1, 4} {2, 3} {2, 4} {3, 4}
{2, 1} {3, 1} {4, 1} {3, 2} {4, 2} {4, 3}
Число размещений, взятых из n элементов по k, мы будем обозначать символом
Значит,
Возвращаемся к примеру 1. В нем, как теперь уже стало ясно, надо найти число размещений
из 12 по 5.
По формуле находим:
Вычислить число размещений можно другим способом:
Итак,
Словами можно сказать, что число размещений из n элементов по k равно произведению k элементов
Например,
Таким образом, составив процедуру вычисления размещений по этому принципу, мы избегаем недопустимо больших чисел, которые могут образовываться при вычисление факториалов и упрощаем составление программ, а также имеем возможность в дальнейшем применять процедуру размещений в других программах.
