Дискретная математика. Азарнова Т.В - 35 стр.

UptoLike

Комбинаторика
35
Решение. Обозначим количество студентов в данной группе
Ν
ΝΝ
Ν
и
введем три свойства для студентов данной группы:
1
α
- знать английский
язык,
2
α
- знать французский язык,
3
α
- знать немецкий язык. Тогда
()
,15
1
=
αΝ
ΝΝ
Ν
()
,10
2
=
αΝ
ΝΝ
Ν
()
,6
3
=
αΝ
ΝΝ
Ν
()
,5,
21
=
ααΝ
ΝΝ
Ν
()
,3,
31
=
ααΝ
ΝΝ
Ν
()
,3,
32
=
ααΝ
ΝΝ
Ν
()
2,,
321
=
αααΝ
ΝΝ
Ν
. По формуле включений и исключений
находим число студентов в данной группе
0
Ν
ΝΝ
Ν
, которые не знают ни одного
языка
() () () ( ) ( ) ( )
+++=
3231213210
,,,
αααααααααΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
ΝΝ
Ν
()
823356101530,,
321
=+++=
αααΝ
ΝΝ
Ν
.
Задача 2.
Найти количество трехзначных чисел, в которых сумма цифр
равняется 20.
Решение
.
Обозначим через
321
,,
xxx
соответственно первую, вторую и
третью цифры в произвольном трехзначном числе
32
2
1
1010
xxxa
++=
.
Наша задача состоит в нахождении количества целочисленных наборов
()
321
,,
xxx
, для которых
20
321
=++
xxx
,
90,90,91
321
xxx
.
Обозначим через
Χ
ΧΧ
Χ
множество наборов
()
321
,,
xxx
, у которых
20
321
=++
xxx
,
0,0,1
321
xxx
,
и для элементов данного множества введем три свойства:
1
α
-
10
1
x
,
2
α
-
10
2
x
,
3
α
-
10
3
x
. Таким образом, в задаче требуется найти множество
наборов, для которых не выполнено ни одно из этих свойств.
Вначале найдем количество элементов
Ν
ΝΝ
Ν
в множестве
Χ
ΧΧ
Χ
. Если
ввести переменные
332211
,,1
xyxyxy
===
, то число элементов в
множестве
Χ
ΧΧ
Χ
можно найти как число целочисленных наборов
()
321
,,
yyy
таких, что
19
321
=++
yyy
,
0,0,0
321
yyy
.
Число таких наборов находится по формуле для числа сочетаний с
повторениями из 3 по 19, т.е.
2102110
!2!19
!21
19
1319
19
3
=====
+
CC
Ν
ΝΝ
Ν
.
Число
()
1
αΝ
ΝΝ
Ν
совпадает с числом наборов
()
321
,,
xxx
, для которых
20
321
=++
xxx
,
0,0,10
321
xxx
,
число
()
2
αΝ
ΝΝ
Ν
- с числом наборов
()
321
,,
xxx
, для которых
                                            35
Комбинаторика
       Решение. Обозначим количество студентов в данной группе Ν и
введем три свойства для студентов данной группы: α1 - знать английский
язык, α 2 - знать французский язык, α 3 - знать немецкий язык. Тогда
Ν (α1 ) =15,           Ν (α 2 ) =10,        Ν (α 3 ) =6, Ν (α1 , α 2 ) =5, Ν (α1 , α 3 ) =3,
Ν (α 2 , α 3 ) =3, Ν (α1 , α 2 , α 3 ) =2 . По формуле включений и исключений
находим число студентов в данной группе Ν 0 , которые не знают ни одного
языка
Ν 0 =Ν −Ν (α1 ) −Ν (α 2 ) −Ν (α 3 ) +Ν (α1 , α 2 ) +Ν (α1 , α 3 ) +Ν (α 2 , α 3 ) −
−Ν (α1 , α 2 , α 3 ) =30 −15 −10 −6 +5 +3 +3 −2 =8 .

         Задача 2. Найти количество трехзначных чисел, в которых сумма цифр
равняется 20.
         Решение. Обозначим через x1 , x 2 , x 3 соответственно первую, вторую и
третью цифры в произвольном трехзначном числе
                                  a = x1 ⋅10 2 +x 2 ⋅10 +x 3 .
Наша задача состоит в нахождении количества целочисленных наборов
(x1 , x 2 , x3 ), для которых
                                      x1 +x 2 +x 3 =20 ,
                           1 ≤ x1 ≤9, 0 ≤ x 2 ≤9, 0 ≤ x 3 ≤9 .
Обозначим через Χ множество наборов (x1 , x 2 , x 3 ), у которых
                                      x1 +x 2 +x 3 =20 ,
                                  x1 ≥1, x 2 ≥0, x3 ≥0 ,
и для элементов данного множества введем три свойства: α1 - x1 ≥10 , α 2 -
x 2 ≥10 , α 3 - x 3 ≥10 . Таким образом, в задаче требуется найти множество
наборов, для которых не выполнено ни одно из этих свойств.
           Вначале найдем количество элементов Ν в множестве Χ . Если
ввести переменные y1 = x1 −1, y 2 = x 2 , y 3 = x3 , то число элементов в
множестве Χ можно найти как число целочисленных наборов (y1 , y 2 , y 3 )
таких, что
                                      y1 +y 2 +y 3 =19 ,
                                 y1 ≥0, y 2 ≥0, y 3 ≥0 .
Число таких наборов находится по формуле для числа сочетаний с
повторениями из 3 по 19, т.е.
                                19      19       21!
                          Ν =C 3 =C19     +3−1 =      =10 ⋅ 21 =210 .
                                                19!2!
Число Ν (α1 ) совпадает с числом наборов (x1 , x 2 , x 3 ), для которых
                                      x1 +x 2 +x 3 =20 ,
                                 x1 ≥10, x 2 ≥0, x3 ≥0 ,
число Ν (α 2 ) - с числом наборов (x1 , x 2 , x 3 ), для которых