Симметричные множества.

[Pulseofmalstrem]

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

1) Множество зеркальное относительно функции.
Пусть дано множество $M$ и функция $f$, определенная в том числе и на $M$. Будем называть множество $M$ зеркальным относительно $f$, а функцию $f$ отражающей функцией, если выполнены следующие 2 условия:
1) Замкнутость относительно $f$.
Для всех элементов $x$ множества $M$ элемент $f(x)$ также лежит в $M$.
$\forall x \in M \rightarrow f(x) \in M$
2) Сопряженность относительно $f$.
Для всех элементов $x$ множества $M$ элемент $f(f(x)) = x$.
$\forall x \in M \rightarrow f(f(x)) = x$

Замечания:
1) Договоримся считать пустое множество зеркальным относительно любой функции для удобства (если необходимо в дальнейшем непустота будет оговариваться).
2) Элемент $f(x)$ будем называть сопряженным с элементом $x$.

Предложение 1.
Если множества $A$ и $B$ зеркальны относительно функции $f$, то их объединение также зеркально относительно $f$.
Доказательство.
Рассмотрим два случая:
1) Множества $A$ и $B$ не имеют общих элементов.
Тогда из определения зеркальных множеств следует:
$\forall x \in A \rightarrow f(x) \in A$
$\forall x \in B \rightarrow f(x) \in B$
Очевидно:
$\forall x \in (A \cup B) \rightarrow f(x) \in A (\cup B)$
Аналогично показываем сопряженность, стало быть сумма двух непересекающихся зеркальных множеств также зеркальна.

2) Множества $A$ и $B$ имеют общие элементы.
Тогда существует непусто множество $C = A \cap B$
Оно, очевидно, зеркально относительно $f$, исходя из тех же соображений, что и в пункте 1.
Введем еще два множества $M = A / C; N = B / C$, тогда остается показать их зеркальность относительно $f$, и тогда, так как они не имеют общих элементов, их сумма будет также зеркальна относительно $f$.
Покажем зеркальность $M$ (Для $N$ доказывается аналогично.
2.1) Для начала покажим выполнение сопряженности относительно $f$ :
$\forall x \in M \rightarrow f(f(x)) = x$
Но это верно, так как $M \subset A$, а $A$ зеркально относительно $f$
2.2) Докажем замкнутость относительно $f$:
$\forall x \in M \rightarrow f(x) \in M$
Предположим, что это не выполняется, тогда будет существовать элемент $x_0 \in M$, такой что $f(x_0) \notin M$
$\exists x_0 \in M: f(x_0) \notin M$
Но так как $x_0 \in M, M \subset A \rightarrow x_0 \in A$.
А $A$ зеркально относительно $f$, тогда $f(x_0) \in A, f(x_0) \notin M \rightarrow f(x_0) \in C$.
Но так как $C$ зеркально относительно $f$, то то элемент сопряженный с элементом $f(x_0)$ также должен лежать в $C$, но мы уже доказали что $f(f(x_0)) = x_0 \in M$. Противоречие, значит $M$ замкнуто относительно $f$, а значит зеркально относительно $f$.


Предложение 2.
Всякое зеркальное относительно $f$ множество $M$ (в дальнейшем фразу зеркально относительно $f$ буду опускать) можно представить как сумму двух зеркальных множеств, причем если мощность $M$ больше 2, то двух непустых зеркальных множеств.
Доказательство.
Выберем из $M$ произвольное число несопряженных друг с другом элементов, а потом добавим к ним сопряженных с ними, получим множество $N = {x, f(x), y, f(y), ... }$. Оно очевидно зеркально, так как сопряженность следует из сопряженности $M$, а замакнутость из построения.
Остается показать зеракальность множества $P = M / N$
1) Множество P сопряжено, что следует из сопряженности $M$.
$\forall x \in P \rightarrow f(f(x)) = x$
2) Докажем замкнутость $P$.
Предположим, что это не так, тогда существует $x_0$ такой, что $f(x_0) \notin P$, но так как $x_0 \in M$, то $f(x_0) \in M$, а значит $(f_0) \in N$, но так как $N$ зеркально, то тогда $f(f(x_0)) \in N$, что неверно, так как мы уже доказали, что $f(f(x_0)) = x_0 \in P$. Противоречие, значит $P$ замнкуто и сопряжено, а значит зеркально.
Вот мы и разбили множество $M$ на два зеркальных множества. Если мощность $M$ больше 2, то в $N$ достаточно положить 1 элемент и сопряженный к нему. Тогда в $P$ останется хотябы 1 элемент.

Задача 1.
Дано конечное непустое множество $M$ мощностью $n$. Сколько существует функций вида $M \to M$, относительно которых $M$ зеркально?
1) Для начала вычислим количество функций, относительно которых множество $M$ не зеркально. Поскольку $M$ конечно, то функции могут быть полностью заданы таблицей:
$ m_1 \to m_i$
$ m_2 \to m_j$

