Элементы комбинаторики

ЭЛЕМЕНТЫ КОМБИНАТОРИКИ

§1. Декартово произведение двух множеств

Рассмотрим пример. Число 35 записывается с помощью двух цифр 3 и 5. Эти цифры следует записывать в определенном порядке: сначала 3, а потом 5. Если их переставить, получится другое число 53. Говорят, что — упорядоченная пара чисел. Упорядоченную пару чисел и будем записывать следующим образом: . В число 44 входят две одинаковые цифры. Они образуют упорядоченную пару . Таким образом, в упорядоченных парах числа могут повторяться.

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

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

Например, из букв множества можно составить девять упорядоченных пар: . Примером упорядоченной пары натуральных чисел может служить пара, составленная из числителя и знаменателя дроби — вместо того, чтобы писать , можно записать . При перестановке чисел 3 и 5 получается иная дробь .

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

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

Если множества и совпадают, т.е. , то множество состоит из всех пар таких, что , .

Полагают, что для любого множества .

Декартово произведение множеств, вообще говоря, не обладает ни свойством коммутативности, ни свойством ассоциативности, т. е.:

1) если , то ;

2) если ни одно из множеств не пусто, то .

Действительно, элементами множества являются пары такие, что и , а элементами множества — пары , где и . Но, при пары и различны. Следовательно, если , то множества и различны.

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

Задания для практических занятий и самостоятельного решения.

1. Выпишите три упорядоченные пары действительных чисел, являющихся решением уравнения .

2. Даны два множества , . Запишите элементы множества .

3. Даны три множества , , . Запишите элементы множеств .

4. Докажите справедливость равенства: .

5. Верно ли равенство: , если ?

6. Составьте все дроби, числитель и знаменатель которых – разные однозначные числа из множества . Сколько дробей получилось?

§2. Кортежи

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

Пусть даны множества . Возьмем какой-нибудь элемент из множества , потом элемент из множества ,..., элемент – из множества . Выбранные элементы расположим по порядку: . Получаем упорядоченную – ку элементов (читается: «энка»), выбранных из множеств . Вместо слов «упорядоченная – ка» говорят короче — «кортеж» (французское слово «кортеж» означает торжественное шествие, например, говорят «свадебный кортеж» или «кортеж автомашин»). Число называют длиной кортежа, элементы — его компонентами.

Множества могут иметь общие элементы или даже совпадать друг с другом. Например, слово «математика» — кортеж длины 10, составленный из элементов множества (при этом в слово «математика» входят не все буквы этого множества, а лишь часть этих букв). Предложение «Математика – царица всех наук» — кортеж длины 4, компонентами которого являются слова русского языка. Каждое из этих слов — кортеж, составленный из букв. Таким образом, компонентами кортежа могут быть и кортежи. Можно составлять и кортежи, компонентами которых являются множества, например: .

В математике примером кортежа может служить набор цифр, входящих в десятичную запись какого-нибудь числа. Этот кортеж составлен из цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, причем цифры могут повторяться, а при перестановке цифр может получиться иное число. Так, кортеж цифр числа 112 231 имеет вид .

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

Используя понятие кортежа, можно определить понятие декартова произведения трех, четырех и, вообще, множеств. Пусть заданы множеств: (множества могут иметь общие элементы). Из элементов этих множеств образуем, кортежи длины , первая компонента которых принадлежит множеству , вторая — множеству ,..., – я — множеству . Множество таких кортежей называют декартовым произведением множеств и обозначают

Задания для практических занятий и самостоятельного решения.

7. Запишите множество различных букв слова «параллелограмм». Запишите кортеж букв в этом слове. Какова длина этого кортежа?

8. Запишите различные множества, составленные из букв слова «куб». Запишите кортеж букв в этом слове. Какова длина этого кортежа?

9. Сколько цифр в записи числа 235535? Сколько различных цифр в записи этого числа?

10. Образуйте всевозможные кортежи длины 2 из элементов множества .

