Факториал, примеры решения

Факториал числа n – это произведение чисел от 1 до n. Определён только для целых неотрицательных чисел.

Формула факториала:

n! = 1 * 2 * … * n

Математическая формула представлена восклицательным знаком «!». Термин был введен в 1800 году, а обозначение появилось только в 1808. В формуле нужно умножить все целые числа от 1 до значения самого числа, стоящего под знаком факториала.

Это очень просто, вот пример:

7! = 1 * … * 7 = 5040.

Факторизация — разложение функции на множители.

Таблица факториалов

Свойства факториалов

Рекуррентная формула

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

Функция n может интерпретироваться как количество перестановок. К примеру, для 3-х элементов есть 3! = 6 перестановки.

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

Позволяет не перемножать большие числа. Обычно необходим только главный член:

Можно ли вычислить 0,5 или -3,217? Нет, нельзя. Но можно использовать нечто под названием «Гамма-функция», что намного сложнее.

Расчет по предыдущему значению

Функцию легко вычислить из предыдущего значения:

• 3! = 3 × 2! = 6;
• 41160 = 5! +8! + 6!

А как вычислить факториал нуля? Если вернуться к определению, то видно, что применять его в случае «0» нет смысла. Положительных чисел до 0 нет, поэтому 0 x 0 = 0.

Однако было решено, что в случае 0 результат будет равен 1.

Некоторые очень большие значения

Онлайн калькулятор поможет сделать вычисление – всего лишь надо найти знак, похожий на «x!» или «n!». Нужно обратить внимание, что браузеры могут испытывать затруднения при попытке отобразить более крупные числа и может произойти сбой. 

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

Примеры вычисления факториалов больших чисел:

• 70! приблизительно 1 19785716669969869891796072783721 x 10100, что немного больше, чем «гуголь» (1 и 100 нулей);
• 100! это примерно 9 33262154444944152681699238856 x 101576 x 10157;
• 200! это примерно 7 88657867867364479050355236321393 x 103743.

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

Программа на языке Паскаль:

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

Факториал дроби (½) — это половина квадратного корня pi = (½)√π.

Примеры задач с решениями

Задание 1

Задание 2

Использование факториалов

Математика и многие ее области используют функцию. В комбинаторике функция была введена именно для расчета перестановки. Также понятие тесно связано с биномом ньютона (формула бинома Ньютона необходима для разложения степени (x + y) n в многочлен).

Источник: https://nauka.club/matematika/algebra/faktorial.html

Комбинаторика: факториалы и перестановки

Справочник по математике

Алгебра

Комбинаторика

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

Факториалы

Перестановки

Размещения

Сочетания

      Для произвольного натурального числа   n   формула

определяет факториал числа   n   ( n !   читается, как   n   – факториал).

      Например,

      Считается, что

0 ! = 1 ,     1 ! = 1.

Перестановки

      Рассмотрим следующую задачу.

      Задача.   6   карточек пронумерованы числами   1, 2, 3, 4, 5, 6.   Карточки наугад выкладываем в ряд. Сколько при этом можно получить различных шестизначных чисел?

      Решение. Сначала слева направо пронумеруем места в ряду, куда выкладываем карточки: первое место, второе, третье, четвертое, пятое, шестое.

На первое место можно положить одну из 6 карточек. Для этого есть   6   способов.

В каждом из этих 6 способов на второе место можно положить одну из оставшихся   5   карточек. Таким образом, существует

способов, чтобы положить карточки на первое, второе и третье места. В каждом из этих   120   способов на четвертое место можно положить одну из оставшихся   3   карточек. Отсюда вытекает, что существует

способов, чтобы положить карточки на первое, второе, третье и четвертое места. В каждом из этих   360   способов на пятое место можно положить одну из оставшихся   2   карточек. Следовательно, существует

способов, чтобы положить карточки на первое, второе, третье, четвертое и пятое места. После этого у нас остается одна единственная карточка, которую мы и кладем на шестое место. Таким образом, при выкладывании карточек можно получить   720   различных шестизначных чисел.

      Ответ: 720.

      Замечание 1. В задаче мы рассмотрели   6   пронумерованных карточек и установили, что количество способов выкладывания этих карточек в ряд равно   6!

      Если бы у нас было n пронумерованных карточек, то количество способов выкладывания их в ряд равнялось бы   n ! .

      Замечание 2. Каждое расположение   n   пронумерованных карточек в ряд является перестановкой из n элементов, к изучению которых мы сейчас и переходим.

      Определение 1. Пусть   n   – натуральное число. Рассмотрим произвольное множество, содержащее n элементов. Говорят, что на этом множестве задано упорядочение (отношение порядка), если его элементы пронумерованы числами   1, 2, 3, … , n.

      Определение 2. Рассмотрим множество, содержащее n элементов. Перестановкой из n элементов называют любое упорядочение этого множества.

