Сколько решений у уравнения x + y + z = C? Мне сказали, что $$\binom{C+2}{2}$$, но почему?

Так же, как посчитать кол-во решений если x, y и z ограничены?

Это из задачи, где нужно написать рекурсивную программу, в которой нужно перебрать все возможные распределения вещества в 3х стаканах, каждый из них может быть любой высоты, от 0, до 20. Вещество мы переливаем пока один из стаканов не заполнился или в другом не закончилось вещество, начиная с 1м и 2м пустыми и 3м полным стаканоми. Я всего лишь хотел вычислить размер стека рекурсии, которая это перебирает.

задан 14 Мар '16 14:38

перемечен 14 Мар '16 20:49

Trumba's gravatar image


75118

Оказывается это какой-то стандартный результат в комбинаторике, что у уравнения x1 + x2 + ... + xN = C $$\binom{C+N-1}{N-1}$$ решений.

(14 Мар '16 15:46) pavel1076

@pavel1076: да, это совершенно стандартная вещь. Посмотрите в любом учебнике тему "сочетания с повторениями". Для Вашего случая всё ещё проще: посчитайте число решений с z=C, z=C-1, ... , z=0, и сложите всё вместе. Получится сумма 1+2+...+(C+1)=(C+1)(C+2)/2.

(14 Мар '16 16:29) falcao

@falcao спасибо.

(15 Мар '16 9:32) pavel1076
10|600 символов нужно символов осталось
2

Ниже я покажу как посчитать число решений уравнения $%вида x+y+z = N$% в натуральных числах (0 тоже считаем за натуральное число).

Рассмотрим многочлен $%P(x)=(1+x+\cdots+x^N)^3=\left ( \frac{1-x^{N+1}}{1-x} \right )^3$% и спросим себя чему равен его коэффициент при $%x^N$%?. После некоторых размышлений мы понимаем, что он в точности равен числу решений уравнения $%x+y+z = N$% в натуральных числах. Значит осталось найти этот коэффициент.

Разложим $%\frac{1}{(1-x)^3}$% в ряд Тейлора:

$$\frac{1}{(1-x)^3}=\sum_{k=0}^{+\infty} \frac{-3(-3-1)\cdots(-3-(k-1))}{k!}(-1)^{k}x^k=\\=\sum_{k=0}^{+\infty} \frac{3(3+1)\cdots(k+2)}{k!}x^k=\sum_{k=0}^{+\infty} \binom{k+2}{2}x^k.$$

Теперь должно быть легко видеть, что коэффициент при $%x^N$% в многочлене $%P(x)=\left ( \frac{1-x^{N+1}}{1-x} \right )^3$% равен $%\binom{N+2}{2}$%.

Если ограничения на $%x,$% $%y$% и $%z$% одинаковые, скажем $%x,y,z\le A\le C$%, то задача решается аналогично (надо рассмотреть многочлен $%(1+x+\cdots+x^A)^3$%) и найти его коэффициент при $%x^C$%), а вот если ограничения разные, то, я думаю, потребуется перебор.

ссылка

отвечен 14 Мар '16 15:13

изменен 14 Мар '16 15:22

Спасибо, правда я не силен в математике, не совсем понимаю что такое коэффициент многочлена при x^N и как понять, что он равер x + y + z. Можете подсказать?

(14 Мар '16 15:30) pavel1076

@pavel1076 В многочлене $%27x^{17}-456x^3+7$% $%27$% --- это коэффициент при $%x^{17}$%, а $%-456$% --- это коэффициент при $%x^3$%. Что бы понять почему число решений уравнения вида $%x+y+z=N$% равно этому коэффициенту рассмотрите пример. Возьмете $%N=2$%, аккуратно перемножите $%(1+x+x^2)^3$% и посмотрите как формируется коэффициент при $%x^2.$%

(14 Мар '16 15:47) Sunbro

@Tzara, спасибо!

(14 Мар '16 15:50) pavel1076

@Tzara: зачем так сложно для такой элементарной задачи?

(14 Мар '16 16:30) falcao

как-то да, извратно, проще было даже индукцией по числу переменных

(14 Мар '16 20:49) Trumba
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,449
×946
×174
×76

задан
14 Мар '16 14:38

показан
4008 раз

обновлен
15 Мар '16 9:32

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru