2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Симметричные множества.
Сообщение18.10.2015, 13:55 


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

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$. Из этого следует, что например множество натуральных чисел не симметрично относительно никакой функции.

 Профиль  
                  
 
 Re: Симметричные множества.
Сообщение18.10.2015, 16:52 


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

 Профиль  
                  
 
 Re: Симметричные множества.
Сообщение18.10.2015, 17:01 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Ваши отражающие функции в литературе называются инволюциями на $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

 Профиль  
                  
 
 Re: Симметричные множества.
Сообщение18.10.2015, 17:06 


16/12/14
472
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 Вики, нерекурретная формула.

 Профиль  
                  
 
 Re: Симметричные множества.
Сообщение18.10.2015, 22:38 


16/12/14
472
Пробую решить задачу 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$ (так обозначают в учебнике по дискретной математике Журавлева))

 Профиль  
                  
 
 Re: Симметричные множества.
Сообщение18.10.2015, 23:23 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Симметричные множества.
Сообщение18.10.2015, 23:24 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group