Ломоносов, 2022, 10 класс, задача 7
Есть некоторое количество одинаковых целлофановых пакетов, которые можно вкладывать друг в друга. Если внутри одного из пакетов оказались все остальные пакеты, назовём такую ситуацию «пакетом пакетов». Посчитайте, сколькими способами можно сложить «пакет пакетов» из пакетов.
Пояснение. Обозначим скобочками пакет.
Если у нас был один пакет, то способ сложить «пакет пакетов» всего один: .
Два пакета тоже можно сложить всего одним способом: .
Три пакета можно сложить двумя разными способами: и , и т.д.
Порядок пакетов внутри пакета неважен. Например, вариант не отличается от .
Ответ: .
Решение. Если обозначает число способов для пакетов, то:
Решается задача перебором вариантов. Например, если возьмём :
где -- число способов, соответствующих случаю, когда в корневом пакете находится пакетов.
, способ всего один: .
, способ тоже один: .
, способов разбить пакета на кучки два: и , и . Первому способу соответствует -- два варианта, второму способу -- один вариант, .
способов: .
В сумме получается .
С ростом возникнут случаи, когда надо внимательно относиться к комбинаторике. Скажем, пакетов можно разместить так: , а можно так: . Во втором случае это будет способа, а в первом -- не , а на самом деле всего три, потому что порядок расположения тройных пакетов не важен.