Добрый день. На экзамене по дискретке попался вопрос:

Сколько целых неотрицательных решений имеет уравнение
x1+x2+...+xk = n (справа от х - порядковый номер, а не коэффициент)

Так и не решил. Подскажте пожалуйста, как это сделать

задан 23 Июн '13 13:36

изменен 23 Июн '13 17:32

10|600 символов нужно символов осталось
1

Это сочетания с повторениями. Они сводятся к обычным сочетаниям. Возьмём какое-нибудь решение уравнения, и заменим в нём каждое число $%x_i$% на столько же "палочек", и все "плюсы" оставим. Получится своего рода "штрих-код" решения. Например, если мы видим запись $%|||++|+||$%, то это значит, что у нас был вектор $%(3,0,1,2)$% из чисел $%x_i$%, где $%i=1,2,3,4$%. Здесь $%k=4$%, $%n=3+0+1+2=6$%.

Понятно, что каждому решению соответствует свой "штрих-код", и по нему решение восстанавливается однозначно ($%x_i$% равно количеству палочек, перед которыми стоит ровно $%i-1$% "плюс"). Таким образом, количество решений равно количеству "штрих-кодов", где "палочек" ровно $%n=x_1+\cdots+x_k$%, а "плюсов" ровно $%k-1$%. Всего в коде имеется $%n+k-1$% символ, и чтобы составить такой код, мы из $%n+k-1$% мест выбираем те $%n$% мест, на которых будут стоять "палочки". Это не что иное как $%C_{n+k-1}^n$%: число сочетаний из $%n+k-1$% по $%n$%. Его же можно записать и по-другому -- как $%C_{n+k-1}^{k-1}$%.

ссылка

отвечен 23 Июн '13 14:14

@falcao, из последних двух предложений Вашего решения следует равенство k-1=n. Но даже для Вашего примера это не так. Или я чего-то не понимаю?

(23 Июн '13 16:57) Archi
1

Нет, ничего такого из последнего предложения не следует. Это свойство симметричности сочетаний. Здесь равенство получается не по причине того, что числа вверху равны, а по причине, что в сумме они дают число, написанное внизу. Иными словами, $%C_m^i=C_m^{m-i}$%. Это следует как из определения сочетаний (когда мы берём $%i$% элементов из $%m$%, то оставляем не взятыми $%m-i$%, что делается тем же числом способов), так и из формулы с факториалами. В задаче выше получается ответ $$\frac{(n+k-1)!}{n!(k-1)!}.$$

(23 Июн '13 17:53) falcao

@falcao, спасибо Вам! Теперь все перепроверил и понял.

(23 Июн '13 18:41) Archi
10|600 символов нужно символов осталось
0

Пожалуйста обясните это из какой формулы начили можете все подробно писать формулы, а то я не понял ((

ссылка

отвечен 8 Апр '14 11:50

У меня всё подробно объяснено. Если что-то не до конца ясно, можно задать конкретный вопрос. Но вообще-то это стандартный материал, и его можно прочитать в любом учебнике по комбинаторике. Название темы -- "сочетания с повторениями".

(8 Апр '14 11:57) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×899
×794

задан
23 Июн '13 13:36

показан
5260 раз

обновлен
8 Апр '14 11:57

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

по почте:

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

по RSS:

Ответы

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

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