Реферат на тему «В каком классе изучают факториал»

Введение

Сколькими способами можно рассадить пятерых друзей на пяти стульях? Если попробовать перебрать варианты на листке, терпения хватит ненадолго, а правильный ответ — 120. Для десяти человек вариантов уже больше трёх с половиной миллионов. За такими подсчётами стоит одна из самых простых и одновременно самых «взрывных» функций в математике — факториал.

Записывается он восклицательным знаком: 5! читается «пять факториал» и означает произведение 1 · 2 · 3 · 4 · 5. Восклицательный знак, кстати, придумал не какой-нибудь древний математик, а француз Кристиан Крамп в 1808 году. До этого факториалы записывали по-разному, и общепринятого обозначения не было.

Вопрос, вынесенный в заголовок, на первый взгляд простой, но однозначного ответа на него нет. В разных учебниках и программах факториал появляется в разное время, а иногда в одном и том же классе его то проходят, то пропускают. Нам хотелось разобраться, как это устроено, и заодно объяснить само понятие так, чтобы оно было понятно и без учебника.

Если коротко, то в большинстве современных учебников факториал вводят в 9 классе, в теме о перестановках и сочетаниях, а в профильных классах к нему возвращаются в 10–11 классе при изучении бинома Ньютона. Но встретиться с ним можно и раньше, в задачах на перебор вариантов для 5–6 классов, только там его обычно не называют по имени. Подробнее об этом сказано во второй главе.

Для начала посмотрим на значения факториала для небольших чисел. Уже по таблице видно, как быстро он растёт.

Таблица 1 – Значения факториала для некоторых n

Примечание — n! = 1 · 2 · 3 · … · n, число перестановок из n элементов равно n!; значения вплоть до 20! помещаются в 64-битную целую переменную компьютера, а 21! уже нет; 25! и 30! вычислены точно.

Цель реферата — описать определение и основные свойства факториала, показать, где он применяется, и выяснить, в каком классе российской школы с ним знакомятся по действующим программам. В первой главе речь идёт о теории, во второй — о школьных учебниках и программах.

Мы пользовались школьными учебниками алгебры и курса «Вероятность и статистика», федеральной рабочей программой по математике, а также справочниками по элементарной математике. Ссылки на конкретные учебники мы даём по тексту, потому что от выбранной линии учебников многое зависит.

Глава 1. Теоретические основы факториала

1.1 Определение факториала и его свойства

Задолго до Крампа люди считали перестановки, и часто по очень неожиданным поводам. В древней еврейской «Книге творения» (Сефер Йецира) подсчитано, сколько «слов» можно составить, переставляя буквы: из двух букв два, из трёх шесть, и так далее до семи букв, для которых получается 5040. Это и есть 7!, хотя слова «факториал» тогда, конечно, не было.

Другой пример — английские звонари XVII века. В колокольном искусстве, которое называют change ringing, колокола звонят по очереди в разном порядке, и хорошим тоном считается пройти все перестановки, ни разу не повторившись. В 1677 году Фабиан Стедман выпустил книгу о таких схемах. Для семи колоколов полный звон из 5040 перемен занимает около трёх часов, а для двенадцати колоколов, как легко посчитать, жизни звонаря бы не хватило.

Факториалом натурального числа n называют произведение всех натуральных чисел от 1 до n включительно: n! = 1 · 2 · 3 · … · n. Так, 3! = 6, 4! = 24, 6! = 720. Определение простое, и его обычно понимают сразу, но несколько вопросов всё-таки возникает почти у каждого, кто видит его впервые.

Первый вопрос — чему равен 0!. По договорённости 0! = 1. Это кажется странным (как будто мы ничего не умножаем, а получаем единицу), но у договорённости есть хорошие причины. Во-первых, тогда сохраняется удобное правило n! = n · (n − 1)!, и при n = 1 оно даёт 1! = 1 · 0!. Во-вторых, расставить в ряд ноль предметов можно ровно одним способом — ничего не делая.

Второе важное свойство мы уже назвали: каждый следующий факториал получается из предыдущего умножением на очередное число. Например, 7! = 7 · 6! = 7 · 720 = 5040. На этом построено рекуррентное определение, которое удобно использовать в программировании, когда факториал считают в цикле или через рекурсию.

Третье свойство — скорость роста. Факториал растёт быстрее любой показательной функции вроде 2ⁿ или 10ⁿ. На рисунке 1 показано, сколько цифр в записи факториала для некоторых n.

Рисунок 1 – Сколько цифр в записи n!

Примечание — посчитано по точным значениям факториалов (см. таблицу 1): 20! = 2 432 902 008 176 640 000, 30! ≈ 2,65 · 10³²; число цифр растёт почти линейно, а само число — гораздо быстрее любой степени.

Двадцать факториал — уже девятнадцатизначное число (2 432 902 008 176 640 000), а в записи 30! тридцать три цифры. Популярные книги любят сравнивать такие числа с количеством песчинок на всех пляжах Земли, которое оценивают в 10¹⁸–10²¹. Так вот, 30! больше и этого, причём в сотни миллиардов раз.

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

Например, дробь 10! / 8! считается в уме: все множители от 1 до 8 сокращаются, и остаётся 9 · 10 = 90. Этот приём постоянно используется в комбинаторике, и школьники, которые его освоили, решают задачи на сочетания намного быстрее.

Для очень больших n существует приближённая формула Стирлинга, названная по имени шотландского математика Джеймса Стирлинга (XVIII век): n! ≈ √(2πn) · (n/e)ⁿ. В школе её обычно не изучают, но она хорошо показывает, что факториал растёт примерно как nⁿ, то есть очень быстро.

1.2 Практическое применение факториала в математике

Главная область, где нужен факториал, — комбинаторика, наука о подсчёте вариантов. Число перестановок из n различных предметов равно n!. Если на полке пять разных книг, их можно расставить 120 способами, если шесть — уже 720.

Бывает, что порядок не важен (учителю всё равно, кто из дежурных первый). Тогда считают число сочетаний по формуле n! / (k! · (n − k)!). Сколькими способами учитель может выбрать трёх дежурных из класса в 25 человек? Подставляем: 25! / (3! · 22!) = 25 · 24 · 23 / 6 = 2300.

Отсюда прямая дорога к теории вероятностей. В лотерее «6 из 45» число возможных комбинаций равно 45! / (6! · 39!), то есть 8 145 060. Значит, шанс угадать все шесть чисел одним билетом — примерно один на восемь миллионов, и это хорошо видно только тогда, когда умеешь считать сочетания.

Факториалы встречаются и в алгебре, например в формуле бинома Ньютона, где коэффициенты разложения (a + b)ⁿ — это числа сочетаний. Их удобно находить по треугольнику Паскаля, но формула с факториалами позволяет получить любой коэффициент сразу, без построения всего треугольника.

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

У программистов с факториалом связана классическая ловушка. Обычная целая переменная в большинстве языков хранит числа примерно до двух миллиардов, а 13! = 6 227 020 800 уже больше. Если считать факториал в цикле и не подумать о типе данных, на тринадцатом шаге программа выдаст бессмыслицу, причём без всякого сообщения об ошибке.

Даже 64-битного целого хватает только до 20!, а 21! в него уже не помещается. Поэтому в олимпиадных задачах ответ часто просят выдать «по модулю» какого-нибудь большого числа, например 10⁹ + 7, — так участникам не приходится работать с огромными числами, но факториал всё равно приходится считать аккуратно.