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

комбинаторные задачи, решая которые приходится составлять различные комбинации из конечного

числа элементов и подсчитать число комбинаций.
Раздел математики, в котором рассматриваются комбинаторные задачи, называется комбинаторикой.

Немного из истории: Комбинаторика возникла в XVI веке. В карты и кости выигрывались и проигрывались золото, бриллианты, дворцы и имения. Поэтому первые комбинаторные задачи касались в основном азартных игр.

входят пять человек - Антон, Борис, Виктор, Глеб и Дмитрий,

тренер выделяет пару для участия в соревнованиях. Сколько существует вариантов выбора такой пары?
Дерево (граф) возможных вариантов
Пример: Сколько трехзначных чисел можно составить из цифр 1, 3, 5 и 7, используя в записи числа каждую из них не более одного раза?

блюда: борщ, щи, рассольник. На второе: гуляш, жаркое, голубцы, плов.

Из напитков: чай, кофе, компот. Сколько различных обедов может заказать посетитель?
В общем виде
Пусть имеется n элементов (n1 возможных первых, n2 возможных вторых и т. д.) и требуется выбрать из них один за другим k элементов.
Число способов , которыми могут быть выбраны все k элементов, равно произведению  n1 ∙ n2 ∙ n3 ∙ … ∙ nк.

из города В в город С — 3 дороги. Сколько

путей, проходящих через В, ведут из А в С?
Имеется 5 видов конвертов без марок и 4 вида марок одного достоинства. Сколькими способами можно выбрать конверт с маркой для посылки письма?
Сколькими способами можно выбрать гласную и согласную буквы из слова «камзол»? А из слова «здание»?
Бросают игральную кость с 6 гранями и запускают волчок, имеющий 8 граней. Сколькими различными способами могут они упасть?
На вершину горы ведут 5 дорог. Сколькими способами турист может подняться на гору и спуститься с нее? То же самое при условии, что спуск и подъем происходят по разным путям.
На ферме есть 20 овец и 24 свиньи. Сколькими способами можно выбрать одну овцу и одну свинью? Если такой выбор уже сделан, сколькими способами можно сделать его еще раз?
Сколькими способами можно указать на шахматной доске два квадрата — белый и черный? А если нет ограничений на цвет выбранных квадратов?
Сколькими способами можно выбрать на шахматной доске белый и черный квадраты, не лежащие на одной и той же горизонтали и вертикали?

n! = 1 ∙2 ∙3 ∙… ∙ (n -2)∙ (n – 1)∙ n
1! = 1
2! = 1∙2 = 2
3! = 1∙2∙3 = 6
4! = 1∙2∙3∙4 = 24
5! = 1∙2∙3∙4∙5 = 120
6! = 5! ∙ 6 = 120 ∙ 6 = 720
7! = 6! ∙ 7 = 720 ∙7 = 5040

5.

6.

7. Что больше 6!∙5 или

5!∙6 ?
8. Что больше (n+1)!∙n или n!∙(n+1) ?
9. На сколько нулей оканчивается 10!, 15!, 25! ?

 Рn = n∙(n -1)∙(n – 2

)∙ …∙3∙2∙1=n!
Рn = n! – формула количества всевозможных перестановок из n элементов

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

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

четырехместной скамейке?

3. Сколько различных четырехзначных чисел, в которых цифры не повторяются, можно составить из цифр 0,5,4,8 ?
Р4 - Р3 = 4! – 3! = 24 – 6 = 18
4. Сколько пятизначных чисел содержат все цифры а) 1, 2, 3, 4, 5? б) 0, 2, 4, 6, 8? Какова сумма всех таких пятизначных чисел в каждом из пунктов?*
5. Сколько четных и сколько нечетных чисел можно составить перестановкой цифр из числа 3694?
6. Имеется 10 различных книг, из которых 3 – на французском языке. Сколькими способами их можно расставить на полке, при условии, что книги на французском языке должны стоять рядом?
7. Сколькими способами можно расставить на полке 4 книги по алгебре и 3 по геометрии так, чтобы книги по геометрии стояли рядом?
8. Сколькими способами можно посадить за круглый стол 5 мужчин и 5 женщин так, чтобы никакие два лица одного пола не сидели рядом?
9. Сколькими способами можно посадить на карусель 5 мужчин и 5 женщин так, чтобы никакие два лица одного пола не сидели рядом. Способы, переходящие друг в друга при вращении карусели, считаются совпадающими.

