МЕТОДЫ ПЕРЕБОРА РАЗЛИЧНЫХ ВАРИАНТОВ

МЕТОДЫ ПЕРЕБОРА РАЗЛИЧНЫХ ВАРИАНТОВ

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

·                       когда конфигурации составляют из одинаковых элементов или из различных;

·                       когда конфигурации содержат данный элемент ровно один раз, не более одного раза, хотя бы один раз, более одного раза;

·                       когда порядок извлечения элементов будет существенным или несущественным при составлении конфигураций;

·                       когда конфигурация образуется выбором элементов с возращением или без возращения.

Сущность метода перебора вариантов лучше всего рассматривать на примерах.

Задача. Если сначала подкинуть одну монету номиналом в 1 рубль, а потом другую номиналом в 2 рубля – какими способами они могут упасть на стол?

Решение. Монета может упасть на стол двумя способами – орел или решкой.

Чтобы выписать все возможные варианты обозначим номинал монеты цифрами 1 и 2, а сторону О и Р – орел и решка, т. е. закодируем предметы и необходимые нам признаки. Возможные варианты:

1О 2О                   1Р 2О

1О 2Р                    1Р 2Р

Рассмотрим второй способ перебора, основанный на построении так называемого дерева возможных вариантов.

Построим дерево перебора вариантов А (рис.1). На первом уровне дерева А поместим все способы падения первой монеты – орел и решка, а на втором – все способы падения второй монеты.

Таким образом, получается, что в дереве всего 4 пути. Каждый путь дерева – это последовательность, первый член – одна из сторон первой монеты, а второй член – одна из сторон второй монеты. 

Рис. 1. Дерево перебора вариантов А

Третий способ (набор точек и отрезков (метод графов)) применим в том случае, когда из некоторой совокупности предметов выбирают два. Изобразим шары в виде точек, расположенных так, что никакие три точки не лежат на одной прямой. Затем соединяем каждые две точки отрезков прямой (рис. 2). И снова получаем тот же результат.

Рис. 2. Метод графов

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

Номинация монетки	№ варианта
	1	2	3	4
Один рубль	О	О	Р	Р
Два рубля	О	Р	О	Р