9. Комбинаторика. Основные опр-я. Правило суммы и произведения. Метод включений и исключений.

Подмножество из r эл-в выбранного из мн-ва состоящего из n эл-ов наз. Из n по r выборкой (n,r), где r- объем выборки.

Выборка наз. упорядоченной, если порядок следования эл-ов в ней задан.

2 упорядоченные выборки, различающиеся только лишь порядком следования эл-ов считаются различными.

Если порядок следования эл-ов не является существенным, то выборка наз. не упорядоченной

Упорядоченная (n,n) выборка, в которой эл-ты могут повторяться назыв. Перестановкой с повторениями из n по n. Перестановка с повторениями = =

Если эл-ты упорядочены (n,n) – выборка попарно различны, то она наз. (n,n) – без повторений

Перестановка без повторений: =n!

Упорядоченная (n,r) – выборка, в которой эл-ты могут повторяться называется размещением с повторениями из n эл-ов по r =

Если эл-ты упорядочены (n,r) выборки попарно различны, то она наз (n,r) размещением без повторений =

Неупорядоченная выборка (n,r) в которой эл-ты попарно различны наз. сочетанием без повторений =

Если эл-ты неупорядочены (n,r) выборке могут повторяться, то она наз. сочетанием с повторениями =

Правило суммы: Если объект А может быть выбран m-способами, а объект B n-способами при условии, что одновременный выбор A и B не возможен, то выбор «A или B» осуществить (m+n) – способами

Правило произведения: Если A может быть выбран m-способами, и после каждого из таких выборов B в свою очередь может быть выбран n-способами, то «A и B» в указанном порядке m n

n(A

n(A

10. Бином Ньютона. Основные свойства биномиальных коэффициентов. Треугольник Паскаля. Полиномиальная теорема.

Def: всякий двучлен наз биномом, т.е это сумма или разность 2 алгебраич выражений, называемых членами бинома.Известны формулы сокращенного умножения, позволяющие сразу же ввести бином во 2,3 … степени.

(а+b)ⁿ=∑C_n^k a^k b^n-k= C_n⁰ a⁰ bⁿ + C_n¹ a¹ b^n-1 + C_n² a² b^n-2 + … + C_n^n-1 a^n-1 b¹ + C_nⁿ aⁿ b⁰ - формула Бином Ньютона, а числа сочетания (n,k) наз биноминальными коэффициентами. Теорема Бином Ньютона.

(а+b)ⁿ=∑C_n^k a^k b^n-k

При n=1. (а+b)¹=∑C₁^k a^k b^k-1= C₁⁰ a⁰ b¹ + C₁¹ a¹ b⁰=b+a.

При n=j. (а+b)^j=∑C_j^k a^j b^n-j

При n=j+1. (а+b)^j+1 = (a+b)^j(a+b) = (∑C_j^k a^k b^j-k)(a+b) = ∑C_j^k a^k+1 b^j-k + ∑C_j^k a^k b^j+1-k = ∑C_j^k a^k+1 b^j-k + C_j^k a^j+1 b⁰ + C_j⁰ a⁰ b^j-k+1 + ∑C_j^k a^k b^j+1-k = C_j⁰ a¹ b^j + C_j¹ a² b^j-1 + C_j² a³ b^j-2 +…+ C_j^j-1 a^j b¹ + C_j^j a^j+1 b⁰ + C_j⁰ a⁰ b^j+1 + C_j¹ a¹ b^j + C_j² a² b^j+1 +…+ C_j^j a^j b¹ = C_j⁰ a⁰ b^j+1 + ∑(C_j^k + C_j^k+1 )a^k+1 b^j-k + C_j^j a^j+1 b⁰ = C_j⁰ a⁰ b^j+1 + ∑C_j+1^k+1 a^k+1 b^j-k + C_j^j a^j+1

Следствия ∑C_n^k=2ⁿ – сумма всех биноминальных коэфф = 2ⁿ.

Основные свойства биномиальных коэффициентов.

1. C_n^k = C_n^n-k. Коэфф членов равноудаленных от начала и от конца разложения равны между собой. Соотношение симметрии

2. - формула сложения

3.

4. 5. - тождество Коши

Треугольник Паскаля.

С помощью свойства 2 можно последоват вычислить , используя кроме указ соответствия, след: . Вычисляемые коэфф распол в виде таблицы, кот наз треугольником Паскаля или арифметич треугольником.

Полиномиальная теорема.

Обобщение формулы Ньютона на случ k-слагаемых , где r₁+r₂+r_k=n, ,…, . Где суммирование производ по всем решениям ур r₁+r₂+…+r_k=n в целых неотриц числах.