Факториальная запись

Эта тема является частью раздела о комбинаторике в Quant GMAT Focus. Мы изучили принципы подсчета с ограничениями. 

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

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

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

Произведение числа n на все положительные целые числа, меньшие n, называется
n факториал.

Например:

• 5 факториал = 5 × 4 × 3 × 2 × 1
  
  

Считаем по шагам:

• 5 × 4 = 20
  
  
• 3 × 2 × 1 = 6
  
  
• 20 × 6 = 120
  
  

Обозначение факториала

Факториал записывается как число с восклицательным знаком:

• 5! читается как «пять факториал»
  
  

Примеры:

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

Уже на этом этапе видно, что факториалы растут очень быстро.

Насколько быстро растут факториалы

Некоторые ориентиры:

• 10! — больше 1 000 000
  
  
• 13! — больше 1 000 000 000
  
  
• 15! — больше 1 000 000 000 000
  
  

Начиная примерно с 15!, числа становятся практически невообразимо большими.

Поэтому на GMAT или GRE никто не будет просить вас вычислять, например, 20! численно.
Даже если бы был калькулятор, такое число слишком велико, чтобы иметь практический смысл.

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

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

Рассмотрим:

20! = 20 × 19 × 18 × 17 × … × 3 × 2 × 1

Отсюда сразу видно:

• 20! = 20 × 19!
  
  
• 20! = 20 × 19 × 18!
  
  
• 20! = 20 × 19 × 18 × 17!
  
  

Таким образом, любой меньший факториал является делителем большего факториала.

Например:

• 17! делит 20!
  
  
• 13! делит 20!
  
  

Поэтому задачи вида
«чему равно 20! / 19»
или
«делится ли 20! на 18!»
решаются алгебраически, без вычисления самих чисел.

Связь факториалов с комбинаторикой

Из предыдущих уроков мы уже знаем важный факт:

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

Это и есть первое и базовое применение факториалов в комбинаторике.

Ключевые свойства факториалов

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

Выводы

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

Это завершает ввод в факториальную нотацию и подготавливает нас к дальнейшим темам по Counting в GMAT и GRE Quant.

Далее изучим подсчет перестановок с одинаковыми объектами.