ТЕОРИЯ КОНЕЧНЫХ МНОЖЕСТВ (КОМБИНАТОРИКА) §1. Принципы сложения и умножения Комбинаторика занимается подсчетом количеств разных комбинаций, которые можно получить различными способами из тех или иных конечных множеств.

Если конечное множество A состоит из m элементов, то мы будем

Доказательство:
При l=2 ссылаемся на теорему 1:
n(A1 A2) = n(A1)

Иногда принцип сложения можно встретить в таком виде: если объект x

Теорема 3 (принцип умножения). Если множество A состоит из m элементов,

Где множествоB'={b1, b2 ,…, bk}состоит из k элементов.
По индуктивному предположению
n(A

В комбинаторном изложении принцип умножения часто формулируют так: если объект x

Теорема 4.
Если множества A1, A2, …, Ak конечны,
то n(A1

Задача . Пусть A и B конечные мн-ва, B A. Сколько

Задача . Из цифр A={0,1,2,3,5,6,7} составить все четырех­значные числа, не содержащие

A1 = {0, 1, 2, 3}, A2 = {0, 1, 2,

Аналогично
n(B2 )=n(B3 )=n(B4 )=n(B5 )=n(B6 )=n(B7 )=18
По принципу произведения n(B8

§2. Размещения и перестановки

Определение 1. Пусть дано конечное множество A, n(A)=n

Пример. Пусть A={a,b,c,d}.
Выпишем все 2-размещения этого четырёхэлементного множества:
(a;b), (b;a), (a;c),

Теорема 2. Пусть n ∈ N, 1 ≤ k ≤ n.

C другой стороны ,
то есть

Допустим, равенство выполняется для k < n, то есть
Докажем равенство для

Пример. В первенстве страны участвуют 12 команд. Сколькими способами они смогут

Замечание 3. При k>n невозможно построить k-размещение, поэтому
при k>n.
Замечание

Определение 5. Пусть конечное множество A состоит из n элементов. k

Теорема 6.

Доказательство.
Применим индукцию по k.
При k=1 число 1-размещений равно числу

Докажем утверждение при k= l +1.
Из каждого упорядоченного l-элементного набора

Пример. Номер машины состоит из двух букв русского алфавита (32 буквы)

Определение7.
Перестановкой n-элементного множества называется упорядоченный набор длины n, составленный из этих

Теорема 8. Pn=n!

Доказательство. Каждую перестановку n-элементного множества можно рассматривать

Задача. Сколькими способами на шахматной доске можно расставить 8 ладей таким

§3.Сочетания. Свойства сочетаний. Бином Ньютона  

Определение 1.
Пусть дано n-элементное множество. Любое k-элементное подмножества множества

Теорема 2. при k ≤ n.

Доказательство. Из одного k-сочетания можно

и отсюда получаем искомую формулу:

Теорема 3 (простейшие свойства сочетаний).
1) 
2)  
3)  
4) 
5)      , (m≥1);

Теорема 4 (бином Ньютона).

Доказательство.
Второе равенство представляет собой не что иное, как разные записи

Раскрыв скобки, получим сумму
В первой сумме количество слагаемых равно количеству элементов

Число слагаемых в k-ой сумме равно количеству k-элементных подмножеств n-элементного множества

Следствие 5.
Следствие 6.
Следствие 7 . (a+b)n =

Замечание. В силу большой важности бинома Ньютона для самых разных разделов

Определение 10. Пусть А = {a1, a2, …, an} - n–элементное

Лемма . Число всех упорядоченных нулей и единиц последовательностей из нулей