Лекции по курсу математики для юристов. Саакян Г.Р - 25 стр.

                                                     - 25 -
        Упорядоченные множества считаются различными, если они отличаются либо своими
элементами, либо их порядком.
        Определение. Различные упорядоченные множества, которые отличаются лишь по-
рядком элементов (т.е. могут быть получены из элементов одного и того же множества), на-
зываются перестановками данного множества.
        Пример 9. Перестановки множества A = {a, b, c} из трех элементов имеют следующий
вид:
                                     abc, acb, bac, bca, cab, cba .
        Найдем число различных способов, которыми может быть упорядочено данное мно-
жество, т.е. число перестановок n -элементного множества A . Число перестановок множест-
ва, содержащего n элементов, обозначают символом Pn .11 Имеет место
        Теорема 1. Pn = n ! (читается: «эн факториал»).
        ∆ Будем последовательно выбирать элементы множества A и размещать их в опреде-
ленном порядке на n местах. На первое место можно поставить любой из n элементов. По-
сле того, как заполнено первое место, на второе место можно поставить любой из оставших-
ся n − 1 элементов и т.д. По правилу произведения все n мест можно заполнить
n(n − 1)(n − 2)...2 ⋅ 1 = n ! способами. Следовательно, множество A из n элементов можно
упорядочить n ! способами.▲
                                            Размещения
        Определение. Пусть имеется множество, содержащее n элементов. Каждое его упо-
рядоченное подмножество, состоящее из k элементов, называется размещением из n эле-
ментов по k элементов (коротко: размещением из n по k ).
        Из определения вытекает, что 0 ≤ k ≤ n и что размещения из n по k – это все k -
элементные подмножества ( n -элементного множества), отличающиеся составом элементов
или порядком их следования.
        Пример 10. Размещения множества A = {a, b, c, d } из 4-х элементов по 2 имеют сле-
дующий вид:
                                            ab ac ad
                                            ba bc bd
                                            ca cb cd
                                            da db dc
        В комбинаторных задачах необходимо уметь подсчитывать число всех размещений из
n по k . Для обозначения этого числа применяется специальный символ A kn .12
       Теорема 2. Ank = n(n − 1)(n − 2)...(n − k + 1) .
       ∆ Число размещений из n по k равно числу всех k -элементных упорядоченных под-
множеств множества, содержащего n элементов. Первый элемент подмножества можно,
очевидно, выбрать n способами, второй элемент подмножества можно выбрать уже только
n − 1 способами, т.к. в качестве второго элемента можно взять любой элемент множества,
кроме уже выбранного первым. После выбора первых 2-х элементов остаются n − 2 возмож-
ности для выбора третьего элемента, и т.д. до последнего k -го элемента, который может
быть выбран n − k + 1 способом. ▲
       Замечание. Формулу для числа размещений удобно записывать в другом виде:
                                                       n!
                                            Ank =            .
                                                  (n − k ) !
       Пример 11. Сколькими способами можно рассадить 4-х студентов на 25-ти местах?
       Ответ. A nk = 25 ⋅ 24 ⋅ 23 ⋅ 22 = 303600 .

11
     P – первая буква английского слова «permutation» – перестановка.
12
     A – первая буква английского слова «arrangement» – размещение.