Дискретная математика Комбинаторика. Сколькими способами 2n человек различного роста могут быть построены в две шеренги так, чтобы в каждой шеренге они стояли по росту, и каждый стоящий в первой шеренге был выше стоящего за ним?
Дискретная математика Комбинаторика. Сколькими способами 2n человек различного роста могут быть построены в две шеренги так, чтобы в каждой шеренге они стояли по росту, и каждый стоящий в первой шеренге был выше стоящего за ним?
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для решения этой задачи можно воспользоваться методом динамического программирования.
Обозначим f(n) - количество способов распределения 2n человек по шеренгам. При этом первым в первой шеренге будет стоять самый высокий человек.
f(0) = 1, так как если нет людей, то распределить их не нужно.
f(1) = 1, так как есть только один способ разместить одного человека.
f(n) = C(2n, n) * f(n-1), где C(2n, n) - число сочетаний из 2n по n, или число Каталана.
Таким образом, общее количество способов разместить 2n человек по шеренгам - f(n).
Пример:
Пусть у нас есть 4 человека. Тогда f(2) = C(4, 2) f(1) = 6 1 = 6 способов разместить их по шеренгам.