Перестановки

Перестановки

Миасский городской округ,
Гимназия №19

Выполнил: Семченко Алёна,
ученица 11-Б класса.
Проверил: Копылова С. В.,
учитель математики.

Перестановки

Перестановками из n элементов называются соединения, которые состоят из одних и тех же n элементов и отличается одно от другого только порядком их расположения.

История перестановок:

Перестановки, называемые гексаграммами, использовались в Китае в И Цзин еще в 1000 году до нашей эры. Аль-Халил (717–786), арабский математик и криптограф , написал Книгу криптографических сообщений. Она содержит первое использование перестановок и комбинаций, чтобы перечислить все возможные арабские слова с гласными и без них.

История перестановок:

Правило определения количества перестановок n объектов было известно в индийской культуре около 1150 года. В «Лилавати» индийского математика Бхаскары II содержится отрывок, который переводится как: Произведением умножения начала и увеличения арифметического ряда на единицу и продолженного до количества знаков будут вариации числа с конкретными цифрами.

История перестановок:

В 1677 году Фабиан Стедман описал факториалы при объяснении количества перестановок колоколов в переменном звоне . Начиная с двух колокольчиков: «во-первых, два должны быть допущены для изменения двумя способами», что он иллюстрирует, показывая 1 2 и 2 1. Затем он объясняет, что с тремя колокольчиками «трижды две цифры должны быть произведено из трех », что еще раз проиллюстрировано. Его объяснение включает в себя «отбросьте 3, и 1. 2 останется; отбросьте 2, и 1. 3 останется; отбросьте 1, и 2. 3 останется». Затем он переходит к четырем колокольчикам и повторяет аргумент отвержения, показывающий, что будет четыре разных набора из трех. По сути, это рекурсивный процесс. Он продолжает с пятью колокольчиками, используя метод «отбрасывания», и составляет итоговые 120 комбинаций.  Он сдается и замечает: Природа этих методов такова, что изменения одного числа включают изменения всех меньших чисел до такой степени, что кажется, что полный Звук изменений одного числа формируется путем объединения завершенных Звонков на всех меньших числах. В одно целое тело.

Часто нужно с использованием закона умножения вычислить произведения натуральных чисел по порядку, начиная с 1. Например, 1, 2, 3, 4, 5, 6, 7 и т. д. Не всегда важно вычислить числовое произведение. Чтобы можно было короче записать выражения такого вида, в математике используется знак «!».

Произведение всех натуральных чисел от 1 до n включительно называется факториалом числа n и записывается n! (читается как «эн факториал»).
Pn=n!=1⋅2⋅3⋅...⋅(n−2)⋅(n−1)⋅n
Принято, что 0!=1
Свойство факториала: (n+1)!=(n+1)*n!

Факториал

Пример 1: Сколькими способами можно разместить на полке 4 книги?

Pn=n!
P4=4!=4*3*2*1 = 24 (способа)
Ответ: 24 способа.
В этой задаче фактически было найдено число всевозможных соединений из четырёх элементов, которые отличались одно от другого порядком расположения этих элементов. Такие соединения называют перестановками.

Пример 2: Сколькими способами можно положить 6 различных открыток в 6 имеющихся конвертов (по одной открытке в конверт)?

Pn=n!
P6=6!=6*5*4*3*2*1=720 (способов)
Ответ: 720 способов.

Использование перестановок:

Перестановки используются почти во всех областях математики и во многих других областях науки. В информатике они используются для анализа алгоритмов сортировки; в квантовой физике для описания состояний частиц; и в биологии для описания последовательностей РНК.

Шифры перестановки

В шифре перестановки буквы открытого текста не замещаются на другие, а меняется сам порядок их следования. Например, в шифре простой колонной перестановки исходный открытый текст записывается построчно (число букв в строке фиксировано), а шифртекст получается считыванием букв по колонкам. Расшифрование производится аналогично: шифртекст записывается поколонно, а открытый текст можно затем прочесть по горизонтали. Для повышения стойкости полученный шифртекст можно подать на вход второго шифра перестановки. Существуют еще более сложные шифры перестановки, однако почти все они легко взламываются с помощью компьютера. Хотя во многих современных криптографических алгоритмах и используется перестановка, ее применение ограничено узкими рамками, поскольку в этом случае требуется память большого объема, а также накладываются ограничения на длину шифруемых сообщений. Замена получила значительно большее распространение.

