Дискретная математика. Азарнова Т.В - 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
, для которых