Помогите решить комбинаторную задачу на сочетания.

[deMarchi]

Необходимо найти кол-во целочисленных решений системы:
x1+x2+...+xn<=k; k>=0; xi>=0; i=1,2,...,n; n>=1


В "Дискретной Математике" Б.Н. Иванова приводится почти такая же задача, когда x1+x2+...+xn=k. В этом случае задача сводится к решению простого сочетания с повторениями, хотя я не сразу понял объяснение решения

Потом я написал алгоритм, чтоб програмно строить сочетания и отбрасывать сочетания не входящие в условие, но это не математическое решение. Помогите пожалуйста с с решением (формулой)

Спасибо, Денис

[Xaositect]

Насчет случая $=k$ - это классическая задача, количество решений равно количеству способов поставить $n-1$ разделителей среди $k$ шариков (на $k+1$ место).

Случай $\leq k$ можно свести к случаю $=k$, добавив фиктивную переменную:
$\sum\limits_{i=1}^n x_i \leq k,\ x_i\geq 0 \Leftrightarrow \sum\limits_{i=1}^{n+1} x_i = k, x_i\geq 0$
Так как $x_{n+1}$ определяется из этого соотношения однозначно, то соответствие это взаимно-однозначное, так что число решений одинаково.

[Brukvalub]

Я бы попробовал просуммировать ответы из Иванова, меняя правую часть уравнения от 0 до k.

[deMarchi]

Xaositect, понятно! Спасибо! Но я видимо ошибся с постоновкой задачи. Мне вначале показалось, что эта задача соответствует моей задаче, но проанализирова Ваш ответ, понял что ошибся.
Попробую еще раз, только на примере:
У меня есть размещения с повторениями, например из 3х элементов 1 , 2 и 3 по 2, т.е. 11, 12, 21, 13, 31, 23, 32, 33.
Теперь, имея уравнение вида x1+x2<=k, находим решения для различных k.
при k=1, решение 0; k=2, решение 1; k=3, решение 3; k=4, решение 5....

[Xaositect]

хмм. для $k=4$ не 5, а 6 вроде. Еще 22.

Я думаю, вряд ли замкнутая формула существует, но посчитать без перебора можно. Надо вывести рекуррентное соотношение или, как советует Brukvalub, записать сумму.

[deMarchi]

Спасибо Гоcпода Xaositect и Brukvalub.
Пошел я вспоминать рекуррентные соотношения, почти 20 лет прошло, с тех пор, как рекуррентность изучал

[deMarchi]

В общем навычеслял кучу вариантов для разных группировок по элементам и выходит, что "Сочетания с повторениями из n элементов по k элементов", те С с черточкой сверху есть ответ на мою задачу. Иванов был прав. Видимо я понял его задачу тоже правильно. А поскольку "условное равенство" не влияет, как Вы подсказали, значит мы получили ответ эксперементальным путем! Спасибо!!!

PS И на моих актуальных числах дугих порядков сошлось!!!