•       Число перестановок из   n   элементов обозначают символом   Pn.
•       В соответствии с Замечанием 1, справедлива формула:
• Pn = n !
•       В частности,

P6 = 6! = 720 .

      Замечание 3. Введенные в данном разделе перестановки называют также перестановками без повторений.

   С понятиями размещений из   n   элементов по   m   элементов и сочетаний из   n   элементов по   m   элементов можно познакомиться в разделе «Комбинаторика: размещения и сочетания» нашего справочника.

      На нашем сайте можно также ознакомиться нашими учебными материалами для подготовки к ЕГЭ и ОГЭ по математике.

Источник: https://www.resolventa.ru/spr/algebra/comb1.htm

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

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

Факториал — быстрорастущая функция, уже для небольших значений N значение N! имеет много значащих цифр. Попробуем реализовать эту функцию на языке программирования. Очевидно, нам понадобиться язык, поддерживающий длинную арифметику.

Я воспользуюсь C#, но с таким же успехом можно взять Java или Python.

Наивный алгоритм

Итак, простейшая реализация (назовем ее наивной) получается прямо из определения факториала: static BigInteger FactNaive(int n)
{
BigInteger r = 1;
for (int i = 2; i r)
return 1;
if (l == r)
return l;
if (r — l == 1)
return (BigInteger)l * r;
int m = (l + r) / 2;
return ProdTree(l, m) * ProdTree(m + 1, r);
}

static BigInteger FactTree(int n)
{
if (n < 0) return 0; if (n == 0) return 1; if (n == 1 || n == 2) return n; return ProdTree(2, n); } Для N=50 000 факториал вычисляется за 0,9 секунд, что почти вдвое быстрее, чем в наивной реализации.

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

Второй алгоритм быстрого вычисления использует разложение факториала на простые множители (факторизацию). Очевидно, что в разложении N! участвуют только простые множители от 2 до N. Попробуем посчитать, сколько раз простой множитель K содержится в N!, то есть узнаем степень множителя K в разложении.

Каждый K-ый член произведения 1 * 2 * 3 *… * N увеличивает показатель на единицу, то есть показатель степени будет равен N / K. Но каждый K2-ый член увеличивает степень еще на единицу, то есть показатель становится N / K + N / K2. Аналогично для K3, K4 и так далее.

В итоге получим, что показатель степени при простом множителе K будет равен N / K + N / K2 + N / K3 + N / K4 +…

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

Каждый восьмой дает восьмерку (23), такой множитель всего один 10 / 8 = 1 (8). Шестнадцать (24) и более уже не дает ни один множитель, значит, подсчет можно завершать.

Суммируя, получим, что показатель степени при двойке в разложении 10! на простые множители будет равен 10 / 2 + 10 / 4 + 10 / 8 = 5 + 2 + 1 = 8.

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

10! = 28 * 34 * 52 * 71 = 3 628 800

