Комбинаторика

Комбинаторика — раздел математики о вычислении количества различных комбинаций каких-либо элементов.

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

Пример:

1. Сколько различных трёхзначных номеров телефона можно составить из пяти цифр? (Ответ: 125)

  2. Сколькими различными способами можно составить танцевальную пару, если в коллективе 3 мальчика и 4девочки? (Ответ: 12).

  3. Сколькими различными способами можно образовать пару дежурных, если в классе остались Надя, Вика, Саша и Юра? (Ответ: 6).

  4. Сколькими различными способами можно выбрать двух учеников (одного - чистить доску, второго - подметать пол), если в классе остались Надя, Вика, Саша и Юра?  (Ответ: 12)

Один из способов решения задач комбинаторики — это рассмотреть все возможные комбинации элементов, что называется полным перебором вариантов.

Древовидная диаграмма — один из способов показать и систематизировать все размещения. С помощью древовидной диаграммы осуществляется полный перебор.

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

Решение:

Составляется древовидная диаграмма:

Ответ: можно составить 6 различных чисел.

 

Пример:

Р ассмотрим 3-й пример (см. выше):

Сколькими различными способами можно образовать пару дежурных, если в классе остались Надя, Вика, Саша и Юра?

На древовидной диаграмме видно, что можно образовать только 6 пар дежурных (Надя и Вика, Надя и Саша, Надя и Юра, Вика и Саша, Саша и Юра, Вика и Юра), т.к. каждая пара повторяется 2 раза.

 Рассмотрим 4-й пример: 

Сколькими различными способами можно выбрать двух учеников (одного — чистить доску, второго — подметать пол), если в классе остались Надя, Вика, Саша и Юра?

 Используется та же древовидная диаграмма, но в данном случае ответ будет 12 пар, т.к. каждая пара из диаграммы отличается. Если детей поменять местами, они выполняют уже другие функции.

С помощью древовидной диаграммы были получены различные результаты, т.к. в 3 и 4 примере были рассмотрены различные виды комбинаций: сочетания и размещения.

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

Для того чтобы найти число всех возможных исходов независимого проведения двух испытаний А и В, следует перемножить число всех исходов испытания А и число всех исходов испытания В. 

Марина купила 3-х кроликов: серого (с), белого (б) и рябого (р). Сколько существует различных способов посадить этих кроликов в 3 клетки, если в одной клетке может находиться только 1 кролик?

 

Первый вариант решения — схематический рисунок.

 

 

Это задание можно решить по-другому, используя закон умножения.

Если элемент A можно выбрать k способами и затем второй элемент B можно выбрать m различными способами, то пару элементов A и B можно выбрать k⋅m способами.

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

Второй вариант решения — с использованием закона умножения:

чтобы посадить кролика в клетку, нужно выбрать пару — кролик и клетка.

 

В первую клетку можно посадить одного из 3 кроликов — 3 возможности.

Во вторую клетку можно посадить одного из 2 оставшихся кроликов — 2 возможности.

В третьей клетке остаётся последний кролик — 1 возможность.

Вместе 3⋅2⋅1 =6 (возможностей). 

Ответ: кроликов можно распределить по клеткам 6 способами.

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

Использование закона умножения упрощает и ускоряет решение задач.

  Юра хочет подобрать одежду для классного вечера. Сколько различных комплектов одежды может получиться у Юры, если у него есть майки 2-х цветов, но у каждого цвета есть 3 различных вида (одноцветная майка, в полоску и в клеточку), а также белые и чёрные шорты?

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

 

По закону умножения Юра может одеться  2⋅3⋅2 =12 различными способами.

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

Таблица

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

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

	1	2	3	4	5	6
1	1	2	3	4	5	6
2	2	4	6	8	10	12
3	3	6	9	12	15	18
4	4	8	12	16	20	24
5	5	10	15	20	25	30
6	6	12	18	24	30	36

 

  Различные произведения — это 1;2;3;4;5;6;8;9;10;12;15;16;18;20;24;25;30;36 —  всего 18 различных результатов.

Закон сложения в комбинаторике

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

 

Если взять яблоко, то существует 5 возможностей,

если взять грушу, то существуют 4 возможности,

если взять мандарин, то существуют 3 возможности.

Значит, чтобы взять один фрукт из всех лежащих в вазе, существует 5+4+3=12 возможностей.

 

Этот пример можно обобщить.

  Допустим, что есть две группы: в одной k различных элементов, во второй n различных элементов. Если из первой группы какой-либо элемент можно выбрать k способами, а из второй — n способами, то выбрать один элемент из первой или второй группы можно k+n способами.

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

 

Закон сложения используется тогда, когда нужно выбрать только 1 элемент.

Чтобы использовать закон сложения:

1. нужно понять, каковы группы, из которых нужно выбрать 1 элемент;

2. нужно выяснить количество элементов в каждой группе;

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

 

Пример:

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

Решение:

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

8+5+5=18.

Ответ: Вика может выбрать десерт 18 способами.

При использовании закона сложения надо следить, чтобы ни один из способов выбора объекта a не совпадал с каким-либо способом выбора объекта b. 
Если такие совпадения есть, то закон сложения утрачивает силу, и мы получаем лишь (k+n−m) способов выбора, где m — число совпадений.

Итак:

