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

1. Сочетания

2. Сочетания

Определение 1
Сочетанием из n элементов по k называется
всякая совокупность попарно различных k
элементов, выбранных каким-либо способом из
данных n элементов.
Другими словами k-сочетание – это kэлементное подмножество n элементного
множества.
Пример. Дано множество A a; b; c .
Составим 2- сочетания: {a; b};{a; c};{b; c}

3. Сочетания

Теорема 1
Число k- сочетаний n-элементного множества
вычисляется по формуле
n!
C nk
k!(n k )!
Доказательство. Из каждого k-сочетания,
переставляя его элементы всевозможными
способами, получим k! размещений. Значит,
k! Cnk Ank
Отсюда
k
A
n!
k
n
Cn
k! k!(n k )!

4. Пример

Сколькими способами можно выбрать 3
плитки шоколада из имеющихся 5 плиток?
Решение. Задача сводится к вычислению
числа сочетаний из 5 по 3
5!
C
10
3!(5 3)!
3
5

5. Свойства сочетаний

1)
Сn0 Cnn 1
Доказательство:
Сn0
2)
n!
n!
1
0!(n 0)! n!
Сnn
n!
n!
1
n!(n n)! n!
Cn1 Cnn 1 n
Доказательство:
Сn1
n!
(n 1)! n
n
1!(n 1)! (n 1)!
Сnn 1
n!
n!
(n 1)! n
n.
(n 1)!(n (n 1))! (n 1)!1! (n 1)!

6. Свойства сочетаний

3) С nk C nn k
Доказательство:
Сnk
n!
k!(n k )!
Сnn k
n!
n!
(n k )!(n (n k ))! (n k )! k!
C C
k
n
n k
n
4) C nk 11 C nk 1 C nk
Доказательство:
Сnk 11
(n 1)!
(n 1)!
(k 1)!(n 1 (k 1))! (k 1)!(n k )!
Сnk 1 Cnk
n!
n!
n!(n k ) n!(k 1)
n!(n 1)
(n 1)!
(k 1)!(n k 1)! k!(n k )!
(k 1)!(n k )!
(k 1)!(n k )! (k 1)!(n k )!

7. Бином Ньютона

n
( а b) C a
n
k 0
k
n
n k
b
k

8. Следствия из бинома Ньютона

n
1)Равенство
k
n
C
2
получается из бинома Ньютона при
n
k 0
a b 1.
n
k
k
(
1
)
C
n 0 получается из бинома Ньютона при
2) Равенство
k 0
a 1, b 1.

9. Сочетания с повторениями

10. Сочетание с повторениями

Определение 1
Сочетанием из n элементов по k называется
всякая совокупность k элементов, выбранных
каким-либо способом из данных n элементов.
Пример: Дано множество А= a; b; c .
Составим 2- сочетания с повторениями:
a; b ; b; c ; a; c ; a; a ; b; b ; c; c

11. Число сочетаний с повторениями

Теорема1. Число k-сочетание с повторениями n
– элементного множества вычисляется по
формуле
C C
k
n
k
n k 1
(n k 1)!
k!(n 1)!

12. Пример

В магазине продаются пирожные 4 сортов.
Сколькими способами можно купить 7
пирожных?
Решение. Используем формулу числа
сочетаний с повторениями, так как покупка
будет содержать пирожные повторяющихся
сортов.
7
4
C C47 7 1 C107
10!
10! 8 9 10
120.
7!(10 7)! 7!3!
2 3

13.

Сводная таблица
Порядок важен
С повторениями
Аnk n k
P(n1 , n2 , , nk )
Без повторений
Порядок не важен
C nk C nk k 1
(n1 n2 nk )!
n1!n2 ! nk !
Ank
n!
n k !
Ann Pn n!
C nk
n!
k!(n k )!