Сегодня у нас достаточно простая статья, связанная с занимательной математикой. Я думаю, все прекрасно, знают, что такое факториал:
![Приветствую Вас, уважаемые Читатели! Сегодня у нас достаточно простая статья, связанная с занимательной математикой.](https://habrastorage.org/getpro/habr/upload_files/823/117/8e0/8231178e0efe6ab4079b773927a48c0a.png)
Более изощренные любители математики знают и про такое понятие, как субфакториал:
![Приветствую Вас, уважаемые Читатели! Сегодня у нас достаточно простая статья, связанная с занимательной математикой.-2](https://habrastorage.org/getpro/habr/upload_files/15a/a64/5a6/15aa645a6b5bac3d832759d15d402431.png)
Субфакториал
Субфакториал (или subfactorial) - обозначается символом !n и представляет собой количество перестановок n элементов, в которых ни один элемент не остается на своем месте (по сути - это аналогия полного беспорядка). Для небольших значений n это можно проиллюстрировать следующим образом:
Для n = 1: !1 = 0. Единственный элемент не может "переставляться" сам с собой.
Для n = 2: !2 = 1. Всего две возможные перестановки (1, 2) и (2, 1), и только одна из них соответствует требованию "ни один не остается на своем месте".
Для n = 3: !3 = 2. Возможные перестановки: (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1). В двух из них ни один элемент не остается на своем месте: (2, 3, 1) и (3, 1, 2).
![Первая книга, в которой обсуждался факториал называется "Анализ азартных игр", и написана в 1708 году французским математиком Пьером Ремонтом де Монмором Первая книга, в которой обсуждался факториал называется "Анализ азартных игр", и написана в 1708 году французским математиком Пьером Ремонтом де Монмором](https://habrastorage.org/getpro/habr/upload_files/c3f/34e/cad/c3f34ecad7725d9f6ae02feff69cb199.png)
Более жизненная интерпретация субфакториала: профессор дал тест 4 студентам – 1, 2, 3 и 4 – и хочет, чтобы они оценили тесты друг друга. Конечно, ни один студент не должен оценивать свой собственный тест. Сколько существует способов, чтобы никто не получил обратно свой собственный тест для проверки?
![Таких вариантов 9, как и показывает формула Таких вариантов 9, как и показывает формула](https://habrastorage.org/getpro/habr/upload_files/ff7/54b/976/ff754b976d20c5bcb497bae1527d0c70.png)
Первые десять значений субфакториалов натуральных чисел:
!1 = 0
!2 = 1
!3 = 2
!4 = 9
!5 = 44
!6 = 265
!7 = 1854
!8 = 14833
!9 = 133496
!10 = 1334961
Если внимательно присмотреться к формуле субфакториала, то можно увидеть, что она очень похожа на формулу разложения экспоненты в ряд Тейлора:
![](https://habrastorage.org/getpro/habr/upload_files/f3f/de1/01b/f3fde101ba6cd9583ff75af993535660.png)
Если подставить "-1" вместо n, то можно получить любопытное отношение между факториалом и субфакториалом:
![](https://habrastorage.org/getpro/habr/upload_files/66d/d1d/974/66dd1d9748ad8980133cb475df141a8c.png)
Эта величина - предел вероятности того, что выбранная во множестве перестановка является полным беспорядком. А еще можно увидеть, что !n является ближайшим целым числом к n!/e:
![](https://habrastorage.org/getpro/habr/upload_files/afe/164/957/afe16495750d806a493763c592644e08.png)
Субфакторион
Теперь перейдем к субфакторионам - числам, которые равны сумме субфакториалов своих цифр. Для начала определим верхнюю границу таких чисел. Итак:
![Всё, что больше уже выбывает из статуса кандидата. Т.е. мы установили, что если субфакторион существует, то он максимум состоит из 6 цифр. Затем домножили на 6, по сути рассмотрев число 999999. Конечно, "потолок" можно опустить и пониже, но на скорость это не повлияет Всё, что больше уже выбывает из статуса кандидата. Т.е. мы установили, что если субфакторион существует, то он максимум состоит из 6 цифр. Затем домножили на 6, по сути рассмотрев число 999999. Конечно, "потолок" можно опустить и пониже, но на скорость это не повлияет](https://habrastorage.org/getpro/habr/upload_files/981/210/6f5/9812106f528e6ef10cace57d0d54349d.png)
Теперь нам нужен простейший код на Python и онлайн-компилятор:
![](https://habrastorage.org/getpro/habr/upload_files/4f6/928/ee9/4f6928ee96cd594eccc6f46c00ca9484.png)
Итоговый результат, который выдала программа :
![](https://habrastorage.org/getpro/habr/upload_files/257/77b/ceb/25777bcebba5bbc812c2510428d01d5e.png)
И это единственное число, которое носит гордое название "субфакторион". Первые его следы можно найти в достаточно интересной книжке 1966 года "Математика на каникулах":
![](https://habrastorage.org/getpro/habr/upload_files/95b/8bc/12b/95b8bc12bf7f71ea39ba6791b6951a9d.png)
На странице 167 есть упоминание этого факта:
![](https://habrastorage.org/getpro/habr/upload_files/865/dab/b16/865dabb166ba69b0a6b1dfbfa40af4f2.png)
Покопавшись еще в сети, удалось найти превью статьи из "Mathematical Magazine" с упоминанием факта, что субфакторион впервые был найден в 1966 году с применением ЭВМ:
![](https://habrastorage.org/getpro/habr/upload_files/c59/3e0/a59/c593e0a593a52b5f1a3e35f6627e606e.png)
Однако, стоит заметить, что мой "топорный" код выполнялся бы на компьютерах середины 70-х очень долго. Так что стоит отдать почести простым студентам-энтузиастам за программирование решения такой интересной задачки.
Больше математики в Telegram - "Математика не для всех".
Эта статья поддерживается командой ITGLOBAL.COM
Мы — первый облачный провайдер в России, а также интегратор, поставщик ИТ-услуг, продуктов, сервисов и разработчик собственного ПО.
• Наш сайт
• Наш блог про виртуализацию и Enterprise IT
• Истории успеха наших клиентов