Що таке перестановка?

Перестановка є однією з тем, що обговорюються в дисципліні комбінаторний аналіз з математики. Маючи на руках будь-яку впорядковану послідовність з «n» кількістю різних елементів, будь-яка інша послідовність, утворена тими ж «n» впорядкованими елементами, називається перестановка.

Таким чином, можна сказати, що якщо A є перестановкою B, то A і B складаються з одних і тих же елементів, але впорядкованих по-різному.

Звідки беруться перестановки?

Перестановки - поодинокі випадки Прості домовленості. Це впорядковані групування множини елементів, такі, що групи мають меншу або однакову кількість елементів, ніж множина А.

Набір A = {X, Y, Z}, {X, Y} та {Y, X} є a просте розташування з елементів з А взято 2 до 2. Кількість елементів A представлена ​​літерою "n". О номер замовлення, або номер класу, є "k". Це число - це кількість елементів у кожному простому масиві (у випадку прикладу це число дорівнює 2).

Список з усіма простими розташуваннями трьох елементів A, взятих з 3 по 3, є таким:

XYZ, XZY, ZXY, ZYX, YZX та YXZ

Цей список є саме приватним випадком домовленостей, які отримують назву перестановки.

Розрахунок простих домовленостей

Кількість простих компонувань множини A, яка має немає взяті елементи k о, можна обчислити за такою формулою:

THE_{ні, добре} = немає!
(n - k)!

Визначення перестановки

Нехай A - множина з немає окремі елементи. ти прості домовленості з цих елементів, прийнятих n до n, називаються прості перестановки А. Таким чином, щоб це була перестановка, необхідно, щоб був номер замовлення k бути рівним числу немає елементів А. З цього випливають такі розрахунки:

Беручи формулу, яка використовується для простих масивів, та номер замовлення k = n, ми матимемо:

Це формула, що використовується для обчислення кількості перестановок елементів множини A, що зазвичай позначається P_немає. Незабаром:

Не зупиняйтесь зараз... Після реклами є ще щось;)

P_немає = A_{ні ні} = n!

P_немає = n!

Приклад

Обчисліть кількість перестановок букв слова LOVE.

Рішення:

Зауважте, що слово ЛЮБОВ має 4 різні елементи. Для обчислення кількості перестановок цього слова скористаємось наведеною вище формулою:

P_немає = n!

P₄ = 4!

P₄ = 4·3·2·1

P₄ = 24

Отже, можна сформувати 24 різні перестановки букв слова LOVE. Також називаються перестановки слів анаграми.

Перестановки з повторюваними елементами

Будь-який набір може мати повторювані елементи. В перестановки цей набір повинен враховувати повторення цих елементів, оскільки порядок їх появи не має значення, на відміну від порядку інших елементів у наборі. Якщо ми змінимо лише два "А" місця у слові AMAR, ми отримаємо одне і те ж слово. Схожих слів немає перестановки, отже, це повторення потрібно відняти у формулі для перестановок.

Відняти всі можливі повторення елементів в одному перестановка з повторюваними елементами, ми повинні зробити наступне:

Нехай A - множина з немає елементи, з яких k елементи повторюються. Формула для обчислення перестановок A має вигляд:

P_немає^k = немає!
k!

Якщо встановлено A, за допомогою немає елементи, володіти k повторення елемента і j повторення іншого, обчислення відбуватиметься наступним чином:

P_немає^ха-ха =  немає!
k! · j!

Якщо множина A, с немає елементів, має k повторення елемента, j повторення іншого,…, м Повторення іншого, формула приймає такий вигляд:

P_немає^{k, j,..., m} =  немає!
k! · j! ·... · М!

Приклад

Обчисліть кількість анаграм слова ANTONIA.

Рішення:

Щоб вирішити приклад, просто обчисліть перестановки з повторюваними елементами слова АНТОНІЯ. І буква А, і буква Н повторюються 2 рази. Дивитися:

P₇^2,2 =  7!
2!·2!

P₇^2,2 = 7·6·5·4·3·2·1
2·1·2·1

P₇^2,2 = 5040
4

P₇^2,2 = 1260

Луїс Пауло Морейра
Закінчив математику