Дискретная математика. Элементы теории задачи и упражнения. Булгакова И.Н - 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%. 
           (2)                                                        (k)
       N         = N(a1 , a2) =…= N(an-1 , an), … , N                       = N(a1 , … , ak) =…= N(an-k+1,
… , an),
           (n)
       N         = N(a1, a2 , … , an ), N =N( a 1 , a 2,…, a n).
      Тогда формула (9) примет вид:
                         1          2
        N =N - C n N + Cn N -…+(-1)
                   (0)       (1)        (2)             n       C nn N(n),
или
                                               n
                                     N=       ∑      (-1)
                                                            k
                                                                C nk N(k)                          (10)
                                              k =0




      Очевидно, формула (10) есть частный случай формулы (9).

       Пример 15. Пусть имеется п карточек, пронумерованных от 1 до п.
Сколькими способами можно расположить их в ряду так, чтобы ни для ка-
кого i (1 ≤i ≤n) карточка с номером i не занимала бы i-ого места?
       Решение. Число всевозможных расположений (перестановок) n кар-
точек в ряд равно P n=n!=N(0). Обозначим через ai свойство: “i-ая карточка
занимает место с номером i (i = 1, 2, … , n)”. Тогда N(ai ) = N(1) = Pn – 1 = (n –
1)! – число перестановок всех карточек в ряду, кроме i-ой ,которая остаётся
на i-ом месте; N(ai, aj) = N(2) = Pn – 2 = (n – 2)! – число перестановок всех
карточек в ряду, кроме двух карточек с номерами i и j, остающихся на мес-
те, т. е. на i-ом и j-ом местах, и т. д. N(ai1, ai2, … , aik ) = N(k) = Pn-k = (n – k)! –
число расположений, при которых карточка с номером is занимает “своё”
место is (s = 1, k ). По формуле (10) получаем, что искомое число N равно
                                                 n!
                                                         (n −k )! =n! ∑ (−1)k 1
                     n               n                                   n
              N =∑ (−1) Cnk Pn −k =∑ (−1)
                          k               k

                   k =0            k =0     k ! (n −k )!               k =0      k!
       Заметим, что полученное число способов располагаться любой i-ой
карточки не на i-ом месте согласуется с формулой "числа беспорядков"
(см. (8) на стр. 41).


ЗАДАЧИ И УПРАЖНЕНИЯ

1. При обследовании читательских вкусов студентов оказалось, что 60%
   студентов читает журнал А, 50% - журнал В, 50% - журнал С, 30% -
   журналы А и В, 20% - журналы В и С, 40% - журналы А и С, 10% -
   журналы А, В и С. Какой процент студентов: а) не читает ни одного из
   этих журналов? б) читает в точности два журнала? в) читает только
   один журнал В? Задачу решить двумя способами (с помощью формулы
   (9) и кругов Эйлера).
                                                                            Ответ: а) 20%; б) 60%.

Страницы