Основные формулы комбинаторики 1 Факториал
Скачать 0.49 Mb.
|
Практические задачи с решениями можно найти на странице http://mathprofi.ru/zadachi_po_kombinatorike_primery_reshenij.html © http://mathprofi.ru , Емелин А., Высшая математика – просто и доступно! Основные формулы комбинаторики 1) Факториал (произведение всех натуральных чисел от 1 до n включительно) ) 1 ( ) 1 )( 2 ( 5 4 3 2 1 )! 1 ( ) 1 )( 2 ( 5 4 3 2 1 ! ) 1 )( 2 ( 5 4 3 2 1 )! 1 ( 5040 7 6 5 4 3 2 1 ! 7 720 6 5 4 3 2 1 ! 6 120 5 4 3 2 1 ! 5 24 4 3 2 1 ! 4 6 3 2 1 ! 3 2 2 1 ! 2 1 ! 1 n n n n n n n n n n n n Кроме того: 1 ! 0 2) Перестановки, сочетания и размещения без повторений Участники действий: множество, состоящее из n различных объектов (либо объектов, считающихся в контексте той или иной задачи различными) Формула количества перестановок: ! n P n Типичная смысловая нагрузка : «Сколькими способами можно переставить n объектов?» Формула количества сочетаний: ! )! ( ! m m n n С m n Типичная смысловая нагрузка : «Сколькими способами можно выбрать m объектов из n ?». Поскольку выборка проводится из множества, состоящего из n объектов, то справедливо неравенство n m 0 Формула количества размещений: n n m n A m n ) 1 ( ) 1 ( Типичная смысловая нагрузка : «сколькими способами можно выбрать m объектов (из n объектов) и в каждой выборке переставить их местами (либо распределить между ними какие-нибудь уникальные атрибуты)» Исходя из вышесказанного, справедлива следующая формула: m n m m n A P С И в самом деле: m n m m n A n n m n m n n n m n m n m n n m m m n n P С ) 1 ( ) 1 ( ) ( 3 2 1 ) 1 ( ) 1 )( ( 3 2 1 )! ( ! ! ! )! ( ! Практические задачи с решениями можно найти на странице http://mathprofi.ru/zadachi_po_kombinatorike_primery_reshenij.html © http://mathprofi.ru , Емелин А., Высшая математика – просто и доступно! 3) Бином Ньютона и треугольник Паскаля Под биномом Ньютона чаще всего подразумевают формулу возведения двучлена ) ( b a в целую неотрицательную степень n : ) ( ) ( ) ( ) ( ) ( ) ( ) ( 1 1 1 2 2 2 3 3 3 2 2 2 1 1 1 0 5 5 5 4 1 4 5 3 2 3 5 2 3 2 5 1 4 1 5 5 0 5 5 4 4 4 3 1 3 4 2 2 2 4 1 3 1 4 4 0 4 4 3 3 3 2 1 2 3 1 2 1 3 3 0 3 3 2 2 2 1 1 1 2 2 0 2 2 1 1 0 1 1 0 n n n n n n n n n n n n n n n n n n b C b a C b a C b a C b a C b a C a C b a b C b a C b a C b a C b a C a C b a b C b a C b a C b a C a C b a b C b a C b a C a C b a b C b a C a C b a b C a C b a b a 5 4 3 2 2 3 4 5 4 3 2 2 3 4 3 2 2 3 2 2 b 5ab b 10a b 10a b 5a a b 4ab b 6a b 4a a b 3ab b 3a a b 2ab a b a 1 Биномиальные коэффициенты m n C можно рассчитать по стандартной формуле (см. пункт 2), но удобнее воспользоваться так называемым треугольником Паскаля, который представляет собой бесконечную таблицу биномиальных коэффициентов. По бокам этого треугольника расположены единицы, а каждое внутреннее число равно сумме двух ближайших верхних чисел (красные метки): Так, например, для возведения двучлена в 6-ю степень следует руководствоваться общей формулой бинома, после чего сразу записать числа из строки № 6 треугольника Паскаля: 6 5 4 2 3 3 2 4 5 6 b 6ab b 15a b 20a b 15a b 6a a 6 6 6 5 1 5 6 4 2 4 6 3 3 3 6 2 4 2 6 1 5 1 6 6 0 6 6 ) ( b C b a C b a C b a C b a C b a C a C b a Кроме того, данная таблица позволяет быстро находить отдельно взятые биномиальные коэффициенты (например, в целях проверки вычислений по формуле ! )! ( ! m m n n С m n ): 2 6 C – находим строку № 6 и (внимание!) 2 + 1 = 3-й элемент слева (зелёный кружок): 15 2 6 C ; 5 9 C – находим строку № 9 и выбираем 5 + 1 = 6-й элемент слева (малиновый кружок): 126 5 9 C ; 3 10 C – находим строку № 10 и выбираем 3 + 1 = 4-й элемент слева (коричневый кружок): 120 3 10 C Практические задачи с решениями можно найти на странице http://mathprofi.ru/zadachi_po_kombinatorike_primery_reshenij.html © http://mathprofi.ru , Емелин А., Высшая математика – просто и доступно! 4) Комбинаторное правило суммы и комбинаторное правило произведения Если объект A можно выбрать из некоторого множества объектов m способами, а другой объект B – n способами, то выбор объекта A или объекта B (без разницы какого) возможен n m способами. Если объект A можно выбрать из некоторого множества объектов m способами и после каждого такого выбора объект B можно выбрать n способами, то упорядоченная пара объектов ) ; ( B A может быть выбрана mn способами. Данные принципы справедливы и для бОльшего количества объектов. Важная содержательная часть правил состоит в том, знак «плюс» понимается и читается как союз ИЛИ, а знак «умножить» – как союз И. 5) Перестановки, сочетания и размещения с повторениями Участники действий: множество, состоящее из объектов, среди которых есть одинаковые (либо считающиеся таковыми по смыслу задачи) Формула количества перестановок с повторениями: ! ! ! ! ! 3 2 1 ) ( k повт n n n n n n P , где n n n n n k 3 2 1 Типичная смысловая нагрузка : «Количество способов, которыми можно переставить n объектов, среди которых 1-й объект повторяется 1 n раз, 2-й объект повторяется 2 n раз, 3-й объект – 3 n раз,…, k -й объект – k n раз» Следует отметить, что в подавляющем большинстве задач в совокупности есть и уникальные (не повторяющиеся) объекты, в этом случае соответствующие значения i n равны единице, и в практических расчётах их можно не записывать в знаменатель. Формула количества сочетаний с повторениями: ! )! 1 ( ! ) 1 ( 1 ) ( m n m n С С m m n m повт n Типичная смысловая нагрузка : «Для выбора предложено n множеств, каждое из которых состоит из одинаковых объектов. Сколькими способами можно выбрать m объектов?» То есть, здесь в выборке могут оказаться одинаковые объекты, и если n m , то совпадения точно будут. По умолчанию предполагается, что исходная совокупность содержит не менее m объектов каждого вида, и поэтому выборка может полностью состоять из одинаковых объектов. Формула количества размещений с повторениями: m m повт n n A ) ( Типичная смысловая нагрузка : «Дано множество, состоящее из n объектов, при этом любой объект можно выбирать неоднократно. Сколькими способами можно выбрать m объектов, если важен порядок их расположения в выборке? » Для бОльшей ясности здесь удобно представить, что объекты извлекаются последовательно (хотя это вовсе не обязательное условие). В частности, возможен случай, когда из n имеющихся объектов m раз будет выбран какой-то один объект. |