Комбинаторика. Продолжение

3 свойство – основное свойство

Доказательство.

Комбинаторное доказательство.

Составим k-сочетание из n элементов а₁, а₂, …,a_n и разобьем их на два класса. В первый из них войдут сочетания, содержащие элемент a_n, во второй – не содержащие этого элемента. Если из любого сочетания первого класса откинуть элемент а_n, то останется (к –1)-сочетание, составленное из элементов а₁, а₂, …, a_n-1. Число таких сочетаний равно . Поэтому в первый класс входит комбинаций. Сочетания второго класса являются k-сочетаниями, составленными из элементов а₁, а₂, …,a_n-1. Поэтому их число равно . Поскольку любое k-сочетание принадлежит одному и только одному из этих классов, а общее число этих сочетаний равно , то, используя правило сложения, приходим к искомому равенству.

4 свойство:

Комбинаторное доказательство.

2ⁿ – число всех размещений с повторениями из элементов двух типов. Разобьем эти размещения на классы, отнеся в k-ый класс те, в которые входят k элементов первого типа и n–k элементов второго типа. Размещения k-го типа - это ни что иное, как всевозможные перестановки из k элементов первого типа и n–k элементов второго типа. Число таких перестановок равно P(k, n–k)=C(n, k). По правилу суммы общее число размещений всех классов равно . С другой стороны, это же число равно 2ⁿ.

5 свойство:

Комбинаторное доказательство.

Выпишем все сочетания из n элементов а₁, …,а_n и сделаем следующее преобразование: к сочетанию, не содержащему элемент а₁, допишем его, а из сочетаний, куда оно входит, вычеркнем. Легко проверить, что при этом снова получаются все сочетания, и притом по одному разу. Но при этом преобразовании все сочетания, имевшие четное число элементов, превратятся в сочетания, имеющие нечетное число элементов, и обратно. Значит сочетаний с четным и нечетным количеством элементов одинаковое количество (пустое сочетание тоже входит в рассмотрение). Это и выражает данная формула.

Упражнение 1.

На окружности отмечено 11 точек. Сколько существует многоугольников с вершинами в отмеченных точках?

 

 

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

Задача.

В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?

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

Чтобы решить задачу, поступим следующим образом. Зашифруем каждую покупку с помощью нулей и единиц. Сначала напишем столько единиц, сколько куплено наполеонов. Потом, чтобы отделить наполеоны от эклеров, напишем нуль, затем – столько единиц, сколько куплено эклеров, и т. д. Например, если куплено 3 наполеона, 1 эклер, 2 песочных и 1 слоеное пирожное, то получим такую запись: 1110101101. Ясно, что разным покупкам соответствуют разные комбинации из 7 единиц и 3 нулей. Обратно, каждой комбинации 7 единиц и 3 нулей соответствует какая-то покупка.

Таким образом, число различных покупок равно числу перестановок с повторениями, которые можно составить из 7 единиц и 3 нулей. А это число равно P(7,3)=120.

К тому же самому результату можно было прийти и другим путем, а именно: расположим в каждой покупке пирожные в таком порядке: наполеоны, эклеры, песочные и слоеные, а потом перенумеруем их. Но при нумерации будем к номерам эклеров прибавлять 1, к номерам песочных – 2, к номерам слоеных – 3. К номерам наполеонов ничего прибавлять не будем. Например, пусть куплено 2 наполеона, 3 эклера, 1 песочное пирожное и 1 слоеное. Тогда эти пирожные нумеруются так: 1, 2, 4, 5, 6, 8, 10. Ясно, что самый большой номер может быть 10, самый маленький – 1, а кроме того, ни один из номеров не повторяется, причем они образуют возрастающую последовательность. Обратно, каждой возрастающей последовательности из 7 чисел соответствует некоторая покупка. Например, последовательность 2, 3, 4, 5, 7, 8, 9 соответствует покупке из 4 эклеров и 3 песочных пирожных. Чтобы убедиться в этом, надо отнять от заданных номеров числа 1, 2, 3, 4, 5, 6, 7. Мы получим числа 1, 1, 1, 1, 2, 2, 2. Но 1 мы прибавляли к номерам эклеров, а 2 – к номерам песочных.

Отсюда, общее число покупок равно числу возрастающих последовательностей из 7 чисел от 1 до 10. А число таких последовательностей равно C(10,7)=120.

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

