Таблицы Брадиса

Заметим, что определение из указания

Заметим, что определение из указания

Элементы математики в задачах - Г. А. Мерзон

Указание. Эквивалентное определение: подстановка 0112"1п^ назы­вается четной, если число пар (к, I), таких что 1к > 11, но )к < )1, четно.

Другими словами, четность перестановки а есть четность числа пе­ресечений совокупности отрезков, соединяющих I с а(0.

146                                    Подстановки 2

Решение. Заметим, что определение из указания эквивалентно опре­делению 1 для подстановки, записанной в канонической форме. Кро­ме того, ясно, что это определение не зависит от формы записи подстановки.

Осталось показать, что это определение эквивалентно определе­нию из задачи. То есть нужно проверить, что общее число беспоряд­ков в обеих строках записи подстановки имеет ту же четность, что и число пар (к, I), таких что 1к > ц, но }к < }1.

Это достаточно проверить для каждой неупорядоченной пары {к, 1}

(будем для определенности считать, что к < I): если 1к > ц, }к < } или Ч < Ч, }к > }1, в обе суммы эта пара дает вклад, равный 1 (отметим, что в одном случае вклад во вторую сумму дает пара (к, I), а в другом —

(I, к)); если же 1к > 11, }к > }1 или 11 < ц, }к < }1, то вклад в одну сумму равен 0, а в другую — 2.

Задача 1. Найдите четности подстановок из задач 1, 2 предыдущего листка.

Решение. —тождественная, а потому четная. (123) —также тож­дественная. (^бэ) = (635412) • Беспорядков 12: (3, 6), (4, 6), (1, 6),

(2,6), (1,3), (2,3), (4,5), (1,5), (2,5), (3,5), (1,4), (3,4). Значит, подстановка четная. (^234) = (4321)' Беспорядков 6: (4,3), (4,2),                                                                                                                    ””^3""

(4,1), (3, 2), (3,1), (2,1). Подстановка также является четной. —