Факториал числа n это

Факториал числа n это

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

Комбинаторная интерпретация факториала служит обоснованием тождества 0! = 1, т. к. пустое множество упорядочено единственным способом.

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

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

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

Путём аналитического продолжения её также расширяют и на всю комплексную плоскость, исключая особые точки при

Более непосредственным обобщением факториала на множество вещественных (и комплексных) чисел является пи-функция, определяемая как

Поскольку то пи-функция натурального числа совпадает с его факториалом: Как факториал, пи-функция удовлетворяет рекурсивному соотношению

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

см. O-большое. Коэффициенты этого разложения дают последовательность A001163 в OEIS (числители) и последовательность A001164 в OEIS (знаменатели).

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

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

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

  • 100! ≈ 9,33×10 157 ;
  • 1000! ≈ 4,02×10 2567 ;
  • 10 000! ≈ 2,85×10 35 659 .

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

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

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

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

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

Обобщения

Двойной факториал

Двойной факториал числа n обозначается n!! и определяется как произведение всех натуральных чисел в отрезке [1, n ], имеющих ту же чётность что и n . Таким образом,

По определению полагают 0!! = 1.

Последовательность значений n!! начинается так:

1, 1, 2, 3, 8, 15, 48, 105, 384, 945, 3840, 10 395, 46 080, 135 135, 645 120, 2 027 025, 10 321 920, 34 459 425, 185 794 560, 654 729 075, 3 715 891 200, 13 749 310 575, 81 749 606 400, 316 234 143 225, 1 961 990 553 600, 7 905 853 580 625, 51 011 754 393 600, … (последовательность A006882 в OEIS).

Кратный факториал

m -Кратный факториал числа n обозначается и определяется следующим образом:

Пусть число n представимо в виде где Тогда [1]

Двойной факториал является частным случаем m -кратного факториала для m = 2.

Кратный факториал связан с гамма-функцией следующим соотношением [2] :

Убывающий факториал

Убывающим факториалом (или неполным факториалом) называется выражение

Убывающий факториал даёт число размещений из n по k .

Возрастающий факториал

Возрастающим факториалом называется выражение

Праймориал или примориал

Праймориал или примориал (англ. primorial ) числа n обозначается n# и определяется как произведение всех простых чисел, не превышающих n. Например,

11# = 12# = 2 · 3 · 5 · 7 · 11 = 2310.

Последовательность праймориалов (включая ) начинается так:

1, 2, 6, 30, 210, 2310, 30 030, 510 510, 9 699 690, 223 092 870, 6 469 693 230, 200 560 490 130, 7 420 738 134 810, 304 250 263 527 210, 13 082 761 331 670 030, 614 889 782 588 491 410, 32 589 158 477 190 044 730, 1 922 760 350 154 212 639 070, … (последовательность A002110 в OEIS).

Суперфакториалы

Нейл Слоан и Саймон Плоуф (англ.) в 1995 году определили суперфакториал как произведение первых n факториалов. Согласно этому определению, суперфакториал четырёх равен

(поскольку устоявшегося обозначения нет, используется функциональное).

Последовательность суперфакториалов чисел n⩾0 начинается так:

1, 1, 2, 12, 288, 34 560, 24 883 200, … (последовательность A000178 в OEIS).

Идея была обобщена в 2000 году Генри Боттомли (англ.), что привело к гиперфакториалам (англ. Superduperfactorial ), которые являются произведением первых n суперфакториалов. Последовательность гиперфакториалов чисел n⩾0 начинается так:

Читайте также:  Май топ апс что это

1, 1, 2, 24, 6912, 238 878 720, 5 944 066 965 504 000, 125 411 328 000, 5 056 584 744 960 000, 1 834 933 472 251 084 800 000, 6 658 606 584 104 736 522 240 000 000, 265 790 267 296 391 946 810 949 632 000 000 000, 127 313 963 299 399 416 749 559 771 247 411 200 000 000 000 … (последовательность A055462 в OEIS)

Продолжая рекуррентно, можно определить факториал кратного уровня, или m -уровневый факториал числа n , как произведение первых n ( m −1)-уровневых факториалов, то есть

где для 0" border="0" /> и

Субфакториал

