Задача 60447

Темы:    [ Числа Каталана ] [ Мощность множества. Взаимно-однозначные отображения ]

Сложность: 4 Классы: 8,9,10,11

Условие

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

Решение

  Установим взаимно однозначное соответствие между такими последовательностями и расстановками скобок в произведении  x₀x₁...x_n  (включая внешние скобки, например,  (x₀((x₁x₂)x₃))).  Именно, каждой открывающей скобке поставим в соответствие единицу, а каждому знаку умножения – минус единицу. Например указанной выше расстановке скобок в произведении x₀x₁x₂x₃ соответствует последовательность  {1, –1, 1, 1, –1, –1}.  Условие на неотрицательность частичных сумм выполнено, поскольку каждому знаку умножения соответствует своя пара скобок, "включающая" выражения, которые он перемножает.
  Наоборот, по каждой последовательности можно построить расстановку скобок. Сначала, как указано выше, расставляем в пустой строке открывающие скобки и знаки умножения, затем восстанавливаем закрывающие скобки следующим образом. Пусть открывающей скобке в последовательности соответствует  a_k = 1.  Ищем наиболее "короткую" частичную сумму  a_k + ... + a_m = 0  (такая, очевидно, найдется). При этом
a_k = –1,  и мы ставим закрывающую скобку после знака произведения, соответствующего a_m. Затем уже легко вставить в полученную строку знаки неизвестных  x₀, ..., x_n.

Ответ

C_n.

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

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