Автор Тема: Задача на числа Каталана  (Прочитано 299 раз)

0 Пользователей и 1 Гость просматривают эту тему.

Оффлайн guerrino

  • Новичок
  • *
  • Сообщений: 11
    • Просмотр профиля
Задача на числа Каталана
« : 30 Апрель 2018, 02:07:55 »
Не уверен в правильности решения, поэтому и спрашиваю.
Итак, вот задача:

Некоторый объект находится на прямой в позиции 0. Он может за один шаг переместиться либо влево, либо вправо на одну позицию. Сколькими способами можно переместиться из начальной позиции в неё же за 2n шагов так, чтобы ни разу не оказаться левее нуля?

Понятно, что каждое перемещение вправо можно заменить открывающейся скобкой, влево - закрывающейся и ответ - количество правильных скобочных последовательностей из n пар закрывающихся и открывающихся скобок. Это количество равно Cn, т.е n-ому числу Каталана. Но что если не знать про эти числа? Вот мое решение:

Переформулируем условие задачи: сколько существует различных последовательностей a1, a2,...,a2n из n единиц и n минус единиц таких, что любая частичная сумма a1+a2+...+aj⩾0,  1⩽j⩽2n. Найдем общее количество различных последовательностей из равного количества 1 и -1 (их по n; назовем это множеством A):
Очевидно, это число равняется C2nn. Однако понятно, что не все комбинации будут удовлетворять условию.

Теперь рассмотрим n+1 минус единиц и n-1 единиц. Количество последовательностей из этих элементов равно C2nn-1. Все они неправильны и в каждом из них есть хотя бы одна отрицательная частичная сумма. Осталось лишь заметить, что каждую такую частичную сумму в отдельно взятой последовательности можно сопоставить неправильной последовательности (из равного количества единиц и минус единиц) и наоборот. Действительно, рассмотрим частичную сумму S, S<0; Пусть в ней количество минус единиц не превосходит n. Тогда эту частичную сумму можно продлить до длины 2n (так, чтоб единиц и минус единиц было поровну). То есть в таком случае множество S принадлежит множеству A; Рассмотрим остальные элементы S в которых минус единиц n+1: каждый такой элемент сопоставим элементу из A такому, что a1 и/или a2n отрицательны. Значит A=S; Получаем, что количество правильных последовательностей равняется C2nn - C2nn-1, что по определению равно Cn.

Возможно, ошибка в нестрогости. Возможно, вообще, в подходе. Так или иначе хотел бы спросить мнения у вас.

Оффлайн c2h5oh

  • Постоялец
  • ***
  • Сообщений: 114
    • Просмотр профиля
Re: Задача на числа Каталана
« Ответ #1 : 05 Май 2018, 13:33:09 »
Наглядно это можно представить так:
https://ibb.co/eBg9B7
Каждому пути из O в M которых очевидно Cn-12n, можно сопоставить ровно один путь из O в N, такой что хотя бы одна точка этого пути лежит выше диагонали ON. У таких путей совпадают точка K - первая точка выше ON и пути из O в K. Участки путей из K в N и из K в M симметричны относительно диагонали KL.