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

Задача. Из 28 студентов группы 14 человек занимаются плаванием, 18 человек – баскетболом, 12 студентов – легкой атлетикой, 8 – плаванием и баскетболом, 7 – легкой атлетикой и баскетболом, 6 – плаванием и легкой атлетикой, 3 студентов занимаются и плаванием, и баскетболом, и легкой атлетикой. Сколько в группе студентов, которые не занимаются ни одним из данных видов спорта?

Решение. Обозначим через p − увлечение плаванием, через b − увлечение баскетболом, через a − увлечение легкой атлетикой. Подсчитаем, сколько студентов в данной группе не занимаются ни одним из данных видов спорта, то есть найдем чему равно N().

По условию задачи имеем N(p)=14, N(b)=18, N(a)=12, N(pb)=8, N(ba)=7, N(pa)=6, N(pba)=3.

Значит, по формуле включений и исключений получаем, что N()=28−14−18−12+8+7+6−3=2.

Ответ: 2 студента не занимаются ни одним из данных видов спорта.

Решите задачи, предложенные на странице 28, с помощью формулы включений и исключений.

Задача. Сколькими способами можно отправить 8 различных фотографий, использовав при этом 5 различных конвертов?

Решение. Решим задачу, используя формулу включений и исключений.

Найдем сначала, при скольких способах распределения данные k конвертов оказываются пустыми (а остальные могут быть как пустыми, так и содержать фотографии). В этом случае фотографии кладутся без ограничений в (5−k) конвертов, число таких распределений равно . Но k конвертов можно выбрать из пяти способами.

Отсюда, применяя формулу включений и исключений, выводим, что число распределений, при которых ни один конверт не оказывается пустым, равно

Ответ: 126000 способами.

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

Число способов распределения выражается формулой:

Рассмотрим общее утверждение.

Пусть имеются , предметов первого вида, предметов второго вида, …, предметов k-го вида. Сколькими способами можно раздать их т лицам так, чтобы каждый получил хотя бы один предмет?

Число способов распределения выражается формулой:

Задача. Необходимо разделить 8 яблок, 10 груш и 7 апельсинов между 4 ребятами, при этом каждый должен получить хотя бы один фрукт. Сколькими способами можно это сделать?

Решение. Число способов распределения фруктов между детьми выражается формулой:

Ответ: 5239688 способами.

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

Задача. Имеется n различных сигнальных флагов и m мачт, на которые их вывешивают. Значение сигнала зависит от того, в каком порядке развешены флаги. Сколькими способами можно развесить флаги, если все флаги должны быть использованы, но некоторые из мачт могут оказаться пустыми?

Решение. Каждый способ развешивания флагов является комбинацией двух этапов. Первый − определение конфигурации, то есть мест, на которых будут висеть n флагов на m мачтах. На этом этапе не учитывается ни форма, ни окраска флага, все флаги считаются одинаковыми. Тогда, как мы уже знаем, п флагов можно развесить на m различных мачтах способами.

Второй этап − заполнение всех этих n мест конкретными флагами. Это можно сделать n! способами, потому что можно заполнить эти n мест флагами произвольным образом, а потом переставлять флаги друг с другом всевозможными способами, не меняя конфигурации. Число таких перестановок равно n!.

Значит, для каждой конфигурации размещения флагов получается n! конкретных способов развешивания флагов. Общее же число способов развешивания флагов равно:

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

28. Сколькими способами можно расставить 20 разных книг в книжном шкафу с 5 полками, если каждая полка может вместить все 20 книг?

29. Сколькими способами можно надеть 5 различных колец на пальцы одной руки, исключая большой палец?

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

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

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

Приведем один известный пример из области комбинаторики.

Задача. Пусть требуется назначить n рабочих на n различных работ, причем каждая работа должна выполняться только одним рабочим. Сколькими способами можно осуществить такое назначение?

Решение. Поставим в соответствие рабочим − горизонтали шахматной доски n×n, а работам − ее вертикали. Если i-й рабочий назначается на j-ю работу, то поле, соответствующее пересечению i-й горизонтали и j-й вертикали, займем ладьей. Так как каждая работа выполняется одним рабочим и каждый рабочий назначается на одну работу, то в результате расстановки n ладей все вертикали и горизонтали доски будут содержать по одной ладье, то есть ладьи не могут бить друг друга. Итак, задаче о назначении можно придать шахматную формулировку.

Задача. Сколькими способами можно расставить n ладей, которые не могли бы бить друг друга, на доске размера n×n?

Решение. Заметим, что при любом расположении более n ладей найдется хотя бы одна вертикаль и хотя бы одна горизонталь с двумя или более ладьями, то есть n − это наибольшее число мирных ладей на доске n×n. Одна из расстановок восьми мирных ладей на обычной доске приведена на рисунке 8.

Рис.8

Выясним например, сколько всего существует искомых расстановок n ладей на доске n×n. На первую вертикаль можно произвольно поставить одну из n ладей затем на вторую вертикаль − одну из (n-1) оставшихся ладей, причем горизонталь, занятая первой ладьей исключается (ладьи не должны угрожать друг другу) на третью вертикаль − одну из (n-2) оставшихся (горизонтали, занятые первыми двумя ладьями, исключаются) и т.д., вплоть до (n-1)-й вертикали, на которой для ладьи остается выбор из двух горизонталей, и последней, n-й вертикали, с единственным полем для ладьи. Комбинируя n различных расположений ладьи на первой вертикали с (n-1) расположением на второй, (n-2) − на третьей и т.д., получаем n(n-1)∙…∙2·1=n! различных расположений ладей. Это число и является искомым.