11. Используя цифры 2, 7, 8, запишите всевозможные двухзначные числа (цифры в записи числа не повторяются).

§ 3. Правила и формулы комбинаторики

3.1. Общие правила комбинаторики

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

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

Обозначим число элементов конечного множества через . Множество, состоящее из элементов, назовем – множеством. Например, если , то , и поэтому является 6–множеством.

Пусть содержит элементов, a содержит элементов. Найдем, сколько элементов содержит объединение . Однозначный ответ на этот вопрос можно дать лишь в случае, когда множества и не пересекаются. В этом случае множество содержит элементов, например, если , то содержит элементов.

Таким образом, справедливо следующее утверждение: если множество содержит элементов, а множество содержит элементов, причем эти множества не пересекаются, то множество содержит элементов.

Иными словами, (1)

Это очевидное утверждение называют в комбинаторике правилом суммы.

В комбинаторике равенство (1) обычно формулируют следующим образом: если элемент можно выбрать способами, а элемент можно выбрать способами, то выбор элемента или элемента можно выбрать способами.

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

Итак, число элементов объединения двух множеств равно сумме чисел элементов в каждом из них, уменьшенной на число элементов пересечения этих множеств.

Приведем без вывода формулу для числа элементов в объединении трех множеств:

(3)

Пример 1. Из 32 студентов группы 12 человек успешно сдали зачет по легкой атлетике, а 15 — по анатомии. 8 студентов получили неудовлетворительные отметки по обоим предметам. Сколько студентов имеют академическую задолженность?

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

Пример 2. Из 35 студентов на экзамене получили оценку «5» по математике 14 студентов, по анатомии 15 студентов, по педагогике – 18 студентов, по математике и анатомии – 7 студентов, по математике и педагогике – 9 студентов, по анатомии и педагогике – 6, по всем трем предметам 4 студента. Сколько студентов получили хотя бы по одной отличной оценке?

Решение: Пусть множество – множество студентов, получивших отличную оценку по математике. Пусть множество – множество студентов, получивших отличную оценку по физике. Пусть множество – множество студентов, получивших отличную оценку по педагогике. Тогда – множество студентов, получивших отличную оценку по математике и физике, – множество студентов, получивших отличную оценку по математике и педагогике, – множество студентов, получивших отличную оценку по физике и педагогике, – множество студентов, получивших отличную оценку по всем трем предметам. Тогда

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

Итак, число упорядоченных пар, которые можно составить из элементов –множества и – множества , равно , т. е. произведению числа элементов множества на число элементов множества . Множество упорядоченных пар, составленных из элементов множеств и , мы назвали в §1 декартовым произведением этих множеств и обозначили . Поэтому доказанное утверждение можно записать так: (4)

Справедливо и более общее утверждение, называемое правилом произведения:

(5)

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

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

Решение: Чтобы решить задачу, обозначим костюмы числами 1, 2 и 3, а рубашки — буквами а и в. Тогда каждый вариант одежды, включающий костюм и рубашку, задается парой, состоящей из числа и буквы. Число пар такого вида по правилу произведения равно . Вот эти варианты: .

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

Пример 4. Найдем число слов, содержащих 4 буквы, в которых любые две соседние буквы различны (число букв в алфавите равно 33; при этом допускаются и слова, лишенные смысла, например «ваха»).

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

Задания для практических занятий и самостоятельного решения.

12. Из 40 студентов группы 35 человек успешно сдали экзамен по математике, а 37 — по анатомии. Двое студентов получили неудовлетворительные отметки по обоим предметам. Сколько студентов имеют академическую задолженность?

13. Из 80 студентов 40 играют в футбол, а 50 — в волейбол, причем 27 студентов играют и в футбол, и в волейбол. Сколько студентов играет хотя бы в одну из этих игр? Сколько студентов играет лишь в одну из этих игр?

