Числа Каталана

57 школа, 9 класс
30 апреля 2002 г.

Числа Каталана
(дополнительный листочек)

1.   Рисуем ломаные на клетчатой бумаге: начинаем из точки (0; 0), движемся по диагоналям клеток. Звено ломаной может идти либо вправо-вверх, либо вправо-вниз.
   а)   Сколько таких ломаных заканчиваются в точке (2N; 0)?
Пусть Е(N) -- множество ломаных, заканчивающихся в точке (2N; -2); F(N) -- множество ломаных, заканчивающихся в точке (2N; 0) и пересекающих прямую Y = -1/2.
   б)   Установите взаимно однозначное соответствие между множествами Е(N) и F(N).
   в)   Сколько ломаных c концом в точке (2N; 0) не пересекают прямую Y = -1/2?

2.   (Блуждания на прямой.) Назовем траекторией длины n последовательность целых чисел d₀, ..., d_n, в которой d₀ = 0 и |d_k-d_k+1|=1 при всех k.
   а)   Сколько существует траекторий длины 2n, таких что d_n > n-5 и d_2n = 0?
   б)   Сколько существует траекторий длины n, состоящих из неотрицательных чисел
   в)   Сколько существует траекторий длины n, состоящих из неотрицательных чисел        и таких, что d_n = k?

3.   В строчку записаны n чисел b₁, ... , b_n. Мы хотим премножить эти числа, не переставляя их. Это можно сделать по-разному. Например, при n = 4 можно поступить так: b₁((b₂b₃)b₄). Или так: (b₁b₂)(b₃b₄). Сколькими способами можно перемножить n чисел?

4.   Автобусные билеты имеют номера от 000000 до 999999. Номер называется счастливым, если сумма первых трёх его цифр равна сумме последних трёх его цифр.
   а)   Докажите, что число счастливых номеров равно коэффициенту при X²⁷
       в многочлене (1 + Х + Х² + Х³ + Х⁴ + Х⁵ + Х⁶ + Х⁷ + Х⁸ + Х⁹)⁶.
   б)   Найдите число счастливых номеров.

5.   Из 57 школы вышли n школьников. Через 5 минут они разделились на две непустые группы. Далее раз в 5 минут каждая имеющаяся на этот момент неодноэлементная группа делится на две непустые группы. В конце концов каждый школьник остаётся в одиночестве. Сколькими способами может происходить этот процесс?

6.   Имеется n разных кабин для колеса обозрения. Сколькими способами можно соорудить из этих кабин несколько колес обозрения? (В колесе -- от 1 до n кабин.)

7.   Нужно организовать авиационное сообщение между n городами. Если самолет летит из А в В, то он летит и обратно из В в А. Требуется, чтобы можно было долететь из любого города в любой (возможно, с пересадками), и чтобы в случае отмены любого рейса это условие нарушалось. Сколько существует способов организовать авиаперевозки?