Задача «сумма факториалов» решение

Свойства

Комбинаторная интерпретация

В комбинаторике факториал натурального числа n интерпретируется как количество перестановок (упорядочиваний) множества из n элементов. Например, для множества {A,B,C,D} из 4-х элементов существует 4! = 24 перестановки:

ABCD  BACD  CABD  DABC
ABDC  BADC  CADB  DACB
ACBD  BCAD  CBAD  DBAC
ACDB  BCDA  CBDA  DBCA
ADBC  BDAC  CDAB  DCAB
ADCB  BDCA  CDBA  DCBA

Комбинаторная интерпретация факториала подтверждает целесообразность соглашения !=1{\displaystyle 0!=1}. Так, формула для числа размещений из n{\displaystyle n} элементов по m{\displaystyle m}

Anm=n!(n−m)!{\displaystyle A_{n}^{m}={\frac {n!}{(n-m)!}}}

при n=m{\displaystyle n=m} обращается в формулу для числа перестановок из n{\displaystyle n} элементов (порядка n{\displaystyle n}), которое равно n!{\displaystyle n!}.

Связь с гамма-функцией

Пи-функция, определённая для всех вещественных чисел, кроме отрицательных целых, и совпадающая при натуральных значениях аргумента с факториалом.

Факториал связан с гамма-функцией от целочисленного аргумента соотношением

n!=Γ(n+1){\displaystyle n!=\Gamma (n+1)}.

Это же выражение используют для обобщения понятия факториала на множество вещественных чисел. Используя аналитическое продолжение гамма-функции, область определения факториала также расширяют на всю комплексную плоскость, исключая особые точки при n=−1,−2,−3…{\displaystyle n=-1,-2,-3\ldots }.

Непосредственным обобщением факториала на множества вещественных и комплексных чисел служит пи-функция Π(z)=Γ(z+1){\displaystyle \Pi (z)=\Gamma (z+1)}, которая при Re(z)>−1{\displaystyle \mathrm {Re} (z)>-1} может быть определена как

Π(z)=∫∞tze−tdt{\displaystyle \Pi (z)=\int _{0}^{\infty }t^{z}e^{-t}\,\mathrm {d} t} (интегральное определение).

Пи-функция натурального числа или нуля совпадает с его факториалом: Π(n)=n!{\displaystyle \Pi (n)=n!}. Как и факториал, пи-функция удовлетворяет рекуррентному соотношению Π(z)=zΠ(z−1){\displaystyle \Pi (z)=z\Pi (z-1)}.

Формула Стирлинга

Формула Стирлинга — асимптотическая формула для вычисления факториала:

