Задачи на разбиение чисел - часть 2
Используя значения
для
, легко найти
:
После этого находим
и т.д. Наконец, получаем значение
. Таким образом, марки можно наклеить восемью способами. Эти способы таковы:
;
;
;
;
;
;
;
. Отметим, что значения
для
можно было получить иначе, не приводя непосредственно проверки. Дело в том, что при
имеем
, поскольку отрицательную сумму нельзя уплатить, наклеивая неотрицательное количество марок. В то же время, как мы видели,
. Поэтому
.
Точно так же получаем значение
, а для
имеем
.
Задача 5.Общая задача о наклейке марок.
Разобранная задача является частным случаем следующей общей задачи:
Имеются марки достоинством в
. Сколькими способами можно оплатить с их помощью сумму в
рублей, если два способа, отличающиеся порядком, считаются различными? Все числа
различны, а запас марок неограничен. Здесь на первом месте мы будем указывать число слагаемых, на втором – разбиваемое число и на последнем - ограничения на величину слагаемых.
В этом случае число
способов удовлетворяет соотношению
При этом
, если
и
. С помощью соотношения 5.5 можно найти
для любого
, последовательно вычисляя
.
Рассмотрим частный случай этой задачи, когда
,
. Мы получаем всевозможные разбиения числа
на слагаемые
, причем разбиения, отличающиеся порядком слагаемых, считаются различными. Обозначим число этих разбиений через
. (
На первом месте мы будем указывать число слагаемых, на втором - разбиваемое число и на последнем – ограничения на величину слагаемых.) Из соотношения 5.5 следует, что
При этом
и
,если
. Вычисление
можно упростить, если заметить, что
и потому
Ясно, что слагаемые не могут быть больше
. Поэтому
равно числу всех разбиений на
на натуральные слагаемые (включая и "разбиение"
. Если число слагаемых равно
, то получаем
разбиений. Поэтому
Итак, мы доказали, что натуральное число
можно разбить на слагаемые
способами. Напомним, что при этом учитывается порядок слагаемых.Например, число 5 можно разбить на слагаемые
способами.
5 = 5 | 5 = 3 + 1 + 1 | 5 = 1 + 2 + 2 |
5 = 4 + 1 | 5 = 1 + 3+ 1 | 5 = 2 + 1 + 1 + 1 |
5 = 1 + 4 | 5 = 1 + 1 + 3 | 5 = 1 + 2 + 1 + 1 |
5 = 2 + 3 | 5 = 2 + 2 + 1 | 5 = 1 + 1 + 2 + 1 |
5 = 3 + 2 | 5 = 2 + 1 + 2 | 5 = 1 + 1 + 1 + 2 |
| | 5 = 1 + 1 + 1 + 1 + 1 |
Содержание Назад Вперед