AOP_Tom1 (1021736), страница 166
Текст из файла (страница 166)
В некотором смысле это упражнение является комбинацией упр. 19 и 26. 28. Каждый член этого разложения имеет вид произведения а1р, ...а р Ь1о,...Ь„о„, где 0 < р < и для 1 < ! < т и 0 < о„< т лля 1 < ! < п, которое умножено на некоторый целочисленный коэффициент. Представьте это произведение в виде ориентированного графа с вершинами (О, ип, и,„, щ,, е ) и дугами от и, к ир, и от е, к ио,, где ио = ь'о = О. Если этот диграф содержит цикл, целочисленный коэффициент будет равен нулю.
Каждому такому циклу соответствует множитель вида а ооо Ьро ~ ач„... а,„„,, Ь„, „, где индексы (!о, !и..., ц. о) различны и также различны индексы (!о,уп,зь о). Сумма всех членов, содержащих (*) в качестве множителя, являетсн детерминантам, который получается при условии, что а,п э- [у =д) для 0 < !' < и и Ь „о- [! = опец „„о ь) для О < ! < т при 0 < 1 < (г, тогда как переменные в других гп + и — 2)г строках остаются неизменными.
Этот детерминант тождественно равен нулю, потому что сумма строк Ьо, (и ..., (г ~ в верхней части равна сумме строк !о, ум ..., уо, в нижней части. С другой стороны, если ориентированный граф не содержит циклов, то целый коэффициент будет равен +1.
Это следует из того, что все множители а,р, и Ь,о! должны находиться на диагонали детерминанта; если любой недиагональный элемент а„, выбран в строке 1о в верхней части, то необходимо выбрать некоторый недиагональный элемент Ь,оч из столбца зо в левой части. Следовательно, затем необходимо выбрать некоторый недиагональный элемент ач, из строки (1 в верхней части и т. д., образуя замкнутый цикл.
Таким образом, коэффициент равен +1 тогда и только тогда, когда соответствующий диграф является ориентированным деревом с корнем О. Количество таких членов (а значит, и количество таких ориентированных деревьев) получается за счет установки кахсдого ао и Ь, равным 1, например 0 3 1 1 4 0 О 0 1 3 О 0 0 0 3 0 0 0 0 3 4 0 1 1 1 0 4 1 1 1 бег 1 1 3 0 0 1 1 0 3 0 1 1 0 0 3 4 0 1 1 1 — 4 4 0 0 0 =бес 1 1 3 0 0 0 0 — 3 3 0 0 0 — 3 0 3 4 0 = <1е1 2 0 0 =бес( ) 4 3 3.
В общем, получим с1ес("р' ",) . (и+ 1)"' ' (т+ 1)" Замечания. Дж. Дж. Сильвестр (2. 2. Яу1чезсег) рассмотрел особый случай, когда т = и и а»о = аго = = а о = 0 [лгаагсег!у Х оЕ Риге аай Аррйей Мас6. 1 (1857), 42-5б], и справедливо предположил, что общее количество членов равно и" (и+ 1)" '. Он также утверждает без доказательства, что количество ненулевых членов равно (и+ 1)" ', если а»1 = 5»1 соответствуют всем связным графам без циклов с вершинами (О, 1,..., и).
В этом особом случае он свел детерминант к виду, рассмотренному в теорел»е о дереве матрицы из упр. 19, например /Ью+ 6ш + Ь»з -Ьш -Ь»з йеС вЂ” Ьг» Ьго + Ьш Ч- Ьгз — Ьгз -6з» -6зг Ью+Ьм+Ьз»1 Кэпи (Сау!еу) цитирует этот результат [Сгейе 52 (1855), 279], приписывая его Сильвестру; таким образом, по иронии судьбы теорема о количестве таких графов часто приписывается Кэпи. Меняя знак элементов первых т строк данного детерминанта на противоположный, а затем л»еняя знак элементов первых т столбцов, л»ажно свести данное упражнение к теореме о матрице дерева. [Рассмотренные в настоящем упражнении матрицы общего вида имеют большое значение для итеративных методов решения уравнений в частных производных. Их часто называют матрицами, обладающими свойством А (ргорегсу А) [см., например, Ьошз А.
Набе»пап апй 11ач!й М. гоппб, Аррйей 1сегабге Ме»Ьойз (Асайепцс Ргевз, 1981), СЬарсег 9.] РАЗДЕЛ 2.3.4.3 1. Корнем является пустая последовательность, а дуги проходят от (х»,...,х ) к (х»,...,х»). 2. Возьмем один тетрадный тип и повернем его на 180', чтобы получить другой тетрадный тип.
Очевидно, что эти два тетрадных типа позволяют полностью покрыть плоскость (без дальнейших вращений), копируя фрагменты размером 2 х 2. 3. Рассмотрим множество тетрадных типов для всех положительных целых чисел сй Правую половину плоскости можно покрыть несчетныл» числом способов, но при размещении любого квадрата в ее центре устанавливается конечный предел расстояния, на которое это покрытие может быть продолжено влево. 4. Необходимо последовательно перебрать все возможные варианты покрытия с помощью блоков размером и х и для и = 1, 2,..., проводя поиск тороидальных решений внутри блоков. Если покрыть плоскость нельзя, то согласно лемме о бесконечном дереве существует такое и, для которого нет решений размерол» и х и. А если ссгль способ покрытия плоскости, то согласно этому предположению существует такое и, для которого есть решение размером и х и, содержащее прямоугольник тороидального решения, Следовательно, в любом случае алгоритм прекратит работу за конечное число шагов.
(Но, как будет показано в следующем упражнении, это утверждение ложно: на самом деле нет алгоритма, который позволяет за конечное число шагов определить, существует ли споеоб покрытия плоскости с помощью заданного множества тетрадных типов.) 5. Начнем с того, что фрагменты В должны присутствовать в любом решении в виде » 3 групп 2 х 2. Тогда необходимо выполнить следующие действия. Этап 1. рассмотрим только и-тетрады и покажем, что фрагмент ~ а должен повторяться в а-тетрадях в виде групп 2 х 2.
Этапы п ) 1; определим фрагмент, который должен находиться в крестообразной области с высотой и шириной 2" — 1, причем внутренняя часть крестов содержит фрагмент вида '„, „э, который повторяется по всей плоскости. л лэ Например, после этапа 3 содержимое блоков 7 х 7 по всей плоскости будет отделяться друг от друга полосами единичной ширины через каждые восемь единиц. Блоки 7 х 7 с Юа-тетрадей в центре имеют вид "Крест" образуют средний столбец и средняя строка, которые заполняются на этапе 3; другие четыре квадрата 3 х 3 заполняются на этапе 2; квадраты справа и снизу от этого квадрата 7 х 7 являются частью креста размером 15 х 15, который заполняется на этапе 4.
Аналогичное построение, которое приводит к набору только из 35 тетрадных типов и содержит только тороидальные решения, можно найти в работе В.. 5Ь НоЬ1пэоп, )лэепйолеэ Майе 12 П971), 177 — 209. Робинсон также продемонстрировал набор из шести квадратообрвзных форм, которые покрывают плоскость только нетороцдальным образам, даже с использованием вращений и зеркальных отображений.
В 1974 году Роджер Пенроуз П1ойег Репгоэе) обнаружил набор из двух многоугольников, которые основываются не на квадратной решетке, а на "золотом" отношении и покрывают всю плоскость только апериодически. Это приводит к множеству всего 1б тетрадных типов лишь с неторондальными решениями )см. В. СгйпЬапш аль С. С. ЯЬерЬагб, Тибпбз алг) Рассегпэ (Ргеешап, 1987), СЬаргегэ 10 — 11; Мах11п Сагбпег, Релгоэс Тйез го Тгарс1оог С1рйегэ (Ргеешап, 1989), СЬарГегэ 1 — 2).
6. Пусть к и гл фиксированы. Рассмотрим ориентированное дерево, каждая вершина которого представляет для некоторого и одна из разбиений 11,..., п) на к частей, не содержащих арифметических прогрессий длины пь Узел, который представляет разбиение (1,..., п -Ь 1), является ребенком одного из разбиений (1,..., и), если оба они совпадают в части 11,..., п). Если бы существовал бесконечный путь от корня этого дерева, можно было бы разделить все целые числа на к множеств без арифметических прогрессий длины гл.
Следовательно, согласно лемме о бесконечном дереве и теореме Ван дер Вардена это дерево конечно. 1Если к = 2 и т = 3, его структуру можно достаточно быстро определить вручную и наименьшим значением Х будет 9.) 7. Положительные целые числа можно разбить на два таких множества ло и 5ы которые не содержат бесконечной емчислимай постедовательности (см. упр.
3.5 — 32). Так, в частности, они не содержат бесконечной арифметической прогрессии. Теорема К здесь неприменима, потому что не существует способа включения частичных решений в дереве с конечными степенями в каждой вершине. 8. Назовем контрпримером последовательности бесконечную последовательность деревьев, для которой нарушается теорема Крускала, если таковые последовательности вообще существуют. Предположим, что данная теорема неверна, и в этом случае пусть Т~— такое дерево с минимально возможным количеством узлов, что Т~ может быть первым деревом в контрпримере последовательности. Если выбраны Тм ..., Т„пусть Тгес— такое дерево с минимально возможным количеством узлов, что Тс, ..., Т, Тг~ы является началом кантрпримера последовательности. Этот процесс определяет кантрпример последовательности (Т,).
Ни одно из деревьев Т не является талька корнем. Рассмотрим теперь эту последовательность более внимательно. (а) Предположим, чта имеется последовательность Т„,, Т„„, контрпримером которой является!(Т„,), 1(Т,), .... Это невозможно, ибо последовательность Тм ..., Т„, !(Тт ), 1(Т,), ... была бы контрпримером последовательности, что противоречит определению Тгч. (Ь) Согласно (а) существует только конечное количество с, для которых 1(Т,) нельзя вложить в 1(Т») для любого й > 71 Следовательно, для пм большего, чем такое /б можно получить падпоследовательность, для которой 1(Тт ) С 1(Т„,) С 1(Т„,) С (с) Теперь согласно результату упр.
2.3 2-22 г(Т„, ) нельзя вставить в г(Т ) для любого й > 1, так как в противном случае Т„С Т„,. Значит, Тс,..., Т„, и г(Т,), г(Т,), кантрпример последовательности. Но это противоречит определению Т,. Замечания. Крускал в своей работе (Тгапэ. Атег. Масй. Бос. 95 (1960), 210 — 225) на самом деле доказал более "сильный" результат на основе более "слабого" понятия вставки. Его теорема не следует непосредственно из леммы о бесконечном дереве, хотя оба результата, в общем, подобны.
Действительно, Кениг доказал особый случай теоремы Крускала о том, что не существует бесконечной последовательности парных несравнимых а-кортежей неотрицательных целых чисел, где под сравнимостью подразумевается, что все компоненты одного картежа меньше соответствующих компонентов другого кортежа или равны им (Масетас!йш' ез Г!»!йш' Сарой 39 (1932), 27-29]. Дальнейшее развитие этой интересной темы можно найти в работе Х Сотб!лаоог!а! Тйеогу А13 (1972), 297-305, а применение результатов для изучения вопроса о том, закончится ли алгоритм, — в работе Н.
Дершовица (.зС 1)егзЬожй», !лб Ргос. Ее!Сего 9 (1979), 212 — 215). РАЗДЕЛ 2.3.4.4 1. 1и А(») =!п»-~ ~ аь!и( !! = !и»+ ~ = !и»+ ~ 1 оь» А(»') 1 — »" с »21 —,зйс ~>1 2. Дифференцируя и приравнивая коэффициенты»", получим тождество по„с = 2 2 с!ооо эс ь, а затем изменим порядок суммирования. 4. (а) А(») сходится па крайней мере длк (»( < -', так как о„меньше числа упорядоченны» деревьев Ь„ь Поскольку А(1) — бесконечно и все коэффициенты положительны, существует такое положительное число а < 1, что А(») сходится для ~ »( < а, и существует особая точка» = а. Пусть д(») = А(»)/»: так как ф(») > е*г01, ясно, что из 15(») = т следует» < 1лго/т, поэтому функция ЗС(») ограничена и существует предел !пп- — о бо(»).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
