Лекции по дискретной математике. Ч.II. Комбинаторика, разостные уравнения, алгоритмы на графах. Гайдамака Ю.В - 5 стр.

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

Лемма 1.1.
r
n
rn
n
1rn1nnrnP )(
)!(
!
))...((),(
Δ
=
−
=+−−=
.
Доказательство. 1-й элемент выбираем из всех n, 2-й – из (n-1)
оставшихся и т.д. r -й выбираем из (n-r+1) элементов.
Следствие. P(n,n)=n! - число различных перестановок всех эле-
ментов A.
r
nrnP =),(
ˆ
. Лемма 1.2.
Доказательство. Каждый из r элементов выбираем из всех n
элементов.
5
Лемма 1.3.
()
!
!( )!!
r
r
n
n
n
rnrr
==
−
C .
Доказательство: Все перестановки можно разбить на группы, в
каждой из которых перестановки отличаются только порядком
элементов. Число перестановок в каждой группе есть r!. Следова-
тельно
()
!
!( )!
r
r
n
n
n
C
rnr
==
− !r
.
Лемма 1.4.
CC
.
1
1
ˆ
rn
nnr
−
+−
=
Доказательство: Каждому сочетанию с повторением можно по-
ставить в соответствие вектор )
,( rnx
длины (n+r-1) из r нулей и
(n-1) единицы такой, что число нулей между (i-1)-ой и i-ой едини-
цей равно числу элементов a
i
из A в сочетании с повторением.
Пример 1.2. A={a,b,c,d,e}, r=4.
)(
)(
01100110xacce
00101011xaabc
=↔
=
↔
Построенное соответствие является взаимно однозначным. Ко-
личество векторов с указанными свойствами равно числу способов
расположения r нулей на (n+r-1) месте, т.е.
1
r
nr
C
+
−
. По свойству
kn
nn
CC
k
−
=
, для числа сочетаний с повторениями верна формула
.
1
11
rn
nr nr
CC
−
+− +−
=
Лекция 2. Биномиальные коэффициенты. Бином Ньютона.
Треугольник Паскаля.
Биномиальные коэффициенты
По определению число сочетаний – это число различных r-
r
n
C

Страницы