Дискретная математика. Комбинаторика. Соколова С.В. - 17 стр.

UptoLike

ВУЗ: 

ТПУ | Томск

Составители: 

Рубрика: 

17
Свойство
Паскаля
1
1 1
k k k
n n n
C C C
−
− −
= + .
Пусть
{
1 2
, ,...,
n
X x x x
=
.
Число
k
n
C
−
это
количество
подмножеств
из
k
элементов
множества
Х
.
Разделим
все
подмножества
на
два
класса
:
1)
подмножества
,
не
содержащие
элемент
1
,
x
−
их
будет
1
k
n
C
−
;
2)
подмножества
,
содержащие
элемент
1
,
x
−
их
будет
1
1
k
n
C
−
−
.
Т
.
к
.
эти
классы
не
пересекаются
,
то
по
правилу
суммы
количество
всех
k
-
элементных
подмножеств
множества
X
будет
равно
1
1 1
k k
n n
C C
−
− −
+ .
На
этом
свойстве
основано
построение
треугольника
Паскаля
(
рис
. 2.2),
в
n
-
ой
строке
которого
стоят
коэффициенты
разложения
бинома
(
)
n
a b
+ .
0
n
=
1
1
n
=
1 1
2
n
=
1 2 1
3
n
=
1 3 3 1
4
n
=
1 4 6 4 1
...
… … … … …
Рис. 1. Треугольник Паскаля
Свойство суммы
0 1 2
... 2
n n
n n n n
C C C C
+ + + + =
.
Подставим
в
формулу
бинома
Ньютона
( )
0
n
n
k k n k
n
k
a b C a b
−
=
+ =
∑
значения
1, 1
a b
= =
.
Получим
0 0
2 1 1
n n
n k k n k k
n n
k k
C C
−
= =
= =
∑ ∑
.
Заметим
,
что
с
точки
зрения
теории
множеств
сумма
0 1
...
n
n n n
C C C
+ + +
выражает
количество
всех
подмножеств
n
-
элементного
множества
.
По
теореме
о
мощности
булеана
это
количество
равно
2
n
.

Страницы