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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

N
(2)
= N(a
1
, a
2
) =… = N(a
n-1
, a
n
), … , N
(k)
= N(a
1
, … , a
k
) =… = N(a
n-k+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% -
журналы А , В и С. Какой процент студентов: а ) не читает ни одного из
этих журналов? б) читает в точности два журнала ? в) читает только
один журнал В? Задачу решить двумя способами (с помощью формулы
(9) и кругов Эйлера ).
Ответ : а ) 20%; б) 60%.

Страницы