ВУЗ:
Составители:
Рубрика:
какой вклад он дает в правую часть равенства (4.1).
В первом слагаемом он учитывается 1 раз. Во втором слагае-
мом он учитывается
1
3
3C
=
раза (т.к. N
1
= 1, N
2
= 1, N
4
= 1). В
третьем слагаемом он учитывается
2
3
3C
=
раза (т.к. N
12
= 1, N
14
=
1, N
24
= 1). В четвертом слагаемом он учитывается
3
3
1C
=
раз (т.к.
N
124
=1). В пятом (последнем для рассматриваемого примера) сла-
гаемом он учитывается 0 раз (т.к. N
1234
= 0).
Таким образом, вклад рассматриваемого шара в правую часть
равенства (4.1) равен 1 – 3 + 3 – 1 + 0 = 0.
Замечание.
Формула (4.1) называется формулой включений и
исключений.
Пример 4.2.
(задача о беспорядках).
Определить количество перестановок a
1
,…,a
n
, чисел 1,…,n та-
ких, что
n1iia
i
,, =≠ .
Решение. Число всех перестановок N=n!
Свойство
n1iias
ii
,,: == .
r1
ii
N
,...,
- число перестановок, оставляющих на месте по крайней
мере числа , следовательно,
r1
ii ,...,
)!(
,...,
rnN
r1
ii
−
=
В имеется слагаемых – количество способов
выбора чисел i
∑
<<
r1
r1
ii
ii
N
...
,...,
r
n
C
1
,…,i
r
из 1,…,n. Итак, на основании (4.1):
12
0
2
! ( 1)! ( 2)! ... ( 1) ( )! ...
11
( 1) 0! !(1 1 ... ( 1) ... ( 1) )
2! ! !
1
!(1)
!
rr
nn n
nn r n
n
n
r
r
NnCn Cn Cnr
Cn
rn
n
r
=
=− −+ − ++− − +
+− = − + + + − + + − =
=−
∑
1
≥
Лемма 4.2 (вспомогательная)
(1) 0, , ,
n
kr k r
nk
kr
CC nr N n r
−
=
−=∀∈
∑
(4.2)
Доказательство.
Рассмотрим тождество
0
(1 )
n
nk
n
k
k
x
Cx
=
+=
∑
(4.3)
15
Страницы
- « первая
- ‹ предыдущая
- …
- 13
- 14
- 15
- 16
- 17
- …
- следующая ›
- последняя »
