Решение комбинаторных задач

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

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

Комбинаторные навыки оказались полезными и в часы досуга. Нельзя точно сказать, когда наряду с состязаниями в беге, метании диска, прыжках появились игры, требовавшие в первую очередь, умения рассчитывать, составлять планы и опровергать планы противника.

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

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

Задачи, в которых идет речь о тех или иных комбинациях объектов, называется комбинаторными. Область математики, в которой изучаются комбинаторные задачи, называются комбинаторикой.

Комбинаторика как наука стала развиваться в 18 веке параллельно с возникновением теорией вероятности, так как для решения вероятностных задач необходимо было подсчитать число различных комбинаций элементов.

Первые научные исследования по комбинаторике принадлежат итальянским ученым Дж. Кардана, Н. Тарталье (ок. 1499-1557), Г. Галилею (1564-1642) и французским ученым Б. Паскалю (1623-1662) и П. Ферма. Комбинаторику, как самостоятельный раздел математики, а первым стал рассматривать немецкий ученый Г. Лейбниц в своей работе об искусстве комбинаторики, опубликовал в 1666 г. Он также впервые ввел термин комбинаторика. Значительный вклад в развитие комбинаторики внес Л. Эйлер. В современном обществе с развитием вычислительной техники комбинаторика добилась новых успехов. Так, с помощью ЭВМ была решена комбинаторная задача, известная под названием проблема четырех красок удалось доказать, что любую карту можно раскрасить в четыре цвета так, что никакие обе страны, имеющие общую границу, не будут окрашены в один и тот же цвет.

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

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

ПЕРЕСТАНОВКА.

Различают три типа комбинаций: перестановки, размещение и сочетания.

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

Размещение из n элементов по к комбинации, составленные из n данных элементов по к элементов в каждой.

Два размещения считаются различными, если они отличаются либо элементами, либо их порядком.

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

Обозначение: P (n) – число перестановок из n элементов по к элементов; An, к – число размещений из n элементов по к элементов; Cn,к – число сочетаний из n элементов по к элементов. Например:

1. Для того, чтобы определить сколько четырехзначных чисел можно записать с помощью цифр 1,2,3,4 при условии, что каждая цифра входит в изображение числа только один раз, необходимо вычислить Р (4) = 4! = 1 * 2 * 3 * 4 = 24.

2. Если необходимо определить количество трехзначных чисел, записываемых нечетными цифрами 1,3,5,7,9 при условии, что каждая цифра входит в изображение числа только один раз, то используют формулу для размещений: Аn,к = _n!_ В нашей задаче это А5,3 = _5!_= _5!_ = 60.

(n – k)! (5-3)! 2!

Следовательно, таких чисел можно записать 60.

3. Если необходимо определить, сколькими способами можно расположить в ряд 5 черных и 5 белых шашек, то для этого используется формула для сочетаний: Сn,k = _10!_= _6*7*8*9*10_ = 252. Следовательно таких способов 252.

5! 5! 1*293*4*5

