Формула включений исключений

Формула включений-исключений (или принцип включений-исключений) — комбинаторная формула, позволяющая определить мощность объединения конечного числа конечных множеств, которые в общем случае могут пересекаться друг с другом. В теории вероятностей аналог принципа включений-исключений известен как формула Пуанкаре.

Случай двух множеств

Например, в случае двух множеств формула включений-исключений имеет вид:

В сумме элементы пересечения учтены дважды, и чтобы компенсировать это мы вычитаем из правой части формулы. Справедливость этого рассуждения видна из диаграммы Эйлера-Венна для двух множеств, приведенной на рисунке справа.

Таким же образом и в случае множеств процесс нахождения количества элементов объединения состоит во включении всего, затем исключении лишнего, затем включении ошибочно исключенного и так далее, то есть в попеременном включении и исключении. Отсюда и происходит название формулы.

Билет

Размещение с повторениями

В комбинаторике размеще́нием (из 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!=1⋅2⋅3⋅...⋅(n −1)⋅ n

Символ n! называется факториалом и обозначает произведение всех целых чисел от 1 до n. По определению, считают, что 0!=1,1!=1.

Пример всех перестановок из n =3 объектов (различных фигур) - на картинке справа. Согласно формуле, их должно быть ровно P 3=3!=1⋅2⋅3=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!(n − m)!⋅ m!

Пример всех сочетаний из n =3 объектов (различных фигур) по m =2 - на картинке справа. Согласно формуле, их должно быть ровно C 23=3!(3−2)!⋅2!=3. Ясно, что сочетаний всегда меньше

чем размещений (так как при размещениях порядок важен, а для сочетаний - нет), причем именно в m! раз, то есть верна формула связи:

Amn = Cmn ⋅ Pm.

Билет 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.