$ \dots \dots$

$ m_n \to m_k$
Так как для зеркальности требуется сопряженность, то мы свободно можем определить только половину таблицы, число отражающих функций $s = n^{n // 2}$ (где $//$ - деление нацело с округлением вниз, вроде бы правильно)


-- 18.10.2015, 14:12 --

Задачи, которые я еще пока не решил:

Задача 2.
Дано непустое, конечное множество $M$ мощностью $n$. Сколько существует функций вида $M \to M$, относительно которых не зеркально ни одно непустое подмножество $M$.

Задача 3 (О симметрчных расстановках крестиков на доске).
Назовем областью тривиальности функции такое множество агрументов $x$, что $f(x) = x$.
Дано непустое, конечное множество $M$ и функция $f:M /to M$, и известная ее область тривиальности $T$.
Сколько существует зеркальных относителньо $f$ подмножеств $M$?
Набросок решения:
По предложению 2 каждое зеркальное подмножество мощности $m$ можно представить как сумму двух подмножеств мощности $1$ и $m - 1$, так мы сможем снижать мощность рассматриваемых подмножеств, а количество зеркальных подмножеств мощности 1 и 2 нам известны из области тривиальности.

Часть 2. Определение симметричного множества относительно f.
Часто когда речь идет о симметрии геометрической подразумевается равенство "расстояний от точки и ее отражения до центра симметрии", но как нам адптировать это представление в нашу модель? Я пока рассматривую такой вариант (для полностью упорядоченных множеств)
Множество $M$ симметрично относительно функции $f$, если оно зеркально отностлньо $f$ и выполнено условие:
$ \forall x \in M, \forall y \in M, y \geqslant x \right \rightarrow f(x) \geqslant f(y)$
То есть для всех элементов $x$ отражение любого элемента $y$ большего $x$, будет меньше чем отражение $x$. Из этого следует, что например множество натуральных чисел не симметрично относительно никакой функции.

[Pulseofmalstrem]

Задача 1 решена неверно. Я не учел тот факт, что в первых $n // 2$ строках могут быть тождествав таблице.

[Xaositect]

Ваши отражающие функции в литературе называются инволюциями на $M$.

Pulseofmalstrem в сообщении #1063927 писал(а):

Так как для зеркальности требуется сопряженность, то мы свободно можем определить только половину таблицы, число отражающих функций $s = n^{n // 2}$ (где $//$ - деление нацело с округлением вниз, вроде бы правильно)

Неверно, так как не учитывается, что элемент может переходить в себя, и не учитывается, что элементы из верхней половины не обязательно переходят в элементы из нижней половины. При $n=3$ расхождение - $n^{\lfloor n/2\rfloor} = 3$, а количество инволюций равно $4$ (тождественная функция и 3 функции, которые оставляют 1 элемент на месте).

Любая инволюция разбивает $M$ на множество неподвижных точек $M_0 = \{x\mid f(x) = x\}$ (у вас потом называется областью тривиальности) и оставшееся множество, состоящее из пар, элементы которых инволюция переводит друг в друга.

Количество инволюций на OEIS: A000085
Количество инволюций можно считать рекурсивно. Обозначим количество инволюций на $n$-элементом мноежстве $I(n)$. Рассмотрим множество $M$ из $n$ элементов и фиксированный элемент $x\in M$. Любая инволюция либо оставляет $x$ на месте, а на оставшемся множестве действует одним из $I(n-1)$ вариантов, либо переводит $x$ в один их оставшихся из $n-1$ элементов, а на остальных $n-1$ действует одним из $I(n-1)$ способов. Получается $I(n) = I(n-1) + (n - 1) I(n - 2)$. Вроде это никак хорошо не сворачивается, но можно посчитать экспоненциальную производящую функцию из уравнения $\mathcal{I}'(x) = \mathcal{I}(x) + x\mathcal{I}(x)$, $\mathcal{I}(0) = 1$, откуда $\mathcal{I}(x) = e^{x + x^2/2}$ и найти асимптотику методом Хэймана (см. Wilf "generatingfunctionology", последняя глава).

Цитата:

Задача 2.
Дано непустое, конечное множество $M$ мощностью $n$. Сколько существует функций вида $M \to M$, относительно которых не зеркально ни одно непустое подмножество $M$.

Иными словами, у функции не должно быть неподвижных точек и циклов длины $2$. OEIS: A134362

[Pulseofmalstrem]

Xaositect
Ну ошибку в своей задаче 1 я осознал, но все равно спасибо, почитаю на досуге, что там понапридумывали до меня. Спасибо за ссылки.

Цитата:

Иными словами, у функции не должно быть неподвижных точек и циклов длины $2$.

Да-да, ятоже хотел так решать, правда я хотел представлять функции как граф. Сбрасываем все элементы на плоскость и соединяем все точки между собой. Ну и тамдальше циклы ищем. Правда сложность в том, что могут быть два непересекающихся между собой цикла.

-- 18.10.2015, 17:28 --

Xaositect в сообщении #1064000 писал(а):

Количество инволюций можно считать рекурсивно. Обозначим количество инволюций на $n$-элементом мноежстве $I(n)$. Рассмотрим множество $M$ из $n$ элементов и фиксированный элемент $x\in M$. Любая инволюция либо оставляет $x$ на месте, а на оставшемся множестве действует одним из $I(n-1)$ вариантов, либо переводит $x$ в один их оставшихся из $n-1$ элементов, а на остальных $n-1$ действует одним из $I(n-1)$ способов. Получается $I(n) = I(n-1) + (n - 1) I(n - 2)$. Вроде это никак хорошо не сворачивается, но можно посчитать экспоненциальную производящую функцию из уравнения $\mathcal{I}'(x) = \mathcal{I}(x) + x\mathcal{I}(x)$, $\mathcal{I}(0) = 1$, откуда $\mathcal{I}(x) = e^{x + x^2/2}$ и найти асимптотику методом Хэймана (см. Wilf "generatingfunctionology", последняя глава).

$ I(n) = \sum\limits_{k = 0}^{[n / 2]}\frac{n!}{2^{k}(n - 2k)! k! }$
C Вики, нерекурретная формула.

[Pulseofmalstrem]

Пробую решить задачу 3. Переформулируем условие в общепринятыз терминах:
Дано конечное, непустое множество $M$ мощностью $n$, на котором определена инволюция $f: M /to M$, для которой известна мощность множества неподвижных точек $t$. Посчитать число подмножеств M, для которых $f$ также инволюция.
Элементы являющиеся неподвижными точками будем называть одиночными элементами, а те которые обрзуют пары - парными. Обозначим общее число пар за $p = \frac{n - t}{2}$

1) По предложению 1 подмножество мощностью $m$ может быть образовано слиянием одиночного элемента с подмножеством мощностью $m - 1$, в котором этот элемент не лежит, или слияним пары с подмножеством мощности $m - 2$, в котором эта пара не лежит.

2) Каждый раз когда я образую подмножество добавлением 1 элемента, я уменьшаю число одичноных элементов которые оно может в дальнейшем принять на 1. Аналогично для пар.

