Главная Войти О сайте












Как посчитать количество комбинаций

Предположим, что даны 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)!).


CompleteRepair.Ru