Сколькими способами его можно разрезать

Полоски из домино

Задача

а) Сколькими способами можно замостить полосу 2×10 доминошками 2×1? Замощения, получающиеся друг из друга вращением полосы, считаются разными; например, на рисунке 1 изображено два разных замощения полоски 2×3.
б) Тот же вопрос для полосы 3×30.

Подсказка 1

а) Попробуйте искать ответ на поставленный вопрос как частный случай более общей задачи: сколькими способами можно замостить доминошками полосу 2×n для произвольного натурального числа n? Обозначим число замощений такой полосы через a_n — это даст последовательность чисел. Как связан очередной элемент этой последовательности с предыдущими?

б) Можно ли воспользоваться теми же соображениями, что и в пункте а)?

Подсказка 2

б) Действовать совсем аналогично пункту а) не получится: замостить доминошками фигуру, состоящую из нечетного числа клеток, невозможно. Поэтому нужно рассматривать только полосы четной длины. Пусть b_n — число замощений полосы 3×2n доминошками. Как связан очередной элемент этой последовательности с предыдущими?

Решение

а) Для начала заметим, что a₁ = 1, a₂ = 2 — соответствующие замощения изображены на рис. 2. Далее, предположим, что для некоторого натурального n все значения от a₁ до a_n нам уже известны. Как найти a_n+1? Для этого рассмотрим левую верхнюю клетку полосы 2×(n + 1). В каждом замощении она покрыта некоторой фигуркой домино, вертикальной или горизонтальной (рис. 3). В первом случае мы можем отрезать эту доминошку, так что оставшаяся фигура будет представлять собой полосу 2×n. Последнее означает, что количество замощений полосы 2×(n + 1), у которых левая верхняя клетка покрыта вертикальной фигуркой домино, совпадает с числом замощений полосы 2×n и равно a_n. Что же касается второго случая, то в нем со всей определенностью левая нижняя клетка также будет покрыта горизонтальной фигуркой домино, а вместе эти доминошки образуют квадрат 2×2, отрезав который, мы получим полосу 2×(n − 1). Следовательно, количество замощений полосы 2×(n + 1), у которых левая верхняя клетка покрыта горизонтальной фигуркой домино, совпадает с числом замощений полосы 2×(n − 1) и равно a_n−1.

Суммируя полученные результаты, мы получаем следующее рекуррентное соотношение: a_n+1 = a_n + a_n−1. В этом месте читатель, знакомый с числами Фибоначчи, сразу скажет ответ. Но и не обладая подобным знанием, последовательным вычислением нетрудно найти, что a₃ = 3, a₄ = 5, a₅ = 8, a₆ = 13, a₇ = 21, a₈ = 34, a₉ = 55, a₁₀ = 89.

Отметим, что полученное нами соотношение справедливо также для n = 1, если считать, что a₀ = 1: в этом случае равенство a_n+1 = a_n + a_n−1 превращается в 2 = 1 + 1. Указанное соображение будет справедливо и для пункта б), что в ближайшее время сослужит нам добрую службу.

б) К полосе 3×30 применимо аналогичное, хотя и несколько более хитрое рассуждение. Для начала можно заметить, что b₀ = a₀ = 1, b₁ = a₃ = 3. Далее, предположим, что для некоторого натурального n все значения от b₀ до b_n уже известны, и попробуем выразить через них b_n+1. Для этого рассмотрим доминошку, которой накрыта левая средняя клетка, — имеется три возможных варианта ее расположения. В одном из них рассматриваемая доминошка горизонтальна, и легко видеть, что количество таких замощений полосы 3×2(n + 1) совпадает с числом замощений полосы 3×2n, которое равно b_n. В оставшихся двух вариантах доминошка вертикальна, а каждый из этих вариантов естественным образом разбивается на два случая: в одном из них количество замощений равно b_n, а в другом снова возможно подразбиение на два вида слагаемых, и т. д. (рис. 4).

Продолжая рассуждение указанным образом, приходим к выводу, что последовательность b_n должна удовлетворять следующему соотношению:

Складывая вместе подобные слагаемые, мы приходим к более компактной версии:

В принципе, полученное соотношение уже вполне пригодно для того, чтобы вычислить b₁₅, особенно если для этой цели использовать компьютер. Но если хочется посчитать искомое значение вручную, удобнее сначала упростить полученное выражение. Для этого достаточно вычесть из обеих частей последней формулы то же соотношение, но выписанное не для b_n+1, а для b_n. Сделав это, получим

или, после очевидных преобразований:

Последнее выражение позволяет получить ответ довольно быстро даже вручную: b₂ = 11, b₃ = 41, b₄ = 153, b₅ = 571, b₆ = 2131, b₇ = 7953, b₈ = 29 681, b₉ = 110 771, b₁₀ = 413 401, b₁₁ = 1 542 841, b₁₂ = 5 757 961, b₁₃ = 21 489 003, b₁₄ = 80 198 051, b₁₅ = 299 303 201.

Послесловие

