Элементы комбинаторики

Выбор способа нахождения числа возможных перестановок и комбинаций k элементов из их общего числа n выполняется с учетом комбинаторных конфигураций. Основными комбинаторными конфигурациями являются:

- Правило произведения

- Перестановка

- Выборка с возвращением

- Сочетание

- Размещение

Правило произведения применяется когда необходимо определить число способов (m), которыми могут быть выполнены одно за другим k действий. Если первое действие можно выполнить n1 способами, второе n2 способами и так до nk –го действия, то возможное число способов равно

m = n₁ * n₂ * n_k.

Задача: в гардеробе имеется 5 различных галстуков, 8 рубашек и 3 заколки для галстука.

Решение: общее число разных вариантов по их использованию в одном комплекте согласно правилу произведения будет равно

m =5 * 8 * 3 = 120.

В программе Excel такие вычисления выполняются формулой =5*8*3.

Перестановка – это такие выборки элементов, которые отличаются только порядком расположения элементов. Число перестановок из n элементов (например чисел 1,2,…,n) называется всякий упорядоченный набор из этих элементов. Возможное число перестановок из n элементов определяется по формуле:

A_n = 1 * 2 * 3 * … * (n−2) * (n−1) * n = n!, где A_n=число перестановок.

Обозначение n! означает факториал числа, например

4! = 1*2*3*4 = 24.

В программе Excel для вычисления факториала применяется функция =ФАКТР(n), поэтому формула в ячейке Excel = ФАКТР(4) даст результат 24.

Задача: за круглый стол садятся 7 человек.

Решение: ч исло возможных вариантов их размещения за столом равно

A7 = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 7! = ФАКТР(7) = 5040.

Выборка с возвращением

Выборка с возвращением – это число способов (m), которыми можно создать комбинацию из n элементов k действиями с возвращением элементов в исходное множество. В этом случае число способов, которыми можно выполнить k действий, для множеств (n) с одинаковым числом элементов (с возвратом выбранных элементов в множество) равно

m = n^k.

Задача: при кодировании замков деверей учебных классов используются трёхзначные номера из 5 цифр от 0 до 5.

Решение: число различных кодов, которые можно составить, равно

m =5³ = 125.

В программе Excel такие вычисления выполняются формулой =5^3.

Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов, при этом наборы отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми. Этим сочетания отличаются от размещений. Такие неупорядоченные выборки называются сочетаниями из n элементов по k и обозначаются С_n^k.

Выборка без возвращения (число возможных вариантов).

Выборка без возвращения - сочетание из n элементов с выбором k из них без возвращения в исходное множество. Число возможных сочетаний определяется по формуле:

Число сочетаний определяется по формуле С_n^k = n! / k! *(n − k)!.

где: C ^k_n – число сочетаний;

n - общее число элементов;

k – выбираемое число элементов.

Обозначение n! означает факториал числа, например 4! = 1*2*3*4 = 24.

Задача: Сколько сочетаний можно составить из 36 карт игральной колоды, из которой выбирается по 2 карты без учёта порядка расположения этих карт, при условии, что выбранная карта не возвращается в колоду.

Решение: C²₃₆ =36!/2!(36-2)! =

= 371 993 326 789 901 000 000 000 000 000 000 000 000 000 / 2 * 295 232 799 039 604 000 000 000 000 000 000 000 000 =

= 3,72E+41 / 2 * 2,952E+38

= 630

В программе Excel такие вычисления выполняет функция =ЧИСЛКОМБ(N;K), например =ЧИСЛКОМБ(63;2) = 360.

Размещением (выборочной перестановкой) из n элементов по k (мест) называются такие выборки, которые имея по k элементов, выбранных из числа данных n элементов, отличаются одна от другой либо составом элементов, либо порядком их расположения. Размещением считается упорядоченный набор из k различных элементов некоторого n -элементного множества.

Число размещений из n по k обозначается A _n^k и определяется по формуле
A _n ^k = n ·(n − 1)·(n − 2)·...·(n − m + 1) = n!/ (n − k)!.

Или:

В Excel эти вычисления выполняются функцией =ПЕРЕСТ(n;k).

Задача: Сколько всего сочетаний можно составить из 36 по 2 с учётом порядка расположения этих 2-х карт, при условии, что выбранные карты возвращаются в колоду.

Решение: A²₃₆ = 36!/(36-2)!= 36!/(34)!=

= 371 993 326 789 901 000 000 000 000 000 000 000 000 000 / 295 232 799 039 604 000 000 000 000 000 000 000 000 =

= ПЕРЕСТ(36;2) = 1260

Если при выполнении размещения выбираются все элементы множества, т.е. n=k, то такое размещение является перестановкой (см.выше) и тогда функция =ПЕРЕСТ(n;k) дает одинаковы результат с функцией ФАКТР(n). Например, число возможных вариантов размещения за круглым столом 7 человек равно

A ₇ = 1 * 2 * 3 * 4 * 5 * 6 * 7 = 7! =ПЕРЕСТ(7;7)= ФАКТР(7) = 5040.