Размещения
Прежде вспомним некоторые основные понятия из математики, в частности из теории множеств.
Во-первых, что такое множество вообще? Понятие множества является основополагающим в математике и неопределяемым.
Под множеством понимается некоторая совокупность объектов, объединенных по какому-то общему признаку.
Так, можно говорить о множестве стульев и столов в классе, множестве натуральных чисел, целых, рациональных и действительных (вещественных) чисел.
Объекты, входящие в множество, мы будем называть элементами.
Число 5 является элементом множества натуральных чисел. Стол является элементом множества столов в классе. Обычно множества обозначаются большими латинскими буквами
A, B, C, D, ..., X, Y, Z, а их элементы - малыми буквами a, b, c, d, ..., x, y, z.
О том факте, что a является элементом множества A говорят, что a принадлежит
множеству A.
Обычно элементы множества записываются в фигурных скобках
Пусть нам даны множества A, с уже указанными его элементами, и множество B = {a1, a2, a3, a4}.
Как вы заметили, каждый элемент множества B является и элементом множества A. В этом случае говорят, что B является подмножеством множества A.
Определение. Если каждый элемент множества B является в то же время элементом и множества A, то говорят, что B есть подмножество (часть) A.
Очень часто нам будет важно знать не только элементы множества, но и порядок их расположения в множестве.
Если учитывается порядок расположения элементов в множестве, тогда множества, имеющие одинаковые элементы, но имеющие их разное расположение, будут для нас различными.
Например: Z = {z1, z2, z3, z4 } и B = {z2, z1, z3, z4} будут считаться разными, так как у них различен порядок расположения элементов.
Множество, в котором задан порядок следования элементов, называются упорядоченным.
Рассмотрим некоторые простые примеры.
Пример 1. В классе 12 учебных предметов. В день проводится 5 разных уроков. Сколькими способами может быть составлено расписание занятий.
Для простоты рассуждений обозначим учебные предметы числами от 1 до 12:
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 элементов
Например,
Таким образом, составив процедуру вычисления размещений по этому принципу, мы избегаем недопустимо больших чисел, которые могут образовываться при вычисление факториалов и упрощаем составление программ, а также имеем возможность в дальнейшем применять процедуру размещений в других программах.
Процедура
размещений из n элементов по k элементов.
Procedure placement(n, k : integer; var
r : longint);
var
i : integer;
begin
r := 1;
for i := 1 to k do r := r*(n - k + i)
end;
Программа
Program Problem1;
uses WinCrt;
var
n, k, r : longint;
{----------------------------------------------------------------------------------------}
{ Процедура вычисления числа размещений из n по k }
Procedure placement(n, k : integer; var
r : longint);
var
i : integer;
begin
r := 1;
for i := 1 to k do r := r*(n - k + i)
end;
{----------------------------------------------------------------------------------------}
begin
write('Введите число всех предметов '); readln(n);
write('Введите число уроков в день '); readln(k);
Placement(n, k, r);
writeln('Число вариантов расписания равно ', r)
end.
Пример 2. Сколько различных четырехзначных чисел можно написать при помощи цифр 0, 1, 2, ..., 9?
Рассуждения могут быть очень простыми. Нам надо выяснить сколькими способами можно выбрать по 4 цифры из 10, причем важен порядок расположения цифр, так как 1234 и 2134 дают разные числа. Значит необходимо определить число размещений из 10 элементов по 4,
Но из этого количества чисел мы должны исключить те, которые начинаются цифрой 0, например, 0123, 0213 и т.п. Эти числа уже не будут четырехзначными.
Сколько таких чисел? Да столько, сколько трехзначных чисел получится из 9 цифр (без нуля), т. е. равное числу размещений из 9 элементов по 3,
Окончательное количество четырехзначных чисел, которые можно составить из 10 цифр равно разности:
Программа
Program Problem2;
uses WinCrt;
var
n, k, a, a1 : longint;
{----------------------------------------------------------------------------------------}
Procedure placement(n, k : integer; var r : longint);
var
i : integer;
begin
r := 1;
for i := 1 to k do r := r*(n - k + i)
end;
{----------------------------------------------------------------------------------------}
begin
write('Введите заданное ко-во цифр '); readln(n);
write('Введите ко-во цифр, из скольких составляется число '); readln(k);
placement(n, k , a);
placement(n - 1, k - 1, a1);
writeln('Число различных 4-х знач. чисел, которые можно');
writeln('написать при помощи цифр 0, 1, 2, .., 9 равно ', a - a1)
end.
