Пример. Множество называется упорядоченным, если между его элементами установлено отношение

Пример.

Пусть М₁ = {7, 8, 9, 11, – 10}; М₂ ={–1, 10, 13}; М₃ = {– 10, 9, 8, 7, 11}. Множества М₁ и М₃ равны, так как все элементы М₃ принадлежат М₁, а элементы М₁ – М₃.

Множество называется упорядоченным, если между его элементами установлено отношение предшествования, удовлетворяющее следующим условиям:

1) для любых a и b из М (a ¹ b) либо a предшествует b, либо b предшествует a;

2) если a предшествует b, b предшествует c, то a предшествует c.

Множество натуральных чисел N является упорядоченным; список фамилий в журнале – упорядоченное множество.

Два упорядоченных множества равны, если они равны как множества и одинаково упорядочены.

Пример.

Пусть даны упорядоченные множества М₁ ={– 1, 2, 3, 4, 11}; М₂ = {2, 3, 4, 11, – 1}; М₃ ={1, 2, – 1}; М₄ ={– 1, 2, 3, 4, 11}.

Равными являются множества М₁ и М₄. Множества М₁ и М₂ не являются равными, так как, хотя они и состоят из одних и тех же элементов, их порядок разный.

Пусть дано множество М, состоящее из n элементов. Размещением из n элементов по m называется любое упорядоченное подмножество множества М, содержащее m элементов.

Пример.

Пусть М = {1, 3, 2}. Выпишем все возможные размещения данного множества при m = 2.

М₁ = {1, 2}; М₂ = {2, 1}; М₃ = {1, 3}; М₄ = {3, 1}; М₅ = {2, 3}; М₆ = {3, 2}.

Следует отметить, что М₁ и М₂, М₃ и М₄, М₅ и М₆ являются разными размещениями, поскольку размещение – это упорядоченное множество.

В большинстве задач нас будут интересовать не конкретные размещения данного множества из n элементов, а как много таких размещений существует при заданном m. На этот вопрос отвечает

ТЕОРЕМА. Количество размещений из n элементов по m равно произведению m натуральных чисел, большее из которых равно n, т.е.

Отметим, что при m = 0 количество размещений считают равным единице, т.е. .

Для дальнейшей работы нам понадобится понятие факториала (обозначается n!). Факториалом числа n называется последовательное произведение натуральных чисел от 1 до n, т.е.

Отметим, что 0! = 1.

Рассмотрим теперь важный частный случай размещения при n = m. Такие размещения называются перестановками. Другими словами, перестановка – это размещение из n элементов по n или различные упорядочения одного и того же множества. Количество перестановок обозначается P_n и находится по формуле

P_n = n!