Арифметика на тривиальных множествах

Если обозначить через {} пустое множество, а через {x} - одноэлементное множество с элементом x, то с помощью операции "U" объединения множеств можно построить структуры, назвав их тривиальными множествами, являющиеся по сути множествами и эквивалентные неориентированным деревьям. Формально, множество таких структур T вводится индуктивным способом (отношение "@" здесь и далее означает принадлежность элемента множеству):

{} @ T;
x @ T => {x} @ T;
x @ T & y @ T => x U y @ T.

Оказывается, на тривиальных множествах можно ввести арифметику и даже определить списки, то есть упорядоченные последовательности элементов, несмотря на неупорядоченность самих множеств.

( Арифметика и списки )

Вычисление чисел Каталана

Задача о нахождении количества вариантов скобочных структур возникает во многих областях комбинаторики, а ее решением являются так называемые числа Каталана: (2n)!/((n + 1)!n!). Один из многочисленных способов вычисления этих чисел следующий.

( Способ вычисления )