Комбинаторика: факториалы и перестановки
| Справочник по математике | Алгебра | Комбинаторика |
При решении задач по комбинаторике используют следующие важные понятия
| Факториалы |
| Перестановки |
| Размещения |
| Сочетания |
Для произвольного натурального числа n формула
определяет факториал числа n ( n ! читается, как n – факториал).
Перестановки
Рассмотрим следующую задачу.
Задача. 6 карточек пронумерованы числами 1, 2, 3, 4, 5, 6. Карточки наугад выкладываем в ряд. Сколько при этом можно получить различных шестизначных чисел?
Решение. Сначала слева направо пронумеруем места в ряду, куда выкладываем карточки: первое место, второе, третье, четвертое, пятое, шестое.
На первое место можно положить одну из 6 карточек. Для этого есть 6 способов.
В каждом из этих 6 способов на второе место можно положить одну из оставшихся 5 карточек. Таким образом, существует
способов, чтобы положить карточки на первое и второе места. В каждом из этих 30 способов на третье место можно положить одну из оставшихся 4 карточек. Следовательно, существует
способов, чтобы положить карточки на первое, второе и третье места. В каждом из этих 120 способов на четвертое место можно положить одну из оставшихся 3 карточек. Отсюда вытекает, что существует
способов, чтобы положить карточки на первое, второе, третье и четвертое места. В каждом из этих 360 способов на пятое место можно положить одну из оставшихся 2 карточек. Следовательно, существует
способов, чтобы положить карточки на первое, второе, третье, четвертое и пятое места. После этого у нас остается одна единственная карточка, которую мы и кладем на шестое место. Таким образом, при выкладывании карточек можно получить 720 различных шестизначных чисел.
Ответ: 720.
Если бы у нас было n пронумерованных карточек, то количество способов выкладывания их в ряд равнялось бы n ! .
Замечание 2. Каждое расположение n пронумерованных карточек в ряд является перестановкой из n элементов, к изучению которых мы сейчас и переходим.
Определение 1. Пусть n – натуральное число. Рассмотрим произвольное множество, содержащее n элементов. Говорят, что на этом множестве задано упорядочение (отношение порядка), если его элементы пронумерованы числами 1, 2, 3, … , n.
Множество с заданным упорядочением называют упорядоченным множеством.
Определение 2. Рассмотрим множество, содержащее n элементов. Перестановкой из n элементов называют любое упорядочение этого множества.
- Число перестановок из n элементов обозначают символом Pn.
- В соответствии с Замечанием 1, справедлива формула:
- Pn = n !
- В частности,
Замечание 3. Введенные в данном разделе перестановки называют также перестановками без повторений.
С понятиями размещений из n элементов по m элементов и сочетаний из n элементов по m элементов можно познакомиться в разделе «Комбинаторика: размещения и сочетания» нашего справочника.
На нашем сайте можно также ознакомиться нашими учебными материалами для подготовки к ЕГЭ и ОГЭ по математике.
Формулы, упрощающие решение
Использование факториала нашло широкое применение в комбинаторике: сочетаниях, перестановке и размещениях. Проводя решение неравенств и уравнений, необходимо найти неизвестное значение. Для упрощения вычисления применяются следующие правила:
- «2n!!» равно произведению всех четных чисел 2, 4, 6, 8 и других;
- «(2n+1)!!» применяется для всех цифр вида 1, 3, 5 и подобных;
- существует равенство “2n!!*(2n+1)!!=(2n+1)!” или “2n!!*(2n-1)!!=2n!”.
Если в примере с несколькими членами уравнения имеются факториалы, то меньший из них выделяется и выносится за скобки. Это упрощает вычисление, поскольку требуется выполнить более простое произведение оставшихся параметров и общего значения. При наличии дробей, в числителе и знаменателе которых приведены факториалы, возможно их изменить с помощью нахождения одинаковой части. Она выносится за скобки, а затем сокращается.
Существует метод вычисления функций по предыдущему значению. Подсчёт показан на примере: 4! = 4 * 3! или 4 * (3*2*1). В математике старших классов школы и начальных курсов высших учебных заведений применяется Гамма-функция и бином Ньютона.
Для вычисления больших значений и решения сложных уравнений с факториалом возможно применение программного обеспечения, поскольку ручная работа с ними будет слишком трудоемкой, а онлайн-калькуляторы дают погрешность. Существуют специальные приложения и сценарии, которые вычисляют итоговое значение по заданным параметрам.
Наш искусственный интеллект решает сложные математические задания за секунды.
Мы решим вам контрольные, домашние задания, олимпиадные задачи с подробными шагами. Останется только переписать в тетрадь!
Что такое факториал?
Я думаю трудно найти человека, который не знал бы, что такое факториал. Но, чёрт возьми, такая красивая математическая операция, давайте поговорим о ней снова. Тем более постарался максимально доходчиво объяснить материал даже очень далеким от математики людям. Поехали!
Кто из Вас помнит, когда столкнулся с факториалом впервые? Я, например, абсолютно уверен, что первый раз увидел значок n! на советской микро-ЭВМ Электроника МК-71. Меня поразило, в первую очередь, как с помощью этой кнопки быстро переполняется буфер и выскакивает ошибка. Потом уже, начав изучать математику, удалось поближе познакомиться с этим зверем. Начнем с определения:
Лаконично и просто.
Факториал крут тем, насколько быстро возрастает его значение, и если 5! равен всего лишь 120, то 10! — уже 3 628 800, а, например, факториал 1000000 равен 8,263931688Е+5565708. Факториал возрастает быстрее чем экспонента и степенная функция и даже чем их произведение, но, однако уступает функции n в степени n.
Короткий пример вычисления факториала
Самым натуральным образом понятие «факториал» возникает в комбинаторике при попытке посчитать количество перестановок элементов множества. Например, пусть множество состоит из 4 шаров разного цвета: красного, синего, желтого и зеленого. Ответьте на вопрос: сколько существует способов укладки этих шаров (разный порядок — разный способ) ?
Если взять первым красный шар, а затем найти варианты расположения остальных — получим 6 вариантов. Перебрав все 4 шара получим 24 = 1*2*3*4=4! Таким образом, количество перестановок во множестве равно факториалу количества его членов.
Во-вторых, факториал применяется при расчете количества размещений — еще одной операции из мира комбинаторики. Суть ее проста, поясним ее на всё том же примере разноцветных шаров. Ответьте на вопрос: сколько способов отдельного размещения 2 шаров из представленных 4 (разный порядок — разный способ) ?
Всего имеется 12 вариантов размещения 2 элементов из 4. То, что мы сейчас посчитали руками формализуется следующим образом через факториал:
Читается как количество размещений из n элементов по m
В-третьих, факториал присутствует в формуле количества сочетаний из n элементов по m. Сочетания отличаются от размещений тем, что если набор элементов одинаков — он не учитывается.
На рисунке обведены сочетания: как видно, их стало в 2 раза меньше. Формула вычисления количества сочетаний из n элементов по k выглядит так:
Раз уж мы разобрались с перестановками, размещениями и сочетаниями, перейдем к «имени нарицательному», страшному и пугающему: биному Ньютона. Как окажется, знание факториала и последней формулы легко позволит Вам расколоть этот «крепкий орешек».
Как ни странно, бином Ньютона это выражение (1+x)^n и его легко найти через формулу сочетаний (доказательство естественно опустим). Вот небольшой пример нахождения бинома третьей степени, который легко перепроверить перемножением.
Разобравшись с этим примером, можете спокойно спорить с друзьями и знакомыми, что без проблем вычислите бином Ньютона n-ной степени!
Некоторые интересные свойства факториала
Во многих случаев, когда не требуется точного вычисления факториала не требуется, можно воспользоваться формулой Стирлинга:
Например, реальное значение факториала 5 — это 120. По формуле Стирлинга получается так:
Строго говоря, это только первый член бесконечного ряда. С увеличением количества членом приближение будет всё точнее
Идем дальше. До этого мы условились, что в качестве подфакториальной переменной, рассматриваем только натуральные числа. А что, если бы нам захотелось вычислить факториал дробного числа? Оказывается, и такой факториал тоже существует.
Используются такие расчеты при статистическом описании нейронных сетей. Данные вычисления приближенные, чтобы точно вычислять значение таких факториалов, используется Гамма-функция. Но это уже совсем другая история.
Есть еще двойной факториал, обозначаемый n!!. Формула его вычисления зависит от четности или нечетности аргумента.
Думаю принцип понятен без дополнительных пояснений.
Кроме того, существует «король факториалов», так называемый суперфакториал, который равен произведению факториалов числа, меньше либо равного данному:
Ну а дальше пошло-поехало: придумали гиперфакториалы, которые равны произведениям суперфакториалов, а потом и вовсе обобщили в m-кратный факториал.
Вот еще несколько интересных свойств факториала и заканчиваем:
1) n! — никогда не является квадратом какого-либо числа.
Источник
Формулы и свойства факториала
Чтобы научиться быстро вычислять факториалы, воспользуемся таблицей. Спасите себя и решите раньше остальных.
Помните 0! = 1
| 1! = 1 |
| 2! = 2 |
| 3! = 6 |
| 4! = 24 |
| 5! = 120 |
| 6! = 720 |
| 7! = 5040 |
| 8! = 40320 |
| 9! = 362880 |
| 10! = 3628800 |
| одиннадцать! = 39916800 |
| 12! = 479001600 |
| 1. 3! = 6227020800 |
| 14! = 87178291200 |
| 15! = 1307674368000 |
| 16! = 20922789888000 |
| 17! = 355687428096000 |
| 18! = 6402373705728000 |
| 19! = 121645100408832000 |
| 20! = 2432902008176640000 |
| 21! = 51090942171709440000 |
| 22! = 1124000727777607680000 |
| 23! = 25852016738884976640000 |
| 24! = 620448401733239439360000 |
| 25! = 15511210043330985984000000 |
В 9 классе по математике много факториалов. Чтобы всегда быть готовым решить пример, запомните основные формулы:
- (н — 1)! = 1*2*3*4*5*…*(n — 2)(n — 1)
- нет! = 1*2*3*4*5*…*(n — 2)(n — 1)n
- (n + 1)! = 1*2*3*4*5*…*(n — 2)(n — 1)n(n + 1)
С помощью формулы Стирлинга можно вычислить множитель многозначных чисел.
Эта формула дает результат с небольшой погрешностью.
 |
