Четыре лекции по комбинаторике. Семенов А.С. - 14 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

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

Рубрика: 

16
= .
)!1(!
)!1(
)1()!()!1(
)1(!
1
k
n
C
knk
n
kknknk
nn
+
=
−+⋅
+
=
−+⋅−⋅−
+⋅
Следствие. Свойство (2) показывает, что биномиальные коэффициенты можно по-
следовательно выписывать в виде треугольной таблицы, которая называется тре-
угольником Паскаля:
1 n=1
1 2 1 n=2
1 3 3 1 n=3
1 4 6 4 1 n=4
1 5 10 10 5 1 n=5
. . . . . . . .
В −n ой строке треугольника Паскаля стоят коэффициенты разложения бинома
Ньютона, причем каждый коэффициент, кроме крайних двух, которые равны едини-
це, равен сумме двух его «охватывающих» коэффициентов из предыдущей строки.
Свойство 3.
∑
=
=
n
k
nk
n
C
0
.2
Это равенство было доказано в §5 под номером (14), а так же следует из (19) при
.1== ba
Свойство 4.
∑
=
=−=−+−+−
n
k
k
n
kn
n
n
nnn
CCCCC
0
210
.0)1()1(... (21)
Равенство (21) получается из формулы бинома Ньютона, если в ней положить
.1,1 −== ba
Свойство 5.
∑
+
−
=
−
−
=
1
1
1
.
rn
i
r
in
r
n
CC (22)
Доказательство. Рассмотрим все
−
r
элементные подмножества множества
},,...,{
1 n
aaA = т.е. множество .)(),(
r
nr
CBNAMB == Представим множество
B в виде ,
1
1
U
+−
=
=
rn
i
i
TB где −
i
T подмножество всех тех
−
r
элементных подмно-
жеств множества ,
A
в которых элемент с наименьшим индексом равен ;
i
a ясно,
что =
U
jk
TT Ø .
j
k
≠∀ Так как каждый элемент из
i
T может быть получен при-
соединением к
i
a некоторого
)1(
r
элементного подмножества множества
},,...,,{
21 nii
aaa
++
то .)(
1
−
−
=
r
ini
CTN Следовательно,
=)(
B
N
U
1
1
1
1
1
1
1
,)()(
+−
=
+−
=
+−
=
−
−
∑∑
==
rn
i
rn
i
rn
i
r
inii
CTNTN т.е. .
1
1
1
∑
+−
=
−
−
=
rn
i
r
in
r
n
CC
Свойство 5 доказано.
Свойство 6.
.
0
k
mn
k
i
ik
m
i
n
CCC
+
=
−
=⋅
∑
Доказательство. Запишем тождество .)1()1()1(
mnmn
xxx
+
+=+⋅+ Откуда, ис-
пользуя формулу бинома Ньютона, получаем

Страницы