КОМБИНАТОРИКА
Комбинаторика – раздел математики, который изучает задачи выбора и расположения элементов из некоторого основного множества в соответствии с заданными правилами. Формулы и принципы комбинаторики используются в теории вероятностей для подсчета вероятности случайных событий и, соответственно, получения законов распределения случайных величин. Это, в свою очередь, позволяет исследовать закономерности массовых случайных явлений, что является весьма важным для правильного понимания статистических закономерностей, проявляющихся в природе и технике.
Правила сложения и умножения в комбинаторике
Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В – n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.
Пример 1.
В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?
Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.
По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.
Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n1 способами, второе действие n2 способами, третье – n3 способами и так до k-го действия, которое можно выполнить nk способами, то все k действий вместе могут быть выполнены:
Пример 2.
В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить двух дежурных?
Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.
После того, как мы выбрали первого дежурного, второго мы можем выбрать из оставшихся 25 человек, т.е. 25-ю способами.
По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.
Сочетания без повторений. Сочетания с повторениями
Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?
Пример 3.
Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?
Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:
.
Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m (
) из этих (n*r) предметов?
.
Пример 4.
В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?
Т.к. среди 7 пирожных могут быть пирожные одного сорта, то число способов, которыми можно купить 7 пирожных, определяется числом сочетаний с повторениями из 7 по 4.
.
Размещения без повторений. Размещения с повторениями
Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?
Пример 5.
В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?
В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:
Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.
Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов, среди которых есть одинаковые?
Пример 6.
У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера– составить каталог. Сколько различных пятизначных номеров может составить мальчик?
Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр (1, 3, 7). Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:
.
Перестановки без повторений. Перестановки с повторениями
Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?
Пример 7.
Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?
Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.
Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k
Пример 8.
Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?
Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно
ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ «КОМБИНАТОРИКА»
Источник
Сколькими способами можно набрать подряд четыре различные цифры
§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 по определению;
3 способ. Применение формулы для вычисления числа размещений.
 | = |  | = |  | = | 3 · 4 | = | 12 |
Задача 2. Набирая номер телефона, абонент забыл две последние цифры. Сколько различных вариантов нужно набрать, чтобы дозвониться, если абонент помнит , что цифры различны?
= 
= 9 · 10 = 90
Определение . Пусть дано множество 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 .
ОпреОпре деление . Пусть имеется множество, состоящее из n элементов . Каждое его подмподмножество , содержащее k элементов , называется сочетанием из n элемэлементов по k элементов.
ЗадаЗадача 1. Сколько наборов из двух книг можно скомпоновать из четырех книг ?
1 спо 1 способ . Перебор вариантов.
В озможны следующие наборы ( указываются номера книг) 1 2 1 3 1 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. 
Биномиальные коэффициенты можно получить , пользуясь только сложением, следующим образом.
В верхней строке пишутся две единицы. Все следующие строки начинаются и оканчиваются единицей. Промежуточные числа получаются сложением соседних чисел вышестоящей строки.
Источник
