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

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

Інструкція

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

У попередньому випадку кількість можливих елементів і кількість місць ряду збігалися, і їх число було рівне N. Але можлива ситуація, коли в ряду менше місць, ніж є можливих елементів. Іншими словами, кількість елементів у вибірці дорівнює деякому числу M, причому M < N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
По-перше, може знадобитися порахувати загальну кількість можливих способів, якими можна вибудувати в ряд M елементів з N. Такі способи називаються розміщеннями.
По-друге, дослідника може цікавити число способів, якими можна вибрати M елементів з N. При цьому порядок розташування елементів вже не важливий, але будь-які два варіанти повинні відрізнятися між собою хоча б одним елементом. Такі способи називаються сполученнями.

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

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