Дискретная математика. Элементы теории, задачи и упражнения. Часть 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
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 % – журналы А, В и С. Какой процент студентов: а) не читает ни одного 
Тогда имеем N = 70, N(a1) = 45, N(a2) = 29, N(a1,a2) = 9. Нужно найти число
N( a 1, a 2). По формуле (9) получаем
              N( a 1 , a 2) = N – N(a1) – N(a2) + N(a1,a2) = 70 – 45 – 29 + 9 = 5.
        Предположим теперь, что число N(a1,a2,...,an) зависит не от самых
этих свойств, а лишь от их числа.
        Введём следующие обозначения : N(0) = N, N(1) = N(a1) =…= N(an),
        N(2) = N(a1, a2) =…= N(an-1, an), … , N(k) = N(a1, … , ak) =…= N(an–k+1, … , an),
        N(n) = N(a1, a2, …, an), N =N( a 1, a 2,…, a n).
        Тогда формула (9) примет вид:
       N =N
             (0)       1
                   – C n N(1) +   Cn2 N(2) –…+(–1)n C nn N(n),
или
                                                 n             k
                                          N=    �      (–1)k C n N(k)               (10)
                                                k �0



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

        Пример 15. Пусть имеется п карточек, пронумерованных от 1 до п.
Сколькими способами можно расположить их в ряду так, чтобы ни для ка-
кого i (1 � i � n) карточка с номером i не занимала бы i-го места?
        Решение. Число всевозможных расположений (перестановок) n карто-
чек в ряд равно Pn = 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 % – журналы А, В и С. Какой процент студентов: а) не читает ни одного

                                               43

Страницы