Составители:
Рубрика:
Глава 1 Элементы комбинаторики 15
Можно доказать эту теорему, основываясь на том, что каждое со-
четание определяет k! различных кортежей длины k, составленных из
элементов S без повторений.
C
k
n
k! = n(n − 1) . . . (n − k − 1).
Задача 1.17. Сколько существует способов составить подароч-
ный набор из трех предметов, если всего имеется восемь различных
сувениров?
Все сувениры можно принять за множество S из восьми элементов. По
условию надо выбрать из него трехэлементное подмножество (порядок не
важен). Значит получится
8!
3! 5!
=
8 · 7 · 6
1 · 2 · 3
= 56 способов.
Задача 1.18. В языке племени «АББА» всего две буквы: А и Б.
Сколько слов из трех А и двух Б может образовать это племя?
Изобразим каждое слово кортежем из пяти компонент. Например: (А,
А, А, Б, Б), (А, Б, А, Б, А), (Б, А, Б, А, А), . . . Каждый кортеж опре-
деляется тем, какие из пяти мест занимают буквы Б (остальные — А).
Значит, слов будет столько, сколькими способами можно выбрать два
места из пяти, то есть
C
2
5
=
5 · 4
1 · 2
= 10 (слов).
Задача 1.19. Сколько различных семизначных чисел можно со-
ставить из двух единиц, четырех двоек и одной тройки?
Каждое число представим как кортеж из цифр 1, 2, 3 с заданным
числом повторений, то есть кортежем состава {1(2), 2(4), 3(1)}. Зд есь в
скобках указано число повторений для каждой цифры. Таких кортежей
будет C
2
7
· C
1
5
= 105. Действительно, разобьем все кортежи на классы по
расположению единиц, затем каждый класс разобьем на классы по рас-
положению тройки на одном из оставшихся пяти мест. Места под двойки
определяются однозначно.
Страницы
- « первая
- ‹ предыдущая
- …
- 12
- 13
- 14
- 15
- 16
- …
- следующая ›
- последняя »