static BigInteger FactFactor(int n)
{
if (n < 0) return 0; if (n == 0) return 1; if (n == 1 || n == 2) return n; bool[] u = new bool[n + 1]; // маркеры для решета Эратосфена List p = new List(); // множители и их показатели степеней for (int i = 2; i 0) { c += k; k /= i; } // запоминаем множитель и его показатель степени p.Add(new Tuple(i, c)); // просеиваем составные числа через решето int j = 2; while (i * j = 0; —i) r *= BigInteger.Pow(p[i].Item1, p[i].Item2); return r; } Эта реализация также тратит примерно 0,9 секунд на вычисление 50 000!

Библиотека GMP

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

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

Однако этому вопросу вероятно стоит посвятить отдельную статью.

Сравнение производительности

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

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

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

lany распараллелил дерево на Java с помощью Stream API и получил ускорение в 18 раз

Mrrl предложил оптимизацию факторизации на 15-20% PsyHaSTe предложил улучшение наивной реализации Krypt предложил распараллеленную версию на C# SemenovVV предложил реализацию на Go pomme предложил использовать GMP ShashkovS предложил быстрый алгоритм на Python

Исходные коды

Исходные коды реализованных алгоритмов приведены под спойлерамиC#using System;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Collections.Generic;
using System.Collections.Specialized;

namespace BigInt
{
class Program
{

static BigInteger FactNaive(int n)
{
BigInteger r = 1;
for (int i = 2; i r)
return 1;
if (l == r)
return l;
if (r — l == 1)
return (BigInteger)l * r;
int m = (l + r) / 2;
return ProdTree(l, m) * ProdTree(m + 1, r);
}

static BigInteger FactTree(int n)
{
if (n < 0) return 0; if (n == 0) return 1; if (n == 1 || n == 2) return n; return ProdTree(2, n); } static BigInteger FactFactor(int n) { if (n < 0) return 0; if (n == 0) return 1; if (n == 1 || n == 2) return n; bool[] u = new bool[n + 1]; List p = new List(); for (int i = 2; i 0) { c += k; k /= i; } p.Add(new Tuple(i, c)); int j = 2; while (i * j = 0; —i) r *= BigInteger.Pow(p[i].Item1, p[i].Item2); return r; } static void Main(string[] args) { int n; int t; Console.Write(«n = «); n = Convert.ToInt32(Console.ReadLine()); t = Environment.TickCount; BigInteger fn = FactNaive(n); Console.WriteLine(«Naive time: {0} ms», Environment.TickCount — t); t = Environment.TickCount; BigInteger ft = FactTree(n); Console.WriteLine(«Tree time: {0} ms», Environment.TickCount — t); t = Environment.TickCount; BigInteger ff = FactFactor(n); Console.WriteLine(«Factor time: {0} ms», Environment.TickCount — t); Console.WriteLine(«Check: {0}», fn == ft && ft == ff ? «ok» : «fail»); } } } C++ с GMP#include
#include
#include
#include

#include

using namespace std;

mpz_class FactNaive(int n)
{
mpz_class r = 1;
for (int i = 2; i r)
return 1;
if (l == r)
return l;
if (r — l == 1)
return (mpz_class)r * l;
int m = (l + r) / 2;
return ProdTree(l, m) * ProdTree(m + 1, r);
}

mpz_class FactTree(int n)
{
if (n < 0) return 0; if (n == 0) return 1; if (n == 1 || n == 2) return n; return ProdTree(2, n); } mpz_class FactFactor(int n) { if (n < 0) return 0; if (n == 0) return 1; if (n == 1 || n == 2) return n; vector u(n + 1, false); vector p; for (int i = 2; i 0) { c += k; k /= i; } p.push_back(make_pair(i, c)); int j = 2; while (i * j = 0; —i) { mpz_class w; mpz_pow_ui(w.get_mpz_t(), mpz_class(p[i].first).get_mpz_t(), p[i].second); r *= w; } return r; } mpz_class FactNative(int n) { mpz_class r; mpz_fac_ui(r.get_mpz_t(), n); return r; } int main() { int n; unsigned int t; cout > n;

t = clock();
mpz_class fn = FactNaive(n);
cout

Источник: https://habr.com/post/255761/

Факториал

Факториалом в математике называют произведение всех натуральных чисел, включая указанное число. Обозначается факториал восклицательным знаком после числа, например 4!. Так что, если вы встретили восклицательный знак в математике, это совсем не означает «Вау! Число!». Это просто факториал.

Из священных математических текстов нужно выучить одну фразу «Факториал нуля равен единице». Почему факториал нуля равен единице? Читайте по ссылке. Точные значения факториалов чисел до 50 приведены на рисунке.

Факториал нуля равен единице фото. Факториал 1, 2, 3, 4, 5. Посчитать факториал, нахождение факториала. Значение факториала натурального числа. Математика для блондинок.» id=»BLOGGER_PHOTO_ID_5517996820177294226″ src=»http://4.bp.blogspot.com/_JwbCNIxiifg/TJPc31JnE5I/AAAAAAAAARU/aFyhd8WlX_M/s400/%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B0%D0%BB++%D1%82%D0%BE%D1%87%D0%BD%D1%8B%D0%B5+%D0%B4%D0%BE+50+%D0%B1%D0%BB%D0%BE%D0%BD%D0%B4%D0%B8%D0%BD%D0%BA%D0%B8.GIF»>

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

Факториал 1 (единицы) равен единице.

1! = 1 Факториал 2 (двух) равен двум.2! = 1 · 2 = 2 Факториал 3 (трех) равен шести.3! = 1 · 2 · 3 = 6 Факториал 4 (четырех) равняется двадцати четырем.4! = 1 · 2 · 3 · 4 = 24 Факториал 5 равен ста двадцати.5! = 1 · 2 · 3 · 4 · 5 = 120 Ну и так далее.

В общем виде формулу для нахождения факториала можно записать так:

n! = 1 · 2 · 3 · 4 · … · (n — 2) · (n — 1) · n

Таблица факториалов до 255 представлена на отдельной странице.

Кстати, если вы будете ехать за рулем автомобиля и увидите восклицательный знак в треугольнике на белом или желтом фоне — это не урок математики с факториалами, это дорожный знак «Внимание!».

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

Найти решение:

Чему равен 50 факториал — последняя строчка таблицы факториалов на картинке дает точный ответ на этот вопрос. Приблизительное значение (более короткая запись числа) можно посмотреть на отдельной странице «Таблица факториалов до 255».

Действие факториала — математически действие факториала представляет собой последовательность умножения натуральных чисел между собой. Такой себе математический междусобойчик во множестве натуральных чисел.

Факториал 15 равен — ответ можно посмотреть в таблице факториалов на картинке.

Как считать факториал — здесь в тексте написано, как считается факториал, а на картинке есть пример факториала семи (7!).

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

Как счетать факториал — вообще-то, у меня написано как «счИтать» факториал. Мне кажется, помимо факториалов, вам не помешает изучить курс «Русский язык для блондинок». А то не красиво будет смотреться фраза «Я табе лублу!» краской на асфальте.

Математика для блондинок факториал — это именно та страница, которую вы ищете. Если вы мне не верите, посмотрите вверху страницы, там написано «Математика для блондинок» и адрес этого сайта именно www.webstaratel.ru

Источник: http://www.webstaratel.ru/2010/09/blog-post_12.html

Калькулятор факториалов

Факториал числа 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!. После подсчёта значения факториала калькулятором, искомое значение можно использовать в решении более сложных задач.
Вы можете посмотреть необходимый факториал в таблице: «Таблица факториалов»

Бесплатный онлайн калькулятор факториалов

Источник: https://www.pocketteacher.ru/calculator-factorialov-ru

Пределы с факториалами

Факториал числа $n!$ равен произведению чисел от 1 до $n$. Например, $5! = 1cdot 2cdot 3cdot 4cdot 5$. Для решения примеров на пределы с факториалами понадобится знать и понимать формулу разложения на множители. $$ (n+1)! = n!(n+1) qquad (1) $$

Например, $5! = 4! cdot 5 $, или $5! = 3! cdot 4 cdot 5$, а можно еще так $5! = 2! cdot 3 cdot 4 cdot 5 $.

Основная суть идеи:

1. Выносим наименьший факториал числа за скобки в числителе и знаменателе
2. Сокращаем факториалы, избавляя тем самым предел от них
3. Вычисляем предел подходящим способом

Пример 1

Вычислить предел с факториалами $lim_limits{x o infty} frac{n!}{(n+1)!} $

Решение

Подставляя $x=infty$ в предел получаем неопределенность бесконечность делить на бесконечность. Избавимся от факториалов. Для этого используем формулу (1) для их разложения на множители. $ (n+1)! = n! (n+1) $ Подставляем в предел полученное выражение и сокращаем на $n!$ числитель со знаменателем. $$ lim_limits{x o infty} frac{n!}{n! (n+1)} = lim_limits{n o infty} frac{1}{n+1} $$ Теперь подставляя бесконечность в предел вычисляем ответ. $$ lim_limits{n o infty} frac{1}{n+1} = (frac{1}{infty}) = 0 $$ Если не получается решить свою задачу, то присылайте её к нам. Мы предоставим подробное решение. Вы сможете ознакомиться с ходом вычисления и почерпнуть информацию. Это поможет своевременно получить зачёт у преподавателя!

Ответ

$$lim_limits{x o infty} frac{n!}{(n+1)!} = 0 $$

Пример 2

Решить предел с факториалом $ lim_limits{x o infty} frac{(2n+1)! + (2n+2)!}{(2n+3)!} $

Решение

Определяем наименьший факториал $(2n+1)!$. Его нужно вынести за скобки. Но перед этим нужно разложить остальные факториалы на множители, одним из которых будет $(2n+1)!$. Для этого воспользуемся формулой (1). $$(2n+2)! = (2n+1)! cdot (2n+2) $$ $$ (2n+3)! = (2n+1)! cdot (2n+2)cdot(2n+3) $$ Выполняем замену в пределе на полученные выражения. $$lim_limits{x o infty} frac{(2n+1)! + (2n+1)! (2n+2)}{(2n+1)! (2n+2)(2n+3)} = $$ Выносим общий множитель с факториалом в числителе за скобки и выполняем сокращение со знаменателем. $$ lim_limits{x o infty} frac{(2n+1)! (1+ (2n+2))}{(2n+1)!(2n+2)(2n+3)} = lim_limits{x o infty} frac{1+ (2n + 2)}{(2n+2)(2n+3)} = $$ Раскрываем полученные скобки и сокращаем на $2n+3$. $$ = lim_limits{x o infty} frac{2n+3}{(2n+2)(2n+3)} = lim_limits{x o infty} frac{1}{2n+2} = (frac{1}{infty}) = 0$$

Ответ

$$ lim_limits{x o infty} frac{(2n+1)! + (2n+2)!}{(2n+3)!} = 0 $$

Пример 3

Найти предел $lim_limits{x o infty} frac{3(n+1)!}{2(n+1)!-n!} $

Решение

Понятно, что предел имеет неопределенность $frac{infty}{infty}$. Попробуем её устранить избавившись от факториалов. Сразу находим среди них наименьший $n!$. Его нужно будет вынести за скобки. Но перед этим остальные факториалы нужно разложить по формуле (1) и затем подставить в предел. $$ (n+1)! = n! (n+1) $$ $$ lim_limits{x o infty} frac{3n! (n+1)}{2n!(n+1) — n!} = lim_limits{x o infty} frac{3(n+1)}{2(n+1)-1} = $$ Далее раскрываем скобки, попутно упрощая выражения, и затем выносим $n$. $$ = lim_limits{x o infty} frac{3n+3}{2n+1} = lim_limits{x o infty} frac{n(3+frac{3}{n})}{n(2+frac{1}{n})} = $$ Осталось выполнить сокращение на $n$ и получить ответ. $$ = lim_limits{x o infty} frac{3+frac{3}{n}}{2+frac{1}{n}} = frac{3+0}{2+0} = frac{3}{2} $$

Ответ

$$lim_limits{x o infty} frac{3(n+1)!}{2(n+1)!-n!} = frac{3}{2} $$

Нужно подробное решение своей задачи?

ЗАКАЗАТЬ РЕШЕНИЕ

Источник: https://xn--24-6kcaa2awqnc8dd.xn--p1ai/predely-s-faktorialami.html

Факториал, перестановки | Александр Будников

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

Почему? Потому, что в нём сплошь и рядом фигурируют более сложные для визуального восприятия термины и обозначения. Если символы 10, 2, 3/4 и даже ,  или log25 нам визуально понятны, т.е. мы можем их как-то «пощупать», то с обозначениями типа 15!, P9, ,  начинаются проблемы. Кроме того, в большинстве учебников эта тема излагается довольно сухо и затруднительно для восприятия. Надеюсь, данный материал хотя бы немного поможет решить эти проблемы и комбинаторика вам понравится.)

        С комбинаторными задачами ежедневно сталкивается каждый из нас. Когда утром мы принимаем решение, как одеться, мы комбинируем те или иные виды одежды. Когда готовим салат, мы комбинируем ингредиенты. От того, какая комбинация продуктов выбрана, зависит результат – вкусно или невкусно.

Правда, вопросами вкуса занимается уже не математика, а кулинария, но тем не менее.) Когда, играем «в слова», составляя маленькие словечки из одного длинного, мы комбинируем буквы. Когда открываем кодовый замок или набираем номер телефона, то комбинируем цифры.) Завуч школы составляет расписания уроков, комбинируя предметы.

