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

UptoLike

ВУЗ: 

РУДН | Москва

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

Рубрика: 

элементных подмножеств n-элементного множества. Числа
встречаются в формулах решения многих комбинаторных задач.
r
n
C
Основная формула для числа сочетаний
!
()!
r
n
n
C
nrr
=
− !
.
позволяет получить ряд простых тождеств. Рассмотрим некоторые
из них.
6
Теорема 2.1.
C
rnr
nn
C
−
=
.
Доказательство.
!!
()!(())!()!!
nr r
nn
nn
CC
nr n nr nrr
−
=
==
−−− −
.
1
11
rr r
nn n
CCC
−
Теорема 2.2.
−
−
=+
.
Доказательство.
1
11
(1)! (1)!
!( 1)! ( 1)!( 1 ( 1))!
(1)! (1)!
( 1)!( 1)! ( 1)!( )( 1)!
( )(1)!(1)!( )(1)!
( 1)!( )( 1)! !( )!
!
.
!( )!
rr
nn
r
n
CC
nn
rn r r n r
nn
rnr rnrnr
nrn rn nrrn
rr nrnr rnr
n
C
rn r
−
−−
+=
−−
=+ =
−− − −− −
−−
=+ =
−−− −−−−
−−+− −+−
===
−−−− −
==
−
Теорема 2.3.
ir ri
ni n nr
CC CC
r
−
−
⋅=⋅
.
Доказательство.
!! !
!( )! !( )! !( )!( )!
!( )! ! ( )!
!( )!( )!( )! !( )! ( )!( )!
.
ir
ni
rir
nnr
CC
ni n
in i ri r ri r n i
nn r n n r
ri r n i n r rn r i r n i
CC
−
−
⋅=
=⋅= =
−− −−
−−
==⋅=
−−− − −−
=⋅

Страницы