Сетевое издание

Международный студенческий научный вестник

ISSN 2409-529X

Введение

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

Типичные задачи комбинаторики:

· определить количество комбинаторных конфигураций, соответствующих заданным правилам (в частности, доказать или опровергнуть их существование);

· найти практически пригодный алгоритм их полного построения;

· определить свойства заданного класса комбинаторных конфигураций.

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

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

1 Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества.

2 Перестановкой из n элементов (например, чисел 1, 2, … n) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n .

3 Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений [1].

1. Размещение без повторения:

Задача 1.

В футбольной команде 11 человек. Сколькими способами можно выбрать: а) капитана и его ассистента; б) капитана, первого ассистента и второго ассистента?

Решение

а) Капитаном можно выбрать любого из 11 футболистов. Ассистентом — любого из 10 оставшихся. Поэтому капитана и ассистента можно выбрать 11 · 10 = 110 способами.

б) Капитана и первого ассистента мы уже выбрали 11 · 10 способами. Для выбора второго ассистента остаётся 9 способов. Поэтому капитана, первого ассистента и второго ассистента можно выбрать 11 · 10 · 9 = 990 способами.

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

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

Число размещений из n элементов по k элементов обозначается .Это число упорядоченных наборов из k элементов (или число цепочек длины k), выбранных из n-элементного множества. Найдём, чему равно это число. Рассуждаем так же, как и в задаче про футболистов. Для выбора первого элемента цепочки имеется n способов, для выбора второго элемента имеется n − 1 способов, для выбора третьего элемента имеется n − 2 способов и т. д. Для выбора последнего, k-го элемента цепочки имеется n – k +1 способов.

Следовательно:(1)

Данную формулу можно записать в более компактном виде, если правую часть умножить и разделить на :

то есть:

(2)

2. Перестановка без повторения:

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

Задача 2.

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

Решение

Для выбора первой цифры имеется пять способов, для выбора второй — четыре,

для выбора третьей — три, для выбора второй — два, и для выбора последней цифры остаётся один способ. Всего чисел получается 5 · 4 · 3 · 2 · 1 = 5! = 120.

Задача 3.

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

Решение

Первый шар можно выбрать n способами, второй шар можно выбрать n − 1 способами и т. д. Для выбора последнего, n-го шара остаётся один способ. Всего получается

способов выложить наши n шаров в ряд.

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

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

Переходим к рассмотрению сочетаний. Вернёмся к нашей футбольной команде, в которой мы выбирали капитана и ассистента.

Задача. В футбольной команде 11 человек. Сколькими способами можно выбрать из них двух игроков для прохождения допинг-контроля?

Решение. На первый взгляд кажется, что ситуация аналогична выбору капитана и ассистента: первого человека выбираем 11 способами, второго — 10 способами, так что всего имеется 11 · 10 способов. Однако в данном случае это не так. В самом деле, пара «капитан и ассистент» является упорядоченной: выбрать Петю капитаном, а Васю ассистентом — это не то же самое, что выбрать Васю капитаном, а Петю ассистентом. С другой стороны, пара человек, отправленных на допинг-тест, является неупорядоченной:

отправить Петю и Васю на тест — это ровно то же самое, что отправить Васю и Петю на тест.

Соответственно, в данной задаче нас интересует именно число неупорядоченных пар футболистов, выбираемых из 11 человек.

Давайте представим себе, что неупорядоченная пара {Петя, Вася} как бы склеивается из двух упорядоченных пар (Петя, Вася) и (Вася, Петя). Иными словами, любые две упорядоченные пары, отличающиеся лишь порядком следования объектов, дают одну и ту же неупорядоченную пару. Следовательно, число неупорядоченных пар будет в два раза меньше числа

упорядоченных пар и окажется равны:

Таким образом, двух футболистов можно выбрать для допинг-контроля 55 способами.

Задача. Сколькими способами можно выбрать троих футболистов из 11 для прохождения допинг-контроля?

Решение. Произведение 11 · 10 · 9 (число способов выбора капитана, первого ассистента и второго ассистента) есть число упорядоченных троек футболистов. В данном же случае, как и в предыдущей задаче, порядок не важен, поэтому нам нужно найти число неупорядоченных троек футболистов, выбираемых из 11 человек.

