КОМБИНАТОРИКА
1. Правило суммы. Классическая формулировка
Если элемент 
можно выбрать k способами, а элемент 
можно выбрать m способами.
Тогда или можно выбрать k + m способами.
Теорема о мощности объединения множеств (современная формулировка)
Количество элементов объединения двух множеств равно сумме количества элементов в первом и во втором множестве, за вычетом количества элементов их пересечения: 
.
Причем, если множества не пересекаются, то теорема приобретает вид, аналогичный классической формулировке: 
.
Для трех множеств теорема имеет вид: 
.
Пример: Из 35 учащихся класс по итогам года имели “5” по математике – 14 человек; по физике – 15 человек; по химии – 18 человек; по математике и физике – 7 человек; по математике и химии – 9 человек; по физике и химии – 6 человек; по всем трем предметам – 4 человек.
Сколько человек имеют “5” по указанным предметам? Сколько человек не имеет “5” по указанным предметам? Имеет “5” только по математике? Имеет “5” только по двум предметам?
2. Правило произведения. Классическая формулировка
Если элемент можно выбрать k способами, а элемент можно выбрать m способами.
Тогда и можно выбрать km способами.
Теорема о мощности прямого произведения множеств (современная формулировка)
Количество элементов прямого произведения двух множеств равно произведению количества элементов первого и второго множества: 
.
Пример: Из 3 экземпляров учебника алгебры, 7 экземпляров учебника геометрии и 6 экземпляров учебника физики, надо выбрать комплект, содержащий все учебники по одному разу. Сколькими способами это можно сделать?
Число размещений без повторений
Число размещений без повторений из n по k – это число способов, сколькими можно из n различных элементов построить векторов с k различными координатами.
Число размещений без повторений находится по формуле: 
.
Пример: Сколькими способами можно построить 3-значное число с различными цифрами, не содержащее цифры 0?
Число размещений с повторениями
Число размещений с повторениями из n по k – это число способов, сколькими можно из n различных элементов построить векторов с k координатами, среди которых могут быть одинаковые.
Число размещений с повторениями находится по формуле: 
.
Пример: Сколько слов длины 6 можно составить из 26 букв латинского алфавита?
Число перестановок без повторений
Число перестановок без повторений из n элементов – это число способов, сколькими можно расположить на n различных местах n различных элементов.
Число перестановок без повторений находится по формуле: 
.
Пример: Сколькими способами можно расставить на книжной полке 5 различных книг? В скольких случаях две определенные книги А и В окажутся рядом?
Замечание: 
, где х – число способов выбрать нужные места; у- число способов расположить на них нужные элементы; z- число способов расположить остальные элементы на оставшихся местах.
Число сочетаний без повторений
Число сочетаний без повторений из n по k – это число способов, сколькими можно из n различных элементов выбрать k штук без учета порядка.
Число сочетаний без повторений находится по формуле: 
.
Свойства: 1) 
; 2) 
; 3) 
; 4) 
; 5) 
; 6) 
.
Пример: В урне 7 шаров. Из них 3 белых. Наугад выбирают 3 шара. Сколькими способами это можно сделать? В скольких случаях среди них будет: 1) один белый; 2) два белых; 3) все белые.
Задачи
1) В аквариуме 11 рыбок. Из них 4 красных, остальные золотые. Наугад выбирают 4 рыбки. Сколькими способами это можно сделать? Найти число способов сделать это так, чтобы среди них будет: а) ровно одна красная; б) ровно 2 золотых; в) хотя бы одна красная.
2) В списке 8 фамилий. Из них 4 – женские. Сколькими способами их можно разделить на две равные группы так, чтоб в каждой была женская фамилия?
3) Из колоды в 36 карт выбирают 4. Сколько способов сделать это так, чтобы: а) все карты были разных мастей; б) все карты были одной масти; в) 2 красные и 2 черные.
4) На карточках разрезной азбуки даны буквы К, К, К, У, У, А, Е, Р. Сколько способов сложить их в ряд так, что бы получилось «кукареку ».
5) Даны карточки разрезанной азбуки с буквами О, Т, О, Л, О, Р, И, Н, Г, О, Л, О, Г. Сколько способов сложить их так, что бы получилось слово «отолоринголог ».
6) Даны карточки нарезной азбуки с буквами Л, И, Т, Е, Р, А, Т, У, Р, А. Сколько способов сложить их в ряд так, что бы получилось слово «литература ».
7) 8 человек становятся в очередь. Сколько способов сделать это так, что бы два определенных человека А и Б оказались: а) рядом; б) на краях очереди;
8) 10 человек садятся за круглый стол на 10 мест. Сколькими способами это можно сделать так, чтоб рядом оказались: а) два определенных человека А и Б; б) три определенных человека А, Б и С.
9) Сколькими способами можно расположить на 10 путях станции 1 товарный и 2 пассажирских поезда так, чтоб товарный не находился на соседнем пути ни с одним из пассажирских поездов.
10) Из 10 арабских цифр составляют 5-значный код. Сколькими способами это можно сделать так, чтобы: а) все цифры были разными; б) на последнем месте четная цифра.
11) Из 26 букв латинского алфавита(среди них 6 гласных) составляется шестибуквенное слово. Сколькими способами это можно сделать так, чтобы в слове были: а) ровно одна буква «а»; б) ровно одна гласная буква; ровно две буквы «а»; в) ровно две гласные.
12) Сколько четырехзначных чисел делятся на 5?
13) Сколько четырехзначных чисел с различными цифрами делятся на 25?
14) В скольких десятизначных числах сумма цифр ровна 3?
15) Брошены 3 игральные кости. В скольких случаях выпала: а) ровно 1 «шестерка »; б) хотя бы одна «шестерка ».
16) Брошены 3 игральные кости. В скольких случаях будет: а) все разные; б) ровно два одинаковых числа очков.
17) Сколько слов с различными буквами можно составить из алфавита а, в, с, d. Перечислить их все в лексикографическом порядке: abcd, abcd….
18) Записать прямое произведение множеств А= 
В= 
.
19) В классе 8 человек имеют «5» по литературе; 9 человек – по английскому; 10 человек – по истории. Кроме того известно, что 6 человек имеют «5» по литературе и истории; 5 – по литературе и английскому; 5 – по истории и английскому; 3 – по всем предметам. Сколько человек имеют «5»: а) только по литературе; б) только по двум предметам; в) не имеют «5» по английскому.
20) В 20 комнатах общежития института Дружбы Народов живут студенты из России; в 15 – из Африки; в 20 – из стран Южной Амери ки.Причем в 7 – живут россияне и африканцы, в 8 – россияне и южноамериканцы; в 9 – африканцы и южноамериканцы. В 3х комнатах живут и россияне, и южноамериканцы, и африканцы. В скольких комнатах живут студенты:
а) только с одного континента;
б) только с двух континентов;
в) только африканцы.