§3.
Элементы комбинаторики.
Размещения.
Определение. Пусть имеется множество, содержащее n элементов. Каждое его упорядоченное подмножество, состоящее из k элементов , называется размещением из n элементов по k элементов.
Рассмотрим задачу .
Задача1. Сколькими способами можно составить различные двузначные числа из четырех цифр 1,2,3,4 ?
Решение.
В этой задаче речь идет о размещениях из четырех элементов по два.
1
способ.
Перебор вариантов.
Рассмотрим все такие числа : 12 13 14 23 24 34
21 31 41 32 42 43
Всего таких чисел 12.
Правило суммы.
Если элемент a можно выбрать m способами, а элемент b – n способами, причем любой выбор элемента a отличен от любого выбора элемента b, то выбор “a или b” можно сделать m + n способами.
Правило произведения.
Если из некоторого множества А элемент ai можно выбрать КA способами, а элемент bj из множества В – КB способами, то совокупность (ai ; bj ) можно образовать КA* КB способами. Правило верно и для совокупностей, состоящих из большего, чем 2 числа элементов.
2 способ. С применением правила произведения.
Первая цифра числа выбирается 4 способами из данных цифр, а вторая цифра числа выбирается 3 способами ( из оставшихся трех цифр). По правилу произведения 4 * 3=12 ( способов).
Формула
для вычисления числа
размещений.
Первый элемент размещения выбирается n способами, второй элемент ( n -1) способами, …, k-ый элемент (n -(k -1)) способами ,т.е. можно ввести формулу для числа вариантов
= (n –1)·(n – 2)
…·(n – (k – 1))
или
=
, где
- число
размещений из n по
k ,
( n! читается n - факториал); n!=1*2*3*….* n ; 0!= 1 по определению;
1!= 1.
3 способ. Применение формулы для вычисления числа размещений.
 |
= |
 |
= |
 |
= | 3 · 4 | = | 12 |
Задача 2. Набирая номер телефона, абонент забыл две последние цифры. Сколько различных вариантов нужно набрать, чтобы дозвониться, если абонент помнит , что цифры различны?
Решение:
=
= 9 · 10 = 90
1.
Перестановки.
Определение. Пусть дано
множество N из n
объектов. Всевозможные
последовательности из всех
n
объектов называются перестановками.
ЗЗадача
1. Сколькими способами можно рассадить
n
человек на n местах
?
еРешение:
11
способ . Перебор вариантов.
1)
n = 1. Число возможных вариантов 1.
2)
n = 2. Возможные
варианты: 12 и 21 ,
всего их 2.
3)
n = 3. Возможные
варианты: 123 213 312
132 231
321, всего их 6.
4)
n = 4 Возможные
варианты: 1234
2134 3124
4123
1324 2314
3214 4213
1432 2431
3421 4321
1243 2341
3142 4132
1342 2143
3241 4231
1423 2431
3412 4312
Всего их 24.
С
увеличением числа n этот способ становится очень
трудоемким. Можно заметить, что
перестановки являются частным случаем
размещений из n
элементов по n , значит
= n!
т.к.
=
=
=
= n!.
2 способ.
Применение формулы перестановок.
= 2!=1·2=2;
=3!=1·2·3=6 ;
=4!=1·2·3·4=24;
3 способ.
Применение правила произведения. (для
n
= 4)
1.
на 1 место человека можно посадить
четырьмя способами : 1, 2, 3, 4
2.
на 2 место только тремя способами :
пример 12 13
14
3.
на 3 место только двумя способами :
пример 123 124
4.
на 4 место только одним способом :
пример 1234
всего
вариантов : 4·3·2·1=24
Задача
2. Сколькими способами можно
составить расписание одного учебного
дня из 6 различных предметов ?
Решение:
= 6!=1·2·3·4·5·6=720
Задача 3. Сколько
различных «слов» можно составить из
букв слова математика?
Решение:
В слове математика 10 букв, значит
перестановок будет
=10!
Однако буква а повторяется 3 раза , буква
т –2 раза , буква м – 2 раза и их
перестановки не дают новых вариантов,
значит
=
=
=151200
Задача 4. Для
дежурства по классу в течение недели (
кроме воскресения) выделены 6 учащихся.
Сколькими способами можно установить
очередность дежурств, если каждый
учащийся дежурит один раз?
Решение:
P=6!=720.
Задача 5. Сколько шестизначных чисел, кратных пяти , можно составить из цифр 1,2,3,4,5,6, при условии , что цифры в числе не повторяются?
Решение:
Последняя цифра должна быть 5,
предыдущие цифры могут быть составлены
из оставшихся пяти цифр 1,2,3,4,6.
Р=5!=120 .
2.
Сочетания.
ОпреОпределение.
Пусть имеется множество, состоящее из n элементов . Каждое его
подмподмножество , содержащее k
элементов , называется сочетанием из n
элемэлементов по k элементов.
ЗадаЗадача
1. Сколько наборов из двух книг можно
скомпоновать из четырех книг ?
Реш
Решение:
1
спо 1 способ. Перебор вариантов.
Возможны следующие наборы ( указываются номера книг) 1 2 1 3 1 4
2
3 2 4
3 4
Формула числа сочетаний.
Число сочетаний можно получить через число размещений , если учесть, что при вычислении числа сочетаний не считаются разными варианты, составленные из перестановок элементов внутри каждого размещения, которых имеется k! , т.е.
.
=
,
Замечание.
=
–
формула, связывающая
сочетания с размещениями.
2
способ. Применение формулы для
вычисления числа сочетаний.
=
=
= 6 .
Задача
2. Сколькими способами можно составить
из 14 преподавателей зкзаменационную
комиссию из 7 членов?
Решение:
Задача
3. Сколькими способами можно выбрать
трех дежурных из группы в 20 человек ?
Решение:
Задача
4. В вазе стоят 10 белых и 5 красных роз.
Сколькими способами можно выбрать из
вазы букет , состоящий из двух красных и
одной белой розы?
Решение:(по
правилу произведения)
·
=
=10 ·
= 100.
Задача
5. В чемпионате страны по футболу ( высшая
лига) участвуют 18 команд , причем каждые
две команды
встречаются между собой два раза.
Сколько матчей играется в течение
сезона?
Решение:
в первом круге
=153
Во втором круге
=153
Всего : 153 ·2 =306
встреч.
1.
БИНОМ НЬЮТОНА.
Биномом Ньютона называют
формулу представляющую выражение
при целом положительном n в виде многочлена .
Знакомые формулы :
Бином Ньютона :
Можно проверить для
n = 2:
.
для n = 3 :
.
Формулы
выполняются.
Числа
называются
биномиальными коэффициентами.
Задача 1.
ТРЕУГОЛЬНИК
ПАСКАЛЯ.
Биномиальные коэффициенты можно получить , пользуясь только сложением, следующим образом.
В верхней строке пишутся две единицы. Все следующие строки начинаются и оканчиваются единицей. Промежуточные числа получаются сложением соседних чисел вышестоящей строки.
1 1
1 2
1
n = 2
1 3
3 1
n = 3
1 4
6 4
1 n = 4
1 5
10 5
10 1
n = 5
1 6
15 20
15 6 1
n = 6
1 7
21 35
35 21 7
1 n
= 7
1 8
28 56
70 56 28
8 1
n = 8
1 9 36
84 126
84 36
9 1 n = 9
1 10 45 120 210 252 210 120 45 10 1
n
= 10