Футбольные команды на Чемпионате Мира или Европы распределяют по группам, образуя комбинации. И так далее.)

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

        И начнём мы изучение комбинаторики с такого краеугольного понятия, как факториал.

Что такое факториал?

           Красивое слово «факториал», но многих пугает и ставит в тупик. А зря. В настоящем уроке мы разберёмся и хорошенько поработаем с этим несложным понятием.) Это слово происходит от латинского «factorialis», что означает «умножающий». И неспроста: в основе вычисления любого факториала стоит обыкновенное умножение.)) Итак, что же такое факториал. 

        Чтобы не расписывать каждый раз это длинное произведение, просто придумали краткое обозначение. ? Читается немного непривычно: «эн факториал» (а не наоборот «факториал эн», как может показаться).

•         И всё! Например,

        Улавливаете идею?)) Отлично! Тогда считаем примеры:

2.         Ответы (в беспорядке): 30; 0,1; 144; 6; 720; 2; 5040.

        Всё получилось? Прекрасно! Считать факториалы и решать простейшие примеры с ними уже умеем. Идём дальше. ?

• Свойства факториала
•         Рассмотрим не очень понятное с точки зрения определения факториала выражение 0! Так уж в математике договорились, что

        Да-да! Такое вот интересное равенство. Что от единицы, что от нуля факториал один и тот же – единичка.)) Пока примем это равенство за догму, а вот почему это именно так, будет ясно чуть позже, на примерах.))