Пример:
Повторяющаяся формула
 |
Примеры:
- 5! = 5*(5 — 1)! = 5*4! = 5*24 = 120
- 6! = 6*(6-1)! = 6*5! = 6*120 = 720
См примеры в таблице.
Примеры факториального умножения:
- Используйте готовую таблицу 5! *7! = 120 * 5040 = 604800
- Или разверните факторы отдельно, если хотите потренироваться:
5! = 1*2*3*4*5 = 4! * 5 = 120
7! = 1*2*3*4*5*6*7 = 6! * 7 = 5040
120 * 5040 = 604800
Вам нужно быстро освежить свои знания перед экзаменом? Запишитесь на курс ЕГЭ по математике в Skysmart!
1. Факториал
Возникнув естественным образом в комбинаторике — науке, где изучаются проблемы, связанные с выбором и расположением различных элементов, обычно конечных множеств. Подробнее о происхождении читайте здесь.
2. Двойной факториал
Этот фактор имеет лишь большое количество приложений в комбинаторике и достоин отдельного материала. Впервые он был использован при выводе замечательного произведения Уоллиса, связывающего натуральные числа и число π:
3. Субфакториал
Этот член семейства, в отличие от общего фактора, определяющего число перестановок, определяет число нарушений. Подробнее в моей прошлой статье.
4. Праймориал
Он определяется как произведение простых чисел, меньших или равных заданному. Подробная информация и функции в приложении — здесь.
5. Суперфакториал Слоуна
Название дал создатель уникальной онлайн-энциклопедии целочисленных последовательностей (OEIS). Определяется как произведение факториалов чисел, меньших или равных заданному числу.
6. Суперфакториал Пиковера
Запись показателя степени в левом верхнем углу числа определяет специальную математическую операцию — тетрацию. Запись показателя степени в верхнем левом углу числа определяет специальную математическую операцию — тетрацию
Невероятно быстрорастущая функция. Для №3 это уже такая невероятная башня:
Оценки «схлопываются» справа налево Оценки «схлопываются» справа налево
7. Экспоненциальный факториал
По сравнению с предыдущим представителем растет «медленно». Например, для приведенного выше выражения это 262144. Правда, для числа 6 результат уже равен 10^183230 нулей.
9. Фиббоначиал (бонус)
Равен произведению первых n чисел Фибоначчи.
А вот и факториал дроби! Читайте об этом в моем увлекательном материале! Вы также можете заглянуть сюда и узнать, что такое фактории и почему их всего 4 !
Алгоритмы быстрого вычисления факториала
Понятие факториала известно всем. Это функция, вычисляющая произведение последовательных натуральных чисел от 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, 
* P(9, 10) ) ( (P(2, 3) * P(4) ) * P(5, 6) ) * ( P(7, * P(9, 10) ) ( ( (2 * 3) * (4) ) * (5 * 6) ) * ( (7 * * (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 десятью итерациями. В таблице указано среднее значение времени работы в миллисекундах.
График с линейной шкалой
График с логарифмической шкалой
Идеи и алгоритмы из комментариев
Хабражители предложили немало интересных идей и алгоритмов в ответ на мою статью, здесь я оставлю ссылки на лучшие из них
Исходные коды реализованных алгоритмов приведены под спойлерами
Источник
Как решать задачи с перечислением
Этот тип задач отличается от предыдущих лишь тем, что в задаче предметы поименованы. А вычисления выполняются по той же формуле:
Приведем пример такой задачи.
Задача 4
В портфеле у Васи лежали учебники по алгебре, геометрии, химии, биологии и литературе. Вася не глядя вынимает один учебник, какова вероятность того, что он вытянул алгебру?
Решение. Не смотря на то, что теперь предметы поименованы, принцип решения задачи остался прежним. Общее количество вариантов (т.е. учебников в портфеле) – 5. Нужный нам вариант (т.е. учебник по алгебре) – 1. Следовательно, вероятность нужного нам события равна:
Р = = 0,2
Ответ: 0,2
Что такое вероятность простыми словами
Вся наша жизнь состоит из случайных событий, которые могут либо произойти, либо нет. Например, вы сегодня идете на экзамен, по которому лучше остальных знаете один билет, достанется он именно вам или нет – случайность. Так как билетов всего 20, а вам нужно вытянуть всего 1, мы можем определить вероятность, с которой вам достанется желаемый билет. Эта вероятность будет составлять 1 шанс к 20 возможным, то есть 1 к 20 или 1/20 или 0,05.
Формула вероятности
Формула для вычисления вероятности события выглядит следующим образом:где P – вероятность события;
m — число вариантов, которые нас устраивают (число благоприятных исходов);
n – общее количество вариантов (возможных исходов).
Логично, что число благоприятных исходов всегда меньше, чем общее количество исходов, т.е. меньшее число мы делим на большее. Таким образом вероятность всегда находится в диапазоне от 0 до 1.
Приведем еще пример.
Задача 1
У нас есть пакет, в котором лежит 15 шариков, 9 из которых фиолетового цвета, а остальные белые. Какова вероятность вытащить из пакета один белый шарик?
Решение. Итак, общее количество белых шариков 15 – 9 = 6 штук, следовательно количество благоприятных исходов нашего события – 6. Общее количество возможных исходов – 15. Подставляем в формулу и получаем:
Таким образом, вероятность вытащить белый шарик равна 6/15.
Ответ: 6/15
Задачи на вероятность нужно читать внимательно, чтобы не допускать досадных ошибок. Например, вот в такой задаче.
Задача 2
В автомате, продающем, маленькие мячики есть мячи 5 цветов: 21 синих, 30 красных, 15 зеленых, 8 белых, а остальные желтые. Всего в автомате 90 мячиков. Какова вероятность, что Коле достанется мяч не синего цвета.
Решение
Мы обращаем внимание на то, что Коле должен достаться мяч НЕ синего цвета, а любого другого. Многие ученики просто не замечают частицу НЕ и ищут вероятность выпадения именно синего мяча, и естественно допускаю ошибку
Внимательно читаем условия задачи.
Итак, общее количество возможных вариантов – 90. Нам нужен любой мяч, кроме синего. Следовательно, количество вариантов, когда выпадет не синий мяч равно 90 – 21 = 69. Таким образом, вероятность того, что выпадет мячик любого цвета, кроме синего, равна:
Ну и разберем еще задачу.
Задача 3
На конкурсе выступают 11 участников из Казани, 6 участников из Нижнего Новгорода, 3 участника из Москвы и 7 участников из Твери. Порядок выступления в конкурсе определяется жеребьевкой. Какова вероятность того, что последним будем выступать конкурсант из Нижнего Новгорода? Результат округлите до сотых.
Решение. Итак, представим, что все конкурсанты подошли к барабану, где лежат номерки и тянут по одному номерку. Общее количество конкурсантов n = 11 + 6 + 3 + 7 = 27. Нас интересует, какова вероятность того, что один из конкурсантов из Нижнего Новгорода вытянет номерок с цифрой 27. Конкурсантов из Нижнего Новгорода всего 6, следовательно m = 6. Таким образом, вероятность будет равна:Как представить в виде десятичной дроби?
Очень просто. Нужно разделить 6,0000 на 27 уголком. Тогда вы получите 0,222… или округляя до сотых 0,22.
Ответ: 0,22
Сочетания
Выбирая размещение, мы должны были выбрать из множества несколько объектов и упорядочить их. В частности, мы выбирали три команды из шести и указывали, какая из них будет первой, какая второй, а какая третьей. Поэтому размещения «Локомотив, Зенит, Краснодар» и «Локомотив, Краснодар, Зенит» отличались друг от друга.
Однако порою этот порядок не имеет значения. Так, существует известная лотерея, где предлагается угадать 7 чисел из 49, которые выпадут во время розыгрыша из барабана. При этом порядок их выпадения не играет никакой роли. Игрок, выбирая эти 7 чисел, с точки зрения математики формирует сочетание из 49 по 7.
Количество возможных сочетаний из n по k обозначается буквой С:
Для вычисления количеств сочетаний из n по k сначала найдем количество аналогичных размещений. Оно вычисляется по формуле:
Однако ясно, что, как и в случае с перестановками с повторениями, некоторые сочетания мы посчитали несколько раз. Вернемся к примеру с командами. Если мы выбрали команды Л (Локомотив) , З (Зенит) и К (Краснодар), то мы можем составить ровно 3! = 6 размещений из них:
ЛЗК
ЛКЗ
ЗЛК
ЗКЛ
КЛЗ
КЗЛ
Однако все они соответствуют только одному сочетании – ЛКЗ. Таким образом, считая количество размещений, мы посчитали каждое сочетание не один, а 3! раз. Поэтому для нахождения количества сочетаний в комбинаторике надо поделить число размещений на число перестановок k элементов:
Эта формула связывает важнейшие понятия комбинаторики – перестановки, сочетания и размещения. Подставим в неё формулы для размещений и перестановок и получим:
Пример. Сколько троек призеров турнира можно составить, выбирая три футбольные команды из шести?
Решение. Посчитаем число сочетаний из 6 по 3:
Ответ: 20
Пример. Сколько комбинаций чисел может составить игрок, играющий в лотереи «5 из 36», «6 из 45», «7 из 49»?
Решение. В каждом из этих случаев игрок выбирает сочетание нескольких чисел. Посчитаем их число:
Ответ: 376992; 8145060; 85900584
Пример. На плоскости отмечены 8 точек, причем никакие три из них не лежат на одной прямой. Сколько различных прямых можно провести через них? Сколько треугольников и четырехугольников можно построить с вершинами в этих точках?
Решение. Для того чтобы провести прямую, достаточно выбрать любые 2 точки из 8. Общее количество прямых будет равно числу сочетаний из 8 по 2:
Заметим принципиальную важность того условия, что никакие три точки не лежат на одной прямой. Оно гарантирует, что при выборе двух различных точек мы будем получать различные прямые
Если бы, например, точки АВС лежали бы на одной прямой, то при выборе сочетаний АВ, ВС и АС мы получали бы одну и ту же прямую:
Это же условие гарантирует, что, выбрав любые 3 и 8 точек, мы сможем построить треугольник с вершинами в этих точках, а выбрав 4 точки, получим четырехугольник. Поэтому для подсчета количества треугольников и четырехугольников следует искать число сочетаний по 3 и 4:
Ответ: 28 прямых, 56 треугольников и 70 четырехугольников.
Пример. В одной урне находится 10 различных шаров с номерами от 0 до 9, а в другой – 8 различных шаров с первыми восемью буквами алфавита. По условиям лотереи ведущий вытаскивает из первой урны два шара с числами, а из второй – три шара с буквами. Для победы в лотерее надо угадать выпавшие шары. Сколько комбинаций шаров может выпасть в игре?
Решение. Посчитаем отдельно, сколькими способами можно выбрать 2 шара с цифрами из 10 и 3 шара с буквами из 8:
По правилу умножения мы должны перемножить эти числа, чтобы найти общее количество возможных вариантов:
56•45 = 2520
Ответ: 2520
Заметим, что выбирая, например, сочетание из 49 по 7, мы одновременно выбираем и сочетание из 49 по 49 – 7 = 42. Действительно, игрок, обводящий в кружок в лотерейном билете свои 7 счастливых чисел, одновременно и определяет остальные 42 числа, какие числа он НЕ считает счастливыми. Для наглядности запишем число сочетаний в обоих случаях:
Получили одну и ту же дробь, в которой отличается лишь последовательность множителей в знаменателе. Можно показать, что и в общем случае число сочетаний из n по k совпадает с количеством сочетаний из n по (n– k):
