Раздел: Документация
0 ... 63 64 65 66 67 68 69 ... 117 (Вспомните, что р - имя вектора, определяющего перестановку, например, это нижняя строка в (14.1).) Почему когда вы умножаете А на вектор-столбец и = (1,2,... , п)Т. чтобы ВЫЧИСЛИТЬ Аи, то получаете вектор перестановки р, записанный в виде столбца? Заметьте, что в MATLABe вектор и может быть записан как u=[l:n] . Отсюда следует, что степени перестановки1 можно вычислять как A2u, А3 и, Воспользуйтесь вашим примером из приведенной выше задачи (ш) для иллюстрации того факта, что НОК длин циклов равно порядку перестановки (т. е. наименьшей степени k > 1, для которой Аки= и). Замечание: Возможно, вам покажется проще создать новую версию М-файла, написанного вами перед этим, в которой вы могли бы задавать перестановку, а не выбирать ее случайным образом. (v)Измените cycles.m, чтобы со всем прочим подсчитывалось общее число циклов (включая 1-циклы) в разложении перестановки на непересекающиеся циклы. Затем еще раз измените его, чтобы для заданного числа случайных перестановок (их может быть до 1000) вычислялось среднее число циклов в разложении этих перестановок на непересекающиеся циклы. Выполните его несколько раз для различных значений п, чтобы найти экспериментальную оценку для этих средних при различных п. (vi)Мы изложили теоретические соображения, позволяющие предсказать величину среднего, найденного выше экспериментально в задаче (v). Они не требуют вычислений. Вы должны дополнить доказательство деталями и ответить на ряд вопросов. Мы вычисляем среднее Е непересекающихся циклов по всем п! перестановкам из S(n). Итак, пусть Ри(п) -общее число /г-циклов среди разложений на непересекающиеся циклы всех элементов S(n). Нам нужно найти „ Pi(n)+P2(n)+ • • • +Рп(п) Е =- -п!- Например, пусть п = 3. Разложения на непересекающиеся циклы шести элементов из 5(3) суть (1)(2)(3),(1)(23), (2)(31), (3)(12), (123), (132). Так, А(3) = 6, Рг(3) -3, Рз(3) = 2, и Е - Ц- есть среднее число непересекающихся циклов для перестановок трех объектов. То есть результат ее многократного применения. - Прим. перев. Как много перестановок из S(n) содержат, в частности, 1-цикл (1)? Оставшиеся п - 1 чисел можно переставлять произвольным образом, так что для него имеется (п- 1)! таких перестановок. Аналогично учитываются 1-циклы (2),... , (п). Итак, для каждого из п возможных 1-циклов имеется точно (п - 1)! перестановок, содержащих этот 1-цикл. Поэтому всего будет п(п - 1)! = п\ возможных 1-циклов, входящих в разложения на непересекающиеся циклы всех перестановок из S(n). Поэтому Р\{п) = п\. Теперь рассмотрим 2-циклы. Любой конкретный 2-цикл, такой, как (12), попадается точно в (п - 2)! перестановках из 5(п),а всего имеется п{п~1\ возможных 2-циклов (почему?). Таким образом, возможных 3-циклов, сначала подсчитайте количество различных троек (а, Ь, с) из несовпадающих чисел от 1 до п. Затем учтите, что этих троек в 3 раза больше, чем реальных 3-циклов, поскольку (а, Ь,с)~ (Ь, с, а) = (с,а, 6), так что их число нужно разделить на 3.) Каков результат в общем случае для Pjt(n}?4eMy равно значение Е? Сравните это среднее с полученным вами экспериментально в задаче (v). (vii) В заключение рассмотрите следующие отчасти эксцентричные вычисления. Нам даны числа п и гаакие, что 1 < т < п. Непересекающиеся циклы перестановки тг, содержащей числа из набора 1,2,... ,т, могут содержать или нет все числа, не входящие в него. Например, при п = 4, т = 2 рассмотрим перестановки Для TTi ™ (12)(34) цикл, содержащий 1,2, не содержит 3,4. Для ТГ2 = (1)(234) - содержит. Внесите изменения в cycles.ю, чтобы можно было вычислять в случайной выборке из, скажем, 1000 перестановок долю тех, которые удовлетворяют этому свойству для заданного т {вводя его вначале вместе с п). Подсказка: Это намного легче, чем звучит. Вам нужно ввести т и число проверяемых перестановок testnum. Вам также потребуется счетчик count, чтобы считать число перестановок, обладающих указанным выше свойством. Последнее существенное изменение, которое нужно сделать, состоит в том, чтобы вместо while Кп   /12 3 4 13 4 2  вставить while Km Как только разложение на циклы найдено, вам нужно проверить, обладает ли оно требуемым свойством; это делается посредством сравнения if р == zeros(sizeCp)) count=count+l; end Вы понимаете, почему это срабатывает? В случае, скажем, п = 8 и различных m предложите формулу для этой доли, выразив ее через пит. (viii) Вычисления задачи (vii) можно интерпретировать так. Пусть мы имеем п ящиков, каждый с уникальным ключом, который не подходит к другим ящикам, и у каждого есть узкая прорезь, через которую мы можем протолкнуть ключ внутрь. Ящики закрыты на ключ, и ключи случайным образом опущены в ящики по одному в ящик. Теперь взломаем ящики 1,2,... ,т. Какова вероятность того, что после этого можно будет открыть замки всех ящиков? Объясните, как это связано с проведенными выше вычислениями. В. Тасование карт Цель работы Для некоторых людей тасовании карт - один из примеров перестановок в повседневной жизни. В этой работе рассматриваются результаты как «идеального» (с высокой степенью регулярности) тасования, так и «грубого» тасования, имеющего определенный элемент случайности. Для этого моделируется заурядное тасование внахлест колоды из 52 карт как противоположность тасованию карточных фокусников. Мы обнаружим, к нашему удивлению, что трех (грубых или идеальных) тасований внахлест совершенно недостаточно, чтобы полностью перемешать колоду. На самом деле, если такое тасование выполнено трижды, а затем одна карта перемещается в другое место колоды, то обычно имеется возможность найти эту карту простым способом выкладывания карт в столбцы. Тасование карт обсуждается в [6]. Используемые математические понятия Работа связана с перестановкой конечных множеств, интерпретируемых как колоды карт, пронумерованных от 1 до п. Поэтому при- 0 ... 63 64 65 66 67 68 69 ... 117
|