n!=2πn(ne)n(1+112n+1288n2−13951840n3−5712488320n4+163879209018880n5+524681975246796800n6+O(n−7)),{\displaystyle n!={\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\left(1+{\frac {1}{12n}}+{\frac {1}{288n^{2}}}-{\frac {139}{51840n^{3}}}-{\frac {571}{2488320n^{4}}}+{\frac {163879}{209018880n^{5}}}+{\frac {5246819}{75246796800n^{6}}}+O\left(n^{-7}\right)\right),}

см. O-большое.

Во многих случаях для приближённого значения факториала достаточно рассматривать только главный член формулы Стирлинга:

n!≈2πn(ne)n.{\displaystyle n!\approx {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}.}

При этом можно утверждать, что

2πn(ne)ne1(12n+1)n!2πn(ne)ne1(12n).{\displaystyle {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}e^{1/(12n+1)}

Формула Стирлинга позволяет получить приближённые значения факториалов больших чисел без непосредственного перемножения последовательности натуральных чисел. Например, с помощью формулы Стирлинга легко подсчитать, что

  • 100! ≈ 9,33×10157;
  • 1000! ≈ 4,02×102567;
  • 10 000! ≈ 2,85×1035 659.

Разложение на простые числа

Каждое простое число p входит в разложение n! на простые множители в степени

⌊np⌋+⌊np2⌋+⌊np3⌋+….{\displaystyle \left\lfloor {\frac {n}{p}}\right\rfloor +\left\lfloor {\frac {n}{p^{2}}}\right\rfloor +\left\lfloor {\frac {n}{p^{3}}}\right\rfloor +\ldots .}

Таким образом,

n!=∏pp⌊np⌋+⌊np2⌋+…,{\displaystyle n!=\prod _{p}p^{\lfloor {\frac {n}{p}}\rfloor +\lfloor {\frac {n}{p^{2}}}\rfloor +\ldots },}

где произведение берётся по всем простым числам. Можно заметить, что для всякого простого p большего n соответствующий множитель в произведении равен 1, следовательно произведение можно брать лишь по простым p, не превосходящим n.

Связь с производной от степенной функции

Для целого неотрицательного числа n:

(xn)(n)=n!{\displaystyle \left(x^{n}\right)^{(n)}=n!}

Например:

(x5)(5)=(5⋅x4)(4)=(5⋅4⋅x3)‴=(5⋅4⋅3⋅x2)″=(5⋅4⋅3⋅2⋅x)′=5⋅4⋅3⋅2⋅1=5!{\displaystyle \left(x^{5}\right)^{(5)}=\left(5\cdot x^{4}\right)^{(4)}=\left(5\cdot 4\cdot x^{3}\right)»’=\left(5\cdot 4\cdot 3\cdot x^{2}\right)»=\left(5\cdot 4\cdot 3\cdot 2\cdot x\right)’={5\cdot 4\cdot 3\cdot 2\cdot 1}=5!}

Другие свойства

Для натурального числа n:

n!2⩾nn⩾n!⩾n{\displaystyle n!^{2}\geqslant n^{n}\geqslant n!\geqslant n}
Для любого n>1:

n!{\displaystyle n!} не является квадратом целого числа.

Факториалы

Что такое факториалы и как их решать

Факториал числа n, который в математике обозначают буквой латиницы n, после которой следует
восклицательный знак !. Произносится голосом это выражение как “н факториал”. Факториал – это результат
последовательного умножения между собой последовательности натуральных чисел с 1 и до искомого числа n.
Например, 5! = 1 х 2 х 3 х 4 х 5=720Факториал числа n обозначается латинской буквой n! и произносится
как эн факториал. Представляет собой последовательное перемножение (произведение) всех натуральных чисел
начиная с 1 до числа n.
Например: 6! = 1 х 2 х 3 х 4 х 5=720

Факториал имеет математический смысл, только тогда, когда если это число целое и положительное
(натуральное). Этот смысл следует из самого определения факториала, т.к. все натуральные числа
неотрицательные и целые. Значения факториалов, а именно результат умножения последовательности от
единицы до числа n можно посмотреть в таблице факториалов. Такая таблица возможна, по причине того, что
значение факториала любого целого числа известно заранее и является, так сказать, табличным
значением.

По определению 0! = 1. То есть если имеется ноль факториал, то мы ничего не перемножаем и результат будет
первым натуральным существующим числом, то есть один.

Рост функции факториала можно отобразить на графике. Это будет дуга, похожая на функцию икса в квадрате,
которая будет стремиться быстро вверх.

Факториал – является быстрорастущей функцией. Она растет по графику быстрее, чем функция многочлена любой
степени и даже экспоненциальная функция. Факториал растет быстрее многочлена любой степени и
экспоненциальной функции (но при этом медленнее двойной экспоненциальной функции). Именно поэтому, чтобы
посчитать факториал вручную могут быть сложности, так как результатом может получиться очень большое
число. Чтобы не считать факториал вручную, можно воспользоваться калькулятором подсчёта факториалов, с
помощью которого вы можете быстро получить ответ. Факториал применяется в функциональном анализе, теории
чисел и комбинаторике, в которой имеет большой математический смысл, связанный с числом всевозможных
неупорядоченных комбинаций объектов (чисел).

Чтобы быстро рассчитать число комбинаций n чисел, нужно всего лишь посчитать n!. После подсчёта значения
факториала калькулятором, искомое значение можно использовать в решении более сложных задач.
Вы можете посмотреть необходимый факториал в таблице: «Таблица
факториалов»

История

Факториальные выражения появились ещё в ранних исследованиях по комбинаторике, хотя компактное обозначение n!{\displaystyle n!} предложил французский математик Кристиан Крамп только в 1808 году. Важным этапом стало открытие формулы Стирлинга, которую Джеймс Стирлинг опубликовал в своём трактате «Дифференциальный метод» (лат. Methodus differentialis, 1730 год). Немного ранее почти такую же формулу опубликовал друг Стирлинга Абрахам де Муавр, но в менее завершённом виде (вместо коэффициента 2π{\displaystyle {\sqrt {2\pi }}} была неопределённая константа).

Стирлинг подробно исследовал свойства факториала, вплоть до выяснения вопроса о том, нельзя ли распространить это понятие на произвольные вещественные числа. Он описал несколько возможных путей к реализации этой идеи и высказал мнение, что:

(12)!=π2{\displaystyle \left({1 \over 2}\right)!={\frac {\sqrt {\pi }}{2}}}

Стирлинг не знал, что годом ранее решение проблемы уже нашёл Леонард Эйлер. В письме к Кристиану Гольдбаху Эйлер описал требуемое обобщение:

x!=limm→∞mxm!(x+1)(x+2)…(x+m){\displaystyle x!=\lim _{m\to \infty }{\frac {m^{x}m!}{(x+1)(x+2)\dots (x+m)}}}

Развивая эту идею, Эйлер в следующем, 1730 году ввёл понятие гамма-функции в виде классического интеграла. Эти результаты он опубликовал в журнале Санкт-Петербургской Академии наук в 1729—1730 годах.

Рассмотрим пример из комбинаторики

Лотерея

Всем известны различные лотереи, где игрокам требуется угадать комбинацию 6 чисел из 52 возможных. Правила могут отличаться, иногда требуется угадать 5 чисел из 60 или 6 из 90. Пусть вы купили билет классической лотереи «Спортлото» и для выигрыша вам требуется угадать комбинацию 6 чисел из 49 возможных. Какова вероятность выиграть главный приз? К нам на помощь приходит комбинаторика и факториалы. Общее количество возможных комбинаций для данного примера рассчитывается по формуле:

Общее количество 6 из 49 = 49! / (6! × 43!)

Воспользуемся калькулятором и по отдельности вычислим значения факториалов:

Общее количество 6 из 49 = 6,072e+62 / 720 × 6,030e+52 = 13 985 627.

Это означает, существует приблизительно 14 миллионов шестиэлементных комбинаций, образованных из 49 чисел. Следовательно, вероятность выигрыша в «Спортлото» составляет 1 к 14 миллионам.

Другие виды факториалов

Помимо стандартного n! для ряда натуральных чисел существуют также экзотические виды факториала, которые рассчитываются для четных/нечетных или простых чисел. Последний называется праймориал и рассчитывается для последовательности простых чисел меньших или равных заданному. К примеру, праймориал первых 7 простых чисел представляет собой:

p7 = 2 × 3 × 5 × 7 × 11 × 13 × 17 = 510 510

Кроме того, существует суперфакториал, который представляет собой произведение первых n факториалов. Например, суперфакториал 5 равен:

sf(5) = 1! × 2! × 3! × 4! × 5! = 1 × 2 × 6 × 24 × 120 = 34 560

Очевидно, что последовательность суперфакториалов является самой быстрорастущей.

Наша программа использует формулу Стирлинга для вычисления сколь угодно больших факториалов. Для небольших чисел не забывайте округлять результат до целого в большую сторону, так как факториал — это всегда целое число.

Основная информация

Сначала заметим, что математически факториал записывается при помощи восклицательного знака. Такая запись выглядит как n!, а читается как эн-факториал. Математический смысл факториала состоит в произведении последовательных натуральных чисел от 1 до n:

n! = 1 × 2 × 3 … (n − 2) × (n − 1) × n,

где n — заданное количество натуральных чисел.

Первые значения n! выглядят так:

  • 1! = 1
  • 2! = 2
  • 3! = 6
  • 4! = 24
  • 5! = 120

Факториал очень быстро растущая функция, если 5! эквивалентно 120, то 15! составляет уже 1 307 674 368 000, а 50! имеет в своем составе 64 нуля. Факториал возник в комбинаторике при расчете количества перестановок множества из n-ного количества элементов. К примеру, для трехэлементного множества Z = {A, B, C} существует 3! = 6 вариантов перестановок:

  • ABC;
  • ACB;
  • BAC;
  • BCA;
  • CAB;
  • CBA.

Теоретико-множественное обоснование смысла факториала позволило доказать парадоксальное на первый взгляд утверждение, что 0! = 1. Ноль-факториал, по сути, представляет собой 0 × 1, а каждый пятиклассник знает, что при умножении на ноль в результате также будет ноль. Пустое же множество, не содержащее элементов, может быть упорядоченно одним единственным способом, поэтому факториал нуля равен единице. В целом факториал находит широкое применение в теории чисел, теории вероятностей, функциональном анализе, комбинаторике, а также при разложении функций в ряд Тейлора.

Ссылка на основную публикацию