Задача 022 — Задачи на Графы

Пусть $A$ — количество способов, которыми можно разбить множество натуральных чисел от 1 до $n$ на непустые подмножества. Пусть $B$ — количество способов разбить множество натуральных чисел от 1 до $n+1$ на непустые подмножества так, чтобы соседние числа были в разных подмножествах. Разбиения, отличающиеся только порядком подмножеств, считаются одинаковыми. Докажите, что $A=B$ .

Подсказка

Для каждого разбиения чисел от 1 до $n$ занумеруем составляющие его подмножества в порядке, в котором идут их наименьшие числа. Построим дерево с вершинами, помеченными числами от 1 до $n$ , маршруты из корня которого в его висячие вершины будут находиться во взаимнооднозначном соответствии с разбиениями чисел от 1 до $n$ на непустые подмножества. Корень занумеруем цифрой 1 : единица всегда в первом подмножестве. Двойка может лежать либо в подмножестве 1 , либо в подмножестве 2 , поэтому на следующем ярусе расположим соответствующие этим двум случаям вершины, помеченные цифрами 1 и 2 . Что можно сделать после этого?

Решение

Для каждого разбиения чисел от 1 до $n$ занумеруем составляющие его подмножества в порядке, в котором идут их наименьшие числа. Построим дерево с вершинами, помеченными числами от 1 до $n$ , маршруты из корня которого в его висячие вершины будут находиться во взаимнооднозначном соответствии с разбиениями чисел от 1 до $n$ на непустые подмножества. Корень занумеруем цифрой 1 : единица всегда в первом подмножестве. Двойка может лежать либо в подмножестве 1 , либо в подмножестве 2 , поэтому на следующем ярусе расположим соответствующие этим двум случаям вершины, помеченные цифрами 1 и 2 . Далее дерево строится по индукции: если уже построены $k$ ярусов, то с каждой вершиной $C k$ -го яруса связано $m+1$ вершин ( $k+1$ )-го яруса, помеченных числами от 1 до $m+1$ , где $m$ — наибольшее число на маршруте из $C$ в корень дерева.

Теперь построим аналогичное дерево для разбиений чисел от 1 до $n+1$ , где соседние числа находятся в разных подмножествах. Из его корня, помеченного единицей, ведет ребро в единственную вершину второго яруса, помеченную двойкой, а из неё — в две вершины третьего яруса, помеченные единицей и тройкой (двойка невозможна, поскольку тогда числа 2 и 3 попадут в одно подмножество). Далее дерево строится по индукции: если уже построены $k$ ярусов, то с каждой вершиной $C k$ -го яруса связано $m$ вершин ( $k+1$ )-го яруса, помеченных числами от 1 до $m+1$ , исключая число, которым помечена вершина $C$ , где $m$ — наибольшее число на маршруте из $C$ в корень дерева.

Осталось заметить, что если у второго дерева удалить единственное ребро, ведущее из корня во второй ярус, то в новом корне (бывшей единственной вершине второго яруса) у него окажется двойка, и потому получившийся обрубок второго дерева изоморфен первому дереву (доказывается индукцией по ярусам совместно с утверждением, что максимальное число на пути из вершины в корень во втором дереве на 1 больше максимального числа на соответствующем пути в первом дереве).