Задача по комбинаторике, 4 на 4 шахматная доска и домино

[frostysh]

Читаю книгу "Магия Математики" (у меня по украинском) авторства Артур Бенджамин, вот там этот математик написал что если хотите посчитайте сколько возможных способов заполнения шахматной доски 8 на 8 с помощью домино, прямоугольнички 2 на 1 соответственно. Для доски 2 на 2 это будет два варианта, для доски 4 на 4 это будет... Вот тут я и начал считать:



первый слева кружочек, в нем могут вертеться 4 пары домино, и мы различаем только положение вертикально или горизонтально, соответственно два варианта для каждой пары, исходя из принципа умножения в комбинаторике для каждых двух вариантов одной пары, могут одновременно существовать два варианта другой поэтому будет четыре уникальных исхода для двух пар, к этому додаем еще одну, будет восемь уникальных исходов а для четырех пар — соответственно шестнадцать.
Второй кружок, у нас четыре доминины фиксированы, вертеться могут только две пары, итого четыре исхода, но мы эту конструкцию можем повернуть вертикально, поэтому восемь уникальных исходов. Правда будут случаи когда все доминины будут или вертикально, или горизонтально, а это пересекается с множеством исходов с предыдущего кружка, тобиш минус два варианта.
Третий кружек по аналогии, оборачиваем и отнимаем похожие исходы.

Ответ получается 50 комбинаций всего, НО судя по вот этому: The On-Line Encyclopedia of Integer Sequences, A004003, я гдето накопал четырнадцять повторяющихся комбинаций! Но не могу понять где... Пардон что по таким пустякам беспокою ваш форум, мож завтра проснусь и найду сам ошибку, но все-же...

[Yadryara]

frostysh в сообщении #1389924 писал(а):

НО судя по вот этому: The On-Line Encyclopedia of Integer Sequences, A004003,

Для начала обратите внимание, что на нашем форуме есть тег [oeis][/oeis]. Соответственно, и давать ссылки, и пользоваться ими очень удобно: A004003.

frostysh в сообщении #1389924 писал(а):

я гдето накопал четырнадцять повторяющихся комбинаций! Но не могу понять где...

Так там же как раз приводится пример именно для квадрата $4\times 4$:

Цитата:

A01 = {(1,2), (3,4), (5,6), (7,8), (9,10), (11,12), (13,14), (15,16)}
A02 = {(1,2), (3,4), (5,6), (7,11), (9,10), (8,12), (13,14), (15,16)}
A03 = {(1,2), (3,4), (5,9), (6,7), (10,11), (8,12), (13,14), (15,16)}
...
A35 = {(1,5), (2,3), (6,7), (4,8), (9,13), (10,14), (11,15), (12,16)}
A36 = {(1,5), (2,3), (6,7), (4,8), (9,13), (10,11), (14,15), (12,16)}

В чём проблема? Рисуйте, да сверяйте. Или вам не понятны обозначения? В скобках указаны номера клеток квадрата, которые занимает та или иная доминошка. Клетки квадрата перенумерованы, например, слева направо и сверху вниз. Первая строка — от $1$ до $4$ включительно, вторая — от $5$ до $8$ и т. д.

[frostysh]

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

П. С. Вы даже просто цифры пишете в Латехе?! Не ленитесь. :) (Не люблю Латех, неудобное оно мне...)

[Someone]

(frostysh)

frostysh в сообщении #1389948 писал(а):

Вы даже просто цифры пишете в Латехе?! Не ленитесь.

Правила требуют.

[frostysh]

Хуууух! Победил таки эту задачу! Вот что бывает когда протираешь штаны в универе, а на старости лет решаешь серьезно заняться наукой, не могешь решить школьной задачи... (О старости шутка, мне под тридцять, но просто)

