Комбинаторика чётко упорядоченной структуры

Толь забыл комбинаторный анализ, вылетел у меня из головы, то ли что-то не то.
Сформулирую проблему.
X - множество первых n натуральных чисел.
X={1, 2, ..., n}
X^n- n-ая декардова степень множества X.
X^n=XxXxXx...xX={(a1, a2, a3, ... , an): ai in X, i=1, 2, ... , n}
dim(X^n)=n^n - количество элементов X^n.
M - подмножество X^n.
a - произвольный елемент M. Определяется следующим образом.
a=(a1, a2, a3, ... , an).
Вводится понятие ранга a rang(a)=dim({a1, a2, a3, ... , an})
и максимума a max(a)=max({a1, a2, a3, ... , an}).
Для элемента a должно иметь место соотношение rang(a)=max(a) (первое условие).
Числа элемента a занумерованы слева направо, притом для любого ai, i=1, 2, ... , n,
выполнется второе условие ai<=i.
И третье последнее условие
Пусть max(a)=am, a1<=am<=an, тогда dim({a1, a2, a3, ... , am})=am.
Например. а=(1, 1, 2, 3, 1)
Условие
1) rang(a)=dim({1, 1, 2, 3, 1})=3
max(a)=max({1, 1, 2, 3, 1})=3
rang(a)= max(a).
2) ai<=i,i=1, ... , 5
3) max(a)=3, тогда dim({1, 1, 2, 3})=3.
Нужно определить количесто элементов М для произвольного n.
Для n=1 будет 1.
Для n=2 будет 2.
Для n=3 будет 5.
Для n=4 будет 15.
Для n=5 будет 52.
Для n=6 будет 203.
Для n=7 будет 877.
Для восьми прога 8^8 долго обрабатывала и я недождался :-).
Если кто владеет информацией о формуле для любого n, то поделитесь, плиз.
Буду весьма признателен, если кто-то кроме того что поделится формулой,
даст краткие разьяснение о том, откуда взялась эта формула.

Вот ещё одна ссылка - на энциклопедию целочисленных последовательностей:
http://www.research.att.com/~njas/sequences/A000110
Похоже, что хорошей (замкнутой) формулы для чисел Белла нет. Но есть простая рекуррентная схема для их вычисления (треугольник Белла). Ещё известна асимптотика. Наконец, число Белла можно представить как сумму чисел Стирлинга второго рода.

Раскраской множества {1,...,n} будем называть любое отображение c: {1,...,n}->{1,....,n}. Условия, которые сформулировал Mr. Kook, можно короче записать в виде следующей системы:
c(1)=1,
c(k)<=max(c(1),...,c(k-1))+1 при 1<k<=n.
Раскраски, удовлетворяющие системе этих условий, биективно соответствуют разбиениям множества {1,...,n}.
Кстати, как принято называть такие раскраски? Упорядоченные? Нормальные? Нормализованные?

Легко организовать рекурсивный перебор упорядоченных раскрасок. На k-м уровне рекурсии перебирать возможные значения цвета k-го элемента. В качестве одного из аргументов рекурсивной функции передавать ранг уже сформированного куска (максимальное значение среди предыдущих цветов).

Легко сделать и нерекурсивный перебор - для каждой упорядоченной раскраски строить лексикографически следующую.

Цитата

Mr. Kook писал:
Для n=4 будет 9 L-классов Грина
Для n=5 будет 52 L-классов Грина
Для n=6 будет 76 L-классов Грина
Для n=7 будет 279 L-классов Грина
Для n=8 будет 1156 L-классов Грина
Для n=9 будет 5296 L-классов Грина

Для n=5 не 52, а 24 класса.
Нашёл в энциклопедии целочисленных последовательностей:
http://www.research.att.com/~njas/sequences/A005001
Оказалось, что это последовательность частичных сумм чисел Белла.
Числа Белла умеем считать с помощью простой рекуррентной схемы (треугольник Белла).

Цитата

Mr. Kook писал:
И может кто подскажет быстрый способ генерации таких L-классов Грина?

Каждый такой класс задаётся куском упорядоченной раскраски до элемента со значением rang включительно (остальная часть будет разной для разных раскрасок, входящих в этот класс).

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

Для n=15 получается 223578344 класса. Программа работает около минуты (если только перебирать и считать классы, но никуда не выводить).

Любопытно, а для чего нужны эти L-классы Грина?

Вкратце.
В теории реляционных баз данных, а именно для нахождения наиболее близких реляционных связок, там под связкой как известно
понимают упорядоченный набор данных (сортированный кортеж), вобщем что-то вроде элементов множества М.
В криптографии разрабатывались специальные алгоритмы шифрования, связанные с левыми классами Грина (только они не имеют широкого применеия, может быть где-то какая-то организация сама для себя что-то подобное и сделала)
В теоретической физике есть такие себе полугрупповые методы в
суперсимметрических теориях, а там задействованы особенности L-классов Грина, про это подробно сказать не могу, слышал что в терфизике в такой теории применяют, но более детально сказать не могу как конкретно.

Mn - тоже самое множество всех упорядоченных наборов первых n натуральных чисел.
Mn(k) - подмножество множества Mn, у которого все элементы ранга k.
Известно, что количество элементов множества Mn(k) равно числу Стирлинга второго рода,
то есть dim(Mn(k))=S(n, k).
MLn - множество всех L-классов Грина Mn.
MLn(k) - подмножество множества Ln, у которого все L-классы Грина состоят из элементов ранга k.
Известна формула для dim(MLn), но она не даёт отвена на следующий вопрос, хотя я могу и заблуждаться,
а имено: какой формулой определять количество элементов множества MLn(k)?