Алгебра : Теоремы и алгоритмы. Яцкин Н.И. - 158 стр.

158                   Теория перестановок                       Гл. 3

  Символы в первой строке записи (16.2) разрешается как угодно
переставлять, меняя при этом (соответствующим образом) порядок
элементов во второй строке. Скажем, элемент
                         µ                         ¶
                             1       2 3   4   5
                    ϕ=                                 ∈ S5
                             3       2 4   5   1

можно записать в виде
                             µ                         ¶
                                 5    1 3 4        2
                      ϕ=                                   .
                                 1    3 4 5        2

   Замечание 16.2. Широко распространен другой термин — "под-
становки" (вместо "перестановки"), но в учебнике [2] убедительно
показана бо́льшая адекватность термина "перестановки". При чте-
нии других книг по алгебре (например, [3]) следует иметь в виду
указанное расхождение в терминологии.
   Замечание 16.3. Для отображения ϕ : X → X конечного множе-
ства X в себя справедливы эквивалентности
 (ϕ — инъективно) ⇐⇒ (ϕ — сюръективно) ⇐⇒ (ϕ — биективно).
  Попробуйте сами доказать эти утверждения, предварительно за-
метив, что количество элементов в образе ϕ(X) не превышает коли-
чества элементов X. (Можно обратиться также к замечанию 15.7.)
   Подсчитаем теперь, сколько всего существует перестановок степе-
ни n.
   Во второй строке записи (16.2) все элементы попарно различны;
они такие же, как в первой строке, но расположены в произвольном
порядке.
   Имеется n способов выбора элемента ϕ(1). Если этот элемент уже
выбран, то для выбора ϕ(2) остается n − 1 способов. Каждый из
способов выбора первого элемента может сочетаться с любым спо-
собом выбора второго. Поэтому два элемента ϕ(1), ϕ(2) могут быть
выбраны n · (n − 1) способами. Каждый из этих способов может со-
четаться с любым из способов выбора ϕ(3) и т. д. Если элементы
ϕ(1), ϕ(2), . . . , ϕ(n − 1) уже выбраны, то элемент ϕ(n) определяется
однозначно (один способ выбора). Итоговая формула для определе-
ния количества перестановок степени n:

                      n · (n − 1) · . . . · 2 · 1 = n!