Составители:
Рубрика:
17
Свойства чисел
k
n
C
Числа
k
n
C
обладают рядом замечательных свойств. Эти свойства можно доказывать по-
разному. Можно прямо воспользоваться формулой
)!(!
!
knk
n
C
k
n
−⋅
=
. Однако часто удается
получить доказательство из комбинаторных соображений.
1 свойство: P(k, n-k) =
k
n
C
Доказательство.
k
n
C
knk
n
knkP =
−⋅
=−
)!(!
!
),(
Комбинаторное доказательство.
Поставим по порядку все n элементов, из которых составляют сочетания, и зашифруем
каждое сочетание комбинацией из n нулей и единиц. Каждому k-сочетанию соответствует
комбинация из к единиц и n – k нулей, и наоборот. Отсюда и следует, что число сочетаний
из n элементов по k совпадает с числом перестановок с повторениями из к элементов
одного вида (единиц) и
n – k элементов другого (нулей).
2 свойство – свойство симметричности
kn
n
k
n
CC
−
=
Доказательство.
k
n
kn
n
C
kkn
n
knnkn
n
C =
⋅−
=
−−⋅−
=
−
!)!(
!
))!(()!(
!
.
Комбинаторное доказательство
Если выбрать из n различных предметов некоторое k-сочетание, то останется
дополнительное (n – k)-сочетание, а дополнительным к (n – k)-сочетанию является исходное
k-сочетание. Таким образом, k-сочетание и (n – k) сочетание образуют взаимно
дополнительные пары, поэтому число этих сочетаний одно и то же.
3 свойство – основное свойство
k
n
k
n
k
n
CCC
1
1
1 −
−
−
+=
Доказательство.
k
n
k
n
k
n
C
knk
n
knk
nknnnk
knk
nkn
knk
nk
knk
n
knk
n
CC
=
−⋅
=
=
−⋅
−
⋅
−
−
⋅
+−⋅
=
−
−
⋅
−
+
−⋅
−
⋅
=
−−⋅
−
+
−⋅−
−
=+
−
−
−
)!(!
!
)!(!
)!1()!1()!1(
)!(!
)!1()(
)!(!
)!1(
)!1(!
)!1(
)!()!1(
)!1(
1
1
1
Страницы
- « первая
- ‹ предыдущая
- …
- 15
- 16
- 17
- 18
- 19
- …
- следующая ›
- последняя »
