Республиканская олимпиада по математике, 2013 год, 9 класс

Дано множество $A = \{1, 2, \ldots, n\}$ и натуральное число $m$. Сколько существует способов разделить $А$ на $m$ частей так, что если числа $a < b$ лежат в одной части, а $c < d$ в другой, то $(a-d)(b-c) > 0$? Например, если $n = 4$, $m = 2$, то существует 5 способов разделения: $$ \{1, 2\} \{3, 4\}; \quad \{1, 2, 3\} \{4\}; \quad \{1, 2, 4\} \{3\}; \quad \{1, 3, 4\} \{2\}; \quad \{2, 3, 4\} \{1\}. $$ ( Д. Елиусизов )

Комментарий/решение

Решение: Заметим, что условие $(a-d)(b-c)>0\iff \min(a,b)=a>d=\max(c,d)$ или $\min(c,d)=c>b=\max(a,b).\quad (\color{red}{1})$

Пусть мы разделили множество $A$ на $m$ частей требуемым образом. Давайте выкинем все части с ровно 1 элементом, пусть их количество $k,$ где $0\le k\le m.$ Это можно сделать $\dbinom{n}{k}$ способами.

Теперь выпишем все оставшиеся $n-k$ числа на ленточку в порядке возрастания. Пусть эти числа разделились на множеста $A_1,\ldots, A_{m-k}.$ Выбрав в каждом из этих множеств наибольший и наименьший элементы, приминая во внимание $(\color{red}{1}),$ мы убеждаемся, что все элементы одного множества стоят подряд на нашей ленточке. Иными словами мы разрезали нашу ленту, на которой $n-k$ числа, на $m-k$ ленточек, что на каждой из них хотя бы 2 два числа. Посчитаем количество способов сделать это методом «шары и перегородки».

Для это рассмотрим следующую биекцию: Разделим $a$ шаров $b-1$ перегородкой, что бы в каждом из $b$ кусков было хотя бы 2 шара. В каждом куске выкинем первый шар, тогда получим разбиение $a-b$ шаров $b-1$ перегородкой, что в каждом куске хотя бы 1 шар, и наоборот, добавляя в такое разбиение по шару на первое место в каждом куске снова получим искомое разбиение. По итогу количество способов разбить искомым образом равно $\dbinom{a-b-1} {b-1} $. (Поскольку между шарами $a-b-1$ мест для $b-1$ перегородок).

По итогу ответ на нашу искомую задачу будет

$$\sum_{k=0}^{m} \dbinom{n}{k}\times \dbinom{n-m-1} {m-k-1} = \dbinom{2n-m-1}{m-1},$$

в последнем равенстве можно убедится, если рассмотреть два множества по $n$ и $n-m-1$ элементов, и выбрать в общем из этих двоих $m-1$ элементов.

Ты жёсткий - сразу после апелляции пошёл писать решение на matol

пока остальные отдыхают, он поднимается