Число размещений и число перестановок связаны формулой: A n,n = P(n) = n`.

Соотношение между числом размещение, сочетаний и перестановок:

ССn,к = _An,к_

Необходимо добавить, что бывают перестановки с повторениями, сочетания с повторениями.

Составить двухзначные числа 1, 4 и 7 решение построена специальная схема.

Эта схема действительно похожа на дерево, правда, «вверх ногами» и без ствола. Знак * изображает корень дерева, ветви дерева различные варианты решения. Чтобы получить двузначное число, надо сначала выбрать первую его цифру, а для этого есть три варианта: 1,4 и 7. Поэтому из точки * проведены три отрезка и на концах поставлены цифры 1,4 и 7. Затем надо выбрать вторую цифру, а для этого также есть три варианта: 1,4 и 7. Поэтому от каждой первой цифры проведены по три отрезка, на концах которых снова записано 1, 4 или 7. Итак, получено всего 9 различных двухзначных чисел. Других двузначных чисел из этих трёх цифр составить невозможно.

Любой номер, составленный из трех цифр, нельзя рассматривать как множество из трех элементов, так как:

1) в номерах цифры могут повторяться (например: 775), а множествах элементы не повторяется;

2) в номерах важен порядок цифр (175 и 571 – совсем разные номера), а в множествах порядок элементов роли не играет.

Поэтому при изучении таких объектов, как номера или слова (в них буквы могут повторяться, а от перестановки букв слово меняется), вводится новое математическое понятие «кортеж».

Определение: Пусть имеется несколько множеств н(1),,н(к). Представим себе, что их элементы сложены в мешки, а мешки пронумерованы. Вытащим из первого мешка какой-нибудь элемент (т. е. возьмем какой-нибудь элемент а(1) множество н(1)), затем вытащим элемент а(2) из мешка н(2) и будем продолжать этот процесс до тех пор, пока из мешка н(к) не будет вытащен элемент а(к). После этого расставим полученные элементы в том порядке в каком они появились из мешков (а(1), а(2),. , а(к)). Это и будет кортеж длина к, составлены из элементов н(1), н(2),, н(к). Элементы кортежа могут повторяться, т. к. в определении не сказано, что элементы множеств н(1), н(к),н(к) не могут иметь одинаковых элементов.

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

Примером кортежа длина 5 являются номера телефонов в городе Салехарде, они составлены из элементов множества Х = {0,1,2,3,4,5,6,7,8,9}. Слова русского алфавита, а предложения – кортежа, составленные из русских слов.

Правило произведения: Если элемент а(1) можно выбрать n(1) способами, после каждого выбора этого элемента следующий за ним элемент а(2) можно выбрать n(2) способами, а после выбора элементов а(1),а(r-1) элемент а(r) выбирается n(r) способами, то кортеж (а(1), а(2),а(r)) можно выбрать n (1) * n (2)* n (r) можно выбрать n (1) * n (2)* n (r) способами.

Задача: Сколькими способами можно выбрать гласную и согласную буквы слова «полка»?

Решение: в этом слове две гласные буквы (о, а) и три согласные (п, л, к). Каждый искомый выбор задается картежом (а(1), а(2)), где а(1) – гласная буква, а(2) – согласная. Так как а(1) можно выбрать двумя способами, а а(2) тремя способами, то кортеж (а(1), а(2)) можно по правилу произведения выбрать 2*3=6 способами.

Ответ: 6 способов.

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

Записать всевозможные двузначные числа, используя при этом:

1) цифры 1,2 и 3;

2) цифры 0,1,2 и 3 подсчитать их количество N.

Задача: Продают две игральные кости (каждая кость – кубик с отмеченным на его гранях точками). Одной до шести, причем на различных гранях разное число точек. Сколько различных пар точек может появиться на верхних гранях костей?

Решение: Для каждого случая составим таблицу вариантов:

N = 3*3 =9 N = 3*4 = 12

Ответ: 1) N = 9; 2) N = 12.

При решении задач, аналогичных задачам необязательно каждый раз составлять таблицу вариантов. Можно пользоваться правилом, которое получило в комбинаторике названии «Правило произведение», если существует n вариантов выбора первого элемента и для каждого из них есть m вариантов выбора второго элемента, то всего существует n*m различных пар с выбранными первым и вторыми элементами.

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

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

Задача: Андрей, Борис, Виктор и Григорий играли в шахматы. Каждый сыграл с каждым по одной партии. Сколько партий было сыграно?

Решение: Решим задачу с помощью полного графа с четырьмя вершинами А,Б,В,Г. Обозначенными первыми буквами имени каждого из мальчиков. В полном графе проводятся всевозможные ребра. В данном случае отрезки ребер обозначают органные шахматные партии. Из рисунка видно, что граф имеет 6 ребер, значит, и партий было сыграно 6.

Ответ: 6 партий.

Граф дерево.

Задача: Антон, Борис, Василий купили 3 билета на 1,2,3 места первого ряда на футбольный мачт. Сколькими способами они могут занять имеющиеся места?

Решение: на 1-е место может сесть любой из трех друзей, на 2 любой их двух оставшихся, а на 3 последний. Сказанное изобразим с помощью дерева, помещая в вершины графа первые буквы А,Б и В: 1 место 2 место 3 место упорядочная тройка друзей. Ответ: 6.

Задачи фигуры, рисуемые одним росчерком.

У Лева 2 конверта: обычный и авиа и 3 марки: прямоугольная, квадратная и треугольная. Сколькими способами он может выбрать конверт и марку, чтобы отправить письмо?

Составьте множество двузначных чисел, которые можно записать с помощью цифр 1,2,3.

Сколько таких чисел? (9 способов).

Составьте множества трехзначных чисел, которые можно записать с помощью цифр 2 и 5.

Сколько таких чисел? 8 способов.

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

Первенство класса по настольному теннису 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводится по круговой системе каждый из участников играет каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной и Еленой; Борис как уже говорилось с Андреем и еще с Галиной, Дмитрием и Еленой; Галина – с Андреем, Борисом; Дмитрий с Виктором и Елена с Андреем и Виктором. Сколько игр проведено к настоящему моменту и сколько еще осталось?

Обсуждение: изобразим данные задачи в виде схемы. Участников будем изображать точными.

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

Получается схема. Такие схемы называются графиками.

Ответ: число игр, проведенных к настоящему моменту, рано числу ребер, т. е. семи.

Заметьте, что точки пересечения ребер графа не являются его вершинами. В изображении путаницы вершины графа часто изображают не точками, а маленькими кружочками. Ребра зачастую оказывается удобнее изображать не прямолинейными отрезками, а криволинейными «дугами».

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

Графами мы пользуемся довольно часто. Возьмите схему полезных дорог: здесь станции – это вершины графа, перегоны (участки пути между станциями) – ребра графа.

Вершины и ребра многогранника (куба, пирамида и т. д ), тоже образуют граф.

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

Задача 1: Из города А в город В ведут 5 дорог, а из города В в город С – 3 дороги. Сколько путей, проходящих через В, ведут из АВС?

Решение: Каждый путь школою видов задается картежом (а(1), а(2)), где а(1) – один из путей, соединяющих В и С. Так как по условию а(1) можно выбрать 5 способами, а(2) – 3способами, то картеж (а(1), а (2)) можно по правилу произведения составить 5*3 = 15 способами.

Ответ: 15 путей.

Задача 2: Имеется 6 перчаток различных размеров. Сколькими способами можно выбрать из них одну перчатку на левую руку так, чтобы эти перчатки были различных размеров?

Решение: Эту задачу тоже можно решить по правилу произведения. Перчатка на левую руку может быть выбрана 6 способами. После того как она выбрана, перчатку на правую руку можно выбрать лишь 5 способами. (Размеры перчаток должны быть разными). Поэтому всего имеет 6*5= 30 способов.

Ответ: 30 способов.

Задача 3: сколькими способами могут быть распределены золотая и серебренная медали по итогам первенства по футболу, если число команд 12.

Решение: На золотую медаль претендуют 12 команд, на серебренную 11 команд. (одна получит золотую медаль). По правилу произведения получаем 12 * 11 = 132 способа.

Ответ: 132 способа.

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

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