14. Из 100 студентов английский язык изучают 28 человек, немецкий — 30, французский — 42, английский и немецкий — 8, английский и французский — 10, немецкий и французский — 5, все три языка изучают трое студентов. Остальные студенты изучают испанский язык. Сколько студентов изучают испанский язык?

15. Каждый из студентов группы знает хотя бы один язык, причем 6 студентов изучают английский язык, немецкий — 6, французский — 7, английский и немецкий — 4, английский и французский — 2, немецкий и французский — 3, все три языка изучает один студент. Сколько студентов учится в группе? Сколько студентов изучают только один язык?

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

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

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

19. Из 10 слов мужского рода, 7 женского и 9 среднего рода надо выбрать одно слово, по одному слову каждого рода. Сколькими способами это можно сделать?

3.2. Размещения с повторениями

Рассмотрим задачу: Из 4–множества составить 16 кортежей длины 2.

Решение:

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

Итак, число кортежей длины , составленных из элементов - множества , равно .

Пример 1. Из букв русского алфавита составить слова, длиной 2, 3, 4,…

Решение: Воспользуемся формулой и получим, что из 33 букв русского алфавита можно составить 33² слов длины 2 (аа, аб, ав,..., ая, ба, бб,..., яю, яя), ЗЗ³ слов длины 3, ЗЗ⁴ слов длины 4 и т. д. Точно так же из 10 цифр 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 можно составить 10² двузначных номеров (00, 01,.......,99), 10³ трехзначных номеров и т. д.

Определение. Кортеж длины , составленный из элементов – множества, называют размещением с повторениями из элементов по , а число таких кортежей обозначают (от французского слова arrangement — размещение).

Таким образом, (6)

Формула (6) позволяет решить такую задачу: Найти число подмножеств –множества .

Решение: Перенумеруем элементы множества . Каждое подмножество можно «зашифровать» с помощью кортежа длины из нулей и единиц; мы пишем на некотором месте 1, если элемент с данным номером входит в подмножество, и 0, если он не входит. Например, если , то кортеж (0; 1; 1; 0; 1) шифрует подмножество , а кортеж (0; 0; 0; 0; 0) — пустое подмножество, а кортеж (1; 1; 1; 1; 1) — все . Поэтому найти число подмножеств – множества — это все равно, что найти число кортежей длины , составленных из элементов 2–множества {0; 1}. По формуле (1) число таких кортежей равно . Значит, число подмножеств – множества равно . Например, множество имеет 2³ = 8 подмножеств:

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

Решение: Каждый из студентов может получить любую из оценок: «5», «4», «3». Мы рассматриваем множество , которое состоит из трех различных элементов. При этом порядок расстановки оценок существенен, оценки могут повторяться, а общее число оценок равно четырем. Таким образом, нужно составить размещения с повторениями из трех элементов по пяти: .

Задания для практических занятий и самостоятельного решения.

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

21. Сколькими способами из колоды, содержащей 36 карт, можно выбрать по одной карте каждой масти?

22. В некотором государстве не было двух жителей с одинаковым набором зубов. Какова может быть наибольшая численность населения государства (у человека не более 32 зубов)?

23^*. Сколько существует автомобильных номеров, составленных из трех букв и трех цифр (кроме 000). Буквы – А, В, Е, К, М, Н, О, Р, С, Т, У, Х.

3.3. Размещения без повторений. Перестановки

В задаче п.3.2 из 4-множества составлены 16 кортежей длины 2:

Заметим, что в этой задаче элементы повторяются. Решим эту же задачу при условии, что элементы не повторяются:

Получили 12 кортежей.Если элементы не повторяются, то такие кортежи называются размещениями без повторений из элементов по элементов.

Определение. Размещениями без повторений из элементов по элементов называют кортежи длины , составленные из неповторяющихся элементов множества, содержащего элементов.

Обозначают . (7)

То есть для нашей задачи получаем .

Формулу для можно записать иначе, умножив и разделив первую часть формулы (3) на . Мы получим:

Произведение первых натуральных чисел в математике называют «т – факториал» и обозначают . По определению