Количество сочетаний с повторениямиизn элементов по k обозначают . Общее правило вычисления количества сочетаний с повторениями:

Доказательство

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

Встречаются задачи, в которых на сочетания с повторениями накладывается дополнительное условие, например, когда в комбинацию обязательно должны входить элементы r фиксированных типов, где r≤n. Эта задача легко сводится к уже решенной. Для того чтобы обеспечить присутствие заданных r типов, возьмем с самого начала по одному элементу каждого такого типа. Тем самым в k-сочетании окажутся заняты r мест. Поэтому ответом на задачу будет число . В частности, если требуется, чтобы в каждом сочетании был элемент каждого из типов (n≤k), то получится .

Задача.

Сколько существует различных бросаний двух одинаковых кубиков?

Решение.

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

Комбинаторика разбиений

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

 

Имеется n₁ предметов одного сорта, n₂ – другого, ... , n_k – k-го сорта. Сколькими способами можно разложить их в два ящика?

Так как в каждый ящик может попасть от 0 до n_i предметов i-го сорта (во второй все оставшиеся), по правилу произведения получаем (n₁+1)∙(n₂+1)∙...∙(n_k+1) способов раскладки.

Упражнение 2.

Двое ребят собрали 10 ромашек, 15 васильков и 14 незабудок. Сколькими способами они могут разделить эти цветы?

Следствие 1. Если все предметы различны (n₁=n₂=...=n_k=1), то их можно разложить 2^k способами.

Следствие 2. Если в каждый ящик нужно положить не менее s_i предметов i-го сорта, то получим формулу: (n₁-2s₁+1) × (n₂-2s₂+1) ×...× (n_k-2s_k+1).

Даны n различных предметов и k ящиков. Надо положить в первый ящик n₁ предметов, во второй – n₂, ..., в k-ый – n_k, где n₁+...+n_k=n. Сколькими способами можно сделать такое распределение, если не интересует порядок предметов в ящике?

Выложим все предметы в один ряд. Это можно сделать n! способами. Первые n₁ предметов положим в первый ящик, вторые n₂ предмета – во второй ящик, …, k-ые n_k предметов – в к-ый ящик. Так как нас не интересует порядок предметов в ящике, то любая перестановка первых n₁ предметов не меняет результат раздела. Точно так же его не меняет любая перестановка вторых n₂ предметов, ..., k-ых n_k предметов. По правилу произведения получаем n₁! ×n₂!×...×n_k! перестановок, не меняющих результата раздела. Таким образом, n! перестановок делятся на группы по n₁! ×n₂!×...×n_k! перестановок в каждой группе, причем перестановки из одной группы приводят к одинаковому распределению предметов. Следовательно, число раздела предметов равно =P(n₁,...,n_k).

Задача.

При игре в домино 4 игрока делят поровну 28 костей. Сколькими способами они могут это сделать?

Решение.

Переформулируем задачу: необходимо разложить 28 предметов в 4 ящика по 7 предметов в каждый, причем порядок предметов в ящике не важен. Получаем способов распределения костей домино.

Можно было рассуждать другим способом. Первый игрок выбирает себе 7 костей из 28, это можно сделать способами. Второму необходимо выбрать 7 костей из оставшихся 21, это можно сделать способами. Третьему 7 из 14 – способов. А четвертый заберет оставшиеся. По правилу произведения получаем .

Даны n различных предметов и k одинаковых ящика. Надо положить в каждый ящик n₁ предметов, где n₁= . Сколькими способами можно сделать такое распределение, если не интересует порядок предметов в ящике, и все ящики одинаковы?

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

Упражнение 3.

Сколькими различными способами можно разделить 8 книг на 4 бандероли по 2 книги в каждой?

Сколькими способами можно разложить n одинаковых предметов в k ящиков?

Выложим все предметы в один ряд, добавим к ним k–1 одинаковых разделяющих предмета. Переставим всеми возможными способами n данных одинаковых предметов и k–1 разделяющих. Каждая такая перестановка определяет один из способов распределения. А именно предметы, расположенные до первого разделителя, положим в первый ящик, предметы, расположенные между первым и вторым разделителем, – во второй ящик и так далее, предметы расположенный после k–1 разделителя, – в k ящик. По формуле перестановок с повторениями число таких перестановок равно P(n, k-1)= . Значит, всего имеем способов разложить n одинаковых предметов в k ящиков.

