2014 dxdy logo

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

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


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


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

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

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

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

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



Начать новую тему Ответить на тему
 
 подсчитать количество полных цепочек домино
Сообщение10.12.2007, 12:58 


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

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

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

 Профиль  
                  
 
 
Сообщение10.12.2007, 14:04 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение10.12.2007, 15:57 


10/12/07
6
Спасибо, завтра пойду сдавать

 Профиль  
                  
 
 
Сообщение10.12.2007, 22:03 


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

 Профиль  
                  
 
 
Сообщение10.12.2007, 22:22 
Модератор
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение11.12.2007, 02:31 


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

 Профиль  
                  
 
 
Сообщение11.12.2007, 03:32 
Модератор
Аватара пользователя


11/01/06
5660
Первая, она же последняя вершина, проходится эйлеровым путем 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$. Это и будет ответом.

 Профиль  
                  
 
 
Сообщение11.12.2007, 03:35 


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

 Профиль  
                  
 
 
Сообщение11.12.2007, 04:04 
Модератор
Аватара пользователя


11/01/06
5660
Кстати, ответ $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

 Профиль  
                  
 
 
Сообщение11.12.2007, 04:23 


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

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

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



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

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


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

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