Як порахувати кількість комбінацій

Як порахувати кількість комбінацій

Припустимо, що дані N елементів (чисел, предметів і т.д.). Потрібно дізнатися, скількома способами ці N елементів можна розташувати в ряд. У більш точних термінах, потрібно обчислити кількість можливих комбінацій з цих елементів.

Інструкція

  1. Якщо передбачається, що в ряд входять всі N елементів, і ні один не повторюється, то це завдання про кількість перестановок. Рішення можна знайти простим міркуванням. На першому місці в ряду може стояти будь-який з N елементів, отже, виходить N варіантів. На другому місці — будь-який, крім того, який вже був використаний для першого місця. Отже, для кожного з N вже знайдених варіантів є (N — 1) варіантів другого місця, і загальна кількість комбінацій стає N * (N — 1).

    Це ж міркування можна повторити для інших елементів ряду. Для самого останнього місця залишається тільки один варіант — останній залишився елемент. Для передостаннього — два варіанти, і так далі.

    Отже, для ряду з N неповторюваних елементів число можливих перестановок дорівнює добутку всіх цілих чисел від 1 до N. Цей твір називається факторіалів числа N і позначається N! (Читається «ен факторіал»).
  2. У попередньому випадку кількість можливих елементів і кількість місць ряду збігалися, і їх число дорівнювало N. Але можлива ситуація, коли в ряду менше місць, ніж є можливих елементів. Іншими словами, кількість елементів у вибірці одно деякого числа M, причому M комбінацій може мати два різні варіанти.

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

    По-друге, дослідника може цікавити число способів, якими можна вибрати M елементів з N. При цьому порядок розташування елементів вже не важливий, але будь-які два варіанти повинні відрізнятися між собою хоча б одним елементом. Такі способи називаються сполученнями.
  3. Щоб знайти кількість розміщень з M елементів з N, можна вдатися до такого ж способу міркувань, як і у випадку з перестановками. На першому місці тут як і раніше може стояти N елементів, на другому (N — 1), і так далі. Але для останнього місця кількість можливих варіантів дорівнює не одиниці, а (N — M + 1), оскільки, коли розміщення буде закінчено, залишиться ще (N — M) невикористаних елементів.

    Таким чином, число розміщень з M елементів з N дорівнює добутку всіх цілих чисел від (N — M + 1) до N, або, що те ж саме, приватному N! / (N — M)!.
  4. Очевидно, що кількість сполучень по M елементів з N буде менше кількості розміщень. Для кожного можливого поєднання є M! можливих розміщень, що залежать від порядку елементів цього поєднання. Отже, щоб знайти цю кількість, потрібно розділити число розміщень з M елементів з N на N!. Іншими словами, кількість сполучень по M елементів з N одно N! / (M! * (N — M)!).