1.         Следующие два очень похожих свойства:

        Доказываются они элементарно. Прямо по смыслу факториала.)

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

        Во-вторых, с помощью этих формул можно упрощать и считать некоторые хитрые выражения с факториалами. Типа таких.

        Вычислить:

        Как действовать будем? Последовательно перемножать все натуральные числа от 1 до 1999 и от 1 до 2000? Это одуреешь! А вот по свойствам пример решается буквально в одну строчку:

•         Или так:
•         Или такое задание. Упростить:
•         Снова работаем прямо по свойствам:

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

)) На самом деле приложений у факториала великое множество.

Это и бином Ньютона, и теория вероятностей, и ряды, и формула Тейлора, и даже знаменитое число e, которое представляет собой вот такую интересную бесконечную сумму:

        Чем больше задаётся n, тем большее число слагаемых в сумме и тем ближе будет эта сумма к числу e. А в пределе при  она станет равна в точности числу e. ? Но об этом удивительном числе мы поговорим в соответствующей теме. А здесь у нас – факториалы и комбинаторика.)

        Откуда же они взялись? Они взялись как раз из комбинаторики, с изучения наборов элементов.) Простейшим таким набором является перестановка без повторений. С неё и начнём. ?

Перестановка без повторений

        Пусть в нашем распоряжении имеются два различных объекта. Или элемента. Совершенно любые. Два яблока (красное и зелёное), две конфеты (шоколадная и карамель), две книги, две цифры, две буквы – всего чего угодно. Лишь бы они были различными.) Назовём их A и B соответственно.

        Что можно с ними делать? Если это конфеты, то их, конечно, можно съесть.)) Мы же пока потерпим и будем их располагать в различном порядке.

        Каждое такое расположение называется перестановкой без повторений. Почему «без повторений»? Потому, что все элементы, участвующие в перестановке, различны. Это мы пока что для простоты так решили. Есть ещё перестановка с повторениями, где некоторые элементы могут быть одинаковыми. Но такие перестановки чуть сложнее. О них – позже.)

        Итак, если рассматривается два различных элемента, то возможны такие варианты:

