Перечислить неизоморфные унары

[lamer666]

Назовём унаром пару <A, f>, где A - непустое множество, f: A->A - отображение (всюду определённое) A в себя. Будем говорить, что два унара <A, f> и <B, g> изоморфны, если существует биекция h: A->B такая, что h(f(x))=g(h(x)) для любого x из A. Сколько существует попарно неизоморфных n-элементных унаров? (Наглядно изоморфизм унаров можно представить как топологическую эквивалентность соответствующих диаграмм)
Для маленьких n результаты таковы:
- n=1 число унаров =1
- n=2 число унаров =3
- n=3 число унаров =7
- n=4 число унаров =19
- n=5 число унаров =47
- n=6 число унаров =130
Подойдут любые идеи. Вообще, требуется:
1) Описание перечисляющей (порождающей) программы;
2) Явная/рекуррентная формула.
Есть идеи?

[lofar]

Унар это, в сущности, функциональный орграф, то есть ориентированный граф у которого из каждой вершины выходит ровно одно ребро. Эти графы были перечислены Харари: Harary F. The number of functional digraphs, Math. Ann., 138 (1959), 203--210.

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

[lamer666]

To lofar
А не подойдет книга Харари, Палмер "Перечисление графов"? Или в ней этот вопрос не освещен? До вашего 14 этажа мне из Волгограда далеко!

[lofar]

Да, Есть! (см. с. 90)
Кстати, эта книжка имеется здесь.

[lamer666]

Согласен, формула есть, число неизоморфных унаров можно вычислить, 1-й вопрос снят. 2-й остается: указать эффективную порождающую процедуру .Например, чтобы в программе организовать проверку какого-нибудь свойства по всем унарам фиксированного порядка, достаточно рассмотреть попарно неизоморфные. Если порядок - 8, то таких будет 951, а всех унаров 8 порядка - аж 16777216. У Харари-Палмера в книге этого нет. У Кнута, если не ошибаюсь, тоже.

[bot]

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

ЗЫ. Проблема-то в чём? Может быть конкретнее скажете?

lamer666 писал(а):

До вашего 14 этажа мне из Волгограда далеко!

Уж не от В.Карташова ли задача, случаем?
Ежели увидите, привет ему передайте.

[lamer666]

to bot
Сорри за молчание - праздники!
К вопросу, зачем может понадобиться отобрать по одному представителю из каждого изокласса унаров (и пр. алгебр). Например, чтобы найти простейший (в смысле - наименьшего порядка=мощности носителя), обладающий/необладающий к-л свойством - с помощью программы. Само-собой, абстрактным свойством. Или - хотябы для небольших значений порядка проверить справедливость к-л утверждения. Опять же - с помощью программы. Может быть полезно для первоначальных прикидок, чтобы можно было "пощупать".
С В.К.Карташовым, конечно же, знаком - шеф, как-никак. Вообще-то, такую задачу он мне не ставил, хотя мой интерес в этом направлении - использование компьютера для обременительных прикидок-проверок - поощряет. Привет от хорошего знакомого из Новосибирска обязательно передам.
З.Ы. С праздниками!

[maxal]

Численные результаты со ссылками приведены в A001372. Там же указана Maple'овская программа для подсчета и генерации всех попарно неизоморфных унаров. Типа такой:

> with(combstruct): M:=[F, {F=Set(K), K=Cycle(T), T=Prod(Z, Set(T))}, unlabeled ];
[F, {F = Set(K), K = Cycle(T), T = Prod(Z, Set(T))}, unlabeled]
> c:=n->combstruct[count](M, size=n);
> c(7);
343
> s:=n->combstruct[allstructs](M, size=n);
> s(3);
[Set(Cycle(Prod(Z, Set(Prod(Z, Epsilon), Prod(Z, Epsilon))))), Set(Cycle(Prod(Z, Epsilon)), Cycle(Prod(Z, Set(Prod(Z, Epsilon))))), Set(Cycle(Prod(Z, Epsilon), Prod(Z, Set(Prod(Z, Epsilon))))), Set(Cycle(Prod(Z, Epsilon)), Cycle(Prod(Z, Epsilon)), Cycle(Prod(Z, Epsilon))), Set(Cycle(Prod(Z, Epsilon)), Cycle(Prod(Z, Epsilon), Prod(Z, Epsilon))), Set(Cycle(Prod(Z, Set(Prod(Z, Set(Prod(Z, Epsilon))))))), Set(Cycle(Prod(Z, Epsilon), Prod(Z, Epsilon), Prod(Z, Epsilon)))]