Rambler's Top100





10
Пример. Выпишем все перестановки 3-х элементного множества
A={a;b;c}: (a;b;c),(a;c;b),(b;a;c),(b;c;a),(c;a;b),(c;b;a). Таким
образом, P
3
=6.
Теорема 8. P
n
=n!.
Доказательство. Каждую перестановку n-элементного множества
можно рассматривать как n-размещение этого множества. Поэтому
!
!0
!
)!(
!
n
n
nn
n
AP
n
nn
.
Задача. Сколькими способами на шахматной доске можно расста-
вить 8 ладей таким образом, что бы они не били друг друга.
Решение. Первую вертикаль можно заполнить лишь одной ладьѐй,
чтобы не нарушалось условие задачи. Причѐм количество способов за-
полнить эту вертикаль равно восьми. На вторую вертикаль можно по-
ставить тоже только одну ладью, причѐм уже семью способами, и т.д.
вплоть до восьмой вертикали, которую можно заполнить одним спосо-
бами. По принципу произведения всего способов расстановки ладей так,
чтобы они не били друг друга, будет 8·7·6·….·2·1=8!
§3.Сочетания. Свойства сочетаний.
Бином Ньютона
Определение 1. Пусть дано n-элементное множество. Любое k-
элементное подмножества множества A называется k-сочетанием n-
элементного множества.
Число k-сочетаний n-элементного множества обозначается
k
n
C
.
Пример. Выпишем все 2-сочетания 4-элементного множества
A={a,b,c,d}: {a;b},{a;c},{a;d},{b,c},{b,d},{c,d}.
Таким образом,
6
2
4
C
.
Теорема 2.
)!(!
!
knk
n
C
k
n
при k n.
Доказательство. Из одного k-сочетания можно получить k! k-
размещений n-элементного множества, потому что k элементов можно
упорядочить k! способами. Поскольку каждое k-размещение есть не что
иное, как упорядоченное k-сочетание, то всего k-размещений будет
!kC
k
n
. С другой стороны k-размещений имеется
k
n
A
.