В таком случае хорошо было бы узнать число подмножеств длины $m$ было образовано добавлением $i$ одиночных элементов, аналогично для пар: сколько подмножеств длины $m$ было образовано добавлением $j$ пар. Если оформить это ввиде функции:
$f(m, i)$ - показывает в скольких подмножествах длины $m$ лежит $i$ одиночных элементов.
$g(m, j)$ - показывает в скольких подмножествах длины $m$ лежит $j$ пар.
В каждое подмножество содержащее $i$ одиночных элементов можно добавить $t - i$ элементов, аналогично для пар.
Тогда можно представить число подмножеств длины $m$ по формуле:
$N(m) = \sum\limits_{i = 0}^{m - 1}f(m - 1, i)(t - i) + \sum\limits_{j = 0}^{\frac{m - 2}{2}}g(m - 2, j)(p - j)$

Остается определить вид функций $f(m, i)$ и $g(m, j)$. Сделаем это из реккуретных соображений.

1) $f(m, i)$ показывает сколько подмножеств длины $m$ содеражат в себе $i$ единичных элементов. Предположим мы знаем это данное значение, тогда мы можем добавить в каждое из этих множеств множество один из $t - i$ разнообразных одиночных элементов и получить множества длины $m + 1$ по $i + 1$ элементов в каждом. Тогда имеет место реккуретное соотношение:
$f(m + 1, i + 1) = (t - i)f(m,i) $

2) Остается найти базис реккуретного соотношения:
2.1) Очевидно, что
$f(2k, 1) = 0$ (Подмножества из четного числа элементов не могут содердать в себе ровно 1 одиночных элемент, потому как тогда пары бы должны были покрыть нечетное число элементов)
$f(2k + 1, 1) = t [p]_k$(Равно количеству одиночных элементов умноженному на количество множеств длины $2k$, состоящих из одних только пар, $[p]_k = p(p - 1)(p - 2)...(p - k + 1)$ - $k$ нижняя ступень $p$ (так обозначают в учебнике по дискретной математике Журавлева))

[Xaositect]

Зачем это все? Нужно просто взять некоторое подмножество неподвижных точек и некоторое подмножество пар, всего вариантов будет $2^{t}\cdot 2^p$

[Pulseofmalstrem]

Xaositect
Упс, действительно красиво=) Ну и заданную длину можно получить через биноминальные коэффициенты, ну типо длина 5 это 5 неподвижных точек, 3 неподвижные точки и 1 пара, 1 точка и 2 пары. Логично.