Как я и предполагал раньше, сначала можно начать вертеть только пары, а не домино, а не отдельные домино, их всего четыре (восемь домининок). Как я и думал, поскольку два варианта горизонтальный/вертикальний у нас будет два в степени четыре различных исходов (правило умножения одновременных вариантов). Удобно фиксировать по две пары, а потом перебирать остальные две пари, вертеть то есть. Фиксированные пари или домининки зачеркнутые на рисунке выше. Всего фиксированных, различных пар будет четыре. Что и изображено в розовых квадратиках сверху.

Далее будем фиксировать сначала крайние домино а потом, для удобства (как мы это делали с парами) дофиксируем еще и пару по центре. Можно использовать и при этом полностью замощая достку, только шесть вариантов фиксаций крайних домино. Это уже будет друга череда комбинаций, и нам нужно отбросить одинаковые варианты в общем бассейне. Каждая фиксация пары посредине зафиксированных двух крайних домино, дает четыре дубликата, а фиксация пары между четырьмя зафиксированными крайними, дает два дубликата.

В конечном итого это все складываем, отнимаем и получаем пресловутые тридцать шесть уникальных исходов! Теперь осталось как нить "подлахламить" это все чтобы посчитать для восемь на восемь шахматной доски.

Someone в сообщении #1389984 писал(а):

(frostysh)

frostysh в сообщении #1389948 писал(а):

Вы даже просто цифры пишете в Латехе?! Не ленитесь.

Правила требуют.

(Offtopic)

Тю, даже отдельные числа? Мож какая-то программа есть чтобы допустим автоматически ставить эти Латех-теги цифрам?

[svv]

(Оффтоп)

Привыкнете — даже замечать не будете, рука на автомате будет набирать $42$ вместо 42. А зато как формулы красиво выглядят! Если что — Вам не надо сразу изучать весь $\TeX$, сначала достаточно небольшого подмножества, по мере роста потребностей оно будет потихоньку расширяться.

[frostysh]

svv в сообщении #1390009 писал(а):

(Оффтоп)

Привыкнете — даже замечать не будете, рука на автомате будет набирать $42$ вместо 42. А зато как формулы красиво выглядят! Если что — Вам не надо сразу изучать весь $\TeX$, сначала достаточно небольшого подмножества, по мере роста потребностей оно будет потихоньку расширяться.

(Оффтоп)

Не я думал там эти, скобки квадратные надо и tex а потом /tex, ну знаком доллара попроще будет конечно. Вообще никогда особо не фанател от Латеха, так сказать... Ну не нравиться оно мне... Пока начеркаешь ту формулу, можно всю мыслю упустить. Жаль альтернативы нету, поэтому буду конечно изучать. Я ж типа планирую через сто год какую-то статью написать, хоть какую-нить, а это все в Латехе нужно, там эти, правила приема во всех журналах. А так в себе на компе, если надо формулу так я ее осуществляю на планшете, только не таком как мобильный а на старом, без мониторов, просто с ручкой электронной в программе GIMP, — очень удобно, жаль батарейки надо менять частенько.

По задачи понял что часть ответа будет $36^{4}$, так-как можно легко, без остачи поделить $8 \times 8$ площадку на $4$ ровных квадратика, для которых число расстановок домино мы уже нашли. Но это будет $36^{4} = 1,679,616$ а правильный ответ: $12,988,816$, что и на порядок больше... Это потому что домино на доске восемь на восемь не обязательно должны полностью лежать на одном из квадратиков четыре на четыре, они могу лежать и на двух таких квадратиках одновременно, это пересечение додает тучу возможностей. Придется как нибудь еще поделить эту глупую доску, чтобы было пересечение, а потом сложить число комбинаций...

[svv]

(Оффтоп)

frostysh в сообщении #1390047 писал(а):

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

Я тоже!
http://dxdy.ru/post1091820.html#p1091820

[Yadryara]

frostysh, возможно, рановато переходить к доске $8\times 8$. Вы уже поняли, как получается та самая формула с косинусами для досок $2\times 4$, $2\times 6$, $2\times 8$ ?