Материал: Prak_alg
36
14.
В
некотором
государстве
не
было
двух
жителей
с
одинаковым
набором
зубов
.
Какова
наибольшая
численность
этого
государства
?
Ответ
:
2
32
.
15.
Абитуриенту
необходимо
сдать
4
экзамена
за
10
дней
.
Скольки
-
ми
способами
можно
составить
ему
расписание
,
если
в
один
день
можно
сдавать
только
один
экзамен
?
Ответ
:
10 9 8 7 5 040
´ ´ ´ =
.
16.
Четверо
студентов
сдают
экзамен
.
Сколькими
способами
могут
быть
поставлены
им
оценки
,
если
известно
,
что
никто
не
получил
оценки
«
неудовлетворительно
»?
Ответ
:
81.
17.
Сколько
словарей
надо
издать
,
чтобы
можно
было
выполнять
пе
-
реводы
с
любого
из
пяти
языков
на
любой
другой
из
этих
пяти
языков
?
На
сколько
больше
словарей
надо
издать
,
если
число
различных
языков
равно
10?
Ответ
:
20; 70.
18.
Сколько
существует
различных
пятизначных
чётных
чисел
,
ко
-
торые
начинаются
цифрой
«2»
и
оканчиваются
цифрой
«4»,
если
исполь
-
зуются
цифры
1, 2, 3, 4, 5?
Ответ
:
P
3
=3!.
19.
Сколько
различных
четырёхзначных
чисел
,
делящихся
на
4,
можно
составить
из
цифр
1, 2, 3, 4, 5?
Ответ
:
125.
20.
В
комнате
общежития
живут
трое
студентов
.
У
них
есть
4
раз
-
ные
чашки
, 5
разных
блюдец
и
6
разных
чайных
ложек
.
Сколькими
спо
-
собами
они
могут
накрыть
стол
для
чаепития
(
каждый
студент
получает
одну
чашку
,
одно
блюдце
и
одну
ложку
)?
Ответ
:
172 800.
37
Сочетания
без
повторений
и
с
повторениями
Сочетаниями
без
повторений
из
п
элементов
по
k
называются
не
-
упорядоченные
k-
выборки
из
п
элементов
без
повторений
.
Их
число
обо
-
значается
k
n
C
и
вычисляется
по
формуле
k
n
C
=
k)!
-
(n
k!
!
n
, k
£
n. (5)
Сочетания
из
n
по
k
без
повторений
образуют
k-
элементарные
под
-
множества
исходного
множества
мощности
n.
Числа
k
n
C
называются
би
-
номиальными
коэффициентами
.
Пример
11.
Сколькими
способами
можно
выбрать
три
различные
краски
из
имеющихся
пяти
?
Решение
.
Очевидно
,
что
нужно
подсчитать
число
3-
выборок
из
5
элементов
,
причем
по
условию
задачи
понятно
,
что
среди
выбранных
эле
-
ментов
не
должно
быть
одинаковых
и
что
порядок
расположения
выбранных
красок
не
существенен
.
Значит
,
нужно
найти
число
неупорядоченных
выбо
-
рок
,
т
.
е
.
число
сочетаний
без
повторений
из
5
по
3.
По
формуле
(5)
имеем
:
3
5
С
=
)!
3
5
(
!
3
!
5
-
= 5
´
!
2
4
= 10.
Сочетаниями
с
повторениями
из
п
элементов
по
k
называются
не
-
упорядоченные
k-
выборки
из
п
элементов
с
повторениями
.
Их
число
обо
-
значается
k
n
H
и
вычисляется
по
формуле
k
n
H
=
k
k
n
C
1
-
+
=
)!
1
(
!
)!
1
(
-
-
+
n
k
k
n
,
N
k
n
Î
"
,
. (6)
Пример
12.
В
киоске
имеются
открытки
10
видов
.
Сколькими
спосо
-
бами
можно
купить
:
а
) 5
открыток
?
б
) 5
разных
открыток
?
в
) 15
открыток
с
повторениями
?
Решение
.
В
случаях
а
)
и
в
)
нас
интересуют
неупорядоченные
выбор
-
ки
из
10
элементов
с
повторениями
длины
5
и
15
соответственно
.
Их
число
определяется
по
формуле
(6):
a)
5
10
H
=
5
10 5 1
C
+ -
=
5
14
C
=
)!
5
14
(
!
5
!
14
-
=
5!
10
11
12
13
14
´
´
´
´
=2002 (
способа
);
в
)
15
10
H
=
15
10 15 1
C
+ -
=
15
24
C
=
)!
15
24
(
!
15
!
24
-
=
!
9
!
15
!
24
(
способов
).
В
случае
б
)
нужно
подсчитать
число
неупорядоченных
5-
выборок
из
10
элементов
без
повторений
(
все
открытки
разные
).
Их
число
определяет
-
ся
по
формуле
(5) :
5
10
C
=
!
5
!
5
!
10
= 252 (
способа
).
38
ЗАДАЧИ
И
УПРАЖНЕНИЯ
21.
Из
20
студентов
надо
назначить
5
дежурных
.
Сколькими
спосо
-
бами
это
можно
сделать
?
Ответ
:
15 504.
22.
Сколькими
способами
можно
составить
бригаду
из
четырёх
плот
-
ников
,
если
имеются
предложения
от
10
человек
?
Ответ
:
210.
23.
Сколькими
способами
пять
девушек
и
трое
юношей
могут
раз
-
биться
на
две
команды
по
четыре
человека
в
команде
,
если
в
каждой
ко
-
манде
должно
быть
хотя
бы
по
одному
юноше
?
Ответ
:
3
5
3
C
´
.
24.
Сколькими
способами
можно
расселить
9
студентов
в
комнаты
,
каждая
из
которых
рассчитана
на
трёх
человек
?
Ответ
:
81.
25.
Сколькими
способами
можно
составить
набор
из
8
пирожных
,
если
имеется
4
сорта
пирожных
?
Ответ
:
!
3
!
8
!
11
.
26.
Сколько
различных
подмножеств
из
трех
элементов
имеет
мно
-
жество
А
={1, 2, 3, 4, 5};
В
={*, «,0, 1}?
Ответ
:
10; 4.
27.
Сколькими
способами
из
трех
спортивных
обществ
,
насчиты
-
вающих
соответственно
40, 40
и
60
человек
,
можно
выбрать
команды
по
5
человек
для
участия
в
соревнованиях
?
Ответ
:
5
60
5
40
5
40
C
C
C
´
´
.
28.
Из
группы
в
20
человек
каждую
ночь
выделяется
наряд
из
трех
человек
.
Сколько
существует
вариантов
составления
наряда
?
Ответ
:
1040.
39
29.
Из
группы
,
состоящей
из
7
мужчин
и
4
женщин
,
надо
выбрать
6
человек
так
,
чтобы
среди
них
было
не
менее
двух
женщин
.
Сколькими
способами
это
можно
сделать
?
Ответ
:
371.
30.
Сколькими
способами
можно
выбрать
12
человек
из
17,
если
дан
-
ные
двое
человек
из
этих
17
не
могут
быть
выбраны
вместе
?
Ответ
:
10
15
12
17
C
C
-
.
31.
Найти
натуральное
число
n,
удовлетворяющее
уравнению
5
n
C
=
5
1
2
-
n
C
.
Ответ
:
10
=
n
.
32.
Доказать
следующие
свойства
биномиальных
коэффициентов
:
а
)
k
n
C
=
k
n
n
C
-
(k=1…n);
б
)
k
n
C
=
1
1
-
-
k
n
C
+
k
n
C
1
-
;
в
)
k
n
C
´
k
m
k
n
C
-
-
=
k
m
C
´
m
n
C
;
г
)
å
=
n
k
0
k
n
C
=2
n
;
д
)
å
=
n
k
0
(-1)
k
k
n
C
=0;
е
)
å
=
n
k
0
k
n
C
2
=
å
=
n
k
0
1
2
+
k
n
C
.
Перестановки
.
Подсчет
числа
беспорядков
Перестановки
с
повторениями
.
Рассмотрим
задачу
:
Имеются
предметы
к
различных
видов
.
Сколько
различных
комбинаций
(
перестано
-
вок
)
можно
сделать
из
п
1
предметов
1-
го
вида
,
n
2
предметов
2-
го
вида
,...,
п
k
предметов
k-
го
вида
?
Число
предметов
в
каждой
перестановке
n=n
1
+n
2
+...+n
k
.
Такие
комбинации
называются
перестановками
с
повто
-
рениями
.
Их
число
обозначается
P(
n
1
,n
2
,...,n
k
)
и
вычисляется
по
формуле
Р
(
n
1
,n
2
,...,n
k
)
=
!
!...
!
!
2
1
k
n
n
n
n
(7)
Пример
13.
Сколькими
способами
можно
расположить
в
ряд
5
чер
-
ных
, 4
белых
и
3
красных
фишки
?
40
Решение
.
Эта
задача
на
перестановки
с
повторениями
.
Имеем
фишки
3-
х
различных
видов
:
чёрных
n
1
= 5,
белых
n
2
= 4
и
красных
n
3
= 3.
Всего
фи
-
шек
n = 12.
Следовательно
,
по
формуле
(7)
имеем
Р
(5,4,3) =
!
3
!
4
!
5
!
12
= 27 720
(
способов
).
Замечание
1.
Для
решения
данной
задачи
можно
было
применить
рассуждения
,
подобные
выводу
формулы
для
числа
сочетаний
:
Занумеру
-
ем
чёрные
фишки
числами
1, 2, 3, 4, 5;
белые
–
числами
6, 7, 8, 9;
крас
-
ные
–
числами
10, 11, 12.
Имеем
всего
12
предметов
,
которые
можно
рас
-
положить
в
ряд
12!
способами
.
Но
все
расположения
фишек
не
меняются
при
всех
перестановках
фишек
с
номерами
1–5 (
все
они
одного
вида
),
с
но
-
мерами
6–9
и
с
номерами
10–12.
Поэтому
число
различных
расположений
равно
!
3
!
4
!
5
!
12
.
Замечание
2.
Если
п
1
=
k
, n
2
= n –
k
,
то
имеем
P(k,n – k) =
.
k
n
C
Циклические
перестановки
.
Рассмотрим
задачу
:
Семь
девушек
во
-
дят
хоровод
.
Сколькими
различными
способами
они
могут
встать
в
круг
?
Решение
.
Если
бы
девушки
стояли
на
месте
,
то
получилось
бы
7!
способов
перестановок
в
ряду
.
Но
так
как
они
кружатся
,
то
их
положение
относительно
окружающих
предметов
несущественно
,
а
важно
только
их
взаимное
расположение
.
Поэтому
перестановки
,
переходящие
друг
в
друга
при
кружении
(
циклическом
сдвиге
),
нужно
считать
одинаковыми
.
Так
как
из
каждой
перестановки
циклическим
сдвигом
можно
получить
ещё
6
но
-
вых
,
то
количество
интересующих
нас
перестановок
(7!) : 7 = 6!.
Эту
задачу
можно
обобщить
так
.
Если
рассматривать
перестановки
n
предметов
,
расположенных
не
в
ряд
,
а
по
кругу
,
и
считать
одинаковыми
перестановки
,
переходящие
друг
в
друга
при
вращении
,
то
число
различ
-
ных
перестановок
(n–1)!.
Подсчёт
числа
беспорядков
.
Это
так
называемая
задача
«
о
числе
беспорядков
».
Число
N
перестановок
из
цифр
{1, 2, …, n}
таких
,
что
ни
-
какая
цифра
не
остаётся
на
своём
месте
,
можно
найти
по
следующей
фор
-
муле
:
N
= n!
å
=
-
n
k
k
k
0
!
1
)
1
(
.
(8)