Составители:
Рубрика:
20
и 1 слоеное. Тогда эти пирожные нумеруются так: 1, 2, 4, 5, 6, 8, 10. Ясно, что самый
большой номер может быть 10, самый маленький – 1, а кроме того, ни один из номеров не
повторяется, причем они образуют возрастающую последовательность. Обратно, каждой
возрастающей последовательности из 7 чисел соответствует некоторая покупка. Например,
последовательность 2, 3, 4, 5, 7, 8, 9 соответствует покупке из 4 эклеров и 3 песочных
пирожных. Чтобы убедиться
в этом, надо отнять от заданных номеров числа 1, 2, 3, 4, 5, 6, 7.
Мы получим числа 1, 1, 1, 1, 2, 2, 2. Но 1 мы прибавляли к номерам эклеров, а 2 – к номерам
песочных.
Отсюда, общее число покупок равно числу возрастающих последовательностей из 7
чисел от 1 до 10. А число таких последовательностей равно C(10,7)=120.
Сочетаниями с повторениями из n элементов по k называют всевозможные
комбинации, составленные из элементов n видов по k элементов в каждой. Комбинации
считаются различными, если они отличаются составом, но не порядком входящих в них
элементов. В комбинацию могут входить элементы одного вида.
Количество сочетаний с повторениями из n элементов по k обозначают
k
n
C
. Общее
правило вычисления количества сочетаний с повторениями:
k
kn
k
n
CC
1−+
=
Доказательство
Зашифуем каждую комбинацию с помощью нулей и единиц: для каждого типа
напишем столько единиц, сколько предметов этого типа входит в комбинацию, а предметы
различных типов отделить нулями. При этом число единиц будет k, а число нулей – n–1.
Различным комбинациям будут соответствовать различные перестановки с повторениями из
k элементов первого вида и n–1 элементов второго
вида, а каждой перестановке с
повторениями – своя комбинация. Итак,
k
kn
k
n
CnkPC
1
)1,(
−+
=−= .
Встречаются задачи, в которых на сочетания с повторениями накладывается
дополнительное условие, например, когда в комбинацию обязательно должны входить
элементы r фиксированных типов, где r≤n. Эта задача легко сводится к уже решенной. Для
того чтобы обеспечить присутствие заданных r типов, возьмем с самого начала по одному
элементу каждого такого типа. Тем самым в k-
сочетании окажутся заняты r мест. Поэтому
ответом на задачу будет число
rk
rkn
rk
n
CC
−
−−+
−
=
1
. В частности, если требуется, чтобы в каждом
сочетании был элемент каждого из типов (n≤k), то получится
nk
k
C
−
−1
.
Страницы
- « первая
- ‹ предыдущая
- …
- 18
- 19
- 20
- 21
- 22
- …
- следующая ›
- последняя »
