Комбинаторика в Excel

Комбинаторика — раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения элементов) и отношения на них. Термин комбинаторика был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». Excel поддерживает ряд функций комбинаторики. Чтобы разобраться, какую формулу использовать, следует ответить на ряд вопросов:

1. Исходное множество содержит только уникальные элементы, или некоторые из них могут повторяться?
2. Операция выполняется со всеми элементами множества, или только с некоторой выборкой из них?
3. Важен ли порядок элементов в выборке?
4. После выбора элемента мы его возвращаем назад?

Рис. 1. Дерево решений, какую формулу комбинаторики использовать

Скачать заметку в формате Word или pdf, примеры в формате Excel

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

Возьмем несколько различных элементов (предметов) и будем переставлять их всевозможными способами, оставляя неизменным их число и меняя только их порядок (рис. 2). Каждая из получившихся таким образом комбинаций носит название перестановки. Перестановкой из n элементов называется упорядоченное множество, составленное из всех элементов множества.

Рис. 2. Перестановки (картинка взята здесь)

Если все n элементы разные, то число перестановок обозначается Pn от perturbation.

С другой стороны, произведение n первых натуральных чисел называется n-факториал и обозначается n!

Например

По определению: 1! = 1; 0! = 1.

Функция в Excel =ФАКТР(n). Факториал растет очень быстро. Существенно быстрее экспоненты (рис. 3).

Рис. 3. Расчет числа перестановок без повторений с помощью факториала

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

Если в основном n множестве не все элементы разные, то число перестановок будет меньше n! Например, если наше множество состоит из трех яблок и одной груши, то всего возможно 4 перестановки (рис. 4). Груша может быть первой, второй, третьей или четвертой, а яблоки неразличимы).

Рис. 4. Перестановки с повторениями (картинка найдена здесь)

В общем случае, можно сказать: последовательность длины n, составленная из k разных символов, первый из которых повторяется n1 раз, второй – n2 раз, третий – n3 раз, …, k-й – nk раз (где n1 + n2 + … + nk = n) называется перестановкой с повторениями из n элементов.

Пример. Сколько различных пятибуквенных слов можно составить из букв слова «манна»?

Решение. Буквы а и н повторяются 2 раза, а буква м один раз.

Размещение без повторений

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

Например, два элемента из трех можно выбрать и расположить шестью способами (рис. 4):

Рис. 5. Размещение без повторений (картинка из презентации)

Если m = n количество элементов совпадает с количеством имеющихся мест для размещения. Знаменатель в формуле (4) превращается в 0! = 1. Остается только числитель n! А это – изученная выше перестановка без повторений; см. формулу (1).

Название функции в Excel несколько обескураживает. Но… что поделаешь: =ПЕРЕСТ(n;m)

Рис. 6. Размещение без повторений; обратите внимание на смешанные ссылки, которые позволяют протянуть формулу на всю таблицу

Размещение с повторениями

Размещение с повторениями по смыслу отличается от перестановок с повторением. Перестановки с повторением – это операция над множеством, которое состоит из нескольких видов элементов, так что каждый вид представлен несколькими одинаковыми элементами. Размещение с повторениями – выборки из множества с возвращением выбранного элемента назад перед каждым новым выбором.

Например, если у вас множество, включающее грушу, яблоко и лимон, и вам нужно выбрать два элемента, так что после первого выбора вы возвращаете выбранный предмет назад, то существует девять различных комбинаций (рис. 7).

Рис. 7. Размещение с повторениями

В общем случае размещение с повторениями или выборка с возвращением – это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз. По правилу умножения количество размещений с повторениями из n по k:

Задача. Сколько различных номеров можно составить в одном коде региона?

Подсказка. В номере используется 12 букв алфавита, также существующих и в латинском алфавите (А, В, Е, К, М, Н, О, Р, С, Т, У, Х).

Рис. 8. Номер автомобиля

Решение. Можно воспользоваться формулой для размещения с повторениями:

Каждую цифру можно выбрать 10 способами, а всего цифр 3, при этом они могут повторяться, и их порядок важен. Каждую букву можно выбрать 12 способами, при этом буквы могут повторяться, и их порядок важен.

Сочетания без повторений

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

Например, два элемента из 4 сочетаются 6 способами (порядок следования не важен):

Рис. 9. Сочетания без повторений из 4 по 2

Сочетания без повторений образуют знаменитый треугольник Паскаля (рис. 10). В этом треугольнике на вершине и по бокам стоят единицы. Каждое число равно сумме двух расположенных над ним чисел. Строки треугольника симметричны относительно вертикальной оси. Числа в строках, составляющие треугольник Паскаля, являются сочетаниями

где n – номер строки, m – номер элемента в строке, начиная с нулевого. Например, в строке 7:

Рис. 10. Треугольник Паскаля; чтобы увеличить изображение кликните на нем правой кнопкой мыши и выберите Открыть картинку в новой вкладке

В Excel используется функция =ЧИСЛКОМБ(n;m).

Сочетания с повторениями

Сочетания с повторениями по смыслу похожи на размещение с повторениями – это выборки из множества с возвращением выбранного элемента назад перед каждым новым выбором. При этом порядок в выборке не важен.

Например, два предмета из четырех можно выбрать 10 способами, если после каждого выбора предмет возвращается назад (рис. 11).

Рис. 11. Сочетания с повторениями

В общем случае, число сочетаний с повторениями:

Для нашего примера с фруктами

В Excel для подсчета числа сочетаний с повторениями используется функция =ЧИСЛКОМБА(n;m). В нашем примере =ЧИСЛКОМБА(4;2) = 10.

Калькулятор ниже предназначен для генерации всех сочетаний из n по m элементов.
Число таких сочетаний, как можно рассчитать с помощью калькулятора Элементы комбинаторики. Перестановки, размещения, сочетания.

Описание алгоритма генерации под калькулятором.

Алгоритм

Комбинации генерируются в лексикографическом порядке. Алгоритм работает с порядковыми индексами элементов множества.
Рассмотрим алгоритм на примере.
Для простоты изложения рассмотрим множество из пяти элементов, индексы в котором начинаются с 1, а именно, 1 2 3 4 5.
Требуется сгенерировать все комбинации размера m = 3.
Сначала инициализуется первая комбинация заданного размера m — индексы в порядке возрастания

1 2 3 Далее проверяется последний элемент, т. е. i = 3. Если его значение меньше n — m + i, то он инкрементируется на 1.

1 2 4 Снова проверяется последний элемент, и опять он инкрементируется.

1 2 5 Теперь значение элемента равно максимально возможному: n — m + i = 5 — 3 + 3 = 5, проверяется предыдущий элемент с i = 2.

Если его значение меньше n — m + i, то он инкрементируется на 1, а для всех следующих за ним элементов значение приравнивается к значению предыдущего элемента плюс 1.
1 (2+1)3 (3+1)4 = 1 3 4
Далее снова идет проверка для i = 3.

1 3 5 Затем — проверка для i = 2.

1 4 5 Потом наступает очередь i = 1.

(1+1)2 (2+1)3 (3+1)4 = 2 3 4
И далее,

2 3 52 4 53 4 5 — последнее сочетание, так как все его элементы равны n — m + i.