В частности, на обычной доске восемь ладей, не угрожающих друг другу, можно расположить 8!=40320 способами.

Если ладьи занумерованы числами от 1 до n, то существует уже (n!)² расположений ладей, не угрожающих друг другу. Это следует из того, что n подходящих полей можно выбрать n! способами; столько же способов имеется для расположения на этих полях n занумерованных ладей.

Итак, n рабочих можно назначить на n работ n! различными способами. Пусть выбрано назначение, соответствующее рисунку 7, то есть i-го рабочего назначили на i-ую работу, и требуется сделать новое назначение с учетом того, что каждый рабочий хочет поменять свою предыдущую работу. Сколько существует таких назначений? Эта задача имеет иную ладейную формулировку.

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

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

Для n=8 получаем 4833, то есть при дополнительном условии число расстановок восьми ладей, не угрожающих друг другу, уменьшается почти втрое.

Задача. Сколькими способами можно расставить k ладей на m×n доске так, чтобы, они не могли бить друг друга.

Решение. Ясно, что для разрешимости задачи нужно, чтобы выполнялись условия k<m и k<n − иначе какие-то две ладьи попадут на одну и ту же горизонталь или вертикаль. Пусть эти условия выполнены. Тогда расстановку ладей можно осуществить в два этапа. Сначала выберем горизонтали, на которых будут стоять ладьи. Так как общее число горизонталей равно m, а надо выбрать k горизонталей, то выбор можно сделать способами. Точно так же вертикали, на которых будут стоять ладьи, можно выбратьспособами. Поскольку выбор вертикалей не зависит от выбора горизонталей, то по правилу произведения получаем ∙ способов выбора линии, где стоят ладьи.

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

Задача. Сколькими способами можно расставить три ладьи на обычной шахматной доске?

Решение. Три ладьи на обычной шахматной доске можно расставить способами.

При к=т=п формула дает ответ n!.

Еcли снять ограничение, что ладьи не могут бить друг друга, то ответ будет иной. Именно, нам надо было бы выбрать из m×n клеток любые k клеток. А это можно сделать способами. А если быk ладей различались друг от друга, то полученные ответы надо было бы еще умножить на k!.

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

Самым простым является случай, когда требуется, чтобы ладьи стояли симметрично относительно центра доски (Рис.9)

Рис.9

Обозначим через число решений задачи, когда n ладей стоят на доске из n горизонталей и n вертикалей. Тогда имеет место рекуррентное соотношение .

В самом деле, будем ставить 2n ладей на доску размера 2n×2n. Ладья, стоящая на первой вертикали, может занять на ней любое из 2n полей. По условию этим определяется положение ладьи, стоящей на последней вертикали − она должна расположиться симметрично с первой ладьей относительно центра доски. Вычеркнем первую и последнюю вертикали, а также занятые стоящими на них ладьями горизонтали (так как число горизонталей четно, выбрасываемые ладьи не могут стоять на одной и той же горизонтали) и, если горизонтали не крайние, то «сомкнем ряды» на доске. Получается () горизонталей и () вертикалей. Ясно, что каждому симметричному расположению ладей на новой доске соответствует симметричное исходное расположение ладей. Отсюда и вытекает, что .

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

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

Задача. Сколькими способами можно расставить n мирных ладей на доске n×n, если k из них − белые и (n−k) − черные?

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

Рассмотрим снова расстановку на рисунке. Мы видим, что восемь ладей способны взять под обстрел все поля шахматной доски. Соответственно, для охраны всей доски n×n достаточно иметь n ладей. Если ладей меньше, чем n, то по крайней мере одна ее вертикаль и одна горизонталь окажутся пустыми и, значит, поле, стоящее на их пересечении, не будет атаковано.

Сколькими способами можно расставить n ладей на доске n×n так, чтобы они держали под обстрелом все поля доски?

Если n ладей охраняют доску, то либо на каждой вертикали, либо на каждой горизонтали стоит хотя бы одна из них (если существуют вертикаль и горизонталь, свободные от ладей, то поле, находящееся на их пересечении, не атаковано). Число расстановок i ладей − по одной на каждой вертикали равно nⁿ (первую ладью можно поставить на одно из n полей первой вертикали; вторую, независимо от первой, на одно из n полей второй вертикали и т.д.). Столько же имеется расстановок и по одной на каждой горизонтали. На первый взгляд кажется, что общее число расположений ладей равно nⁿ+nⁿ=2nⁿ. Однако при таком подсчете дважды учитываются расстановки, в которых на каждой вертикали и на каждой горизонтали стоит по одной ладье. Так как каждая из них характеризуется тем, что никакая пара ладей не угрожает друг другу, то решением задачи является число 2·nⁿ−n!. Число расстановок восьми ладей, обстреливающих обычную доску, равно 2·8⁸−8!=33514312.

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

30. Сколькими способами можно расставить 4 мирных ладьи на доске 8×8, если 2 из них − белые и 2 − черные?

31. Сколькими способами можно расставить 8 ладей, которые не могли бы бить друг друга, на доске размера 8×8?

32. Сколькими способами можно расставить 4 ладьи на обычной шахматной доске?

33. Сколькими способами можно поставить 20 белых шашек на шахматной доске так, чтобы это расположение не менялось при повороте доски на 90°?