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

UptoLike

ВУЗ: 

ИвГУ | Иваново

Составители: 

Рубрика: 

§
§
§ 21 Число инверсий в перестановке 191
§
§
§ 21. Число инверсий в перестановке.
Второй способ
определения знака перестановки
21.1. Инверсии в перестановке. Рассмотрим перестановку
[см. (16.2)]
ϕ =
µ
1 2 . . . n
ϕ(1) ϕ(2) . . . ϕ(n)
(21.1)
и всевозможные пары номеров (i, j), такие, что 1 6 i < j 6 n. Сколь-
ко существует таких пар? Если вы немного знакомы с комбинато-
рикой, то легко ответите: их
C
2
n
=
n(n − 1)
2
(21.2)
штук. Формула (21.2) выражает число сочетаний из n элементов
по 2". Но если вы таких слов пока не знаете, то можно объяснить
по-другому: последовательность i, j двух различных номеров можно
выбрать n(n−1) способами; лишь одна из двух последовательностей
i, j и j, i является возрастающей (либо i < j, либо j < i); число
возрастающих последовательностей дается формулой (21.2).
Определение 21.1. Будем говорить, что перестановка ϕ осу-
ществляет инверсию (или: имеет инверсию; или: допускает бес-
порядок; и т. п.) на возрастающей последовательности i, j (i < j),
если ϕ(i) > ϕ(j).
Количество инверсий в перестановке ϕ будем обозначать ι(ϕ)
(ι — греческая буква "йота").
Замечание 21.1. Наш подсчет в начале данного пункта показыва-
ет, что число инверсий ι(ϕ) заключено в пределах от 0 до C
2
n
, причем
ι(ϕ) = 0 для перестановки ϕ = ε (и только для нее), а наибольшее
возможное число инверсий ι(ϕ) = C
2
n
имеет перестановка
ϕ =
µ
1 2 . . . n − 1 n
n n − 1 . . . 2 1
. (21.3)
Можно сказать, что ϕ = ε : X → X является единственной стро-
го возрастающей функцией, а перестановка (21.3) — единственной
строго убывающей.
§ 21             Число инверсий в перестановке                  191

        § 21. Число инверсий в перестановке.
                   Второй способ
           определения знака перестановки

   21.1. Инверсии в перестановке. Рассмотрим перестановку
[см. (16.2)]
                  µ                      ¶
                     1     2  ...    n
               ϕ=                                   (21.1)
                    ϕ(1) ϕ(2) . . . ϕ(n)

и всевозможные пары номеров (i, j), такие, что 1 6 i < j 6 n. Сколь-
ко существует таких пар? Если вы немного знакомы с комбинато-
рикой, то легко ответите: их

                                      n(n − 1)
                              Cn2 =                            (21.2)
                                         2

штук. Формула (21.2) выражает число сочетаний из n элементов
по 2". Но если вы таких слов пока не знаете, то можно объяснить
по-другому: последовательность i, j двух различных номеров можно
выбрать n(n − 1) способами; лишь одна из двух последовательностей
i, j и j, i является возрастающей (либо i < j, либо j < i); число
возрастающих последовательностей дается формулой (21.2).
   Определение 21.1. Будем говорить, что перестановка ϕ осу-
ществляет инверсию (или: имеет инверсию; или: допускает бес-
порядок; и т. п.) на возрастающей последовательности i, j (i < j),
если ϕ(i) > ϕ(j).
   Количество инверсий в перестановке ϕ будем обозначать ι(ϕ)
(ι — греческая буква "йота").
   Замечание 21.1. Наш подсчет в начале данного пункта показыва-
ет, что число инверсий ι(ϕ) заключено в пределах от 0 до Cn2 , причем
ι(ϕ) = 0 для перестановки ϕ = ε (и только для нее), а наибольшее
возможное число инверсий ι(ϕ) = Cn2 имеет перестановка
                      µ                                ¶
                          1    2       ...   n−1   n
                 ϕ=                                        .   (21.3)
                          n   n−1      ...    2    1

   Можно сказать, что ϕ = ε : X → X является единственной стро-
го возрастающей функцией, а перестановка (21.3) — единственной
строго убывающей.

Страницы