AB, BA.

        Всего два варианта, т.е. две перестановки. Негусто.)

ABC, ACB, BAC, BCA, CAB, CBA.

        Идём дальше. Добавляем ещё один элемент D.

        Перестановки из четырёх элементов будем строить так. Сначала на первое место поставим элемент A.   При этом оставшиеся три элемента можно переставить, как нам уже известно, шестью способами:

        Значит, число перестановок с первым элементом A равно 6.

        Но та же самая история будет получаться, если мы на первое место поставим любой из этих четырёх элементов. Они же равноправны и каждый заслуживает оказаться на первом месте.) Значит, общее число перестановок из четырёх элементов будет равно . Вот они:

1.         Итак, подытожим: перестановкой из n элементов называется любой упорядоченный набор из этих n элементов.
2.         Слово «упорядоченный» здесь является ключевым: каждая перестановка различается только порядком элементов, а сами элементы в наборе остаются прежними.

        Осталось только выяснить, чему равно количество таких перестановок из любого числа элементов: мы ведь не мазохисты, чтобы каждый раз выписывать все различные варианты и их подсчитывать. ? Для 4-х элементов мы получили 24 перестановки – это уже довольно много для наглядного восприятия.

А если элементов 10? Или 100? Хорошо бы сконструировать формулу, которая одним махом подсчитывала бы число всех таких перестановок для любого числа элементов. И такая формула есть! Сейчас мы её выведем.

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