В одну неупорядоченную тройку склеиваются те и только те упорядоченные тройки, которые отличаются лишь порядком следования элементов. Число таких троек равно числу перестановок трёх элементов, то есть 3! = 6. Например, в одну неупорядоченную тройку

{Петя, Вася, Коля}

склеиваются ровно шесть упорядоченных троек

(Вася, Коля, Петя), (Вася, Петя, Коля), (Коля, Вася, Петя),

(Коля, Петя, Вася), (Петя, Вася, Коля), (Петя, Коля, Вася).

Следовательно, число неупорядоченных троек в 3! раз меньше числа упорядоченных троек.

Соответственно, имеется

способов выбрать троих человек для допинг-контроля.

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

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

Иными словами, сочетание из n элементов по k элементов — это просто k-элементное подмножество n-элементного множества.

Число сочетаний из n элементов по k элементов обозначается (читается «це из эн по ка»).

Это число неупорядоченных наборов из k элементов, выбранных из n-элементного множества

(то есть число k-элементных подмножеств n-элементного множества). Найдём, чему равно это число.

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

элементов, склеиваются в один неупорядоченный набор. Число таких цепочек равно числу перестановок k элементов, то есть k!. Следовательно, искомое число неупорядоченных наборов из k элементов будет в k! раз меньше числа цепочек длины k:

Согласно формулам (1) или (2) имеем:

Теперь, зная, что такое число сочетаний, мы можем сразу сказать, что двух футболистов из одиннадцати для допинг-теста можно выбрать способами; аналогично, трёх футболистов из одиннадцати можно выбрать способами. [2]

1.1 Примеры решения задач с размещением без повторения:

Пример 1. Студенческая группа состоит из 25 человек. Нужно выбрать старосту, заместителя старосты и профорга. Сколькими способами это можно сделать, если каждый студент может занимать только одну должность.

Решение

Из множества, содержащего из 25 человек (n = 25) нужно выбрать 3 человека (k = 3), причем порядок, в котором они будут указаны, важен, так как они займут разные должности, т.е. каждый выбор представляет собой размещение без повторений. Следовательно, количество способов равно числу размещений из 25 элементов по 3:

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

Решение

Выбираем 7 мест из 11 для согласных букв способами, на оставшиеся места ставим гласные буквы в нужном порядке.

Но так как буква «л» входит в слово 3 раза, то способы, получающиеся перестановкой мест для букв, «л» совпадают и поэтому различных способов в 3! раза меньше.

Окончательно получаем, что число способов, которыми можно переставить буквы слова «параллелизм» так, что бы не менялся порядок гласных букв, равно: . [2]

2.1 Примеры решения задач с перестановкой без повторений

Пример 1. Для дежурства на факультете с понедельника по субботу выделено 6 студентов из группы. Староста группы должен составить график дежурства. Сколькими способами он может это сделать?

Решение

График — это упорядоченный список из 6 человек (n=6). Следовательно, количество способов равно числу перестановок 6 элементов:

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

Решение

При таком расположении на каждой горизонтали и каждой вертикали стоит по одной ладье.

Обозначим номер занятого поля на первой горизонтали, номер занятого поля на второй горизонтали, …, — номер занятого поля на восьмой горизонтали.

Тогда — перестановка из чисел 1,2, …,8, так как среди чисел не может быть одинаковых, иначе две ладьи попадут на одну и ту же вертикаль.

Обратно, если — некоторая перестановка из чисел 1,2, …,8, то ей соответствует некоторое расположение ладей, при котором они не могут бить друг друга.

Таким образом, число способов расстановки 8 ладей, при которых они не могут бить друг друга, равно [3]

3.1 Примеры решения задач с сочетанием без повторения

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

Решение

Добавим к 40 яблокам ещё 2 элемента, например, 2 камешка, если расположить эти 42 элемента в ряд, то эти 2 камешка разделят 40 яблок на 3 части (некоторые из частей при этом могут оказаться пустыми).

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

Пример 2. Из лаборатории в которой работают 20 человек, 5 сотрудников должны уехать в командировку. Сколько может быть различных составов этой группы, если начальник лаборатории, его заместитель и главный инженер одновременно уезжать не должны?

Решение

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

Если начальник, заместитель и главный инженер попали в количество выбранных, то ещё 2 человека будут выбираться из 17 сотрудников способами, эти способы нужно исключить из всех возможных способов. Окончательно получаем, что число различных составов группы, направленную в командировку, равно: [3]