подсчитать количество полных цепочек домино

[IMED]

Помогите решить задачу. Скоро зачёт а с комбинаторикой у меня плохо.

Сколько существует правильных разложений в игре Домино.
Т.е мы можем пойти с любой кости. И построить цепочку из всех 28 костяшек.
Сколько таких цепочек мы можем построить.

Естественно партия строиться по правилам домино.

[maxal]

Каждое правильное разложение домино соответствует эйлерову пути в полном графе на 7 вершинах с петлями (каждая вершина соединена с каждой и с самой собой). При этом число способов выбрать первую вершину равно 7, число выходов из каждой вершины равно 7, и количество способов выбора исходящих ребер при прохождении каждой из вершин равно 7!. Поэтому количество правильных разложений равно 7 * 7!^7 = 578244878777324666880000000. (см. ниже)

[IMED]

Спасибо, завтра пойду сдавать

[IMED]

Сел я вечером обдумывать решение и что-то мне подсказывает что оно не совсем верно. Друзья посмотрите по внимательнее плиз, а то до зачёта осталось 11 часов.

[maxal]

Да, я не учел, что использованные "входящие" ребра должны исключаться при выборе "выходящих". Соответственно, там не 7! будет, а $4\cdot 6!!=192$ для первой (она же последняя) вершины и $3\cdot 5!!=45$ для всех остальных. Таким образом, ответ меняется на $7\cdot 192\cdot 45^6=11160261000000$.

[IMED]

Можешь пояснить откуда ты взял 4*6!! для первой вершины?

[maxal]

Первая, она же последняя вершина, проходится эйлеровым путем 4 раза. Петля в этой вершине соответственно может пройдена на 1-м, 2-м, 3-м или 4-м проходе - отсюда возникает множитель 4. Выбор прохода остальных 6-ти ребер, инцидентных этой вершине, осуществляется так: сначала у нас есть 6 вариантов выйти из вершины, затем мы попадаем в эту вершину второй раз по какому-то ребру и у нас остается 4 непройденных ребра для выхода. Когда мы приходим в эту вершину в третий раз, то выйти можем уже двумя способами, ну и, наконец, придя в четвертый раз мы уже никуда не выходим - это конец пути. Вот и получается $4\cdot 6\cdot 4\cdot 2 = 4\cdot 6!!$ вариантов.

Для остальных шести вершин все то же самое, только проходим мы каждую из них три раза, и первый раз попадаем по какому-то ребру, оставляя 5 вариантов выхода. Затем 3, затем 1... И получается всего $3\cdot 5!!$ вариантов прохода для каждой вершины.

Добавлено спустя 27 минут 53 секунды:

Хотя тут еще возникает проблема с тем, что путь может закончится раньше чем будут пройдены все ребра (придя четвертый раз раньше чем нужно в первую вершину). Придется привлекать тяжелую артелерию.

Как известно из A007082 число эйлеровых циклов в полном графе $K_7$ равно $129976320$. Каждый цикл проходит каждую из вершин $3$ раза, поэтому число эйлеровых циклов в графе $K_7$ с петлями в каждой вершине равно $3^7\cdot 129976320=284258211840$. И, наконец, количество способов разорвать каждый такой цикл (длины 28) и превратить его в путь равно $28\cdot 284258211840=7959229931520$. Это и будет ответом.

[IMED]

Огромное спасибо
значит для нечётных n костяшек домино получается
(([n/2]+1) * (n-1)!! * (([n/2] * (n-2)!!)^(n-1))*n
а для чётных надо выбрасывать (n-2)/2 рёбер.
Если не сильно тяжело можешь помочь составить формулу для чётных n

[maxal]

Кстати, ответ $7959229931520$ подтверждается другими решениями в сети (например). Все решения, что я видел, так или иначе аппелируют к числу эйлеровых циклов в полном графе, без объяснения откуда оно берется. Попробуйте его вывести сами.

Добавлено спустя 1 минуту 22 секунды:

IMED писал(а):

значит для нечётных n костяшек домино получается
(([n/2]+1) * (n-1)!! * (([n/2] * (n-2)!!)^(n-1))*n

К сожалению, эта формула неверна. См. выше.

Добавлено спустя 12 минут 30 секунд:

Для костяшек домино с номиналами от $1$ до $2n+1$ количество правильных разложений равно:

$$EC(2n+1) n^{2n+1} (n+1) (2n+1)$$

где $EC(2n+1)$ - это число эйлеровых циклов в полном графе $K_{2n+1}$, то есть $EC(2n+1)=$A007082(n)$(n-1)!^{2n+1}.$

Добавлено спустя 13 минут 28 секунд:

Как вычислять количество эйлеровых путей в полном графе описано, например, в этой статье (раздел 6):
Asymptotic enumeration of Eulerian circuits in the complete graph

[IMED]

Огромное спасибо, буду разбираться.