•         Правило произведения: если в наборе имеется n различных вариантов выбора первого элемента и для каждого из них есть m различных вариантов выбора второго элемента, то всего можно составить n·m различных пар из этих элементов.
•         А теперь, пусть теперь имеется набор из n различных элементов
• ,

где, естественно, . Нам нужно подсчитать число всех возможных перестановок из элементов этого набора. Рассуждаем точно так же.)) На первое место можно поставить любой из этих n элементов. Это значит, что число способов выбрать первый элемент равно n.

        Теперь представим, что первый элемент у нас выбран (n способами, как мы помним). Сколько невыбранных элементов осталось в наборе? Правильно, n-1. ? Это значит, что второй элемент можно выбрать уже только n-1 способами.

Третий — n-2 способами (т.к. 2 элемента уже выбраны).

И так далее, k-й элемент можно выбрать n-(k-1) способами, предпоследний – двумя способами, а последний элемент – только одним способом, так как все остальные элементы так или иначе уже выбраны. ?

        Что ж, теперь конструируем формулу.

Итак, число способов выбрать первый элемент из набора равно n. На каждый из этих n способов приходится по n-1 способу выбрать второй.

Это значит, что общее число способов выбрать 1-й и 2-й элементы, в соответствии с правилом произведения, будет равно n(n-1). Далее, на каждый из них, в свою очередь, приходится по n-2 способа выбрать третий элемент.

Значит, три элемента можно выбрать уже n(n-1)(n-2) способами. И так далее:

1. 4 элемента —  способами,
2. k элементов   способами,
3. n элементов  способами.
4.         Значит, n элементов можно выбрать (или в нашем случае расположить)  способами.

        Число таких способов обозначается так: Pn. Читается: «пэ из эн». От французского «Permutation — перестановка». В переводе на русский означает: «перестановка из n элементов».

        Значит,

        А теперь посмотрим на выражение , стоящее в правой части формулы. Ничего не напоминает? А если переписать справа налево, вот так?

        Значит, число всех возможных перестановок из n различных элементов равно n!.

•         В этом и состоит основной практический смысл факториала.))
•         Теперь мы с лёгкостью можем ответить на многие вопросы, связанные с комбинациями и перестановками.)
•         Сколькими способами можно разместить на полке 7 разных книг?

        P7 = 7! = 1·2·3·4·5·6·7 = 5040 способами.)

        Сколькими способами можно составить расписание (на один день) из 6 разных предметов?

        P6 = 6! = 1·2·3·4·5·6 = 720 способами.

        Сколькими способами можно расставить в колонну 12 человек?

        Не вопрос! P12 = 12! = 1·2·3·…·12 = 479001600 способами. ?

        Здорово, правда?

        На тему перестановок есть одна очень известная задача-шутка:

        Однажды 8 приятелей зашли в ресторан, в котором стоял большой круглый стол, и долго спорили между собой, как им лучше сесть вокруг этого стола.

Спорили-спорили, пока, наконец, хозяин ресторана не предложил им сделку: «Что же вы спорите-то? Голодным всё равно никто из вас не останется ? Сядьте для начала хоть как-нибудь! Хорошенько запомните сегодняшнюю рассадку. Затем приходите завтра и садитесь уже по-другому.

На следующий день приходите и садитесь опять по-новому! И так далее… Как только вы переберёте все возможные варианты рассадки и настанет черёд сесть снова так, как сегодня, — то так уж и быть, обещаю вас кормить в своём ресторане бесплатно!» Кто останется в выигрыше – хозяин или посетители? ?

        Что ж, считаем число всех возможных вариантов рассадки. В нашем случае это число перестановок из 8 элементов:

P8 = 8! = 40320 способов.

        Пусть в году у нас 365 дней (високосные для простоты учитывать не будем). Значит, даже с учётом этого допущения, число лет, которое потребуется, чтобы перепробовать все возможные способы посадки, составит:

        Более 110 лет! То есть, даже если наших героев в колясках привезут в ресторан их мамы прямо из роддома, то получить свои бесплатные обеды они смогут только в возрасте очень преклонных долгожителей. Если, конечно, все восемь доживут до такого возраста.))

1.         Всё потому, что факториал – ооочень быстро возрастающая функция! Смотрите сами:

        Кстати сказать, как с точки зрения перестановок выглядят равенства  и 1! = 1? А вот как: из пустого набора (0 элементов) мы можем составить только одну перестановку – пустой набор. ? Так же, как и из набора, состоящего всего из одного элемента, мы тоже можем составить лишь одну перестановку – сам же этот элемент.

        Всё понятно с перестановками? Отлично, тогда делаем задания.)

•         Задание 1
•         Вычислите:
• а) P3        б) P5
•       в) P9:P8     г) P2000:P1999
• Задание 2
• Верно ли, что
• Задание 3
• Сколько различных четырёхзначных чисел можно составить
• а) из цифр 1, 2, 3, 4
• б) из цифр 0, 5, 6, 7?
• Подсказка к пункту б): число не может начинаться с цифры 0!
• Задание 4

Слова и фразы с переставленными буквами называются анаграммами. Сколько анаграмм можно составить из слова «гипотенуза»?

1. Задание 5
2.         Сколько пятизначных чисел, делящихся на 4, можно составить, меняя местами цифры в числе 61135?
3.         Подсказка: вспомнить признак делимости на 4 (по двум последним цифрам)!
4. Ответы в беспорядке: 2000; 3628800; 9; 24; 120; 18; 12; 6.

        Ну как, всё получилось! Поздравляю! Уровень 1 пройден, переходим на следующий. Называется «Размещения без повторений.«

Источник: http://abudnikov.ru/shkolnikam/kombinatorika/faktorial-perestanovki.html

Факториал

Здравствуйте, дорогие друзья! Спасибо, что читаете мой канал!

Вы когда-нибудь слышали о факториале? Сегодня расскажу Вам, что это такое и для чего он нужен.

Факториал — это математическая функция, применяемая к неотрицательным целым числам, равная произведению всех натуральных чисел от 1 до числа, для которого она вычисляется (о целых, натуральных и других числах можно почитать здесь).

Обозначается она очень просто: n! (произносится «эн факториал») — да, просто приписывается восклицательный знак к числу ? Чтобы было легче понять определение факториала, сразу приведу пример: 5!=1х2х3х4х5=120.

Определение факториала

Также из определения факториала следует следующая формула:

Факториал предыдущего числа

То есть, зная факториал числа, можно найти факториал предыдущего числа путём деления значения факториала на само число. Из этой же формулы следует, что 0!=1 при n=1. Хотя не все математики считают 0 натуральным числом (подробнее читайте в этой статье), факториал для него можно вычислить.

Вы спросите: для чего же он нужен, этот факториал? Давайте теперь расскажу Вам о его применении.

Факториал очень активно используется в различных разделах математики, особенно там, где заходит речь о различных вариантах, перестановках, комбинациях и т. п. Он применяется в комбинаторике, теории чисел, математическом анализе и других областях.

Очень хорошо становится понятным смысл факториала при изучении и применении вышеозвученной комбинаторики. В ней факториал натурального числа n интерпретируется как количество перестановок множества из n элементов.

Что это означает на практике? Разберём задачу.

В гостиной стоит стол с четырьмя стульями вокруг. В комнату заходит четыре человека. Сколько существует вариантов для рассаживания вокруг стола всех четырёх человек?

Как раз для решения подобных задач требуется факториал. Зная его определение, задача решается в одно действие: 4!=1х2х3х4=24. То есть, ответ: 24 варианта (комбинации). Для такого небольшого числа, как 4, можно проверить правильность решения. Обозначим людей первыми буквами латинского алфавита: A, B, C, D. Тогда все возможные комбинации из них будут выглядеть так:

Комбинации из четырёх объектов подтверждают, что 4!=24

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

В среде математиков существует одна занимательная задачка. Попробуйте её решить сами. Ответ будет в конце следующей статьи. Вот сама задача: дан отрезок времени 10! секунд; сколько это будет в каких-нибудь более удобных, крупных единицах времени?

Надеюсь, теперь Вы хорошо знаете, что такое факториал числа и где он может применяться.

Спасибо, что прочитали статью! Буду благодарен за комментарии, лайки, подписки.

Предыдущая статья

Следующая статья

Источник: https://zen.yandex.ru/media/math4u/faktorial-5ca35fb52aee0400b3d1d202