Математика. Настоящий учебник посвящен системе Mathematica прикладному пакету компьютерной алгебры, при помощи которого можно решать любые задачи, в которых в той или иной форме встречается математика
 Скачать 4.43 Mb.
|
|
является простым? Ответ. Первые шесть из них действительно простые: x 2 = 5, x 3 = 23, x 4 = 53, x 5 = 1523, x 6 = 29243, x 7 = 299513, но вот x 8 = 4383593 = 23 · 190591 простым не является. Следуюшее x 9 = 188677703 снова простое, но вот x 10 = 5765999453 = 41 · 131 · 809 · 1327 имееи четыре простых делителя. Дальше простые встречаются, но доволь- но редко, x 18 , x 63 , x 105 и т.д. 5.6. Пусть x s ≡ (−1) i −1 (mod p i ) для первых s простых p i , причем 0 ≤ x < p 1 . . . p s . Верно ли, что при любом s ≥ 2 это x s является простым? Ответ. Первые пять из них действительно простые: x 2 = 5, x 3 = 11, x 4 = 41, x 5 = 881, x 6 = 14741, но x 7 = 74801 = 131 · 571 простым не является. Для практически встречающихся задач (несколько сотен относительно небольших модулей) описанный выше классический алгоритм вполне эф- фективен. Однако, он требует нахождения линейного представления 1 и вычисления остатка по модулю m = m 1 . . . m s . Для действительно боль- ших чисел обычно используется более эффективный алгоритм Гарне- ра 144 , который не требует деления на m. The reader will be content to wait for a full explanation of these mat- ters till the next year, — when a series of things will be laid open which he little expects. Laurence Sterne, Tristram Shandy 144 H.Garner, The residue number system. — IRE Trans. Electronic Computers, 1959, vol.8, p.140–147. 352 Глава 8. КОМБИНАТОРИКА И ДИСКРЕТНАЯ МАТЕМАТИКА Истинное учение начинается с сохранения знания, овладения зна- нием и понимания. Оно не начинается с любви, усилия или дей- ствия, ибо истинные любовь, усилие и действие становятся возможными лишь благодаря истинному знанию Идрис Шах. Путь суфия По дороге в царство Чу Конфуций вышел из леса и увидел Горбу- на, который ловил цикад так ловко, будто подбирал их с земли. — Неужто ты так искусен? Или у тебя есть Путь? — спросил Конфуций. — У меня есть Путь, — ответил Горбун. — В пятую-шестую луну, когда наступает время охоты на цикад, я кладу на кончик своей палки шарики. Если я смогу положить друг на друга два шарика, я не упущу много цикад. Если мне удастся положить три шарика, я упущу одну из десяти, а если я смогу удержать пять шариков, то поймаю всех без труда. Я стою, словно старый пень, руки держу, словно сухие ветки. И в целом огромном мире, среди всей тьмы вещей, меня занимают только крылатые цикады Я не смотрю по сторонам и не променяю крылышки цикады на все богатства мира. Могу ли я не добиться желаемого? Конфуций повернулся к ученикам и сказал: Помыслы собраны воедино, дух безмятежно спокоен. Не об этом ли Горбуне сказано такое? Чжуан-цзы, Гл. XIX. Постигший жизнь Интеллект обычно определяется как способность к пониманию . . . Он состоит в возможности использовать осознанные знания при столкновении с новыми ситуациями и предвидеть возникновение проблем благодаря абстрактному осмыслению взаимосвязей, вы- раженных в символах. Подобно воображению и интуиции, интел- лект работает путем комбинирования фактов, хранящихся в памя- ти, но делает он это не с помощью причудливой игры в потемках бессознательного, а с помощью логического анализа при полном свете сознания . Его основными инструментами являются: ло- гика, память, способность к концентрации внимания на од- ной проблеме вместе с ее логическими следствиями, способность к абстракции, пренебрежение ко всему, что не относится к делу Ганс Селье. От мечты к открытию Быть магом , — продолжал дон Хуан, — не означает заниматься колдовством, воздействовать на людей или насылать на них де- монов. Это означает достижение того уровня осознания, который делает доступным непостижимое Карлос Кастаньеда, Активная сторона беcкoнечнocти Корень учения один, но ветви его отстоят далеко друг от друга. Чтобы не погубить себя и вернуть себе потерянное, нужно вер- нуться к общему корню. 353 Ле-цзы, Гл. VIII. Рассказы о совпадениях Читателю полезно изучить как можно больше программ, приве- денных в данной книге, поскольку чрезвычайно важно приоб- рести опыт чтения программ, написанных другими . Но, к сожалению, подобной формой обучения пренебрегали во многих компьютерных курсах, что привело к крайне неэффективному ис- пользованию компьютерной техники. Дональд Кнут § 1. Комбинаторика Исчислите все общество сынов Израилевых по родам их, по семей- ствам их, по числу имен, всех мужеского пола поголовно. Числа — Вы, может, знаете — был такой поэт Мандельштам. Так вот, он писал в одном стихотворении: “Бессонница, Гомер, тугие пару- са — я список кораблей прочел до середины . . . ” Это, значит, из “Илиады”, про древнегреческий флот в Средиземном море. Ман- дельштам только до середины дошел, а Вадим Степанович этот список читал до самого конца. Вы можете себе это представить? Виктор Пелевин, Греческий вариант Широкая распространенность на математических олимпиадах за- дач по комбинаторике вызывает недовольство участников, да и просто хороших людей. Федор Петров 145 В настоящей параграфе мы обсуждаем, в основном в чисто калькулятив- ных аспектах, основные классы комбинаторных коэффициентов. Впрочем, в некоторых случаях знание комбинаторного смысла абсолютно необходи- мо для понимания и построения алгоритмов. 1. Факториалы. 146 Напомним, что факториал n! неотрицательного целого числа n ∈ N 0 определяется как n! = 1 ·2·3·. . .·n. Для n = 0 произведение пусто, поэтому 0! = 1. Гамма-функция Эйлера Γ(z) является обобщением факториала на произвольное комплексное значение аргумента. В натуральных точках n! = Γ(1 + n). Factorial[n] n! факториал Gamma[x] Γ(x) гамма-функция Эйлера Factorial2[n] n!! двойной факториал Subfactorial[n] субфакториал 145 Ф.В.Петров, Комбинаторика как раскрытие скобок. — В кн.: Задачи Санкт- Петербургской олимпиады школьников по математике 2004, Невский диалект — БХМ- Петербург, Спб, 2004, с.105–115. 146 There is nothing new under the Sun, but there are a lot of old things we do not know. c Ambrose Bierce 354 1.1. Составьте таблицу n! при 0 ≤ n ≤ 20. Ответ. Приведем начало этой таблицы 0! = 1, 1! = 1, 2! = 2, 3! = 6, 4! = 24, 5! = 120, 6! = 720, 7! = 5040, 8! = 40320, 9! = 362880, 10! = 3628800. Как отмечает Кнут, психологически 10! ≈ 3.5 · 10 6 — это наибольшее ко- личество случаев, которые еще можно рассматривать полным перебором. При большем количестве случаев стоит задуматься о более умных алгорит- мах. 1.2. Напишите десять программ для вычисления факториалов, не исполь- зующих встроенную функцию Factorial и сравните скорость их работы. Решение. Вот несколько наиболее простых программ: faa[0]=1; faa[n ]:=n*faa[n-1] fbb[n ]:=Block[ {i,x=1},For[i=1,i<=n,i++,x=x*i];Return[x]] fcc[n ]:=Apply[Times,Range[n]] fdd[n ]:=Product[i, {i,1,n}] fee[n ]:=Fold[Times,1,Range[n]] 1.3. Напишите программу для вычисления последней ненулевой цифры n!. Для решения двух следующих задач полезно знать главный член в фор- муле Стирлинга, дающий грубое приближение n!: n! ≈ √ 2πn n e n . Впрочем, грубым оно является только с точки зрения анализа, для целей дискретизации при больших n его точность достаточна. 1.4. Что больше, (n − 1)! или n n/2 ? 1.5. Задайте функцию такую, что f (n) = m, если n = m! для некоторого m > 0 в противном случае. Ответ. Проблема, разумеется, состоит не в том, чтобы задать такую функ- цию, а в том, чтобы задать ее таким образом, что f (200000!) вычисляется за 1 секунду. Вот решение из книги Вольфрама, основанное на формуле Стирлинга: InverseFactorial[1]:=1 InverseFactorial[n Integer /; n>0]:= With[ {m=Round[Log[n]/ProductLog[Log[n]/E]]]-1}, m /; m!===n]] Напомним, что встречающаяся здесь функция ProductLog[x] представляет собой главное решение уравнения ye y = x, удовлетворяющее дифференци- альному уравнению dy dx = y x(1 + y) . Эта функция очень часто возникает 355 при решении уравнений, в которые входят экспонента и/или логарифм. Обратите внимание на программистские уловки: паттерн с условием, ис- пользование полупрозрачной конструкции локализации переменных With и проверку тождества в условии. Если m! 6= n, эта функция остается неэвалюированной. При желании можно доопределить ее произвольным образом. Впрочем, чтобы получить более точное приближение, дающее несколько правильных цифр уже при совсем небольших n, можно взять следующий член по n в формуле Стирлинга: n! ≈ √ 2πn n e n 1 + 1 12n + . . . . 1.6. Задайте функцию, выражающую правую часть формулы Стирлинга, и сравните ее значение с n! для небольших n. Начиная с какого n эта формула дает шесть правильных знаков? Как показывает следующая задача, весьма полезно помнить, что n! = Γ(1 + n). Как мы видели в Модуле 1, в связи с характером используе- мых Mathematica алгоритмов, результат упрощения сумм и произведений часто возвращается в виде комбинации значений специальных функций (в первую очередь таких, как гипергеометрические, гамма и дзета) даже в тех случаях, когда эти значения допускают элементарное выражение. 1.7. Вычислите 1 + n X i=1 i i! Ответ. Это (n + 1)!, но система, естественно, возвращает Γ(n + 2). В качестве коэффициентов различных рядов Тэйлора, при изучении пе- рестановок, булевых функций, да и вообще в дискретной математике и алгебре чрезвычайно часто возникает также двойной факториал n!! = n(n − 2)(n − 4)... Таким образом, для четного n двойной факториал n!! является произведе- нием всех четных натуральных чисел, не превосходящих n, а для четного n — произведением всех нечетных натуральных чисел, не превосходящих n: (2n)!! = 2 n n!, (2n − 1)!! = (2n)!/(2n)!! 1.8. Составьте таблицу первых n!! при 0 ≤ n ≤ 21. Ответ. Вот ответ, отдельно для четных n: 0!! = 1, 2!! = 2, 4!! = 8, 6!! = 48, 8!! = 384, 10!! = 3840, 12!! = 46080, 14!! = 645120, 16!! = 10321920, 18!! = 185794560, 20!! = 3715891200 356 и для нечетных: 1!! = 1, 3!! = 3, 5!! = 15, 7!! = 105, 9!! = 945, 11!! = 10395, 13!! = 135135, 15!! = 2027025, 17!! = 34459425, 19!! = 654729075, 21!! = 13749310575 Ясно, что для использовать выражение через (2n)! для фактического вычисления (2n − 1)!! совершенно нецелесообразно. 1.9. Напишите десять программ для вычисления двойных факториалов, не использующих встроенные функции Factorial и Factorial2. Двойные факториалы теснейшим образом связаны со значениями гамма- функции в полуцелых точках. 1.10. Вычислите несколько первых значений Γ(n+1/2), n ∈ N 0 , и угадайте, чему равен ответ в общем случае. Ответ. Взгляд на Γ 1 2 = √ π, Γ 3 2 = √ π 2 , Γ 5 2 = 3 √ π 4 , Γ 7 2 = 15 √ π 8 , Γ 9 2 = 105 √ π 16 , Γ 11 2 = 945 √ π 32 , Γ 13 2 = 10395 √ π 64 , сразу убеждает нас в том, что Γ n + 1 2 = (2n − 1)!! √ π 2 n Основная роль факториала состоит в том, что n! есть количество пере- становок степени n. Точно так же (2n)!! = 2 n n! есть количество означенных перестановок степени n. В связи с задачей Монмора о числе беспорядков степени n нам встретится еще одна функция факториального типа, суб- факториал D n = n! n X i=0 ( −1) i i! Эта функция реализована в ядре Mathematica под именем Subfactori- al[n]. Асимптотически она равна n!/e. 1.11. Напишите программу для вычисления субфакториалов и составьте таблицу первых двадцати субфакториалов. Ответ. Вот начало ответа D 1 = 0, D 2 = 1, D 3 = 2, D 4 = 9, D 5 = 44, D 6 = 265, D 7 = 1854, D 8 = 14833, D 9 = 133496, D 10 = 1334961 2. Убывающий и возрастающий факториалы. 147 147 There is something in this more than natural. c William Shakespeare, Hamlet 357 Наряду с обычными факториалами во многих комбинаторных и алгеб- раических задачах, задачах аппроксимации, а также при разложении раз- личных специальных функций в ряды, возникают возрастающие и убыва- ющие факториалы. В действительности на них естественно смотреть как на многочлены Здесь же убывающие и возрастающие факториалы будут интересовать главным образом как натуральные числа. Pochhammer[x,n] [x] n возрастающий факториал (-1)^n*Pochhammer[-x,n] [x] n убывающий факториал Пусть m ∈ N 0 . Выражение [x] m = x(x − 1) . . . (x − m + 1) называется убывающим факториалом длины m. Для m = 0 произведе- ние пусто, поэтому [x] 0 = 1 для всех x. Для n ∈ N 0 имеем [n] m = n!/(n −m)! Выражение [x] m = x(x + 1) . . . (x + m − 1) называется возрастающим факториалом длины m. Для m = 0 произ- ведение пусто, поэтому [n] 0 = 1 для всех x. Для любого x выполняется равенство [x] m = Γ(x + m)/Γ(x). В частности, для натурального n имеем [n] m = (n + m − 1)!/(n − 1)! Убывающий и возрастающий факториалы находятся в двойственности и выражаются друг через друга формулами [x] m = [x − m + 1] m = ( −1) m [ −x] m , [x] m = [x + m − 1] m = ( −1) m [ −x] m . Убывающие факториалы начал впервые систематически изучать Ван- дермонд, который и ввел для них обозначение [x] n (sic!) Кнут называет убывающий и возрастающий факториалы факториальными степенями и пользуется для них обозначением Капелли [x] m = x m и [x] n = x m . Для разнообразия в Mathematica возрастающий факториал называется симво- лом Поххаммера и обозначается (x) n 2.1. Напишите десять программ для вычисления убывающих и возрас- тающих факториалов, не использующих встроенные функции Pochhammer, Factorial и Gamma. 2.2. Вычислите [n] m и [n] m при 0 ≤ m, n ≤ 20. Ответ. Вот начало таблицы убывающих факториалов: 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 2 2 0 0 0 0 0 0 0 1 3 6 6 0 0 0 0 0 0 1 4 12 24 24 0 0 0 0 0 1 5 20 60 120 120 0 0 0 0 1 6 30 120 360 720 720 0 0 0 1 7 42 210 840 2520 5040 5040 0 0 1 8 56 336 1680 6720 20160 40320 40320 0 1 9 72 504 3024 15120 60480 181440 362880 362880 358 Вот начало таблицы возрастающих факториалов: 1 0 0 0 0 0 0 0 0 1 1 2 6 24 120 720 5040 40320 1 2 6 24 120 720 5040 40320 362880 1 3 12 60 360 2520 20160 181440 1814400 1 4 20 120 840 6720 60480 604800 6652800 1 5 30 210 1680 15120 151200 1663200 19958400 1 6 42 336 3024 30240 332640 3991680 51891840 1 7 56 504 5040 55440 665280 8648640 121080960 1 8 72 720 7920 95040 1235520 17297280 259459200 Обратите внимание, что на главной диагонали первой таблицы и в пер- вой строке второй таблицы (нумерация строк и столбцов начинается с 0) расположены обычные факториалы. 3. Биномиальные коэффициенты. 148 Множество всех m-элементных подмножеств множества X называется m-й внешней степенью множества X и обозначается через V m (X) (в комбинаторике часто используется также обозначение X (m) ): V m (X) = {Y ⊆ X | |Y | = m}. Традиционно количество m-элементных подмножеств n-элементного мно- жества называется числом сочетаний из n по m (n choose m) и обо- значается n m или C m n . Таким образом, по определению, C m n = n m = | V m (n) |. Числа n m называются также биномиальными коэффициентами. Так как Y 7→ X \ Y устанавливает биекцию между m-элементыми под- множествами и (n − m)-элементными подмножествами, то биномиальные коэффициенты симметричны по второму аргументу: n m = n n − m . В системе биномиальные коэффициенты можно вычислять при помощи внутренних функций Binomial или Multinomial. Binomial[n,m] n m = n n − m биномиальный коэффициент Multinomial[m,n-m] n m, n − m ibid. 148 И перекличка ворона и арфы Мне чудится в зловещей тишине. c Осип Мандельштам |