ВУЗ:
Составители:
Рубрика:
свойств, некоторые из которых сформулированы в следующих
теоремах.
Теорема 2.5.
1
0
2.
n
rn
n
r
rC n
−
=
=
∑
Доказательство.
Рассмотрим следующую последовательность из чисел 1,…,n.
Сначала все подмножества длины 0, потом все подмножества дли-
ны 1 и т.д. Имеется подмножеств мощности n, и каждое из них
имеет длину n. Таким образом, всего в этой последовательности
чисел. С другой стороны, каждое число x входит в эту по-
следовательность
r
n
C
0
n
r
n
r
rC
=
∑
1n
xn1
22
−
=
}{\},...,{
раз, а всего чисел n.
9
Теорема 2.6.
C
0
.
k
kiki
nr n r
i
CC
−
+
=
=⋅
∑
Доказательство.
k
nr
C
+
⋅
– это число способов выбрать k предметов из n+r предме-
тов. Предметы можно выбирать в два приема: сначала выбрать i
предметов из первых n предметов, а затем выбрать остальные k-i
предметов из оставшихся r предметов.
Треугольник Паскаля
Из теоремы 2.2 следует способ вычисления биномиальных ко-
эффициентов, известный как треугольник Паскаля.
1
11
121
1331
14641
⋅⋅⋅⋅⋅
Рисунок 3. Треугольник Паскаля.
В этом треугольнике каждое число (кроме единиц на боковых
сторонах) является суммой двух чисел, стоящих над ним. Число
сочетаний находится в (n+1)-м ряду на (r+1)-м месте.
r
n
C
Страницы
- « первая
- ‹ предыдущая
- …
- 7
- 8
- 9
- 10
- 11
- …
- следующая ›
- последняя »
