Найдите количество неубывающих функций f : {1, 2, . . . , n} → {1, 2, . . . , m}. Функция неубывающая, если x <= y влечет f(x) <= f(y).

задан 9 Окт '17 5:35

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

Обозначим $%f(i)$% через $%x_i$% при $%1\le i\le n$%. Требуется найти количество последовательностей из $%n$% чисел с условием $%1\le x_1\le\cdots\le x_n\le m$%.

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

ссылка

отвечен 9 Окт '17 9:33

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×744
×168

задан
9 Окт '17 5:35

показан
3043 раза

обновлен
9 Окт '17 9:33

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

по почте:

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

по RSS:

Ответы

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

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