Задачи на разбиение чисел
Теперь мы переходим к задачам, в которых все разделяемые предметы совершенно одинаковы. В этом случае можно говорить не о разделении предметов, а о разбиении натуральных чисел на слагаемые (которые, конечно, тоже должны быть натуральными числами).
Здесь возникает много различных задач. В одних задачах учитывается порядок слагаемых, в других - нет.
Задача 4. Отправка бандероли.
За пересылку бандероли надо уплатить 18 рублей. Сколькими способами можно оплатить ее марками стоимостью 4, 6, и 10 рублей, если два способа, отличающиеся порядком марок, считаются различными (запас марок различного достоинства считаем неограниченным)?
Обозначим через
число способов, которыми можно наклеить марки в 4, 6 и 10 рублей так, чтобы общая стоимость этих марок равнялась
. Тогда для
справедливо следующее соотношение:
Пусть имеется некоторый способ наклейки марок с общей стоимостью
, и пусть последней наклеена марка стоимостью 4 рубля. Тогда все остальные марки стоят (
) рубля. Наоборот, присоединяя к любой комбинации марок общей стоимостью (
) рубля одну четырехрублевую марку, получаем комбинацию марок стоимостью
рублей. При этом из разных комбинаций стоимостью (
) рублей получается разные комбинации стоимостью
рублей. Итак, число искомых комбинаций, где последней наклеена марка стоимостью 4 рубля, равно
.
Точно так же доказывается, что число комбинаций, оканчивающихся на на шестирублевую марку, равно
, а на десятирублевую марку оканчиваются
комбинацией. Поскольку любая комбинация оканчивается на марку одного из указанных типов, то по правилу суммы получаем соотношение 5.4.
Соотношение 5.4 позволяет свести задачу о наклеивании марок на сумму
рублей к задачам о наклеивании марок на меньшие суммы. Но при малых значениях
задачу легко решить непосредственно. Простой подсчет показывает, что
Равенство
означает, что сумму в 0 рублей можно уплатить единственным образом: совсем не наклеивая марок. А сумму в 1,2,3,5,7 и 9 рублей вообще никак нельзя получить с помощью марок стоимостью 4, 6 и 10 рублей.
Используя значения
для
, легко найти
:
После этого находим
и т.д. Наконец, получаем значение
. Таким образом, марки можно наклеить восемью способами. Эти способы таковы:
;
;
;
;
;
;
;
. Отметим, что значения
для
можно было получить иначе, не приводя непосредственно проверки. Дело в том, что при
имеем
, поскольку отрицательную сумму нельзя уплатить, наклеивая неотрицательное количество марок. В то же время, как мы видели,
. Поэтому
.
Точно так же получаем значение
, а для
имеем
.
Задача 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 |
Содержание раздела