Итак, . (8)

Если , то размещения без повторений из элементов по называют перестановками и обозначают : (9)

Пример 1: В команду КВН от курса выбрали 11 студентов. Из них нужно выбрать капитана и его помощника. Сколькими способами это можно сделать?

Решение: Нам дано множество, состоящее из 11 элементов, из него выбираются 2 элемента. Порядок существенен. Элементы не могут повторяться. Таким образом, нужно найти число размещений без повторений из 11 элементов по 2 элемента в каждом по формуле (8): .

Пример 2: Сколькими способами можно построить слово, длиной 3 из разных букв, выбранных из множества ?

Решение: Используя формулу (8), получим .

Задания для практических занятий и самостоятельного решения.

24. Сколькими способами из 8 спортсменов можно составить команду для эстафеты «4 по 100 метров»?

25. В турнире участвуют 5 команд. Сколькими способами могут распределиться места (1, 2, 3)?

26. Сколькими способами для 3 спортсменов можно выбрать по 1 мячу и 1 обручу, если имеется 5 разноцветных мячей и 6 разноцветных обручей?

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

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

29. Сколькими способами можно посадить на скамейку 8 человек?

30. Сколькими способами 11 человек могут встать в очередь друг за другом?

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

Рассмотрим следующую задачу комбинаторики: сколько подмножеств, содержащих элементов каждое, можно составить из элементов данного – множества ?

Такие подмножества называют сочетаниями без повторений из элементов по , а их число обозначают (от французского слова combinaison — «сочетание»).

Выведем формулу, выражающую через и . Возьмем какое-нибудь –подмножество в – множестве . Так как содержит элементов, то его можно упорядочить способами. При этом каждое упорядоченное – множество, состоящее из элементов множества , может быть получено таким путем. Значит, число упорядоченных – множеств, составленных из элементов множества , в раз больше числа неупорядоченных – подмножеств в . Например, из элементов множества можно составить четыре 3-подмножества: . Число же упорядоченных 3 – подмножеств в 3! = 6 раз больше. Но число упорядоченных – множеств равно , а число – подмножеств мы обозначили . Поэтому . Так как , то (10)

Эта формула выражает число –подмножеств в – множестве .

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

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

Пример 1. В кондитерском магазине продавались 4 сорта пирожных. Сколькими способами можно выбрать 7 пирожных?

Решение:

Числа , выражающие количество - подмножеств в -множестве Х, обладают целым рядом замечательных свойств. Эти свойства выражают различные соотношения между подмножествами множества .

1) Если , то верно равенство (11)

2)Для любых и , таких, что , верно равенство (12)

Отметим, что при получаем равенство . Так как , то следует положить . Аналогично следует положить при . Тогда равенство (12) оказывается верным и при .

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

1 1

1 2 1

1 3 3 1

1 4 6 4 1

и т.д.

Эту треугольную таблицу называют треугольником Паскаля, по имени французского математика Блеза Паскаля (1623 — 1662), в трудах которого она встречается. Это название исторически неточно, так как такую таблицу знал уже арабский математик Омар Хайям, живший в XIII в.

Пример 2: Сколькими способами можно выбрать делегацию в 5 человек из группы, содержащей 12 человек?

Решение: Поскольку порядок выбора членов делегации роли не играет, то нам надо узнать, сколько можно выбрать 5-подмножеств из 12-множества. Это число таково:

Задания для практических занятий и самостоятельного решения.

31. Сколько хорд можно провести через 6 точек, лежащих на одной окружности?

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

33. Сколькими способами можно выбрать три краски из пяти различных красок?

34. Рота состоит из трех офицеров, 6 сержантов и 60 рядовых. Сколькими способами можно выделить из них отряд, состоящий из одного офицера, двух сержантов и 20 рядовых?

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

36. Пользуясь треугольником Паскаля найти коэффициенты при степенях при возведении в степень , если: ; ; ; .

Дата добавления: 2015-08-27