Упражнение 4.

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

Следствие 1. Если в каждый ящик надо положить не менее r предметов, то получим: P(n-k×r,k-1) способов.

Следствие 2. Если в каждый ящик надо положить хотя бы один предмет, то r=1 и получим P(n-k,k-1)= способов распределения.

 

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

Каждый предмет можно положить в любой из k ящиков. Получаем kⁿ способов распределения предметов по ящикам.

Задача.

Сколькими способами можно разделить 8 различных пирожных между 5 детьми?

Решение.

Необходимо разложить 8 предметов по 5 ящикам. Это можно сделать 5⁸=390 625 способами.

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

Данные r ящиков остаются пустыми, если в k–r ящиков предметы кладутся без ограничений. r пустых ящиков можно выбрать C_n^k способами. В оставшиеся k–r ящиков предметы можно разложить (k–r)ⁿ способами. По формуле включений и исключений число распределений, при которых хотя бы один ящик остается пустым, равно . Тогда количество распределений, при которых ни один ящик не окажется пустым, равно

kⁿ-( ).

Задача.

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

Решение.

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

Применяя полученную выше формулу, получаем

5⁸- ×4⁸+ ×3⁸- ×2⁸+ ×1⁸=126 020.

Имеется n₁ предметов одного сорта, n₂ – другого, ... , n_s – s-го сорта. Сколькими способами их можно разложить по k ящикам, если не должно быть пустых ящиков?

Применяя рассуждения, аналогичные предыдущей задаче, получим следующую формулу

.

Задача.

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

Решение.

Требуется 8 предметов одного сорта, 10 второго и 7 третьего разложить в 4 ящика так, чтобы ни один ящик не оказался пустым. По предыдущей формуле получаем

способов такого распределения.

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

Добавим к n предметам k–1 одинаковых разделяющих предмета. Рассмотрим все возможные перестановки из n различных предметов и k–1 одинаковых. Каждая такая перестановка определяет один из способов распределения. Всего таких перестановок . Значит, n различных предметов можно разложить в k ящиков, с учетом расположения их в ящиках, = способами.

К тому же результату можно было прийти и другим путем. Переставим всеми возможными способами данные n предметов (n! способов). Теперь считаем предметы неразличимыми, их можно разложить в k ящиков Р(n, k–1) способами. Получаем n!∙Р(n,k–1)= способов распределения этих вещей по к различным ящикам с учетом порядка их расположения в ящиках.

Упражнение 5.

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

 

Следствие. Если не должно быть пустых ящиков, то выберем k предметов и разложим по одному в каждый ящик. Это можно сделать способами. Оставшиеся n–k предметов разложим в k–1 ящик, причем теперь некоторые ящики могут оказаться пустыми. Это распределение можно осуществить способами. Всего имеем способов распределения.

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

Разобьем все возможные комбинации на классы. В s класс войдут комбинации, в которых использованы ровно s предметов. Из предыдущей задачи известно, что s предметов можно разложить по k ящикам способами. s предметов из данных n можно выбрать способами. Всего в s класс войдут × комбинаций. По правилу суммы имеем

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

Задача.

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

Решение.

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

Следствие. Если не должно быть пустых ящиков, то в этом случае имеем

способов распределения.

 

Упражнения к двум занятиям по комбинаторике:

 

1. Каждую клетку квадратной таблицы 2 × 2 можно покрасить в черный или белый цвет. Сколько существует различных раскрасок этой таблицы?

 

2. Алфавит племени Мумбо-Юмбо состоит из трех букв А, Б и В. Словом является любая последовательность, состоящая не более, чем из 4 букв. Сколько слов в языке племени Мумбо-Юмбо?

 

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

 

4. Слово – любая конечная последовательность букв русского алфавита. Выясните, сколько различных слов сожно составить из слов

а) «ПАРАБОЛА»;

б) «БИССЕКТРИСА»;

 

5. Бусы – это кольцо, на которое нанизаны бусины. Бусы можно поворачивать, но не переворачивать. Сколько различных бус можно сделать из 13 разноцветных бусин?

 

6. Каких 7-значных чисел больше: тех, в записи которых есть 1, или остальных?

 

7. Сколькими способами можно разбить 14 человек на пары?

 

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