$$ f: \{1, 2..n\} -> \{1,2...m\}$$ Функция невозрастающая если для двух значений х и у, где х меньше либо равен у $$f(x) <= f(y)$$

Может быть можно использовать метод шаров и перегородок? Но тогда не очень ясно как работать с равными значениями

задан 7 Ноя 14:52

1

@Arkon: здесь есть готовый ответ. Мы задаём n чисел, которые могут повторяться, со значениями из m-элементного множества. Это в точности число сочетаний с повторениями из m по n, то есть C_{m+n-1}^n. "Перегородки" остаются в доказательстве, но можно их и здесь явно получить: сначала пишем k1 "палочек", потом +, потом k2 "палочек", потом +, и так далее вплоть до km "палочек". Число ki показывает, сколько раз f принимает значение i. Итого получается n "палочек" и m-1 "перегородка" в виде "плюса".

(7 Ноя 15:51) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,005
×553

задан
7 Ноя 14:52

показан
33 раза

обновлен
7 Ноя 15:51

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

по почте:

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

по RSS:

Ответы

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

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