В подсказках к задаче предлагалось подумать над более общим вопросом: сколькими способами можно замостить фигурками домино полоски 2×n и 3×2n? Вполне возможно, что читатель резонно поинтересуется, как обстоит дело с ответом на него. Оказывается, если последовательность удовлетворяет линейному рекуррентному соотношению, то существует формула для ее n-го элемента, которую можно найти, воспользовавшись методом производящих функций. В частности, для чисел Фибоначчи a_n справедлива формула Бине:

а элементы b_n удовлетворяют соотношению

Продемонстрируем на примере последовательности b_n, как работает метод производящих функций. Для начала определим производящую функцию этой последовательности — бесконечную формальную сумму вида \( B(x)=b_0+b_1x+b_2x^2+b_3x^3+ \ldots \). Заметим, что если умножить ее на \((1-4x+x^2) \) и раскрыть скобки, то за счет того, что для всех натуральных n выполняется соотношение \( b_=4b_n-b_ \), почти все сократится:

Таким образом, разделив на \((1-4x+x^2) \), с учетом равенств b₀ = 1 и b₁ = 3 получим выражение для B(x):

мы можем разложить эту дробь на сумму простейших:

После чего, дважды воспользовавшись формулой для суммы геометрической прогрессии,

убеждаемся, что производящая функция B(x) принимает искомый вид:

Можно не ограничиваться замощениями полос и попытаться перейти к еще более общим вопросам. Рассмотрим какую-нибудь связную область Γ на клетчатой бумаге. Естественно полюбопытствовать, во-первых, можно ли в принципе замостить Γ доминошками, а во-вторых, если это возможно, то сколькими способами. Первое, что приходит в голову — раскрасить клетчатую бумагу в черный и белый цвета, как это делают с шахматной доской, и посчитать, сколько клеток какого цвета входит в область Γ. Так как каждая фигурка домино покрывает две клетки разных цветов, получаем необходимое условие: если замощение области Γ доминошками существует, то число черных и белых клеток внутри Γ совпадает. Однако достаточным указанное условие не является; убедиться в этом помогает пример, изображенный на рис. 5.

Тем не менее, существуют методы, которые не только отвечают на поставленные вопросы, но и делают это за полиномиальное время (это значит, что количество требуемых для ответа на вопрос операций зависит от размера входных данных — размера области Γ в данном случае — как многочлен), то есть довольно быстро. Опишем подход, восходящий к голландскому физику Питеру Кастелейну (Pieter Kasteleyn). Пусть область Γ состоит из n черных и n белых клеток. Пронумеруем их от 1 до 2n таким образом, чтобы сначала шли черные клетки, а затем — белые, после чего сопоставим области Γ матрицу K = (K_uv) размера 2n×2n согласно следующему правилу (здесь \(i=\sqrt<-1>\) — мнимая единица):

Тогда оказывается справедливой теорема Кастелейна, утверждающая, что количество замощений области Γ доминошками равно \(\sqrt<|\det|>\) (det — это определитель матрицы). Учитывая, что соседними клетками могут быть только клетки разных цветов, легко видеть, что матрица K на самом деле имеет блочный вид

\[ A=\begin 1 & i & 0\\ i & 1 & i\\ 0 & i & 1 \end, \]

а число замощений равно \(\sqrt<|\det^2|>=\det=3\).

Замощение доминошками областей на клетчатой бумаге можно интерпретировать как частный случай еще более общей задачи. Именно, рассмотрим произвольный граф H. Совершенным паросочетанием (или димерной упаковкой) графа H называется любой набор его ребер, в котором каждая вершина графа встречается ровно один раз. Ясно, что если вершины графа H суть центры клеток некоторой области Γ на клетчатой бумаге, а ребрами соединены те из них, для которых соответствующие клетки являются соседними, то вопрос о количестве совершенных паросочетаний графа H превращается в точности в вопрос о числе замощений области Γ фигурками домино. Например, на рис. 7 изображены граф, отвечающий области Γ с рис. 6, а также его совершенные паросочетания.

Совершенные паросочетания тесным образом связаны с остовными деревьями. Напомним, что деревом называется любой связный граф без циклов. Если же дан связный граф G, то его остовное дерево — это дерево, вершины которого совпадают с вершинами графа G, а каждое ребро является ребром графа G. Выясним, как каждому остовному дереву графа G сопоставить совершенное паросочетание некоторого графа H. Для этого сделаем дополнительное предположение, что граф G — плоский, то есть что его можно расположить на плоскости так, чтобы его ребра не пересекались нигде, кроме вершин. Тогда плоскость окажется разбита ребрами графа G на области, называемые гранями, среди которых будет неограниченная по размеру внешняя грань. Будем обозначать множества вершин, ребер и граней графа G буквами V, E и F соответственно.

Построим на основе графа G новый, расширенный граф H. Для этого отметим вершины, середины ребер и центры граней («центром» грани можно считать любую точку внутри этой грани) исходного графа — это будут вершины нового графа, а ребрами соединим такие пары вершин, для которых соответствующие объекты в исходном графе инцидентны (рис. 8)