Субфакториал ! n определяется как количество беспорядков порядка n , то есть перестановок n -элементного множества без неподвижных точек.

Ссылки

См. также

Примечания

  1. «Энциклопедия для детей» Аванта+. Математика.
  2. wolframalpha.com.
Математические знаки
Плюс ( + ) • Минус ( ) • Знак умножения ( · или × ) • Знак деления ( : или / ) • Знак корня ( ) • Знак равенства ( =, , и др.) • Знаки неравенства ( , >, Факториал ( ! ) • Вертикальная черта ( | ) • Знак градуса ( ° ) • Минута градуса ( ) • Секунда градуса ( ) • Штрих ( ) • Звёздочка ( * ) • Обратная косая черта, бэкслеш ( ) • Процент ( % ) • Промилле ( ) • Тильда (

Wikimedia Foundation . 2010 .

Смотреть что такое "Факториал" в других словарях:

ФАКТОРИАЛ — [англ. factorial Словарь иностранных слов русского языка

ФАКТОРИАЛ — (обозначение «!»), число, получаемое в результате умножения данного числа на все целые числа меньше него. Например, факториал числа 6 равен 6!=6.5.4.3.2.1=720. Факториалом нуля считают 0!=1 … Научно-технический энциклопедический словарь

ФАКТОРИАЛ — (от латинского factor деятель, создатель, множитель), произведение натуральных чисел от единицы до какого либо данного натурального числа n, т.е. 1?2. n; обозначается n! … Современная энциклопедия

ФАКТОРИАЛ — произведение натуральных чисел от единицы до какого либо данного натурального числа n, т. е. 1.2.3. .n; обозначается n!. Напр., 5! = 1.2.3.4.5 = 120 … Большой Энциклопедический словарь

факториал — сущ., кол во синонимов: 1 • термин (18) Словарь синонимов ASIS. В.Н. Тришин. 2013 … Словарь синонимов

Факториал — (от латинского factor деятель, создатель, множитель), произведение натуральных чисел от единицы до какого либо данного натурального числа n, т.е. 1´2´. ´n; обозначается n!. … Иллюстрированный энциклопедический словарь

ФАКТОРИАЛ — произведение всех натуральных чисел от 1 до данного натурального числа n; обозначается n! = 1·2·3·. ·n; по определению, 0! = 1 … Большая политехническая энциклопедия

Факториал — математическая функция целочисленного аргумента, обозначается n! (произведение целых чисел от 1 до n, весьма быстро растет с ростом аргумента); в данном случае возможна ассоциация с ее обозначением восклицательным знаком: ஐ Шел он сквозь… … Мир Лема — словарь и путеводитель

факториал — произведение натуральных чисел от единицы до какого либо данного натурального числа n, то есть 1·2·3·. ·n; обозначается: n!. Например, 5! = 1·2·3·4·5 = 120. * * * ФАКТОРИАЛ ФАКТОРИАЛ, произведение натуральных чисел от единицы до какого либо… … Энциклопедический словарь

факториал — faktorialas statusas T sritis fizika atitikmenys: angl. factorial vok. Faktorielle, f; Fakultät, f rus. факториал, m pranc. factorielle, f … Fizikos terminų žodynas

Этот цикл статей я хочу посвятить обзору математических возможностей python 2.7. Вместе с моей любимой змеёй мы окунёмся в тайны математики и напишем такие функции, который просто поразят воображение. Итак, запускайте python, включайте голову, вперёд!

  1. Занимательная Математика, Очаровательный Python. Эпизод 1: Факториалы
  2. Занимательная Математика, Очаровательный Python. Эпизод 2: Праймориалы И Факторионы
  3. Занимательная Математика, Очаровательный Python. Эпизод 3: Финальный Аккорд
  1. Python (я буду использовать версию 2.7.5 под Windows 64 bit)
  2. Мозги (я буду пользовать свои с примесью google и wikipedia)

Факториал

Факториалы манили меня еще в школе. Красивое слово, необычный (для того времени) синтаксис. Я всегда с некоторой издевкой мог блеснуть талантом, ”вычисляя” факториал простого числа. Став старше, и особенно влюбившись в python, моя страсть к факториалам не просто не уменьшилась, скорее наоборот, именно поэтому эта статья полностью будет посвящена всевозможным факториалам. Но сначала немного математики. Итак,

Факториалом числа n (обозначается n!) называется произведение всех натуральных чисел от 1 до n. Wikipedia

Физический смысл (если так можно сказать) факториала определяется как число упорядочиваний множества из n элементов. Переводя с непонятного на русский, давайте представим себе колоду из 36 карт. Каждый раз, когда мы тасуем эту колоду мы создаем уникальное упорядочивание, одно из Возможно, именно поэтому карточные игры так популярны! &#128578;

Но ближе к делу! Наверняка каждый, кто изучал python, знает как вычислить факториал, причем не одним способом. Когда изучают lambda-функции, пишут так:

… и мало кто что понимает!

Когда изучают рекурсию, пишут так:

Это уже понятней! А те, кто совсем хорошо знают python, вообще не парятся и делают так:

Но мы пойдём своим путём. Мы не будем использовать math, вместо этого мы напишем свой собственный модуль. Откройте свой любимый редактор (я буду пользоваться стандартным IDLE), создайте файл factorials.py и давайте творить! В качестве простейшей задачи сначала давайте определим функцию для вычисления факториала. Я буду делать это с помощью lambda, как в первом примере:

Теперь, если запустить скрипт на выполнение, то можно будет прямо в интерактивном интерпретаторе набрать

Казалось бы супер! И все примеры, которые можно найти в интернете здесь заканчиваются на позитивной ноте, однако как обычно все не так просто. На самом деле наша функция абсолютно некорректна и простейший способ проверить это — передать ей неадекватное значение. И если с совсем бредятинкой типа str python справится сам, то вот значение типа float легко пропустит. Не верите? Попробуйте посчитать факториал 4.125. Не бином Ньютона, что наша новорожденная функция должна работать только с целочисленным типом данных, следовательно нужно переписать её так:

Во-о-о-т! Теперь скормить ересь не получится, так как сразу будет подниматься TypeError . Но и это еще не всё. Если мы попробуем посчитать факториал -5 (минус пяти), то получим в ответ единицу, а это тоже неадекватно. Факториал определяется только для целых и положительных цифр, следовательно нужно ещё раз переписать код.

Для эстетов еще могу порекомендовать обработать значения типа float , которые по сути являются целыми, типа 25.0, 12.0 etc. Я этого делать не буду, так как предпочитаю более жёстко обращаться с типами данных.

Обратный факториал

Простейшая задача выполнена, но я бы не стал городить всё это только ради простейшей задачи! &#128578; Куда более интересно найти обратный факториал. Легко догадаться, что

Обратным факториалом числа i называется такое число, факториал которого будет равен i.

Понятие факториала известно всем. Это функция, вычисляющая произведение последовательных натуральных чисел от 1 до N включительно: N! = 1 * 2 * 3 *… * N. Факториал — быстрорастущая функция, уже для небольших значений N значение N! имеет много значащих цифр.

Попробуем реализовать эту функцию на языке программирования. Очевидно, нам понадобиться язык, поддерживающий длинную арифметику. Я воспользуюсь C#, но с таким же успехом можно взять Java или Python.

Итак, простейшая реализация (назовем ее наивной) получается прямо из определения факториала:

На моей машине эта реализация работает примерно 1,6 секунд для N=50 000.

Далее рассмотрим алгоритмы, которые работают намного быстрее наивной реализации.

Алгоритм вычисления деревом

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

Пусть нам нужно найти произведение последовательных чисел от L до R, обозначим его как P(L, R). Разделим интервал от L до R пополам и посчитаем P(L, R) как P(L, M) * P(M + 1, R), где M находится посередине между L и R, M = (L + R) / 2. Заметим, что множители будут примерно одинаковой длины. Аналогично разобьем P(L, M) и P(M + 1, R). Будем производить эту операцию, пока в каждом интервале останется не более двух множителей. Очевидно, что P(L, R) = L, если L и R равны, и P(L, R) = L * R, если L и R отличаются на единицу. Чтобы найти N! нужно посчитать P(2, N).

Посмотрим, как будет работать наш алгоритм для N=10, найдем P(2, 10):

P(2, 10)
P(2, 6) * P(7, 10)
( P(2, 4) * P(5, 6) ) * ( P(7, 8) * P(9, 10) )
( (P(2, 3) * P(4) ) * P(5, 6) ) * ( P(7, 8) * P(9, 10) )
( ( (2 * 3) * (4) ) * (5 * 6) ) * ( (7 * 8) * (9 * 10) )
( ( 6 * 4 ) * 30 ) * ( 56 * 90 )
( 24 * 30 ) * ( 5 040 )
720 * 5 040
3 628 800

Получается своеобразное дерево, где множители находятся в узлах, а результат получается в корне

Реализуем описанный алгоритм:

Для N=50 000 факториал вычисляется за 0,9 секунд, что почти вдвое быстрее, чем в наивной реализации.

Алгоритм вычисления факторизацией

Второй алгоритм быстрого вычисления использует разложение факториала на простые множители (факторизацию). Очевидно, что в разложении N! участвуют только простые множители от 2 до N. Попробуем посчитать, сколько раз простой множитель K содержится в N!, то есть узнаем степень множителя K в разложении. Каждый K-ый член произведения 1 * 2 * 3 *… * N увеличивает показатель на единицу, то есть показатель степени будет равен N / K. Но каждый K 2 -ый член увеличивает степень еще на единицу, то есть показатель становится N / K + N / K 2 . Аналогично для K 3 , K 4 и так далее. В итоге получим, что показатель степени при простом множителе K будет равен N / K + N / K 2 + N / K 3 + N / K 4 +…

Для наглядности посчитаем, сколько раз двойка содержится в 10! Двойку дает каждый второй множитель (2, 4, 6, 8 и 10), всего таких множителей 10 / 2 = 5. Каждый четвертый дает четверку (2 2 ), всего таких множителей 10 / 4 = 2 (4 и 8). Каждый восьмой дает восьмерку (2 3 ), такой множитель всего один 10 / 8 = 1 (8). Шестнадцать (2 4 ) и более уже не дает ни один множитель, значит, подсчет можно завершать. Суммируя, получим, что показатель степени при двойке в разложении 10! на простые множители будет равен 10 / 2 + 10 / 4 + 10 / 8 = 5 + 2 + 1 = 8.

Если действовать таким же образом, можно найти показатели при 3, 5 и 7 в разложении 10!, после чего остается только вычислить значение произведения:

10! = 2 8 * 3 4 * 5 2 * 7 1 = 3 628 800

Осталось найти простые числа от 2 до N, для этого можно использовать решето Эратосфена:

Эта реализация также тратит примерно 0,9 секунд на вычисление 50 000!

Как справедливо отметил pomme скорость вычисления факториала на 98% зависит от скорости умножения. Попробуем протестировать наши алгоритмы, реализовав их на C++ с использованием библиотеки GMP. Результаты тестирования приведены ниже, по ним получается что алгоритм умножения в C# имеет довольно странную асимптотику, поэтому оптимизация дает относительно небольшой выигрыш в C# и огромный в C++ с GMP. Однако этому вопросу вероятно стоит посвятить отдельную статью.

Все алгоритмы тестировались для N равном 1 000, 2 000, 5 000, 10 000, 20 000, 50 000 и 100 000 десятью итерациями. В таблице указано среднее значение времени работы в миллисекундах.

График с линейной шкалой

График с логарифмической шкалой

Идеи и алгоритмы из комментариев

Хабражители предложили немало интересных идей и алгоритмов в ответ на мою статью, здесь я оставлю ссылки на лучшие из них

Исходные коды реализованных алгоритмов приведены под спойлерами

Ссылка на основную публикацию
Файл с расширением dav чем открыть
Файл формата DAV открывается специальными программами. Чтобы открыть данный формат, скачайте одну из предложенных программ. Чем открыть файл в формате...
У вас сломался холодильник
Поломка холодильника всегда застает в врасплох. И определить причину моментально практически невозможно. Нужно как можно быстрее «спасти» продукты. Обычно надолго...
У каких марок телефонов хорошая камера
Производители будто бы соревнуются - кто сколько датчиков встроит в девайс. Есть уже с четырьмя и даже пятью камерами! Как...
Файл подкачки windows 7 на флешку
В прошлой статье рассказано, как определиться с оптимальным размером файла подкачки, что делать с SSD-дисками и как установить размер файла...
Adblock detector