если объект a можно получить k способами, объект b — n  способами, то объект «a или b» можно получить k+n−m способами, где m — это количество повторяющихся способов.

Пример:

в группе 7 человек имеют «5» по математике, 9 человек — «5» по философии. В сессии 2 экзамена. Известно, что 4человека сдали сессию отлично. Сколько человек имеет хотя бы одну пятерку в сессии?
Решение: 7+9−4=12.

Используя закон умножения, часто нужно вычислить произведения натуральных чисел по порядку, начиная с 1.

Например, 1⋅2⋅3⋅4⋅5⋅6⋅7 и т. д. Не всегда важно вычислить числовое произведение. Чтобы можно было короче записать выражения такого вида, в математике используется знак "!".

Произведение всех натуральных чисел от 1 до n называется факториалом числа n и записывается n! (читается как «эн факториал»).

n!=1⋅2⋅3⋅...⋅(n−2)⋅(n−1)⋅n

Принято, что 0!=1  

1!=1

2!=2⋅1=2

3!=3⋅2⋅1=6

4!=4⋅3⋅2⋅1=24

5!=5⋅4⋅3⋅2⋅1=120

6!=6⋅5⋅4⋅3⋅2⋅1=720

Пример:

1. Вычисли значение выражения.

a) 5!+4!=5⋅4⋅3⋅2⋅1+4⋅3⋅2⋅1=120+24=144

Пример:

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

1⋅2⋅3⋅...⋅24⋅25=25!

Ответ: Список можно составить 25! различными способами

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

Размещения по n элементов из n называются перестановками из n элементов.

  

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

  Количество перестановок обозначается как Pn, где n — количество элементов множества.

  Перестановки вычисляются по формуле Pn=n!

  Если дано множество из двух элементов a;b, из этого множества можно составить две упорядоченные выборки: a;b  и  b;a.

Из двух элементов (n=2) можно составить 2 перестановки, т. е. P2=2!=1⋅2.

 

Если дано 3 элемента a;b;c, размещения такие:

1. a;b;c    3. b;a;c     5. c;a;b  

2. a;c;b    4. b;c;a     6. c;b;a

 

Данные элементы можно переупорядочить 6 способами, т. е.  P3=3!=1⋅2⋅3=6.

  Обрати внимание!

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

Пример:

сколькими различными способами можно составить список учеников из 6 человек?

P6=6!=6⋅5⋅4⋅3⋅2⋅1=720.

Ответ: список учеников можно составить 720 различными способами. 

Пример:

в соревнованиях участвуют 6 команд: A; B; C; D; E и F. Сколько существует вариантов расположений команд с первого по шестое место, где команда A ни на первом, ни на последнем месте?

 

1. Вычисляются все возможные порядки построения команд.
(Для команды A есть 6 различных позиций: 1-е место, 2-е место, 3-е место... 6-е место.)

P6=6!=6⋅5⋅4⋅3⋅2⋅1=720.

 2. Вычисляются все возможные порядки, где команда A не на первом месте.
(Значит, для команды A есть только 5 различных позиций: 2-е место, 3-е место... 6-е место.)

P5=5!=5⋅4⋅3⋅2⋅1=120.

 3. Вычисляются все возможные порядки, где команда A не на последнем месте.
(Значит, для команды A есть 5 различных позиций: 1-е место, 2-е место, 3-е место, 4-е место, 5-е место.)

P5=5!=5⋅4⋅3⋅2⋅1=120.

 

4. Вычисляется, сколько существует вариантов расположений команд с первого по шестое место, где команда Aни на первом, ни на последнем месте. Из количества всех возможных вариантов вычитаются вычисленные ограничения: 720−(120+120)=480 (способов).

 

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

Перестановки с повторениями

Если в основном множестве k элементов a1,a2...ak, и выборка n элементов составляется так:

элемент a1 повторяется n1 раз,

элемент a2 повторяется n2 раз

...

элемент ak повторяется nk раз —

такие выборки называются перестановками с повторениями.

Их возможное количество вычисляется по формуле:

Pn¯=Pn1,n2,...nk/n!n1!⋅n2!⋅...⋅nk!.

Пример:

сколько различных пятибуквенных слов можно составить из букв слова «манна»?

 

Решение:

в слове буквы а и н повторяются 2 раза, а буква м — один раз.

 

P5¯=P2,2,1=5!/2!⋅2!⋅1!=2⋅3⋅4⋅5/2⋅2=30

Выборками называются подмножества какого-либо множества.

 

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

Если в выборке поменяют местами два элемента, и получится другая выборка, то данная выборка является упорядоченной.

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

  Если речь идёт об упорядоченных выборках, то {#;Δ}и{Δ;#} являются различными выборками.

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

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

  Если речь идёт о неупорядоченных выборках, то {#;Δ}и{Δ;#} являются одинаковыми выборками.

  Неупорядоченные выборки                      Упорядоченные выборки

Размещением из n элементов по m элементов (m≤n) называется упорядоченная выборка элементов m из данного множества элементов n.

Количество размещений из n элементов по m элементов обозначается Amn (читается как «размещение из nэлементов по m элементов»).

 

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

Решение:

выбираются 2 элемента из множества 5 элементов.

В данном случае n=5 (т. к. дано множество с 5 цифрами), а m=2 (т. к. нужно выбрать 2 цифры для числа).

Вычисляем A2 5.