Задачи на разбиение чисел - часть 2

Используя значения

$f(N)$

для

$N = 0,1,2,3,4,5,6,7,8,9$

, легко найти

$f(10)$

$f(10)=f(6)+f(4)+f(0)=3.$

После этого находим

$f(11)=f(7) + f(5) + f(1) = 0,$

$f(12)=f(8) + f(6) + f(2) = 2$

и т.д. Наконец, получаем значение

$f(18)=8$

. Таким образом, марки можно наклеить восемью способами. Эти способы таковы:

$10,4,4$

;

$4,10,4$

;

$4,4,10$

;

$6,4, 4,4$

;

$4,6,4,4$

;

$4,4,6,4$

;

$4,4,4,6$

;

$6,6,6$

. Отметим, что значения

$f(N)$

для

$N = 1,2,3,4,5,6,7,8,9$

можно было получить иначе, не приводя непосредственно проверки. Дело в том, что при

$N < 0$

имеем

$f(N) = 0$

, поскольку отрицательную сумму нельзя уплатить, наклеивая неотрицательное количество марок. В то же время, как мы видели,

$f(0) = 1$

. Поэтому

$f(1)=f(-3)+f(-5)+f(-9)=0$

Точно так же получаем значение

$f(2)=0,f(3)=0$

, а для

$N = 4$

имеем

$f(4)=f(0)+f(-2)+f(-6)=1$

Задача 5.Общая задача о наклейке марок.

Разобранная задача является частным случаем следующей общей задачи:

Имеются марки достоинством в
$n_1,n_2,\ldots,n_k$
. Сколькими способами можно оплатить с их помощью сумму в
$N$
рублей, если два способа, отличающиеся порядком, считаются различными? Все числа
$n_1,n_2 ,\ldots,n_k$
различны, а запас марок неограничен. Здесь на первом месте мы будем указывать число слагаемых, на втором – разбиваемое число и на последнем - ограничения на величину слагаемых.

В этом случае число

$f(N)$

способов удовлетворяет соотношению

$f(N) = f(N - n_1 ) + f(N - n_2 ) + \ldots + f(N - n_k).$

(5.5)

При этом

$f(N) = 0$

, если

$f(0)=1$

$N < 0$

. С помощью соотношения 5.5 можно найти

$f(N)$

для любого

$N$

, последовательно вычисляя

$f(1),f(2),\ldots,f(N-1)$

Рассмотрим частный случай этой задачи, когда

$n_1= 1,n_2 = 2,\ldots$

$n_k = k$

. Мы получаем всевозможные разбиения числа

$N$

на слагаемые

$1,2,\ldots,k$

, причем разбиения, отличающиеся порядком слагаемых, считаются различными. Обозначим число этих разбиений через

$\varphi(k;N)$

. (На первом месте мы будем указывать число слагаемых, на втором - разбиваемое число и на последнем – ограничения на величину слагаемых.) Из соотношения 5.5 следует, что

$\varphi(k;N-1)+\varphi(k;N-2)+\ldots+\varphi(k;N-k).$

(5.6)

При этом

$\varphi (k;0) = 1$

$\varphi(k;N)= 0$

,если

$N <0$

. Вычисление

$\varphi (N;k)$

можно упростить, если заметить, что

$\varphi (N-1;k)=\varphi(N-2;k)+\varphi(N-k-1;k),$

и потому

$\varphi(N;k)=2\varphi(N-1;k)-\varphi (N - k - 1;k).$

(5.7)

Ясно, что слагаемые не могут быть больше

$N$

. Поэтому

$\varphi(N,N)$

равно числу всех разбиений на

$N$

на натуральные слагаемые (включая и "разбиение"

$N = N$

. Если число слагаемых равно

$s$

, то получаем

$C_{N - 1}^{s - 1}$

разбиений. Поэтому

$\varphi(N,N)=C_{N-1}^0+C_{N-1}^1+\ldots+C_{N-1}^{N-1}=2^{N-1}.$

Итак, мы доказали, что натуральное число

$N$

можно разбить на слагаемые

$2^{N - 1}$

способами. Напомним, что при этом учитывается порядок слагаемых.Например, число 5 можно разбить на слагаемые

$2^{5 - 1} = 16$

способами.

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

Содержание Назад Вперед