Формула включений исключений
Формула включений-исключений (или принцип включений-исключений) — комбинаторная формула, позволяющая определить мощность объединения конечного числа конечных множеств, которые в общем случае могут пересекаться друг с другом. В теории вероятностей аналог принципа включений-исключений известен как формула Пуанкаре.
Случай двух множеств
Например, в случае двух множеств 
формула включений-исключений имеет вид:
В сумме 
элементы пересечения 
учтены дважды, и чтобы компенсировать это мы вычитаем 
из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера-Венна для двух множеств, приведенной на рисунке справа.
Таким же образом и в случае 
множеств процесс нахождения количества элементов объединения 
состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.
Билет
Размещение с повторениями
В комбинаторике размещением (из n по k) называется упорядоченный набор из k различных элементов из некоторого множества различных n элементов.
Пример 1: 
— это 4-элементное размещение из 6-элементного множества 
.
Пример 2: некоторые размещения элементов множества по 2: 
... 
... 
...
В отличие от сочетаний, размещения учитывают порядок следования предметов. Так, например, наборы 
и 
являются различными, хотя состоят из одних и тех же элементов 
(то есть совпадают как сочетания).
Количество размещений из n по k, обозначаемое 
, равно убывающему факториалу:
Последнее выражение имеет естественную комбинаторную интерпретацию: каждое размещение из n по k однозначно соответствует некоторому сочетанию из n по k и некоторой перестановке элементов этого сочетания; число сочетаний из n по k равно биномиальному коэффициенту 
, в то время как перестановок на k элементах ровно k! штук.
При k=n количество размещений равно количеству перестановок порядка n:
Размещение с повторениями
Размещение с повторениями или выборка с возвращением — это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз.
Количество размещений с повторениями
По правилу умножения количество размещений с повторениями из n по k, обозначаемое 
, равно:
Например, количество вариантов 3-значного кода, в котором каждый знак является цифрой от 0 до 9 и может повторяться, равно:
Ещё 1 пример: размещений с повторениями из 4 элементов a, b, c, d по 2 равно 
эти размещения следующие:
Билет
Размещения без повторений
В размещении с повторениями были допустимы повторы элементов в каждой ячейке. Как на примере кодового замка - одну крутящуюся "крутилку :)" с цифрами можно сопоставить с одной ячейкой, а цифры от нуля до девяти на ней - элементами. Очевидно, что может быть несколько ячеек с одинаковой цифрой. "Отоно шо, Мыхалыч, от оно шо", потому и называется размещения с повторениями.
А что если ячейками является несколько стульев, а элементами люди? Очевидно, что на трех разных стульев не может сидеть один и тот же человек (Конечно если он не наберется наглости и не ляжет вдоль стульев, чем эффектно испортит весь эксперимент). Вот как раз в такие моменты и используется формуларазмещения без повторения которая выглядит вот так:
Где m - количество элементов, а k - количество ячеек.
m! - рассчитывает все возможные варианты комбинаций данных элементов.
(m-k)! - все возможные варианты элементов оставшихся без ячеек.
Разделив одно на другое - каким-то боком узнаем, все варианты размещения без повторений О_о
Это была удобная продвинутая формула. Но так же есть и более простая. То есть если так же выбрать кто будет сидеть на трех стульях из 14 человек, можно не вспоминать то нечто ужасное с восклицательными знаками, а просто перемножить таким образом:
14 (садим одного на стул)*13(посадили еще одного)*12(и еще одного, 3 стула заняты)=2184 комбинации. Если подставить в формулу выше - получим тот же ответ.
И накой же нам тогда верхняя формула с факториалами? А на тот случай, если стульев окажется эдак 80, а человек эдак 120. Не перемножать же все долгой длинной цепочкой =)
Билет 6.
Перестановки. Число перестановок. Примеры.
Перестановки
Пусть имеется n различных объектов.
Будем переставлять их всеми возможными способами (число объектов остается неизменными, меняется только их порядок). Получившиеся комбинации называютсяперестановками, а их число равно
Pn=n!=123...(n1)n
Символ n! называется факториалом и обозначает произведение всех целых чисел от 1 до n. По определению, считают, что 0!=1,1!=1.
Пример всех перестановок из n=3 объектов (различных фигур) - на картинке справа. Согласно формуле, их должно быть ровно P3=3!=123=6, так и получается.
С ростом числа объектов количетство перестановок очень быстро растет и изображать их наглядно становится затруднительно. Например, число перестановок из 10 предметов - уже3628800 (больше 3 миллионов!).
Билет 7.
Сочетания без повторений. Формула сочетаний. Пример.
Сочетания без повторений
Сочетанием без повторений называется такое размещение, при котором порядок следования элементов не имеет значения.
Всякое подмножество X состоящее из m элементов, называется сочетанием из n элементов по m.
Таким образом, количество вариантов при сочетании будет меньше количества размещений.
Число сочетаний из n элементов по m обозначается .
Примеры задач
Сколько трехкнопочных комбинаций существует на кодовом замке (все три кнопки нажимаются одновременно), если на нем всего 10 цифр.
Решение:
Так как кнопки нажимаются одновременно, то выбор этих трех кнопок – сочетание. Отсюда возможно вариантов.
У одного человека 7 книг по математике, а у второго – 9. Сколькими способами они могут обменять друг у друга две книги на две книги.
Решение:
Так как надо порядок следования книг не имеет значения, то выбор 2ух книг - сочетание. Первый человек может выбрать 2 книги способами. Второй человек может выбрать 2 книги . Значит всего по правилу произведения возможно 21*36=756 вариантов.
При игре в домино 4 игрока делят поровну 28 костей. Сколькими способами они могут это сделать?
Первый игрок делает выбор из 28 костей. Второй из 28-7=21 костей, третий 14, а четвертый игрок забирает оставшиеся кости. Следовательно, возможно .
Размещения и сочетания с повторениями
Часто в задачах по комбинаторике встречаются множества, в которых какие-либо компоненты повторяются. Например: в задачах на числа – цифры. Для таких задач при размещениях используется формула , а для сочетаний .
Примеры задач
Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5?
Решение. Так как порядок цифр в числе существенен, цифры могут повторяться, то это будут размещения с повторениями из пяти элементов по три, а их число равно .
В кондитерском магазине продавались 4 сорта пироженных: эклеры, песочные, наполеоны и слоеные. Сколькими способами можно купить 7 пироженных.
Решение: Покупка не зависит от того, в каком порядке укладывают купленные пироженные в коробку. Покупки будут различными, если они отличаются количеством купленных пирожных хотя бы одного сорта. Следовательно, количество различных покупок равно числу сочетаний четырех видов пироженных по семь - .
Обезьяну посадили за пишущую машинку с 45 клавишами, определить число попыток, необходимых для того, чтобы она наверняка напечатала первую строку романа Л.Н. Толстого «Анна Каренина», если строка содержит 52 знака и повторений не будет?
Решение: порядок букв имеет значение. Буквы могут повторяться. Значит, всего есть вариантов.
Сочетания
Пусть имеется n различных объектов.
Будем выбирать из них m объектов все возможными способами (то есть меняется состав выбранных объектов, но порядок не важен). Получившиеся комбинации называются сочетаниями из n объектов по m, а их число равно
Cmn=n!(nm)!m!
Пример всех сочетаний из n=3 объектов (различных фигур) по m=2 - на картинке справа. Согласно формуле, их должно быть ровно C23=3!(32)!2!=3. Ясно, что сочетаний всегда меньше
чем размещений (так как при размещениях порядок важен, а для сочетаний - нет), причем именно в m! раз, то есть верна формула связи:
Amn=CmnPm.
Билет 8.
Свойства числа сочетаний.
Свойства числа сочетаний
В дальнейшем нам понадобятся некоторые свойства числа сочетаний.
1. Свойство симметричности: 
2. Рекуррентная формула для числа сочетаний: 
ПРИМЕЧАНИЕ
Интуитивно свойство 2 означает следующее. Если в множестве G, из которого составляется сочетание H, зафиксировать какой-либо элемент x, то все возможные сочетания делятся на две категории: сочетания H, которые содержат x, и сочетания H, не содержащие его. Количество сочетаний первого типа равно числу сочетаний из n-1 (так как элемент x фиксирован) по k-1, второго типа – из n-1 по k.категории: сочетания H, которые содержат x, и сочетания H, не
категории: сочетания H, которые содержат x, и сочетания H, не содержащие его. Количество сочетаний первого типа равно числу сочетаний из n-1 (так как элемент x фиксирован) по k-1, второго типа – из n-1 по k.
Билет 9.