ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 60447
Темы:    [ Числа Каталана ]
[ Мощность множества. Взаимно-однозначные отображения ]
Сложность: 4
Классы: 8,9,10,11
В корзину
Прислать комментарий

Условие

Сколько последовательностей  {a1, a2, ..., a2n},  состоящих из единиц и минус единиц, обладают тем свойством, что  a1 + a2 + ... + a2n = 0,  а все частичные суммы  a1,  a1 + a2,  ...,  a1 + a2 + ... + a2n  неотрицательны?


Решение

  Установим взаимно однозначное соответствие между такими последовательностями и расстановками скобок в произведении  x0x1...xn  (включая внешние скобки, например,  (x0((x1x2)x3))).  Именно, каждой открывающей скобке поставим в соответствие единицу, а каждому знаку умножения – минус единицу. Например указанной выше расстановке скобок в произведении x0x1x2x3 соответствует последовательность  {1, –1, 1, 1, –1, –1}.  Условие на неотрицательность частичных сумм выполнено, поскольку каждому знаку умножения соответствует своя пара скобок, "включающая" выражения, которые он перемножает.
  Наоборот, по каждой последовательности можно построить расстановку скобок. Сначала, как указано выше, расставляем в пустой строке открывающие скобки и знаки умножения, затем восстанавливаем закрывающие скобки следующим образом. Пусть открывающей скобке в последовательности соответствует  ak = 1.  Ищем наиболее "короткую" частичную сумму  ak + ... + am = 0  (такая, очевидно, найдется). При этом
ak = –1,  и мы ставим закрывающую скобку после знака произведения, соответствующего am. Затем уже легко вставить в полученную строку знаки неизвестных  x0, ..., xn.


Ответ

Cn.

Источники и прецеденты использования

книга
Автор Алфутова Н.Б., Устинов А.В.
Год издания 2002
Название Алгебра и теория чисел
Издательство МЦНМО
Издание 1
глава
Номер 2
Название Комбинаторика
Тема Комбинаторика
параграф
Номер 5
Название Числа Каталана
Тема Классическая комбинаторика
задача
Номер 02.113

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .