AOP_Tom1 (1021736), страница 18
Текст из файла (страница 18)
Например, для перестановки 2 3 1 из (3) получим 231г, 231г, 231г, 231г и после замены получим 3421, 3412, 2413, 2314. Есть еще один способ описания этого процесса. Возьмем перестановку агаг... а„1 и число й, 1 < /с < п; добавим единицу к каждому а, значение которого > Й. В результате получим перестановку Ь|Ьг...
6„, из элементов (1, ..., й — 1, 6+ 1, ..., п); значит, 61 6г... Ь„, И вЂ” зто перестановка чисел (1,..., п). При таком способе построения тоже очевидно, что квждая перестановка из п элементов встречается только один раз. Аналогичные построения можно выполнить, помещая й не справа, а слева либо в любой другой фиксированной позиции.
Если р„— число перестановок из п объектов, то оба описанных метода показывают, что р„= пр„г, это дает два дополнительных доказательства соотношения р„= п(п — 1) ... (1), которое мы уже вывели из (2). р„— это очень важная величина, которую называют и-факториал и записывают следующим образом: (=1 2 ...
=Пй. (4) ь=г Из нашего соглашения, касающегося пустых произведений (раздел 1.2.3), следует, что (5) О! = 1. Учитывая это соглашение, видим, что основное тождество (6) п. '= (и — 1)! и справедливо для всех целых положительных и. В вычислительных задачах факториалы встречаются довольно часто, поэтому я советую читателю запомнить значения первых из них: О! =1.
1!=1, 2! =2, 3! =6, 4!=24 5! =120. Факториалы растут очень быстро, например 1000! — это целое число, имеющее свыше 2 500 цифр. Очень полезно запомнить значение 10! = 3 628 800; кроме того, нужно знать, что 10! — это примерно 3-'мнллиона. В определенном смысле это число представляет собой некую грань межлу тем, что реально можно вычислить на компьютере, и тем, что нельзя. Если в алгоритме предусмотрена проверка более чем 10! случаев, то на практике для его выполнения может потребоваться слишком много машинного времени. С другой стороны, если нужно проверить 10! случаев, на каждый из которых требуется, скажем, одна миллисекунда машинного времени, то выполнение алгоритма займет не больше часа Я согласен, что все эти рассуждения весьма туманны, но во всяком случае они помогут вам получить некоторое представление о том, что реавьяо можно вычислить на компьютере, а что нет.
Естесгвенно, возникает вопрос, как связано и! с другими математическими величинами. Можно ли определить, насколько велико значение 1000!, не выполняя трудоемких операций умножения по формуле (4)? Ответ на этот вопрос дал Джеймс Стирлинг (Лашш БМг(шй) в своей знаменитой работе ЛХейрйи 1Ишгепс(айв (1730 г.), с. 137. Он получил формулу и! ~/2кп ( — ) (7) Здесь "=" означает "приближенно равно", а "е" — зто основание натурального логарифма (см.
раздел 1.2.2). Приближенную формулу Стирлинга (7) мы докажем в разделе 1.2.11.2. А простое доказательство менее точного результата дано в упр. 24. Рассмотрим пример применения формулы Стирлинга. Вычисэим г8тэ 40320 = 8~ 4~/я ~-~ 2эе~/хе э 67108864 1 77245 0 00033546 39902 е В данном случае погрешность составляет приблизительно 13м впоследствии мы увидим, что относительная погрешность расчетов по этой формуле приблизительно равна 1/(12п).
Помимо приближенного значения, которое вычисляется по формуле (7), можно довольно легко получить точное значение и! с помощью разложения на простые множители. Действительно, простое чясло р является делителем и! кратности (8) Например, если и = 1000 и р = 3, то имеем = 333+ 111+ 37+ 12 + 4 + 1 = 498. Таким образом, 1000! делится на Зэээ, но не на Зчээ. Хотя формула (8) записана в ваде бесконечной суммы, на самом деле для любых чисел и и р эта сумма имеет конечное число свашемых; дело в том, что, начиная с некоторого Й, все эти слагаемые обращаются в нуль. Из упр. 1.2.4 — 35 следует, что (и/р"~') = '1(пгр")/р~; это позволяет упростить вычисления по формуле (8), так как можно просто разделить значение предыдущего члена на р и отбросить остаток.
Формула (8) следует из того, что (и/р") — зто количество целых чисел из (1,2,...,п), кратных р". Если рассмотреть целые числа в произведении (4), то станет ясно, что любое целое, которое делится на р', но не делится на р~+', учитывается ровно у рэз: один раз — в (и/р), другой раз — в (п7рз), ...и, наконец, в 1п7р~). Таким образом, учитываются все случаи, когда р является простым множителем в и!. Теперь возникает еще один естественный вопрос. Мы определили пй для неотрицательных целых чисел и.
Но, возможно, факториальная функция имеет смысл также для рациональных и даже для действительных чисел пг Например, чему равен (г)!? Для иллюстрации этого вопроса давайте введем "термиальную" функцию и? =1+2+. +в=~ Ь, (9) которая аналогична факториальной, за исключением того, что здесь выполняется сложение, а не умножение. Из формулы 1.2.3 — (15) мы уже знаем, чему равна сумма арифметической прогрессии: и! = 1+ ~1 — — г) и + ( ? — — + — )п(п — 1) 1(У' (. Н 2(У' 1 1 1~ + (1 — — + — — — )п(п — 1)(п — 2) + П 2! 3() (Мы докажем эту формулу в следующем разделе.) Данная сумма из соотношения (11) кажется бесконечной, но на самом деле она конечна для любого неотрицательного целого и. Тем не менее формула (11) не дает желаемого обобщения для функции и!, так как бесконечная сумма сходится только в том случае, если и— неотрицательное целое число (см.
упр. 1б). Но Стирлинг не упал духом и нашел последовательность аы аг,..., такую, что 1пп! = агп+агп(п — 1)+... = ~~~ аьег П (и — 7). (12) ь>о о<гйь Однако он не смог доказать, что эта сумма определяет функцию и! для всех дробных и, хотя и нашел значение (-')! = ~/к/2. Приблизительно в то же время данной задачей занимался и Леонард Эйлер (? еопЬагб Еп!ег), и именно он первым нашел обоснованное обобщение; т" т! и! = 1пп т-~с (и + 1)(п + 2) ...(и + т)' (13) Эйлер изложил эту идею в письме Христиану ?'ольдбаху (СЬг?эо?ап СоЫЬасЬ) от 13 октября 1729 года. В его формуле и! определяется для любого значения и, и? = —,п(п+ 1).
(10) Таким образом, используя формулу (10) вместо (9), можно обобщить определение "термиальной" функции для произвольного и. И, отвечая на заданный выше вопрос, полйчим (г), = 1. Стирлинг сам предпринял несколько попыток обобщить понятие факториала и! для нецелых и. Он представил приближение (7) в виде бесконечной суммы, но, к сожалению, эта сумма не сходилась ни для одного значения и. Формула (7) дает очень хорошее приближение, но ее нельзя продолжить так, чтобы получить точное значение.
[Эта довольно необычная ситуация обсуждается в книге К. Кпорр, ТЛеогу ап4 Аррйсабол о? ?пбп?се Бег?еэ, 2пс1 е4. (С1ээйо~ч: В1ас?бе, 1951), 518 — 520, 527, 534.) Стирлинг предпринял еще одну попытку, обратив внимание на то. что 1 -3 -2 -1 О 2 3 4 Рис. 7. Функция Г(х) = (х — 1)!. Локальный минимум в точке Х имеет координаты (1.46163 21449 68362 34126 26595, 0.88560 31944 10888 70027 88159). и! = Г(п+ 1) = оГ(п).
(14) Функция Г(х) называется гамма-функцией, и из (13) х! гп* гп! Г(х) = — = !пп х т-~сю х(х+ 1)(х+2) получаем формулу для нее: (15) (х + гп) График функции Г(х) показан на рис. 7. Формулы (13) и (15) определяют факториалы и гамма-функцию как для действительных, так и для комплексных чисел; но если подразумевается переменная, за исключением целых отрицательных, для которых знаменатель в формуле (11) обращается в нуль; в таких случаях н! считается равным бесконечности. В упр. 8 и 22 объясняется, почему формула (13) является обоснованным разумным определением факториала. Примерно двумя столетиями позже, в 1900 гору, ПЬ Эрмит (С. Негш11е) доказал, что на самом деле формула Стирлинга (12) корректно определяет н! для нецелых л и что фактически обобщения Эйлера и Стирлинга идентичны.
В прошлые века для факториалов использовались самые разные обозначения. Эйлер писал ]и], Гаусс (Сацээ) — П п, а в Англии и Италии были популярны символы (н и п). В наше время для целых п универсальным обозначением факториала является и!; его ввел сравнительно малоизвестный математик Кристиан Крамп (С1гг1311ап Кгашр) в своем учебнике по алгебре ]Е!ешелг д'Аг11Лшег19ие Ьл1гегэе11е (Со!обпе: 1808)].
Но для нецелмх н запись н! не нвляется общепринятой; в этом случае обычно используется обозначение, которое ввел А. М. Лежандр (А. М. Ьебепг!ге): имеющая и деиствнтельную; я мнимую части, то дяя ее обозначения обычно ис- пользуется буква х, а не и или х. Связь между факториалом и гамма-функцией выражается не только формуЛой х! = Г(х + 1), но и соотношением ( — х)!Г(х) =— шла.х' которое выполняется для всех нецелых х (см. упр.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
