2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Представление числа в виде суммы [Комбинаторика]
Сообщение22.11.2011, 16:17 
Аватара пользователя
Здравствуйте!
Помогите разобраться с такой задачкой, не знаю с чего начать.
Сколькими способами можно представить натуральное число $m$ в виде суммы $x_1+x_2+...+x_p$, где все $x_k$ - натуральные числа, удовлетворящие неравенствам $l \leq x_k \leq n$ ($l$ и $n$ - фиксированные натуральные числа).

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

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

 
 
 
 Re: Представление числа [Комбинаторика]
Сообщение22.11.2011, 17:56 
Аватара пользователя
Оно равно количеству композиций числа $m-pl$ на неотрицательные слагаемые, не превышающие $n-l$. Можно посчитать через формулу включений-исключений.

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

 
 
 
 Re: Представление числа [Комбинаторика]
Сообщение22.11.2011, 18:00 
Аватара пользователя
Да я нашел пункт 1) используя формулу включений-исключений. Но пункт 1) это не ведь не то что нужно?

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

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

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

Хотя один вопрос возник:
Хорхе в сообщении #506610 писал(а):
Оно равно количеству композиций числа $m-pl$ на неотрицательные слагаемые, не превышающие $n-l$. Можно посчитать через формулу включений-исключений.

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

 
 
 
 Re: Представление числа [Комбинаторика]
Сообщение22.11.2011, 18:40 
Аватара пользователя
Отнимите от каждого $x_k$ по $l$ и получите задачу, о которой я говорю.

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

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

 
 
 
 Re: Представление числа [Комбинаторика]
Сообщение22.11.2011, 18:50 
Аватара пользователя
А количество слагаемых фиксировано?

 
 
 
 Re: Представление числа [Комбинаторика]
Сообщение22.11.2011, 18:51 
Аватара пользователя
gris да $p$ фиксирован.

 
 
 
 Re: Представление числа [Комбинаторика]
Сообщение22.11.2011, 19:02 
Аватара пользователя
Whitaker, все правильно, задача эквивалентна такой.

 
 
 
 Re: Представление числа [Комбинаторика]
Сообщение22.11.2011, 19:03 
Аватара пользователя
Тогда всё понятно!
Спасибо Вам еще раз за помощь, Хорхе

 
 
 
 Re: Представление числа [Комбинаторика]
Сообщение22.11.2011, 19:04 
Аватара пользователя
Всегда пожалуйста. На всякий случай напишите ответ, а мы проверим.

 
 
 
 Re: Представление числа [Комбинаторика]
Сообщение22.11.2011, 20:44 
Аватара пользователя
Обозначим через $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};$
Хорхе вот такой у меня вроде ответ получился

 
 
 
 Re: Представление числа [Комбинаторика]
Сообщение22.11.2011, 20:46 
Аватара пользователя
Навскидку правильно.

 
 
 
 Re: Представление числа [Комбинаторика]
Сообщение22.11.2011, 20:47 
Аватара пользователя
Хорхе спасибо :D

 
 
 
 Re: Представление числа в виде суммы [Комбинаторика]
Сообщение11.10.2020, 22:08 
Whitaker в сообщении #506738 писал(а):
Whitaker

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

 
 
 [ Сообщений: 17 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group