Сколько разлчиных решений в целых неотрицательных числах имеет уравнение:

x1 + x2 + ... + xN = K

где все xi ограниченны некоторым числом L, которое не превосходит K:

0 <= xi <= L, для i из [1,N]
0 <= L <= K

Если L=K, то задача решается просто: это биноминальный коэффициент C_K^N+K-1. А как найти решение для любого L?

Здравствуйте, uncommon, Вы писали:

U>Сколько разлчиных решений в целых неотрицательных числах имеет уравнение:
U>

U>x1 + x2 + ... + xN = K
U>

U>где все xi ограниченны некоторым числом L, которое не превосходит K:
U>

U>0 <= xi <= L, для i из [1,N]
U>0 <= L <= K
U>

U>Если L=K, то задача решается просто: это биноминальный коэффициент C_K^N+K-1. А как найти решение для любого L?

Пусть Q(N,K,L) решение исходной задачи.
Обозначим A(N,K,L) — чесло решений задачи с ограничением

  x1 + x2 + ... + xN <= K
  0 <= xi <= L

тогда Q(N,K,L) = A(N,K,L) — A(N,K-1,L)

При отсутствии ограничения по L ( L>=K )
A(N,K,inf) = C_K^N+K

Введем параметр "превышение" P({x_i}) = Σ_i=1..N x_i / (L+1)
(где деление — целочисленное). Суть: число переменных в множестве {xi}, значения которых превышают L. Если значение превышает 2L+1, учитываем с весом 2, ...
Если P({xi})==0, значит xi <= L

Каждому решению с заданным превышением p, можно сопоставить решение с p=0 :
x'_i == x_i % (L+1)

Причем одному решению x'_i соответствует N^p/p! решений x_i, с заданным превышением p.

Таким образом ответ:

A(N,K,L) =CKN+K - Σp=1..K/(L+1)  Np/p! * A(N,K-p*(L+1), L)
Q(N,K,L) = A(N,K,L) - A(N,K-1,L)

Учитывая, что в рекурсивной формуле на всех шагах фигурируют одни и те же значения K, сложность вычисления равна O( K/(L+1) ), если запоминать уже посчитанные значения A.