Розбиття множини

Розглянемо множину, яка складається з перших $n$ натуральних чисел: N_n = \{1, 2, \ldots, n\}. Розбиття — це подання цієї множини у вигляді об'єднання однієї чи декількох непорожніх підмножин. Прикладами розбиття для n = 5 є:

Всього існує $52$ розбиття множини N_5. Зауважимо, що розбиття, які відрізняються лише порядком об'єднуваних підмножин, не вважаються різними.

Розбиття множини N_n можна впорядкувати лексикографічно.

Щоб визначити цей порядок, спочатку задаємо лексикографічний порядок на підмножинах N_n. Кажемо, що множина A \subset N_n лексикографічно менша за множину B \subset N_n (позначається A \prec B), якщо виконується одна з таких умов:

• існує $i$ таке, що i \in A, i \notin B і для всіх j < i, j \in A тоді й лише тоді, коли j \in B, і існує k < i, таке що k \notin A, k \in B;

• A \subset B та i < j для всіх i \in A і j \in B \setminus A.

Очевидно, що це відношення є повним порядком на підмножинах N_n. Тепер визначимо канонічне подання розбиття як подання, у якому об'єднувані підмножини упорядковано лексикографічно.

Розбиття впорядковуються лексикографічно наступним чином. Розбиття N_n = A_1 \cup A_2 \cup \ldots \cup A_k лексикографічно менше розбиття N_n = B_1 \cup B_2 \cup \ldots \cup B_l, якщо існує $i$ таке, що A_1 = B_1, A_2 = B_2, ..., A_{i-1} = B_{i-1} і A_i \prec B_i.

За поданим розбиттям множини N_n знайдіть наступне у лексикографічному порядку розбиття.