Представление числа в виде суммы [Комбинаторика]

[Whitaker]

Здравствуйте!
Помогите разобраться с такой задачкой, не знаю с чего начать.
Сколькими способами можно представить натуральное число $m$ в виде суммы $x_1+x_2+...+x_p$, где все $x_k$ - натуральные числа, удовлетворящие неравенствам $l \leq x_k \leq n$ ($l$ и $n$ - фиксированные натуральные числа).

С уважением, Whitaker.

[Whitaker]

Я нашел:
1) число способов представить $m$ в виде суммы $x_1+x_2+...+x_p$, где все $x_k \leq n$
2) число способов представить $m$ в виде суммы $x_1+x_2+...+x_p$, где все $x_k \geq l$.
Но как отсюда получить требуемое я пока не знаю.
Буду признателен если кто-нибудь подскажет.

[Хорхе]

Оно равно количеству композиций числа $m-pl$ на неотрицательные слагаемые, не превышающие $n-l$. Можно посчитать через формулу включений-исключений.

upd: если Вы действительно посчитали то, что утверждаете в пункте 1), то, в принципе, Вы задачу решили.

[Whitaker]

Да я нашел пункт 1) используя формулу включений-исключений. Но пункт 1) это не ведь не то что нужно?

-- Вт ноя 22, 2011 18:13:19 --

Хорхе Большое спасибо Вам за ценную подсказку.
К сожалению, сам до этого не догадался.

-- Вт ноя 22, 2011 18:39:58 --

Хотя один вопрос возник:

Хорхе в сообщении #506610 писал(а):

Оно равно количеству композиций числа $m-pl$ на неотрицательные слагаемые, не превышающие $n-l$. Можно посчитать через формулу включений-исключений.

Почему именно так?

[Хорхе]

Отнимите от каждого $x_k$ по $l$ и получите задачу, о которой я говорю.

А дальше, какая разница, как называются параметры, $m$ и $n$ или $m-pl$ и $n-l$. Поэтому, повторюсь, если Вы справились с пунктом 1), то всё хорошо.

[Whitaker]

Хорхе
Т.е. задача эквивалента следующей:
Определить число решений уравнения $y_1+y_2+...+y_p=m-pl$, где $0 \leq y_k \leq n-l$ ?
Надеюсь я нигде не ошибься

[gris]

А количество слагаемых фиксировано?

[Whitaker]

gris да $p$ фиксирован.

[Хорхе]

Whitaker, все правильно, задача эквивалентна такой.

[Whitaker]

Тогда всё понятно!
Спасибо Вам еще раз за помощь, Хорхе

[Хорхе]

Всегда пожалуйста. На всякий случай напишите ответ, а мы проверим.

[Whitaker]

Обозначим через $N(y_1 \leq n-l, y_2 \leq n-l,...,y_p \leq n-l)$ число решений уравнения $y_1+y_2+...+y_p=m-pl$ в целых неотрицательных числах с условием, что $l \leq y_k \leq n$.
Используя формулу включений-исключений я получил, что:
$N(y_1 \leq n-l, y_2 \leq n-l,...,y_p \leq n-l)=C_{m-pl+p-1}^{p-1}-C_{p}^{1}C_{m-pl+p-1-(n-l+1)}^{p-1}+C_{p}^{2}C_{m-pl+p-1-2(n-l+1)}^{p-1}-...+(-1)^pC_{m-pl+p-1-p(n-l+1)}^{p-1};$
Хорхе вот такой у меня вроде ответ получился

[Хорхе]

Навскидку правильно.

[Whitaker]

Хорхе спасибо

[D4nDme]

Whitaker в сообщении #506738 писал(а):

Whitaker

Whitaker, у вас в первом множителе в итоговой формуле сочетаний верхний параметр идет от 0 до p, верно?