Материал: Prak_alg
31
13.
На
ферме
есть
20
овец
и
24
козы
.
Сколькими
способами
можно
выбрать
одну
овцу
и
одну
козу
?
Если
такой
выбор
уже
сделан
,
сколькими
способами
можно
сделать
его
еще
раз
?
Ответ
:
480, 437.
14.
Сколькими
способами
можно
выбрать
по
одному
экземпляру
ка
-
ждого
учебника
,
если
имеется
3
экземпляра
учебника
алгебры
, 7
экзем
-
пляров
учебника
геометрии
и
10
экземпляров
учебника
информатики
?
Ответ
:
210.
15.
Сколькими
способами
можно
выбрать
из
натуральных
чисел
от
1
до
20
два
числа
так
,
чтобы
их
сумма
была
нечетным
числом
?
16.
Имеется
5
видов
конвертов
без
марок
и
4
вида
марок
.
Сколькими
способами
можно
выбрать
конверт
и
марку
для
посылки
письма
?
Ответ
:
20.
17.
Сколькими
способами
можно
выбрать
согласную
и
гласную
бук
-
вы
из
слова
«
здание
»?
Из
слова
«
кабинет
»?
Ответ
:
9.
18.
В
корзине
лежат
12
яблок
и
10
груш
.
Сын
выбирает
из
нее
яблоко
или
грушу
,
после
чего
дочь
берет
и
яблоко
,
и
грушу
.
В
каком
случае
дочь
име
-
ет
большую
свободу
выбора
:
если
сын
взял
яблоко
или
если
он
взял
грушу
?
Ответ
:
Если
сын
выбрал
яблоко
.
19.
Сколькими
способами
можно
совершить
круговой
рейс
из
А
в
В
и
обратно
,
если
на
обратном
пути
выбирать
новую
дорогу
и
известно
,
что
А
и
В
соединены
семью
дорогами
?
Ответ
:
42.
20.
У
некоторых
народов
принято
давать
детям
несколько
имен
.
Сколькими
способами
можно
назвать
ребенка
,
если
ему
дают
не
более
трех
имен
,
а
общее
число
имен
равно
300?
Ответ
:
26 820 600.
32
2.2
Упорядоченные
и
неупорядоченные
выборки
Понятие
выборки
Известно
,
что
k-
выборка
из
некоторого
множества
представляет
со
-
бой
комбинацию
из
к
элементов
этого
множества
.
Выборки
,
в
которых
все
элементы
различны
,
называют
выборками
без
повторений
,
в
отличие
от
выборок
с
повторениями
,
в
которые
могут
входить
одинаковые
элементы
.
Выборка
называется
упорядоченной
,
если
существенным
является
не
только
состав
элементов
в
ней
,
но
и
порядок
их
расположения
.
Две
упоря
-
доченные
k-
выборки
считаются
различными
,
если
они
отличаются
либо
составом
элементов
,
либо
порядком
их
расположения
.
Например
,
упорядо
-
ченные
выборки
(1,2)
и
(2,1)
считаются
различными
,
хотя
и
составлены
из
одних
и
тех
же
элементов
.
Выборка
называется
неупорядоченной
,
если
порядок
следования
элементов
в
ней
не
существенен
.
Так
, {1,2}
и
{2,1}
считаются
одной
и
той
же
неупорядоченной
выборкой
.
Фигурные
и
круглые
скобки
подчеркивают
отличие
неупорядочен
-
ной
выборки
от
упорядоченной
.
Пример
6
.
С
оставьте
всевозможные
2-
выборки
из
элементов
мно
-
жества
М
={
а
, b,
с
}.
Решение
.
(
а
,b), (b,
а
), (
а
,
с
), (
с
,
а
), (b,
с
), (
с
,b) –
это
упорядоченные
2-
выборки
без
повторений
.
Их
,
очевидно
,
всего
6.
(
а
,
а
); (
а
,b); (
а
,
с
); (b,b); (b,a); (b,c); (c,c); (c,a); (c,b) –
упорядоченные
2-
выборки
с
повторениями
.
Их
всего
9.
{a,b}, {
а
,
с
}, {b,c} –
неупорядоченные
выборки
без
повторений
.
Легко
видеть
,
что
и
x
всего
3.
[a,b]; [a,a]; [a,c]; [b,b]; [b,c]; [c,c] –
неупорядоченные
выборки
с
по
-
вторениями
.
Их
всего
6.
В
следующих
параграфах
будут
даны
формулы
для
подсчета
количе
-
ства
k-
выборок
из
n
элементов
.
ЗАДАЧИ
И
УПРАЖНЕНИЯ
1.
Из
ящика
с
70
разными
шарами
вынимается
5
шаров
?
Какого
типа
5-
выборка
?
Ответ
обосновать
.
Ответ
:
Неупорядоченная
без
повторения
.
2.
Какого
типа
7-
выборка
при
совершении
покупки
семи
пирожных
;
если
в
магазине
имеется
четыре
их
сорта
?
Ответ
:
Неупорядоченная
с
повторениями
.
33
3.
На
шахматной
доске
расставлены
:
а
) 8
одинаковых
фигур
;
б
) 8
раз
-
личных
фигур
.
К
какому
типу
относятся
8-
выборки
в
случаях
а
)
и
б
)?
Ответ
:
а
)
Неупорядоченная
с
повторениями
.
б
)
Упорядоченная
без
повторений
.
4.
Какого
типа
4-
выборки
,
если
выбираются
из
10
претендентов
:
а
)
четыре
кандидата
на
конференцию
?
б
)
президент
,
вице
-
президент
,
казначей
и
ученый
секретарь
научного
общества
?
Ответ
:
а
)
Неупорядоченная
без
повторений
.
б
)
Упорядоченная
с
повторениями
.
5.
Переставляются
буквы
слов
:
а
) «
март
»,
б
) «
мама
».
Сколько
полу
-
чится
различных
перестановок
?
Перечислите
их
.
К
какому
типу
выборки
можно
отнести
эти
комбинации
букв
?
Ответ
:
Упорядоченные
.
6.
Из
множества
цифр
{0,1,2,...,9}
составляются
различные
наборы
чисел
по
пять
цифр
в
каждом
.
Какого
типа
выборки
представляют
собой
пятизначные
числа
?
7.
Составляются
слова
длины
4
из
32
букв
русского
алфавита
так
,
что
две
соседние
буквы
этих
слов
различны
.
Какого
характера
эти
выборки
?
Найти
число
таких
наборов
слов
.
8.
Сколько
можно
составить
слов
длины
k
из
32
букв
русского
алфа
-
вита
?
Рассмотреть
случай
k = 2, 3, 4.
Ответ
:
Упорядоченные
с
повторениями
.
1 024
при
k = 2; 32 768
при
k = 34;
32
4
при
k = 4.
9.
Из
множества
A = {a, b, c, d}
составить
:
а
)
упорядоченные
2-
выборки
без
повторений
;
б
)
неупорядоченные
2-
выборки
без
повторений
.
Сколько
их
всего
может
быть
?
Ответ
:
а
) 12;
б
) 6.
При
решении
комбинаторных
задач
,
в
которых
требуется
определить
количество
некоторых
выборок
(
комбинаций
)
из
данного
множества
эле
-
ментов
,
основным
моментом
является
правильное
определение
типа
(
ха
-
34
рактера
)
выборок
–
упорядоченные
это
выборки
или
нет
,
с
повторениями
или
без
повторений
.
Комбинациям
,
которые
встречаются
в
этих
задачах
,
присвоены
осо
-
бые
названия
–
размещения
,
сочетания
и
перестановки
.
Размещения
без
повторений
и
с
повторениями
Размещениями
без
повторений
из
п
элементов
по
k
называются
упорядоченные
k-
выборки
из
п
элементов
без
повторений
.
Их
число
обозначается
k
n
A
и
вычисляется
по
формуле
:
k
n
A
= n
´
(n – 1)
´
(n – 2)
´
…
´
(n – k + 1) =
)!
(
!
k
n
n
-
, k
£
n. (2)
Обычно
размещения
без
повторений
из
n
элементов
по
n
называются
перестановками
из
n
элементов
.
Их
число
обозначается
P
n
и
вычисляется
по
формуле
:
P
n
=
n
n
A
= n! (3)
Пример
7.
Сколькими
способами
можно
составить
трехцветный
по
-
лосатый
флаг
,
если
имеется
материал
пяти
различных
цветов
?
Решение
.
Нужно
найти
число
3-
выборок
из
5
элементов
без
повто
-
рений
(
все
цвета
различны
);
порядок
,
в
котором
располагаются
выбранные
цвета
,
существенен
.
Следовательно
,
нужно
найти
число
упорядоченных
выборок
,
т
.
е
.
число
размещений
из
5
по
3
без
повторений
.
По
формуле
(2)
имеем
3
5
A
=
)!
3
5
(
!
5
-
= 5
´
4
´
3 = 60 (
способов
).
Заметим
,
что
эту
задачу
можно
решить
иначе
.
Для
выбора
цвета
пер
-
вой
полосы
имеется
5
вариантов
.
После
произведенного
выбора
цвет
для
второй
полосы
можно
выбрать
4-
мя
способами
из
4-
х
оставшихся
.
Далее
выбираем
цвет
для
третьей
полосы
флага
из
имеющихся
3-
х
цветов
.
Это
можно
сделать
3-
мя
способами
.
По
правилу
произведения
всего
имеем
5
´
4
´
3 = 60 (
способов
).
Пример
8.
Та
же
задача
из
примера
7,
но
среди
полос
одна
обяза
-
тельно
должна
быть
красной
.
Решение
.
Красную
полосу
можно
расположить
3-
мя
способами
,
т
.
к
.
флаг
трехполосный
.
После
выбора
красной
полосы
,
остался
материал
4-
х
цветов
,
из
которых
нужно
выбрать
два
цвета
.
Этот
выбор
можно
осуществить
2
4
A
=
!
2
!
4
= 4
´
3 = 12 (
способами
) ,
так
как
2-
выборки
упорядоченные
без
повторений
.
По
правилу
произведения
окончательно
имеем
3
´
2
4
A
=
36
(
способов
).
35
Пример
9.
Сколькими
способами
можно
поставить
в
ряд
5
человек
для
фотоснимка
?
Решение
.
Ряд
из
пяти
человек
можно
рассматривать
как
упорядо
-
ченную
выборку
из
5-
ти
элементов
по
5.
По
формуле
(3)
имеем
P
5
=
5
5
A
=
5! = 120 (
способов
).
Размещениями
с
повторениями
из
п
элементов
по
k
называются
упорядоченные
k-
выборки
из
п
элементов
с
повторениями
.
Их
число
обо
-
значается
k
n
A
и
вычисляется
по
формуле
k
n
A
= n
k
,
"
n, k
Î
N . (4)
Пример
10.
В
одной
из
первых
поколений
ЭВМ
«
Стрела
»
ОЗУ
имело
2 048
ячеек
,
каждая
ячейка
состояла
из
43
разрядов
.
Какое
максимальное
количество
различных
чисел
в
двоичной
системе
счисление
можно
было
поместить
в
ОЗУ
?
Решение
.
В
любой
ячейке
информация
(
число
)
представлялась
в
ви
-
де
двоичного
,
т
.
е
.
состоящего
из
0
и
1,
упорядоченного
набора
длины
43.
Всего
мест
для
0
и
1
равно
k = 2 048
´
43 = 88 064.
Таким
образом
,
имеем
упорядоченные
k-
выборки
из
n = 2
с
повторениями
.
Их
число
находим
по
формуле
(4) :
k
A
2
= 2
k
,
где
k = 88 064.
ЗАДАЧИ
И
УПРАЖНЕНИЯ
10.
В
забеге
участвуют
5
человек
.
Сколькими
способами
могут
рас
-
пределиться
2
первых
места
?
Ответ
:
31.
11.
Сколькими
способами
могут
7
человек
встать
в
очередь
за
би
-
летами
в
театральной
кассе
?
Ответ
:
7!.
12.
Сколькими
различными
способами
2
друга
могут
одновременно
посетить
кого
-
либо
из
своих
общих
трёх
знакомых
?
Ответ
:
9.
13.
Сколько
существует
различных
наборов
длины
10
из
нулей
и
единиц
?
Ответ
:
1024.