Question

Сколькими способами можно разбить число 64 на 10 натуральных слагаемых (целых >= 1), наибольшее из которых равно 12?

Answer 1

Как я понимаю, на листочке эту задачу не решить. По крайней мере, это будет мучительно долго. А на компьютере - запросто.

Итак, решение. Т.к. наибольшее слагаемое равно 12, то нам надо посчитать количество разбиений числа 64-12=52 на 9 натуральных слагаемых. Т.е., если обозначим через p(N,M,n) количество разбиений числа n на НЕ БОЛЕЕ, чем M слагаемых, каждое из которых не превосходит N, то нам надо найти p(12,9,52)-p(12,8,52). Если у нас есть произвольное разбиение числа n на РОВНО M слагаемых, где каждое не больше N, то вычитая из каждого такого слагаемого 1, мы получим разбиение числа n-M на НЕ БОЛЕЕ, чем M слагаемых, где каждое слагаемое уже не больше N-1. И в обратную сторону тоже верно.  Т.е. имеет место рекуррентное соотношение p(N,M.n)-p(N,M-1,n)=p(N-1,M,n-M). Его уже достаточно для вычисления p(N,M.n) для произвольных N,M,n. Остается только заметить, что если NM<n или n<0, то p(N,M,n)=0, и если  n=0 или NM=n, то p(N,M,n)=1. В ручную применять это рекуррентное соотношение для наших чисел очень долго, но на компьютере, например в программе MAPLE следующий рекурсивный алгоритм мгновенно находит ответ:

p:=proc(N,M,n)
if (n<0) or (N*M<n) then return 0; fi;
if (n=0) or (N*M=n) then return 1; fi;
return p(N,M-1,n)+p(N-1,M,n-M);
end proc:

Получаем p(12,9,52)-p(12,8,52)=p(11,9,43)=4447. Так что ответ здесь будет 4447.