Question

ОЧЕНЬ СРОЧНО.

Доведіть, що якщо поміняти місцями два будь-які числа в довільній перестановці, то парність кількості інверсій зміниться.

Answer 1

Ответ:

Розглянемо спочатку випадок, коли елементи r,s над якими виконується транспозиція, стоять поруч в перестановці (...,r,s,...) . Транспозиція перетворює цю перестановку в перестановку (...,s,r,..) . Кожен з елементів  r, i s  в обох перестановках утворює ті самі інверсії з елементами, які залишилися на місці. Якщо елементи і не утворювали інверсії в заданій перестановці, то вони утворюють її в новій перестановці, тобто число інверсій збільшилося на одиницю. Навпаки, якщо і утворювали інверсію, то в новій перестановці вони її не утворюють, тобто число інверсій зменшилося на одиницю. В обох випадках парність перестановки зміниться.

Пояснення: Якщо допоміг постав 5 зірок