Материал: Prak_alg
51
31.
Студенту
надо
сдать
4
зачёта
за
8
дней
.
Сколькими
способами
можно
это
сделать
?
А
если
последний
зачёт
обязательно
сдавать
на
вось
-
мой
день
?
Ответ
:
1680; 840.
32.
Сколькими
способами
можно
рассадить
n
гостей
за
круглый
стол
?
33.
На
собрании
должны
выступать
4
человека
А
,
В
,
С
,
Д
.
Скольки
-
ми
способами
их
можно
разместить
в
списке
ораторов
,
если
В
не
может
выступать
до
того
момента
,
пока
не
выступит
А
?
Ответ
:
3 3!
.
34.
Определить
число
всех
плохих
дней
,
если
12
дней
шел
дождь
,
8
дней
дул
ветер
, 4
дня
было
холодно
,
причем
5
дней
были
и
дождливы
,
и
ветрены
, 3
дня
дождливы
и
холодны
, 2
дня
ветреных
и
холодных
, 1
день
дождливый
,
ветреный
и
холодный
,
а
хороших
дней
не
было
за
данный
пе
-
риод
.
Ответ
:
15.
35.
Сколько
натуральных
чисел
в
n-
й
системе
счисления
можно
за
-
писать
k
знаками
?
Ответ
:
(
)
1
1
-
´
-
k
n
n
,
так
как
имеем
упорядоченные
k
-
выборки
с
по
-
вторениями
из
n
элементов
множества
{
}
1
...,
,
2
,
1
,
0
-
=
n
A
.
36.
Сколько
неудачных
попыток
может
быть
сделано
человеком
,
не
знающим
секретного
кода
,
составленного
из
5
цифр
и
подбирающего
его
наудачу
?
Ответ
:
1
5
10
-
A
,
так
как
имеем
упорядоченную
5-
выборку
с
повторе
-
ниями
из
10-
ти
элементов
,
из
них
одна
5-
выборка
удачная
,
ограничений
нет
.
37.
Сколько
имеется
пятизначных
чисел
,
которые
делятся
на
5?
Ответ
:
1 800.
38.
Сколько
пятизначных
чисел
,
у
которых
все
цифры
нечетные
?
Ответ
:
5
5 .
52
39.
Сколькими
способами
можно
сфотографировать
4
танкистов
, 4
летчиков
и
2
артиллеристов
,
поставив
их
в
один
ряд
так
,
чтобы
представи
-
тели
одного
рода
войск
стояли
рядом
?
Ответ
:
6 912.
40.
Сколько
различных
слов
получится
в
результате
перестановки
букв
в
слове
а
) «
математика
»,
б
) «
комбинаторика
»?
Ответ
:
(
)
2,3,2,1,1,1
151 200.
P
=
41.
Сколько
слов
можно
составить
из
12
букв
:
четырех
букв
«
а
» ,
че
-
тырех
букв
«
б
»,
двух
букв
«
в
»
и
двух
букв
«
г
»?
Ответ
:
(
)
4,4,2,2
207 900.
P
=
42.
Сколькими
способами
можно
распределить
n
предметов
среди
k
лиц
?
Ответ
:
.
k
n
Решение
:
Перенумеруем
все
k
предметов
.
Имеем
упорядоченную
k
-
выборку
из
множества
{
}
n
a
a
a
,...,
,
2
1
,
так
как
всего
n
лиц
,
среди
которых
распределяются
предметы
.
43.
Из
цифр
1, 2, 3, 4
составить
неупорядоченные
2-
выборки
с
повто
-
рениями
.
Сколько
всего
их
?
Перечислите
.
Ответ
:
10.
44.
Имеется
3
курицы
, 4
утки
и
2
гуся
.
Сколько
имеется
комбинаций
для
выбора
нескольких
птиц
так
,
чтобы
среди
выбранных
были
и
куры
,
и
гуси
,
и
утки
?
Ответ
:
315.
45.
Сколькими
способами
можно
сервировать
стол
на
четверых
че
-
ловек
,
если
имеется
6
разных
тарелок
,8
разных
вилок
и
7
разных
ножей
?
46.
Сколько
существует
всего
двузначных
чисел
,
составленных
из
цифр
0, 1, 2,..., 9?
Ответ
:
90.
53
47.
Сколько
неотрицательных
целых
чисел
,
меньших
миллиона
,
со
-
стоит
только
из
цифр
1, 2, 3, 4?
Ответ
:
2
2
-
-
-
m
n
m
n
C
C
.
48.
Сколько
существует
сочетаний
из
элементов
1,2,...,n
по
m
(2 < m < n),
которые
не
содержат
вместе
элементы
1
и
2?
49.
Определить
количество
способов
разбить
n
различных
предметов
на
k
различных
групп
,
при
котором
допускаются
пустые
группы
.
Ответ
:
n
k
.
50.
Определить
количество
способов
разбиения
n
различных
предме
-
тов
на
k
различных
групп
(
при
этом
существенен
порядок
элементов
в
группе
).
Ответ
:
1
1
-
-
+
k
k
n
A
.
51.
Определить
количество
способов
распределения
n
предметов
на
k
групп
:
чтобы
в
1-
й
группе
содержалось
n
1
предметов
,
во
второй
группе
– n
2
предметов
, …,
в
k-
й
группе
– n
k
предметов
;
порядок
групп
существенен
,
а
порядок
элементов
внутри
группы
не
играет
роли
.
Ответ
:
!
...
!
!
!
2
1
k
n
n
n
n
.
52.
Та
же
задача
,
но
порядок
групп
не
играет
роли
.
Ответ
:
!
...
!
!
!
!
2
1
k
n
n
n
k
n
.
53.
Распределить
n
предметов
на
k
групп
,
причём
все
группы
не
пустые
.
Ответ
:
1
1
-
-
k
n
C
.
54.
Определить
количество
способов
разбиения
n
одинаковых
пред
-
метов
на
k
групп
,
при
которых
допускаются
пустые
группы
.
Ответ
:
1
1
-
-
+
k
k
n
C
.
55.
Та
же
задача
,
но
каждая
группа
содержит
не
менее
r
предметов
.
Ответ
:
1
-
+
-
k
k
rk
n
C
.
54
3.
РЕКУРРЕНТНЫЕ
СООТНОШЕНИЯ
При
решении
многих
комбинаторных
задач
часто
пользуются
мето
-
дом
сведения
данной
задачи
к
задаче
,
касающейся
меньшего
числа
пред
-
метов
.
Метод
сведения
к
аналогичной
задаче
для
меньшего
числа
пред
-
метов
называется
методом
рекуррентных
соотношений
.
Пользуясь
рекуррентными
соотношениями
,
можно
свести
задачу
об
n
предметах
к
задаче
об
1
-
n
предметах
,
потом
к
задаче
об
2
-
n
предметах
и
т
.
д
.
После
-
довательно
уменьшая
число
предметов
,
доходим
до
задачи
,
которую
уже
легко
решить
.
В
книге
«Liber Abaci»
итальянский
математик
Фибоначчи
среди
мно
-
гих
других
задач
привел
следующую
:
пара
кроликов
приносит
раз
в
месяц
приплод
из
двух
крольчат
(
самки
и
самца
),
причем
новорожденные
крольчата
через
два
месяца
после
рождения
уже
приносят
приплод
.
Сколько
кроликов
появится
через
год
,
если
в
начале
года
была
одна
пара
кроликов
?
Из
условия
задачи
следует
,
что
через
месяц
будет
две
пары
кроликов
.
Через
два
месяца
приплод
даст
только
первая
пара
кроликов
,
и
получится
3
пары
.
А
еще
через
месяц
приплод
дадут
и
исходная
пара
,
и
пара
кроликов
,
появившаяся
два
месяца
тому
назад
.
Поэтому
всего
будет
5
пар
кроликов
.
Обозначим
через
)
n
(
F
количество
пар
кроликов
по
истечении
n
ме
-
сяцев
с
начала
года
.
Мы
видим
,
что
через
1
+
n
месяцев
будет
)
n
(
F
и
еще
столько
новорожденных
пар
кроликов
,
сколько
было
в
конце
месяца
1
-
n
,
то
есть
еще
)
n
(
F
1
-
пар
кроликов
.
Иными
словами
,
имеет
место
рекур
-
рентное
соотношение
).
n
(
F
)
n
(
F
)
n
(
F
1
1
-
+
=
+
Так
как
по
условию
1
0
=
)
(
F
и
2
1
=
)
(
F
,
то
последовательно
находим
8
4
5
3
3
2
=
=
=
)
(
F
,
)
(
F
,
)
(
F
и
т
.
д
.
Числа
)
n
(
F
называются
числами
Фибоначчи
.
3.1
Решение
рекуррентных
соотношений
Будем
говорить
,
что
рекуррентное
соотношение
имеет
порядок
k
,
если
оно
позволяет
выразить
(
)
k
n
f
+
через
( ) (
)
(
)
1
1
-
+
+
k
n
f
,
,
n
f
,
n
f
K
.
Например
,
(
)
( ) (
)
(
)
1
1
3
1
2
2
+
+
-
+
=
+
n
f
n
f
n
f
n
f
–
рекуррентное
соотношение
второго
порядка
,
а
(
)
( ) (
)
(
)
1
2
6
3
+
+
+
=
+
n
f
n
f
n
f
n
f
рекуррентное
соотношение
третьего
порядка
.
Если
задано
рекуррентное
соотношение
k
-
го
порядка
,
то
ему
удов
-
летворяет
бесконечно
много
последовательностей
.
Дело
в
том
,
что
первые
55
k
элементов
последовательности
можно
задать
совершенно
произвольно
–
между
ними
нет
никаких
соотношений
.
Но
если
первые
k
элементов
зада
-
ны
,
то
все
остальные
элементы
определяются
совершенно
однозначно
–
элемент
(
)
1
+
k
f
выражается
в
силу
рекуррентного
соотношения
через
( )
( )
k
f
,
,
f
K
1
,
элемент
(
)
2
+
k
f
–
через
( )
(
)
1
2
+
k
f
,
,
f
K
и
т
.
д
.
Будем
говорить
,
что
некоторая
последовательность
является
реше
-
нием
данного
рекуррентного
соотношения
,
если
при
подстановке
этой
по
-
следовательности
соотношение
тождественно
выполняется
.
Например
,
по
-
следовательность
K
K
,
,
,
,
,
n
2
8
4
2
является
одним
из
решений
рекуррентного
соотношения
(
)
(
)
( )
.
n
f
n
f
n
f
2
1
3
2
-
+
=
+
В
самом
деле
,
общий
член
этой
последовательности
имеет
вид
( )
n
n
f
2
=
.
Значит
,
(
)
(
)
.
n
f
,
n
f
n
n
1
2
2
1
2
2
+
+
=
+
=
+
Но
при
любом
n
имеет
место
тождество
.
n
n
n
2
2
2
3
2
1
2
×
-
×
=
+
+
Поэтому
n
2
является
решением
ука
-
занного
соотношения
.
Решение
рекуррентного
соотношения
k
-
го
порядка
называется
об
-
щим
,
если
оно
зависит
от
k
произвольных
постоянных
k
C
,
,
C
K
1
и
путем
подбора
этих
постоянных
можно
получить
любое
решение
данного
соот
-
ношения
.
Например
,
для
соотношения
(
)
(
)
( )
n
f
n
f
n
f
6
1
5
2
-
+
=
+
(1)
общим
решением
будет
( )
n
n
C
C
n
f
3
2
2
1
+
=
. (2)
В
самом
деле
,
легко
проверить
,
что
последовательность
обращает
соотношение
в
тождество
.
Поэтому
нам
надо
только
показать
,
что
любое
решение
нашего
соотношения
можно
представить
в
виде
(2).
Но
любое
решение
соотношения
(1)
однозначно
определяется
значениями
( )
1
f
и
( )
2
f
.
Пусть
( )
( )
1 = ,
2 =
f
a
f
b
.
Поэтому
нам
надо
доказать
,
что
для
любых
чисел
a
и
b
найдутся
такие
значения
1
C
и
2
C
,
что
a
C
C
=
+
2
1
3
2
и
b
C
C
=
+
2
2
1
2
3
2
.
Но
легко
видеть
,
что
при
любых
значениях
a
и
b
система
уравнений
î
í
ì
=
+
=
+
b
C
C
,
a
C
C
2
1
2
1
9
4
3
2
имеет
решение
.
Поэтому
(2)
действительно
является
общим
решение
соот
-
ношения
(1).