Як обчислити комбінації та перестановки

Зміст

• Замовлення та фактори
• Перестановки з повторенням
• Перестановки без повторення
• Комбінації без повторень
• Поєднання з повторенням

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

Замовлення та фактори

Факторна функція часто використовується при обчисленні комбінацій та перестановок. N! означає N × (N – 1) × ... × 2 × 1. Наприклад, 5! = 5 × 4 × 3 × 2 × 1 = 120. Кількість способів замовлення набору предметів є факторіальним. Візьміть три букви a, b і c. У вас є три варіанти для першого листа, два для другого і лише один для третього. Іншими словами, загалом 3 × 2 × 1 = 6 замовлень. Загалом, є n! способи замовлення n предметів.

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

Припустимо, у вас є три кімнати, які ви збираєтесь малювати, і кожна буде пофарбована одним із п’яти кольорів: червоним (r), зеленим (g), синім (b), жовтим (y) або помаранчевим (o). Кожен колір можна вибирати стільки разів, скільки вам подобається. У вас є п’ять кольорів на вибір для першої кімнати, п'ять для другої та п'ять для третьої. Це дає в цілому 5 × 5 × 5 = 125 можливостей. Загалом, кількість способів відбору групи r елементів у певному порядку з n повторюваних варіантів становить n ^ r.

Перестановки без повторення

Тепер припустимо, що кожна кімната буде іншого кольору. Ви можете вибрати з п’яти кольорів для першої кімнати, чотирьох для другої та лише трьох для третьої. Це дає 5 × 4 × 3 = 60, що буває 5! / 2 !. Загалом, кількість незалежних способів відбору r елементів у певному порядку з n неповторюваних варіантів становить n! / (N – r) !.

Комбінації без повторень

Далі забудьте про те, яка кімната якого кольору. Просто виберіть три незалежні кольори для кольорової гами. Порядок тут не має значення, тому (червоний, зелений, синій) такий же, як (червоний, синій, зелений). Для будь-якого вибору трьох кольорів є 3! способи їх замовлення. Так ви зменшите кількість перестановок на 3! щоб отримати 5! / (2! × 3!) = 10. Загалом, ви можете обрати групу r елементів у будь-якому порядку з вибору n неповторних варіантів n! / способів.

Поєднання з повторенням

Нарешті, вам потрібно створити колірну схему, в якій ви можете використовувати будь-який колір стільки разів, скільки вам потрібно. Розумний код бухгалтерії допомагає цьому завдання підрахунку. Використовуйте три X для представлення кімнат. Ваш список кольорів представлений rgbyo. Змішайте Xs у вашому списку кольорів та з’єднайте кожен X із першим кольором зліва від нього. Наприклад, rgXXbyXo означає, що перша кімната зелена, друга - зелена, а третя - жовта. X повинен мати принаймні один колір зліва, тому для першого X існує п'ять доступних слотів. Оскільки тепер у списку є X, є шість доступних слотів для другого X та сім доступних слотів для третього X. В все, є 5 × 6 × 7 = 7! / 4! способи написання коду. Однак порядок номерів довільний, тому дійсно лише 7! / (4! × 3!) Унікальних композицій. Загалом, ви можете вибрати r елементів у будь-якому порядку з n повторюваних варіантів (n + r – 1)! / Способів.