Дискретная математика. Элементы теории, задачи и упражнения. Часть 1. Булгакова И.Н. - 43 стр.

UptoLike

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

43
Тогда имеем N = 70, N(a
1
) = 45, N(a
2
) = 29, N(a
1
,a
2
) = 9. Нужно найти число
N( a
1
, a
2
). По формуле (9) получаем
N( a
1
, a
2
) = N N(a
1
) N(a
2
) + N(a
1
,a
2
) = 70 45 29 + 9 = 5.
Предположим теперь, что число N(a
1
,a
2
,...,a
n
) зависит не от самых
этих свойств, а лишь от их числа.
Введём следующие обозначения : N
(0)
= N, N
(1)
= N(a
1
) =…= N(a
n
),
N
(2)
= N(a
1
, a
2
) == N(a
n-1
, a
n
), , N
(k)
= N(a
1
, , a
k
) =…= N(a
nk+1
, , a
n
),
N
(n)
= N(a
1
, a
2
, , a
n
), N =N( a
1
, a
2
,…, a
n
).
Тогда формула (9) примет вид:
N =N
(0)
1
n
C
N
(1)
+
2
n
C
N
(2)
+(1)
n
n
n
C
N
(n)
,
или
N =
å
=
n
k 0
(1)
k
k
n
C
N
(k)
(10)
Очевидно, формула (10) есть частный случай формулы (9).
Пример 15. Пусть имеется п карточек, пронумерованных от 1 до п.
Сколькими способами можно расположить их в ряду так, чтобы ни для ка-
кого i (1
£
i
£
n) карточка с номером i не занимала бы i-го места?
Решение. Число всевозможных расположений (перестановок) n карто-
чек в ряд равно P
n
= n! = N
(0)
. Обозначим через a
i
свойство: «i-я карточка за-
нимает место с номером i (i = 1, 2, , n)». Тогда N(a
i
) = N
(1)
= P
n 1
= (n 1)!
число перестановок всех карточек в ряду, кроме i-й, которая остаётся на i-м
месте; N(a
i
, a
j
) = N
(2)
= P
n 2
= (n 2)! число перестановок всех карточек в
ряду, кроме двух карточек с номерами i и j, остающихся на месте, т. е. на
i-м и j-м местах, и т. д. N(a
i1
, a
i2
, , a
ik
) = N
(k)
= P
n–k
= (n k)! число рас-
положений, при которых карточка с номером i
s
занимает «своё» место
i
s
(s = k,1 ). По формуле (10) получаем, что искомое число N равно
( ) ( )
( )
( ) ( )
ååå
==
-
=
-=-
-
-=-=
n
k
k
n
k
k
kn
n
k
k
n
k
k
nkn
knk
n
PCN
000
1
111
!
!!
!!
!
Заметим, что полученное число способов располагаться любой i-й
карточки не на i-м месте согласуется с формулой «числа беспорядков»
(см. (8) на стр. 41).
ЗАДАЧИ И УПРАЖНЕНИЯ
1. При обследовании читательских вкусов студентов оказалось, что
60 % студентов читает журнал А, 50 % журнал В, 50 % журнал С,
30 % журналы А и В, 20 % журналы В и С, 40 % журналы А и С,
10 % журналы А, В и С. Какой процент студентов: а) не читает ни одного