δ = < f >
τ = < 1 >
Sn(δ) = n^n

F = ∀x[f(f(x)) = x]

Найти число моделей для F.

задан 22 Окт '19 19:36

@s18380724: используемую символику надо разъяснить. Что такое delta, tau, Sn? Это же не какие-то общепринятые обозначения.

(22 Окт '19 20:44) falcao

@falcao: δ - набор нелогических символов, называемый нелогической сигнатурой, может состоять из конечного числа так называемых предикатных и функциональных символов, предназначенных, соответственно, для обозначения отношений и функций. Каждому нелогическому символу поставлено в соответствие неотрицательное целое число τ - его местность (арность). Sn(δ) - общее число структур (модели + контр-модели)

(23 Окт '19 16:36) s18380724

@s18380724: теперь для полной ясности надо продолжить объяснение словами. Я понял всё кроме "общего числа структур". Что такое здесь n (фиксированное число, или оно меняется?), и что есть n^n? И что понимается под контр-моделью?

(23 Окт '19 19:40) falcao

@falcao: Контр-моделью называется любая из интерпретаций, при которой данная формула принимает значение ложь. n - может быть любым числом. Например: δ = < R > ; τ = < 2 > ; Sn(δ) = 2^n^2

F = ∀xR(x,x)

Mn(F) - число моделей формулы F ; Mn(F) = 2^(n^2-n)

(23 Окт '19 21:09) s18380724

@s18380724: здесь не хватало важной информации о том, что везде подразумевается подсчёт числа моделей на n-элементом множестве. Теперь суть задачи стала понятной.

(23 Окт '19 23:34) falcao
10|600 символов нужно символов осталось
0

Если отбросить "шелуху", то задача ставится так. Дано $%n$%-элементное множество с одной унарной операцией $%f$%. Ясно, что таких унарных операций имеется $%n^n$%. Требуется найти число таких унарных операций, которые инволютивны, то есть удовлетворяют тождеству $%f(f(x))=x$%.

Обозначим искомую величину через $%a_n$%. Ясно, что $%a_1=1$%, $%a_2=2$% (либо оба элемента неподвижны, либо переходят друг в друга). Выведем рекуррентную формулу. При $%n\ge3$% рассмотрим $%n$%-й элемент множества. Если он переходит при $%f$% в себя, то на оставшемся подмножестве функцию можно задать $%a_{n-1}$% способами. Если он переходит не в себя, то его образ $%y=f(x)$% можно задать $%n-1$% способом. Тогда $%f(y)=x$%. Убираем пару $%\{x,y\}$%, и остаётся $%n-2$%-элементное множество, на котором функция задаётся $%a_{n-2}$% способами. Отсюда $%a_n=a_{n-1}+(n-1)a_{n-2}$%.

По этой формуле легко найти начальные члены последовательности: $%1$%, $%2$%, $%4$%, $%10$%, $%26$%, $%76$%, ... и так далее. Это известная последовательность, она имеется в oeis. Хорошего "замкнутого" выражения для неё не имеется. Можно вычислить или асимптотику, которая по ссылке указана (то есть как быстро она растёт), либо дать формулу в виде суммы. Покажем, как осуществить второе.

Элементы множества при $%f$% либо неподвижны, либо образуют пары переходящих друг в друга. Пусть число пар равно $%k$%, где $%0\le k\le[n/2]$%. Выделить $%2k$%-элементное подмножество "подвижных" элементов можно $%C_{n}^{2k}$% способами. Разбить $%2k$% элементов на пары можно $%(2k-1)(2k-3)\cdot\ldots\cdot3\cdot1$% способами (стандартная задача). Это число выражается через факториалы и степени как $%\frac{(2k)!}{2^kk!}$%. С учётом того, что $%C_n^{2k}=\frac{n!}{(2k)!(n-2k)!}$%, у нас после сокращений и суммирования получается формула $$a_n=\sum\limits_{k=0}^{[n/2]}\frac{n!}{2^k(n-2k)!k!}.$$ Вычислять можно и по ней -- например, $%a_6=1+\frac{6!}{2\cdot4!}+\frac{6!}{2^2\cdot2!2!}+\frac{6!}{2^3\cdot3!}=1+15+45+15=76$%, но рекуррентный способ выглядит попроще.

ссылка

отвечен 23 Окт '19 23:54

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×829
×142
×49

задан
22 Окт '19 19:36

показан
143 раза

обновлен
23 Окт '19 23:54

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru