Чего больше, разбиений n-элементного множества на не более чем k подмножеств или разбиений (n + k)-элементного множества на ровно k подмножеств?

задан 21 Ноя '19 18:02

Какие-то свойства числа сочетаний надо смотреть...

(21 Ноя '19 19:29) all_exist

@all_exist: это должно быть связано не с сочетаниями, а с числами Стирлинга II рода.

(21 Ноя '19 20:28) falcao

Хм... не так понял условие... (((

(21 Ноя '19 21:06) all_exist

Каждому разбиению из первого сопоставим разбиение из второго, добавив в каждое из m подмножеств разбиения по "свежему" элементу, а остаток распределим по k-m одноэлементным подмножествам.
Очевидно, что одному первому разбиению будет соответствовать много вторых разбиений.

(22 Ноя '19 9:17) spades

Вообще странная задача. В аналогичной задаче про разбиение чисел на слагаемые получается биекция между разбиениями, что представляется любопытным. А тут... Бесповодность какая-то.

(22 Ноя '19 9:20) spades

@spades: есть много примеров задач, где строится инъекция, и на основании этого делается вывод, что в каком-то из множеств элементов больше. В принципе, это может иметь разумный смысл.

@man123: если не рассматривать тривиальный случай k=1, когда всего поровну, то берём разбиение множества {1,2,...,n+k} на k частей и удаляем последние k элементов (от n+1 до n+k). Получается разбиение {1,2,...,n} не более чем на k частей. Отсюда легко увидеть, чего здесь больше.

(24 Ноя '19 1:49) falcao
показано 5 из 6 показать еще 1
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,343
×1,212
×6

задан
21 Ноя '19 18:02

показан
215 раз

обновлен
24 Ноя '19 1:49

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

по почте:

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

по RSS:

Ответы

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

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