ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.04.2021
Просмотров: 615
Скачиваний: 1
41
ЗАДАЧИ
И
УПРАЖНЕНИЯ
33.
Сколькими
способами
можно
расставить
белые
фигуры
(2
коня
,
2
слона
, 2
ладьи
,
ферзя
и
короля
)
на
первой
линии
шахматной
доски
?
Ответ
:
5 040.
34.
Четыре
автора
должны
написать
книгу
из
17
глав
,
причём
первый
и
третий
должны
написать
по
5
глав
,
второй
– 4
главы
,
а
четвёртый
– 3
главы
книги
.
Сколькими
способами
можно
распределить
главы
между
авторами
?
Ответ
:
!
3
!
4
!
5
!
5
!
17
.
35.
Сколько
существует
перестановок
элементов
1, 2
,
...,n ,
в
которых
элемент
1
находится
не
на
своём
месте
?
Ответ
:
(
)(
)
1
1
n
n
-
-
!
36.
Сколько
ожерелий
можно
составить
из
семи
бусинок
разных
раз
-
меров
?
Ответ
:
300.
37.
Сколько
различных
браслетов
можно
сделать
из
четырёх
одина
-
ковых
рубинов
,
пяти
одинаковых
сапфиров
и
шести
одинаковых
изумру
-
дов
,
если
в
браслете
должны
быть
все
15
камней
?
Сколькими
способами
можно
из
этих
камней
выбрать
три
камня
для
кольца
?
Ответ
:
(
)
30
6
,
5
,
4
P
;
10
1
2
3
1
3
=
+
+
C
.
38.
Сколькими
способами
можно
разбить
(
п
+
т
+
р
)
предметов
на
три
группы
так
,
чтобы
в
одной
было
п
,
в
другой
т
,
а
в
третьей
р
предметов
?
Ответ
:
(
)
!
p
!
m
!
n
!
p
m
n
+
+
.
39.
Сколькими
способами
можно
переставить
буквы
в
слове
а
) «
космос
?»
б
) «
тартар
»?
Ответ
:
а
) 180;
б
) 90.
40.
Сколькими
способами
можно
переставить
цифры
числа
а
) 12 341 234?
б
) 12 345 234?
Ответ
:
а
)
!
5
21
´
;
б
) P(1,2,2,2,1).
42
41.
Сколько
существует
вариантов
того
,
что
три
человека
,
сдавшие
свои
шляпы
в
гардероб
,
не
получат
в
точности
свою
шляпу
?
Ответ
:
2
=
N
.
42.
Четыре
человека
сдают
свои
шляпы
в
гардероб
.
Предполагая
,
что
шляпы
возвращаются
наугад
,
найти
число
случаев
и
вероятность
того
,
что
в
точности
k
человек
получат
свои
шляпы
.
Рассмотреть
все
значения
k (k = 0, 1, 2, 3, 4 ).
Ответ
:
Имеем
9, 8, 6, 0, 1
случаев
с
вероятностями
3 1 1
1
, , , 0,
8 3 4
24
соответственно
.
Замечание
.
Вероятность
равна
числу
Р
(
А
)
=
n
m
,
где
n –
общее
число
комбинаций
,
т
–
число
«
благоприятных
»
комбинаций
.
2.3
Формула
включений
и
исключений
Пусть
имеется
N
предметов
и
п
свойств
a
1
, a
2
, …, a
n
.
Каждый
из
рас
-
сматриваемых
предметов
может
обладать
одним
или
несколькими
из
этих
n
свойств
.
Обозначим
через
N(
a
i1
, a
i2
, …, a
is
)
число
предметов
,
обладающих
свойствами
a
i1
, a
i2
, … , a
is
(
и
,
быть
может
,
некоторыми
другими
),
а
через
N(
a
1
,
a
2
,…,
a
n
)
–
число
предметов
,
не
обладающих
свойствами
a
i1
, a
i2
, …, a
is
.
Например
, N(
a
1
, a
3
,
a
4
) –
число
предметов
,
обладающих
свойствами
a
1
,
a
3
,
но
не
обладающих
свойством
a
4
.
Справедлива
формула
N(
a
1
,
a
2
,…,
a
n
) = N – N(
a
1
) – N(
a
2
) – …– N(
a
n
) + N(
a
1
, a
2
) +
+ N(
a
1
, a
3
) +…+ N(
a
1
, a
n
) +…+ N(
a
n–1
, a
n
) – N(
a
1
, a
2
, a
3
) –…– (9)
– N(
a
n–2
, a
–1
, a
n
) +…+ (–1)
n
N(
a
1
, a
2
, … , a
n
).
Формула
(9)
н
a
зыв
ae
т
c
я
формулой
включений
и
исключений
.
Здесь
слагаемые
включают
все
комбинации
свойств
a
1
,a
2
,…,a
n
без
учёта
их
по
-
рядка
;
знак
«+»
ставится
,
если
число
учитываемых
свойств
чётно
,
и
знак
« – »,
если
это
число
нечётно
.
Пример
14.
В
результате
опроса
70
студентов
выяснилось
,
что
45
из
них
занимаются
спортом
, 29 –
музыкой
, 9 –
и
спортом
,
и
музыкой
.
Сколько
студентов
из
числа
опрошенных
не
занимаются
ни
спортом
,
ни
музыкой
.
Решение
.
Чтобы
применить
формулу
(9),
обозначим
через
a
1
(
a
2
) –
свойство
студента
,
состоящее
в
том
,
что
он
занимается
спортом
(
музыкой
).
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
k
n
n
k
k
n
k
k
n
k
n
k
n
k
n
P
C
N
0
0
0
1
1
1
1
!
!
!
!
!
!
Заметим
,
что
полученное
число
способов
располагаться
любой
i-
й
карточки
не
на
i-
м
месте
согласуется
с
формулой
«
числа
беспорядков
»
(
см
. (8)
на
стр
. 41).
ЗАДАЧИ
И
УПРАЖНЕНИЯ
1.
При
обследовании
читательских
вкусов
студентов
оказалось
,
что
60 %
студентов
читает
журнал
А
, 50 % –
журнал
В
, 50 % –
журнал
С
,
30 % –
журналы
А
и
В
, 20 % –
журналы
В
и
С
, 40 % –
журналы
А
и
С
,
10 % –
журналы
А
,
В
и
С
.
Какой
процент
студентов
:
а
)
не
читает
ни
одного
44
из
этих
журналов
?
б
)
читает
в
точности
два
журнала
?
в
)
читает
только
один
журнал
В
?
Задачу
решить
двумя
способами
(
с
помощью
формулы
(9)
и
кругов
Эйлера
).
Ответ
:
а
) 20 %;
б
) 60 %.
2.
При
опросе
13
человек
,
каждый
из
которых
знает
по
крайней
мере
один
иностранный
язык
,
выяснилось
,
что
10
человек
знают
английский
язык
, 7 –
немецкий
, 6 –
испанский
, 5 –
английский
и
немецкий
, 4 –
англий
-
ский
и
испанский
, 3 –
немецкий
и
испанский
.
Сколько
человек
знают
:
а
)
все
три
языка
?
б
)
ровно
два
языка
?
в
)
только
английский
язык
?
Ответ
:
2, 6, 3.
3.
На
экскурсию
поехало
92
человека
.
Бутерброды
с
колбасой
взяли
47
человек
,
с
сыром
– 38
человек
;
с
ветчиной
– 42
человека
;
и
с
сыром
,
и
с
колбасой
– 28
человек
;
и
с
колбасой
,
и
с
ветчиной
– 31
человек
;
и
с
сыром
,
и
с
ветчиной
– 26
человек
.
Все
три
вида
бутербродов
взяли
25
человек
.
Не
-
сколько
человек
вместо
бутербродов
взяли
пирожки
.
Сколько
человек
взя
-
ли
с
собой
пирожки
?
Ответ
:
25
человек
.
4.
Найти
количество
натуральных
чисел
,
не
превосходящих
1000
и
не
делящихся
ни
на
одно
из
чисел
3, 5
и
7?
Ответ
:
457.
5.
Найти
количество
натуральных
чисел
,
не
превосходящих
1000
и
не
делящихся
ни
на
одно
из
чисел
6, 15
и
10?
Ответ
:
734.
6.
Показать
,
что
если
п
= 30
т
,
то
количество
натуральных
чисел
,
не
превосходящих
п
и
не
делящихся
ни
на
одно
из
чисел
6, 10
и
15,
равно
22m.
7.
Сколько
неотрицательных
целых
чисел
,
меньших
миллиона
,
со
-
стоит
только
из
цифр
1, 2, 3, 4?
2.4
Задачи
с
ограничениями
Рассмотрим
в
данном
параграфе
комбинаторные
задачи
сначала
с
ог
-
раничениями
на
порядок
элементов
,
когда
на
порядок
элементов
накла
-
дываются
некоторые
дополнительные
условия
.
В
таких
задачах
удобно
45
применять
метод
–
объединение
нескольких
одинаковых
элементов
в
блоки
.
Далее
рассмотрим
задачи
на
разбиения
,
где
требуется
разделить
элементы
на
две
или
более
групп
в
соответствии
с
некоторыми
условиями
,
и
требуется
найти
число
всевозможных
различных
способов
раздела
.
При
этом
необходимо
учитывать
,
существенен
ли
порядок
элементов
в
группах
,
различаем
ли
мы
элементы
,
входящие
в
группы
,
и
сами
группы
и
т
.
д
.
При
решении
этих
задач
обычно
элементы
располагают
в
ряд
и
применяют
так
называемый
метод
введения
перегородок
.
Пример
16.
Имеются
предметы
k
сортов
: n
1
предметов
одного
сорта
,
n
2
предметов
другого
сорта
, … , n
k
предметов
k-
го
сорта
,
где
все
предметы
одного
сорта
всё
же
различны
друг
от
друга
.
Найти
число
перестановок
этих
предметов
,
в
которых
все
предметы
одного
и
того
же
сорта
стоят
ря
-
дом
.
Решение
.
Из
данных
k
сортов
(
блоков
)
можно
сделать
P
k
= k!
пере
-
становок
.
Но
ещё
можно
переставлять
предметы
внутри
блоков
n
1
!, n
2
!, … ,
n
k
!
способами
.
Далее
по
правилу
произведения
имеем
n
1
!n
2
!…n
k
!k!
пере
-
становок
.
Пример
17.
Сколькими
способами
можно
переставить
буквы
слова
«
перемет
»
так
,
чтобы
три
буквы
«
е
»
не
шли
подряд
?
Решение
.
Объединим
все
буквы
«
е
»
в
блок
«
еее
».
Число
перестано
-
вок
,
в
которых
все
три
буквы
«
е
»
идут
подряд
,
равно
числу
перестановок
из
5-
ти
объектов
: «
еее
», «
п
», «
м
», «
р
», «
т
»,
т
.
е
. P
5
= 5!
Всего
же
переста
-
новок
с
повторениями
из
букв
данного
слова
можно
составить
P(3,1,1,1,1) = 840.
Значит
,
искомое
число
перестановок
,
где
три
буквы
«
е
»
не
идут
рядом
равно
N = 840 – 120 = 720 (
способов
).
Пример
18.
Сколькими
способами
можно
расставить
m
нулей
и
k
единиц
так
,
чтобы
никакие
две
единицы
не
стояли
рядом
?
Решение
.
Выпишем
сначала
m
нулей
.
Для
единиц
получается
(m + 1)
место
(
одно
впереди
, (m – 1)
в
промежутках
между
нулями
и
одно
сзади
).
На
любые
из
этих
(m + 1)
мест
можно
поставить
одну
из
k
единиц
.
Это
можно
осуществить
1
k
m
C
+
способами
,
причём
k
£
m + 1.
Пример
19.
На
полке
стоят
12
книг
.
Сколькими
способами
можно
выбрать
из
них
5
книг
так
,
чтобы
никакие
две
из
них
не
стояли
рядом
?
Решение
.
Зашифруем
каждый
выбор
книг
последовательностью
из
нулей
и
единиц
следующим
образом
:
каждой
оставленной
книге
сопоста
-
вим
0,
а
каждой
взятой
– 1.
В
результате
получим
последовательность
из
5
единиц
и
7
нулей
,
причём
в
последовательности
не
будет
двух
подряд