Задача №1: Сколькими способами можно рассадить четверых детей на четырех стульях в столовой детского сада? (№1060, стр. 321)

P=n! P4=4!=1*2*3*4=24 (способа)
Ответ: 24 способа.

Задача №2: Сколькими способами могут занять места 5 учащихся класса за пятью одноместными парами? (№1061, стр. 321)

P=n!
P5=5!=5*4*3*2*1=120 (способов)
Ответ: 120 способов.

Задача №3 Сколькими способами можно установить дежурство по одному человеку в день: 1) среди семи учащихся класса в течение 7 дней; 2) среди девяти учащихся класса в течение 9 дней?(№1062, стр. 321)

1. P=n!
P7=7!=7*6*5*4*3*2*1=5040 (способов)
Ответ: 5040 способов.
2. P=n!
P9=9!=9*8*7*6*5*4*3*2*1=362880 (способов)
Ответ: 362880 способов.

Задача №4: Сколько различных слов можно составить, переставляя местами буквы в слове: 1) гипотенуза; 2) треугольник? (№1068, стр. 322)

P=n!
В слове гипотенуза 10 букв, значит
P10=10!=10*9*8*7*6*5*4*3*2*1=3628800 (слов)
Ответ: 3628800 слов.
2. P=n!
В слове треугольник 11 букв, значит
P11=11!=11*10*9*8*7*6*5*4*3*2*1=39916800 (слов)
Ответ: 39916800 слов.

Задача №5: Сколько различных шестизначных чисел, не содержащих  одинаковых цифр и кратных 5, можно записать с помощью цифр 1, 2, 3, 4, 5 и 6? (№1069, стр. 322)

Так как числа должны быть кратных 5, то последняя цифра в числе должна быть 5. Осталось распределить оставшиеся цифры по разрядам:
P=n!
P5=5!=5*4*3*2*1=120 (чисел)
Ответ: 120 чисел.

Задача №6: Сколько различных шестизначных чисел, не содержащих одинаковых цифр и кратных 4, можно записать с помощью цифр 1, 3, 5, 6, 7 и 9? (№1070, стр. 322)

Так как числа должны быть кратных 4, то последняя цифра в числе должна быть 6. Осталось распределить оставшиеся цифры по разрядам:
P=n!
P5=5!=5*4*3*2*1=120 (чисел)
Ответ: 120 чисел.

Задача №7 (из ЕГЭ 2022): Вы­черк­ни­те в числе 123456 три цифры так, чтобы по­лу­чив­ше­е­ся трёхзнач­ное число де­ли­лось на 27. В от­ве­те ука­жи­те по­лу­чив­ше­е­ся число.

Если число де­лит­ся на 27, тогда оно де­лит­ся на 9. Число де­лит­ся на 9, тогда и толь­ко тогда, когда сумма его цифр де­лит­ся на 9. Сле­до­ва­тель­но, сумма цифр по­лу­чив­ше­го­ся числа долж­на де­лит­ся на 9 (но если число де­лит­ся на 9, то оно не­обя­за­тель­но де­лит­ся на 27, по­это­му по­тре­бу­ет­ся про­вер­ка).
Сумма цифр числа 123456 равна 1 + 2 + 3 + 4 + 5 + 6 = 21. Чтобы сумма цифр по­лу­чив­ше­го­ся числа была равна 9, вы­черк­нем цифры, да­ю­щие в сумме 12: 6, 5 и 1. По­лу­чим число 234, оно не де­лит­ся на 27. Тогда вы­черк­нем 2, 4 и 6, по­лу­чим 135 — де­лит­ся на 27.
Ответ: 135.

Список литературы:

Гугл сайт Боттова: // [электронный ресурс] https://www.sites.google.com/site/bottvaa/11 (дата обращения 17.11.2021).
Вики сайт: // [электронный ресурс] https://hmong.ru/wiki/Permutation (дата обращения 17.11.2021).
Алимов Ш. А. Математика: алгебра и начала математического анализа, геометрия [Текст] / Ш. А. Алимов, Ю. М. Колягин, М. В. Ткачева, Н. Е. Фёдоровна, М. М. Шабунин. - Просвещение, 2019. С. 320-322

Спасибо за внимание!