Д. Кнут - Искусство программирования том 1 (1119450), страница 18
Текст из файла (страница 18)
а„! и число Й, 1 < 6 < и; добавим единицу к каждому а, значение которого > Й. В результате получим перестановку ЬгЬ!... Ь„, из элементов (1, ..., 6 — 1, 6+ 1, ..., п): значит, Ь! Ь!... Ь„! Ь вЂ” это перестановка чисел (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)? Ответ на этот вопрос дал Джеймс Стирлинг (Лают 81пйпй) в своей знаменитой работе Мегйойв Эйуегепбалэ (1730 г.), с. 137. Он получил формулу и! ш ~/2яп( — ) (7) Здесь "ш" означает "приближенно равно", а "е" — это основание натурального логарифма (см. раздел 1.2.2). Приближенную формулу Стирлинга (7) мы докажем в разделе 1.2.11.2.
А простое доказательство менее точного результата дана в упр. 24. Рассмотрим пример применения формулы Стирлинг. Вычислим гйтэ 40320 = 8! 4~/к ~ — ) = 2зв./хе э и 67108864 1.77245-0.00033546 ш 39902. е В данном случае погрешность составляет приблизительно 1%; впоследствии мы увидим, что относительная погрешность расчетов по этой формуле приблизительно равна 1/(12п).
Помимо приближенного значения, которое вычисляется по формуле (7), можно довольно легко получить точное значение и! с помощью разложения на простые множители. Действительно, простое число р является делителем и! кратности (8) Например, если и = 1000 и р = 3, то имеем =1Т1.Ю Ю Ю Ю1 Ю = 333+ 111+37+12+ 4+1 = 498. Таким образом, 1000! делится на Зюэ, но не на 34ээ. Хотя формула (8) записана в виде бесконечной суммы, на самом деле для любых чисел и и р эта сумма имеет конечное число слагаемых; дело в том, что, начиная с некоторого Й, все эти слагаемые обращаются в нуль.
Из упр. 1.2.4 — 35 следует, что ~ и/р" +') = 1(п/рь)/р); это позволяет упростить вычисления по формуле (8), так как можно просто разделить значение предыдущего члена на р и отбросить остаток. Формула (8) следует из того, что 1п/рь) — это количество целых чисел из (1,2,...,и), кратных рь.
Если рассмотреть целые числа в произведении (4), то станет ясно, что любое целое, которое делится нахр1, но не делится на ру+', учитывается ровно,у рэз: один раз — в (и/р), другой раз — в (и/рз), ...и, наконец, в 1п/р~). Таким образом, учитываются все случаи, когда р является простым множителем в и!. Теперь возникает еще один естественный вопрос. Мы определили и! для неотрицательных целых чисел и. Но, возможно, факториальная функция имеет смысл также для рациональных и даже для действительных чисел п? Например, чему равен (г)!7 Для иллюстрации этого вопроса давайте введем "термиальную" функцию п7 = 1+ 2+ + и = ~~~ к, в=1 (9) которая аналогична факториальной, за исключением того, что здесь выполняется сложение, а не умножение. Из формулы 1.2.3 — (15) мы уже знаем, чему равна сумма арифметической прогрессии: и! = 1+ ~1 — — )и+ ~1 — — + — )п(и — 1) 1(У' ~ 1! 2!) 1 1 11 + (1 — — + — — — )п(п — 1)(п — 2) + 1! 2! 3(') (Мы докажем эту формулу в следующем разделе.) Данная сумма из соотношения (11) кажется бесконечной, но на самом деле она конечна для любого неотрицательного целого и.
Тем не менее формула (11) не дает желаемого обобщения для функции и!, так как бесконечная сумма сходится пголько в том случае, если и— неотрицательное целое число (см. упр. 1б). Но Стирлинг не упал духом и нашел последовательность аы аг,..., такую, что 1пи! = аги+ агп(и — 1) + . ° = Е аь+г П (п — у) (12) о<1<э ь>о Однако он не смог доказапгь, что зта сумма определяет функцию и! для всех дробных п, хотя и нашел значение ( г)! = ~(к/2. Приблизительно в то же время данной задачей занимался и Леонард Эйлер (ЬеопЬагт! Еп!ег), и именно он первым нашел обоснованное обобщение; аги! и! = !пп т — ~со (п+ 1)(п+ 2)...
(и + т) (13) Эйлер изложил эту идею в письме Христиану Гольдбаху (СЬНэНал СоЫЬасЬ) от 13 октября 1729 года. В его формуле п! определяется для любого значения и, пу — гп(и + 1). (10) Таким образом., используя формулу (10) вместо (9), можно обобщить определение "термиальной" функции для произвольного п. И, отвечая на заданный выше вопрос, получим (г)7 — й. Стирлинг сам предпринял несколько попыток обобщить понятие факториала п! для нецелых п. Он представил приближение (7) в виде бесконечной суммы, но, к сожалению, эта сумма не сходилась ни для одного значения и.
Формула (7) дает очень хорошее приближение, но ее нельзя продолжить так, чтобы получить пгочное значение. [Эта довольно необычная ситуация обсуждается в книге К. Кнорр, ТЬеогу апд Арр!!сабоп об 1пбл!се Бег!еэ, 2пс1 е0. (С!аяйож: В!аде, 195Ц, 518 — 520, 527, 534.] Стирлинг предпринял еще одну попытку, обратив внимание на то. что — 1 -6 — 4 0 1 2 3 4 -3 -2— Рис. 7. Функция Г(х) = (х — 1)!. Локальный минимум в точке Х имеет координаты (1.46163 21449 68362 34126 26595, 0.88560 31944 10888 70027 88159).
за исключением целых отрицательных, для которых знаменатель в формуле (11) обращается в нуль; в таких случаях п! считается равным бесконечности. В упр. 8 и 22 объясняется, почему формула (13) является обоснованным разумным определением факториала. Примерно двумя столетиями позже, в 1900 году, Ш. Эрмит (С. Негт11е) доказал, что на самом деле формула Стирлинга (12) корректно определяет п! для нецелых п и что фактически обобщения Эйлера и Стирлинга идентичны. В прошлые века для факториалов использовались самые разные обозначения. Эйлер писал [п], Гаусс (Санвз) — П п, а в Англии и Италии были популярны символы (п и п!. В наше время для целых п универсальным обозначением факториала является п1; его ввел сравнительно малоизвестный математик Кристиан Крамп (Спг!611ап Кгатр) в своем учебнике по алгебре (Е!етепз ЕАг!Г)!тес!дне (!и!уегге!!е (Со!обпе: 1808)). Но для пецелых п запись и! не является общепринятой; в этом случае обычно используется обозначение, которое ввел А.
М. Лежандр (А. М. 1ебепдге): (14) п! = Г(п+ 1) = пГ(п). получаем формулу для нее: Функция Г(х) называется гамма-функцией, и из (13) х! пх Г(х) = — = 11т х и -~се х (х + 1) (х + 2) . (х+ т) График функции Г(х) показан на рис. 7. Формулы (13) и (15) определяют факториалы и гамма-функцию как для действительных, так и для комплексных чисел; но если подразумевается переменная, имеющая и деиствителъную; и мнямую части, то для ее обозначения обычно яспользуется буква в, а не и илн х. Связь между факторналом и гамма-функцией выражается не только формуйой в1 = Г(в + 1), но и соотношением ( — в)! Г(в) = (16) шпетт которое выполняется для всех нецелых в (см.
упр. 23). Хотя Г(х) равна бесконечности для отрицательного целого или равного нулю в, функция 1/Г(в) корректно определяетси для всех комплексных в (см. упр. 1.2.7 — 24). Применяя гамма-функцию в теоретических исследованиях, часто приходится падь зоваться интегральным представлением Германа Ганкеля (Неппапп Нап1се1): 1 1 е'~й Г(в) 2~п' ~ Р причем путь интегрирования в комплексной плоскости идет из — оо по отрипдтельной части действительной оси, затем огибает начало координат в положителъном направлении (против ч~совой стрелки) н опись по отрицательной части осн Х возвращаетсл в — оо.
[Хейясйпй 1ш Маей. шк1 РЬувЫс 9 (1864), 1-2Ц Во многих формулах дискретной математики используются произведения факториального типа, которые называются фактлориальнмми стпеяенлми. Для положительного целого й величины хй и хь определяются следующим образом: х- = х(х — 1)...(х — А+1) = П(х — у); (18) *"= (х+Ч (х+ — )=П(х+Я Так, например, величина р„ъ из (2) — это просто нь. Заметим, что (19) х = (х+й — 1)- = ( — 1)"(-х)-. (20) Общие формулы УПРАЖНЕНИЯ т.
[ОО» Сколькими способами можно перетасовать колоду вз 52 карт? 2. [10] Используя обозначения из соотношения (2), покажите, что р„1„П = р, и объясните, почему вто твк. х! 1 Г(х+ к) (21) (х — к)1 Г(х) можно использовать для определения фвкториалъных степеней для не целых значений Е [Обозначение х" ввел А.
Калеллн (А. Саре[5) в работе 01огпа1е сй Масешабсйе й' Ваиай[пи 31 (1893), 291 — 313.] Захватывающая история изучения факториалов со времен Стирлннга до наших дней прослежена в статье Р. Л. ПаИе "ЬеопЬагд Еп1ег'в штейгай А Ь[всог1са[ ргоб!е о1 1Ье йапппа йшсбоп" АММ 66 (1959), 849-869; см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
