Раскраска ориентируемого графа

[Sicker]

Пусть есть ориентируемый граф из $n$ вершин, где от каждой вершины к каждой направлен вектор, вектор от А к B не пересекается с вектором от B к А. Каждый вектор окрашен в один из $n-1$ цветов. Каждая вершина испускает $n-1$ разноцветных векторов, в нее входят столько же таких же векторов. Пусть из вершины $1$ исходят фиксированные $n-1$ разноцветных векторов. Вопрос - столько существует таких графов? Для $n=2,3$ ответ очевиден - $1$, для $n=4$ их $2$. Моя гипотеза - для произвольного $n$ будет $(n-2)!$ различных графов, только как это доказать?

-- 31.12.2020, 00:36 --

P.S. Вопрос связан с цепями Маркова - пусть каждое звено имеет $n-1$ переходов $a,b,c,...$ - сколько существует цепей, которые имеют идентичные вершины, т.е. предельное распределение будет всюду $\frac{1}{n}$.
Или другая формулировка, сколько существует матриц $n \times n$, каждый столбец которых перестановка $a_1,...,a_n$, где $a_1+...+a_n=1$, собственный вектор которых $\lambda (1,1,...1)$?

[Sender]

Что значит "вектор от А к B не пересекается с вектором от B к А"?

[Sicker]

Sender
Мы можем провести два вектор-ребра между двумя вершинами, т.е. как в цепях Маркова

[Sender]

Sicker в сообщении #1498398 писал(а):

для $n=4$ их $2$

Всё-таки логика непонятна. Почему их всего два, а не, скажем, 27? Можете их перечислить?

[DeBill]

Sicker в сообщении #1498398 писал(а):

для произвольного $n$ будет $(n-2)!$

Это, видимо, не так, потому что уже $N_4=4$

Sicker в сообщении #1498398 писал(а):

Или другая формулировка, сколько существует матриц $n \times n$, каждый столбец которых перестановка $a_1,...,a_n$, где $a_1+...+a_n=1$, собственный вектор которых $\lambda (1,1,...1)$?

Как то нехорошо переформулировано: ведь надо запретить повторы среди этих чисел, а этого условия на $a_i$ нет, да и условие про собственный вектор реально их не запрещает. Видимо, правильнее формулировать так:
Сколько способов заполнить таблицу $n\times n$ числами от 1 до $n$ так что в каждой строке и в каждом столбце все числа были различны? (Ответ будет отличаться от задачи ТС множителем $n!(n-1)!$). В таком виде задача выглядит естественно - настолько, что возникает подозрение, что она уже решалась (но я - не знаю). Правда, есть опять же естественное подозрение, что ответ будет нехорош - ибо он нехорош уже для первого шага "Сколько способов расставить на шахматной доске 8 ладей так, чтоб они не били друг друга и не стояли на главной диагонали".

[Sender]

DeBill в сообщении #1498451 писал(а):

Сколько способов заполнить таблицу $n\times n$ числами от 1 до $n$ так что в каждой строке и в каждом столбце все числа были различны?

Это же латинские квадраты: A002860.

[mihaild]

DeBill в сообщении #1498451 писал(а):

Сколько способов заполнить таблицу $n\times n$ числами от 1 до $n$ так что в каждой строке и в каждом столбце все числа были различны?

Это вроде бы отличается от задачи ТС добавлением петель (и использованием $n$ цветов; кроме того, у ТС цвета в первой строчке фиксированы). Ну и для $n = 3$ ваша задача имеет $12$ решений (по $2$ для каждой возможной перестановки первой строчки).

[DeBill]

Sender
А, ну да. А исходная задача ТС - это A000315(n)
mihaild
Да. Поправил (вставил пропущенный множитель $(n-1)!$).

[Sicker]

Ой да, я забыл добавить условие для матрицы - на главной диагонали должны стоять $a-1$

Sender в сообщении #1498445 писал(а):

Всё-таки логика непонятна. Почему их всего два, а не, скажем, 27? Можете их перечислить?

Да
Для $n=2$
$\begin{pmatrix} 1 & 2 \\ 2 & 1 \end{pmatrix} \qquad$

$n=3$
$\begin{pmatrix} 1 & 3 & 2\\ 2 & 1 & 3 \\ 3 & 2 & 1\end{pmatrix} \qquad$

$n=4$
$\begin{pmatrix} 1 & 4 & 3 & 2 \\ 2 & 1 & 4 & 3 \\ 3 & 2 & 1 & 4 \\ 4 & 3 & 2 & 1\end{pmatrix} \qquad$
$\begin{pmatrix} 1 & 3 & 2 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 1 \\ 4 & 2 & 3 & 2\end{pmatrix} \qquad$

-- 31.12.2020, 18:28 --

DeBill в сообщении #1498451 писал(а):

Это, видимо, не так, потому что уже $N_4=4$

Почему?

DeBill в сообщении #1498451 писал(а):

Как то нехорошо переформулировано: ведь надо запретить повторы среди этих чисел, а этого условия на $a_i$ нет

Да, точно!

DeBill в сообщении #1498451 писал(а):

Сколько способов заполнить таблицу $n\times n$ числами от 1 до $n$ так что в каждой строке и в каждом столбце все числа были различны?

Я кстати тоже хотел это написать как четвертую формулировку, но у меня еще на главной диагонали единицы

[Sender]

Sicker в сообщении #1498507 писал(а):

$\begin{pmatrix} 1 & 3 & 2 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 1 \\ 4 & 2 & 3 & 2\end{pmatrix} \qquad$

Это опечатка в $\begin{pmatrix} 1 & 3 & 2 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ 4 & 2 & 3 & 1\end{pmatrix} \qquad$?
Чем плоха матрица $\begin{pmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1\end{pmatrix} \qquad$?

[Sicker]

Sender
Да, конечно

-- 31.12.2020, 20:24 --

Ничем не плоха, когда буду за компом напишу еще последнюю четвертую матрицу

[Sender]

Sicker в сообщении #1498524 писал(а):

когда буду за компом напишу еще последнюю четвертую матрицу

Может, лучше всё-таки соберётесь с силами и напишете чёткое определение того, что вам нужно?

[Sicker]

Вот четвертая
$\begin{pmatrix} 1 & 2 & 4 & 3 \\ 2 & 1 & 3 & 4 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1\end{pmatrix} \qquad$

-- 31.12.2020, 22:54 --

Sender в сообщении #1498527 писал(а):

Может, лучше всё-таки соберётесь с силами и напишете чёткое определение того, что вам нужно?

Да уже написали - найти все матрицы $n \times n$ такие, чтобы в каждой строке и в каждом столбце все числа были различны, в первом столбце были бы числа по возрастанию, а на главной диагонали единицы

[Someone]

Sicker в сообщении #1498532 писал(а):

найти все матрицы $n \times n$ такие, чтобы в каждой строке и в каждом столбце все числа были различны, в первом столбце были бы числа по возрастанию, а на главной диагонали единицы

Очевидно, их столько же, сколько приведённых латинских квадратов: A000315.