в определенном порядке из данных  n элементов.

Аnk = 

Частный случай n=k : Аnn = Pn = n!
Перестановки – частный случай размещений

Задача: Сколькими способами можно составить 3хцветный 
полосатый флаг, если имеется материал 5 разных цветов цветов?

можно составить расписание на один день, чтобы в нем было

4 различных предмета
Решение: А84 = 5 ∙ 6 ∙ 7 ∙ 8 = 1680
Пример 2. Сколько трехзначных чисел (без повторения цифр в записи числа) можно составить из цифр 0,1,2,3,4,5?
Решение: А63 - А52 =  4 ∙ 5 ∙ 6 - 4 ∙ 5 = 120-20=100.
Пример 3. Сколько существует трехзначных чисел (без повторения цифр в записи числа)?
Решение: А103 - А92 =  8 ∙9 ∙10 - 8 ∙9 = 720-72=648.

и секретаря. Сколькими способами это можно сделать?
Сколько словарей надо

издать, чтобы можно было непосредственно выполнять переводы с любого из пяти языков: русского, английского, французского, немецкого, итальянского, на любой  другой из этих пяти языков?
Сколькими способами можно составить трехцветный полосатый флаг, если имеется материал 5 различных цветов?
Та же задача, если одна из полос должна быть красной?
Сколько четырехзначных чисел, в которых нет одинаковых цифр, можно составить из цифр: а) 1,3,5,7,9. б) 0,2,4,6,8?
Какова сумма всех таких пятизначных чисел в каждом из пунктов?

Сочетанием из n элементов по k (k ≤n) называется любое множество, состоящее из k элементов, взятых из

данных  n элементов. (порядок не важен!)
 Сnk = Аnk : Рk , Сnk =  .

6 команд. Продолжат соревнования только две из них. Сколько разных

вариантов прохождения команд?

Решение : С62 = (6 ∙ 5) : (1∙ 2 ) = 15

Пример 2. В классе учатся 12 мальчиков и 10 девочек. Для уборки территории около школы требуется выделить трех мальчиков и двух девочек. Сколькими способами можно сделать этот выбор?

Решение:
С123 ∙ С102 =  (12 ∙11 ∙ 10) : (1∙ 2 ∙ 3) ∙ (10 ∙ 9) : (1∙ 2) = 220 ∙ 45 = 9900

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

них сыграл с каждым по одной партии. Сколько всего партий было сыграно?
Сколько диагоналей можно провести в выпуклом 7-угольнике? n-ке?
В библиотеке читателю предложили на выбор из новых поступлений 10 книг и 4 журнала. Сколькими способами он может выбрать из них 3 книги и 2 журнала?
Из вазы с фруктами, где лежат 9 яблок и 6 груш, нужно выбрать 3 яблока и 2 груши. Сколькими способами можно это сделать?
Из лаборатории, в которой работают заведующий и 10 сотрудников, надо отправить 5 человек в командировку. Сколькими способами это можно сделать, если: а)заведующий лабораторией должен ехать в командировку; б)заведующий лабораторией должен остаться?
На полке стоит 12 книг: англо-русский словарь и 11 художественных произведений. Сколькими способами читатель может выбрать 3 книги, если: а) словарь нужен ему обязательно; б) словарь ему не нужен? 

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

это может быть сделано?
У мамы 2 яблока, 3 груши и 4 апельсина. Каждый день в течение пяти дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано?
Из колоды, содержащей 52 карты, вынули 10 карт. Во скольких случаях среди этих карт окажется хотя бы один туз? Во скольких случаях ровно один туз? Во скольких случаях не менее двух тузов? Ровно два туза?

(a-b)9
3. В разложении (1+x)n четвертый член равен 0,96.
Найти значения

x и n, если сумма биномиальных
коэффициентов равна 1024.

вероятностей : учеб. пособие для учащихся 7—9 кл. общеобразоват. учреждений

/ Ю. Н. Макарычев, Н. Г. Миндюк; под ред. С. А. Теляковского.
Виленкин Н.Я., Виленкин А.Н., Виленкин П.А. Комбинаторика. - М.: ФИМА, МЦНМО, 2006. - 400 с.