yourdomain.com

Толь забыл комбинаторный анализ, вылетел у меня из головы, то ли что-то не то.
Сформулирую проблему.
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.Например. a=(1, 1, 2, 3, 1)Условие1) rang(a)=dim({1, 1, 2, 3, 1})=3max(a)=max({1, 1, 2, 3, 1})=3rang(a)= max(a).2) ai<=i,i=1, ... , 53) max(a)=3, тогда dim({1, 1, 2, 3})=3.Нужно определить количесто элементов M для произвольного n.Для n=1 будет 1.Для n=2 будет 2.Для n=3 будет 5.Для n=4 будет 15.Для n=5 будет 52.Для n=6 будет 203.Для n=7 будет 877.Для восьми прога 8^8 долго обрабатывала и я недождался .Если кто владеет информацией o формуле для любого n, то поделитесь, плиз. Буду весьма признателен, если кто-то кроме того что поделится формулой,даст краткие разьяснение o том, откуда взялась эта формула.

Mr. Kook писал(а):Source of the post
И третье последнее условие
Пусть max(a)=am, a1<=am<=an, тогда dim({a1, a2, a3, ... , am})=am.

A что делать если am несколько? Условие должно выполняться для каждого? Или для первого попавшегося?

Pavlovsky писал(а):Source of the post

Mr. Kook писал(а):Source of the post
И третье последнее условие
Пусть max(a)=am, a1<=am<=an, тогда dim({a1, a2, a3, ... , am})=am.

A что делать если am несколько? Условие должно выполняться для каждого? Или для первого попавшегося?

Извените, я не уточнил. Для всех am. Смысл в том, напр., если стоит 4, то перед 4 должны быть числа
1, 2, 3. (1, 2, 2, 3, 4, 1, 7). Ho учитывая предыдушие условия, можно считать для для первого попавшегося.

Количество имеет прозрачные рекурентные соотношения. Немного манипуляций c Excel и...



[img]/modules/file/icons/application-octet-stream.png[/img] _________.rar

Pavlovsky писал(а):Source of the post
Количество имеет прозрачные рекурентные соотношения. Немного манипуляций c Excel и...

СПАСИБО ОГРОМНОЕ!
Вот что это за числа, нумера Белла
[url=http://mathworld.wolfram.com/BellNumber.html]http://mathworld.wolfram.com/BellNumber.html[/url]
Извените, что надоедаю, может кто подскажет: как быстро сформировать упомянутое выше множество M без перебора всех елементов множества X?

Так из рекурентных соотношений, ясен и способ построения множества M.
Пусть у нас построено множество .
Множество строится так:
Берется элемент из и сзади добавляется еще одно число (от 1 до max элемента плюс 1). Получются элементы из

Pavlovsky писал(а):Source of the post
Так из рекурентных соотношений, ясен и способ построения множества M.
Пусть у нас построено множество .
Множество строится так:
Берется элемент из и сзади добавляется еще одно число (от 1 до max элемента плюс 1). Получются элементы из

Да, действительно, так оно и есть.
Еще раз выражаю огромнейщую благодарность.
Если вдруг возникнут какие-то интересные вопросы по этой тематике, то я их обязательно вынесу в эту тему

Доброго времени суток, уважаемые участники Форума!

Вопрос o разбиении множества Mn на левые классы Грина (L-классы Грина)
a=(a1, a2, ... , an) из Mn
am=max(a), am-первый попавшийся наибольший элемент, 1<=m<=nНапример, a=(1, 1, 2, 3, 1, 3) , am=3, m=4.Будем говорить, что a и b пребывают в одном L-классе Грина <=>
rang( a )=rang( b ), am=max(a) и
(a1, a2, ... , am)=(b1, b2, ... , bm).
Например, разбиение множества M3={(1, 1, 1), (1, 1, 2), (1, 2, 1),(1, 2, 2), (1, 2, 3)}
L1={(1, 1, 1)},
L2={(1, 1, 2)},
L3={(1, 2, 1),(1, 2, 2)}
L4={(1, 2, 3)}
Для n=4 будет 9 L-классов Грина
Для n=5 будет 24 L-классов Грина
Для n=6 будет 76 L-классов Грина
Для n=7 будет 279 L-классов Грина
Для n=8 будет 1156 L-классов Грина
Для n=9 будет 5296 L-классов Грина
Для десяти долго не смог дождаться.
Обрабатывает 13,5 млрд итераций.
Есть ли формула для подсчёта L-классов Грина?
И может кто подскажет быстрый способ генерации таких L-классов Грина?

Чисто экспериментально было обнаружено.
[url=http://www.research.att.com/~njas/sequences/A005001]http://www.research.att.com/~njas/sequences/A005001[/url]
Оказалось, что это последовательность частичных сумм чисел Белла.
Никто не натолкнет на мысль как доказать такую формулу,
что число всех левых классов Грина определяется c помощью последовательности частичных сумм чисел Белла

-множество всех левых классов Грина, тоесть L-классов Грина.
Известно, что

Берем элемент из и приписываем сзади число n, получаем новый элемент из левого класса Грина длинной n.
Из этого построения следуют выше приведенные формулы.