Рис. 8. Соответствие между остовным деревом графа G и паросочетанием графа H. Вершины графа G отмечены черными точками, середины его ребер — белыми, а центры граней — серыми. Обратите внимание, что для удобства внешняя грань графа G отмечена не точкой, а внешним контуром

Заметим, что в графе H имеется только два типа ребер: \((\bar,\bar)\) и \((\bar,\bar)\), где \(v\in\), \(e\in\), \(f\in\), а черточкой мы обозначаем соответствующую вершину графа H. С одной стороны, отсюда следует, что совершенными паросочетаниями граф H не обладает, поскольку знаменитая формула Эйлера для плоских графов гласит, что \(|V|-|E|+|F|=2\). С другой стороны, мы видим, что это легко исправить: достаточно удалить из H две вершины вида \(\bar\) и \(\bar\) вместе с исходящими из них ребрами. Например, удалив вершину, соответствующую внешней грани, а также одну из вершин вида \(\bar\), мы получим граф H’, который уже обладает паросочетаниями. Теперь, чтобы на основе данного паросочетания графа H’ построить остовное дерево графа G, достаточно взять все входящие в паросочетание ребра вида \((\bar,\bar)\) и провести соответствующие им ребра e. Отметим, что указанное сопоставление всегда будет взаимно однозначным, если для получения графа H’ мы будем удалять из H вершины, прилегающие друг к другу с точки зрения графа G.

Как и для числа замощений доминошками, для числа остовных деревьев связного графа без петель существует формула, оперирующая определителем матрицы. Именно, пусть x_uv обозначает количество ребер, соединяющих между собой вершины u и v графа G, а \(\deg\) — степень вершины v, то есть общее количество исходящих из нее ребер. Определим матрицу Δ следующим соотношением:

Очевидно, что сумма чисел в каждой строке матрицы Δ равна нулю, а значит, \(\det\Delta=0\). Однако оказывается, что для достижения цели достаточно вычеркнуть из матрицы строку и столбец, причем неважно, какие. Именно, если мы вычеркнем строку и столбец, соответствующие вершинам u и v соответственно, а получившуюся матрицу назовем \(\Delta^<(u,v)>\), то число остовных деревьев графа G равно \(|\det\Delta^<(u,v)>| \). (Более точно, количество остовных деревьев равно любому алгебраическому дополнению матрицы Δ). Например, если граф G состоит из пяти вершин, соединенных между собой ребрами так, как мы это видели на рис. 8, то ему соответствует матрица

и, согласно описанной выше формуле, число остовных деревьев равно, скажем, \(|\det\Delta^<(3,2)>|\):

В данном случае, число остовных деревьев графа G легко вычислить непосредственно. В самом деле, этот граф состоит из двух циклов длины три и четыре соответственно. Чтобы получить остовное дерево, необходимо удалить по одному ребру из каждого цикла, однако удаляемые ребра должны быть различными. Поэтому количество остовных деревьев есть 3·4 − 1 = 11.

Любопытно, что изначально этот результат, оперирующий математическими понятиями графов и остовных деревьев, был получен немецким физиком Густавом Кирхгофом для электрических цепей. И правда, электрическую цепь можно рассматривать как граф, вершинами которого будут узлы цепи, а ребрами — ее ветви. Теперь если ребру, соединяющему вершины u и v, приписать сопротивление соответствующей ветви R_uv и рассмотреть матрицу T = (T_uv), заданную соотношением

то из законов Кирхгофа можно вывести, что сопротивление между узлами k и l равно \(\dfrac<\det>><\det>>\), где T_{(k, l)} — матрица, получающаяся вычеркиванием строк и столбцов, соответствующих узлам k и l, а T_(l) — матрица, получающаяся из T вычеркиванием строки и столбца, соответствующих узлу l.

Напоследок отметим два классических результата, касающихся замощений доминошками различных областей. Во-первых, нужно сказать о непосредственно связанной с нашей задачей формуле, которая выражает количество способов замостить прямоугольник размера m×n:

Обратите внимание, что если оба числа m и n являются нечетными, получается корректный ответ — ноль. Наиболее типичное доказательство этой формулы базируется на упомянутой выше теореме Кастелейна, но, конечно, ею не ограничивается. А во-вторых, нельзя не отметить задачу об Ацтекском бриллианте. Ацтекским бриллиантом размера n называется фигура на плоскости, состоящая из клеток, центры которых удовлетворяют неравенству \(|x|+|y|\leqslant\) (так, на рис. 9 изображен Ацтекский бриллиант размера 4). Оказывается, общее количество замощений доминошками Ацтекского бриллианта размера n равно \(2^<1+2+\ldots+n>=2^\). Интересно поведение типичного замощения при больших n: теорема о полярном круге утверждает, что внутри вписанной в Ацтекский бриллиант окружности оно является хаотичным. А вот почти все доминошки, находящиеся вне этой окружности — в углах бриллианта, будут «заморожены»: в нижнем и верхнем углах они почти всегда будут горизонтальными, а в левом и правом — вертикальными.

Источник