Подготовка школьников к ЕГЭ и ОГЭ в учебном центре «Резольвента» (Справочник по математике — Алгебра
При решении задач по комбинаторике используют следующие важные понятия
Факториалы
Для произвольного натурального числа n формула
определяет факториал числа n ( n ! читается, как n – факториал).
Например,
Считается, что
0 ! = 1 , 1 ! = 1.
Перестановки
Рассмотрим следующую задачу.
Задача. 6 карточек пронумерованы числами 1, 2, 3, 4, 5, 6. Карточки наугад выкладываем в ряд. Сколько при этом можно получить различных шестизначных чисел?
Решение. Сначала слева направо пронумеруем места в ряду, куда выкладываем карточки: первое место, второе, третье, четвертое, пятое, шестое. На первое место можно положить одну из 6 карточек. Для этого есть 6 способов. В каждом из этих 6 способов на второе место можно положить одну из оставшихся 5 карточек. Таким образом, существует
способов, чтобы положить карточки на первое и второе места. В каждом из этих 30 способов на третье место можно положить одну из оставшихся 4 карточек. Следовательно, существует
способов, чтобы положить карточки на первое, второе и третье места. В каждом из этих 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 элементов можно познакомиться в разделе «Комбинаторика: размещения и сочетания» нашего справочника.
На нашем сайте можно также ознакомиться с разработанными преподавателями учебного центра «Резольвента» учебными материалами для подготовки к ЕГЭ и ОГЭ по математике.
Приглашаем школьников (можно вместе с родителями) на бесплатное тестирование по математике, позволяющее выяснить, какие разделы математики и навыки в решении задач являются для ученика «проблемными». Запись по телефону (495) 509-28-10 |
Для школьников, желающих хорошо подготовиться и сдать ЕГЭ или ОГЭ по математике или русскому языку на высокий балл, учебный центр «Резольвента» проводит
У нас также для школьников организованы
МОСКВА, СВАО, Учебный центр «РЕЗОЛЬВЕНТА»
www.resolventa.ru
Комбинаторные задачи. Видеоурок. Алгебра 9 Класс
Для начала рассмотрим простой пример. Пусть в некотором регионе решили ввести формат номера автомобиля в виде числа. Вопрос: какое количество автомобилей мы сможем снабдить различными номерами? Внимательный учащийся сразу заметит неполноту формулировки задачи, не правда ли? И действительно, во-первых, не указано, какое количество знаков должно находиться в номере автомобиля, во-вторых, какие значения могут принимать отдельные цифры такого номера. Ну и конечно, как принято при решении подобных задач, начнем мы решение с рассмотрения самых простых случаев.
Пусть приняты только трехзначные номера, причем формируются они только цифрами 1, 2 и 3. Также вводится несколько нестандартное требование: пусть одна и та же цифра в номере будет встречаться не более одного раза. Это нужно для упрощения решения. В этом случае ответить на вопрос задачи совсем просто. Нужно перечислить все возможные комбинации из трех цифр. Вот они: , , , , , .
Всего 6 штук. Согласитесь, маловато для автомобильных номеров. Давайте теперь будем нумеровать машины четырехзначными числами. Причем каждая цифра числа будет меняться в диапазоне от одного до четырех. Также сохраним требование к однократному присутствию каждой цифры в номере. Здесь перебирать номера вручную уже заметно тяжелее, если не верите, убедитесь самостоятельно. А пока воспользуемся следующим приемом:
первая цифра номера – 4 значения;
вторая – 3 значения;
третья – 2 значения.
У последней цифры остается только одна возможность. Тогда общее количество вариантов равно произведению . Этот перебор можно проиллюстрировать при помощи так называемого дерева возможных вариантов (Рис. 1.). Номера машин можно получить, если прочитать каждую ветку данной схемы сверху вниз.
Рис. 1. Дерево вариантов автомобильных номеров
24 – это уже значительно лучше, чем 6, однако все равно нам этого мало. В предыдущем примере мы воспользовались так называемым правилом умножения.
Если, независимо друг от друга, элемент можно выбрать способами, элемент – способами и так далее, то комбинацию можно выбрать способами.В случае, когда мы выбираем цифры из четверки цифр, каждая последующая цифра имеет количество способов выбора на единицу меньше предыдущей цифры. Тогда умножение этих количеств способов приводит нас к понятию факториала.
Факториал (обозначается ) – произведение подряд идущих первых натуральных чисел.
Заметьте: при этом полагается, что факториал нуля равен единице: и факториал единицы также равен единице .
Приведем несколько первых значений для n-факториала:
Следует обратить внимание на еще одно важное свойство факториала: значение факториала очень быстро возрастает с увеличением . Так, значение уже больше чем , а превышает триллиона.
Для дальнейшего будет полезно знать еще одно важное свойство факториала:
Доказательство:
.
Сгруппировав все сомножители, кроме последнего, получим:
При этом в скобках, снова, по определению факториала, имеем
На рассмотренных примерах мы смогли убедиться, что число способов, которыми можно составить, например, четырехзначный номер из четырех цифр, равно . Очевидно, что здесь есть общая закономерность, когда количество распределяемых элементов, то есть цифр, совпадает с количествами элементов, по которым надо распределить, то есть количеством разрядов в числе. В этом случае мы имеем дело с примером так называемой «перестановки».
Перестановка из элементов – каждое расположение этих элементов в определенном порядке.
На основании предыдущих рассуждений можно сформулировать такое утверждение: различных элементов можно расставить по одному на различных мест ровно способами.
– число перестановок.
Вновь вернемся к нашему примеру. Будем обсуждать случай, когда число знаков в автомобильном номере, то есть количество распределяемых элементов, меньше количества элементов, по которым нужно распределить, то есть количества цифр, из которых состоит номер. Здесь мы имеем дело уже не с перестановками, а с так называемыми «размещениями».
Размещение из элементов по , где меньше, либо равно , – любое множество, состоящее из элементов, взятых в определенном порядке из данных элементов. Таким образом, два размещения из элементов по считаются различными, если они различаются самими элементами или порядком из расположения.
– число размещений.
Опираясь на правило умножения, можно найти выражение для .
Пусть у нас есть 5 цифр, из которых нужно составить трехзначное число. Применим уже известный нам способ подсчета количества возможных вариантов:
первая цифра может принимать 5 возможных значений;
вторая – 4 значения;
третья – 3.
Общее число вариантов .
Вам предлагается самостоятельно разобрать ситуацию, когда необходимо сформировать, например, двузначный номер, а я приведу лишь здесь ответ:
Если рассмотреть подобные примеры при различных и , то можно убедиться, что все они описываются одной формулой:
В такой форме выражение очень тяжело запомнить, поэтому немного его преобразуем, ведь в нашем распоряжении есть факториал.
Умножим и разделим правую часть этого равенства на факториал числа :
Заменив произведением :
И, расположив сомножители в порядке возрастания, получим:
В числителе дроби записано произведение всех натуральных чисел . Это произведение по определению равно . Следовательно, число размещений равно:
Мы получили формулу для вычисления числа размещений из элементов по , при .
Формула для числа размещений остается справедливой и в случае, когда . В этом случае мы имеем формулу для числа размещений из элементов по : .
Но давайте обратим внимание: когда мы говорим «число размещений из элементов по », то такие размещения отличаются друг от друга лишь порядком элементов, ведь состав элементов у них один и тот же. И там по элементов. А мы помним, что те перечисления, которые отличаются друг от друга лишь порядком элементов, называются перестановками. То же самое получим при помощи формулы: итак, при мы получаем:
Мы пришли к уже известной формуле числа перестановок.
Будем снова считать, что каждая цифра номера лежит в диапазоне . Для простоты снова рассмотрим трехзначные номера без повторения цифр. Представим себе такую ситуацию: нам необходимо разделить автомобили на группы по профессиональной принадлежности владельца. Например, врачам будем выдавать лишь номера, состоящие из цифр 1, 2 и 3. Учителям – только номера, состоящие из цифр 1, 2 и 4, и т. д. Вопрос: сколько различных профессий мы сможем идентифицировать таким способом?
В чем отличие такой задачи от той, где мы подсчитывали число размещений? А разница в том, что здесь для нас не имеет значения порядок следования цифр. Т. е., к примеру, если мы видим автомобиль с номером , или автомобиль с номером , или автомобиль с номером , то мы однозначно утверждаем, что за рулем этой машины сидит врач. Если мы видим автомобиль с номерами , или то мы говорим: «Это едет учитель».
Для этого нам просто необходимо перебрать все варианты группировок из 4 цифр по 3 (Рис. 2).
Рис. 2. Автомобильные номера
После чего, объединить в группы номера, отличающиеся только порядком цифр (Рис. 3).
Рис. 3. Автомобильные номера, объединенные в группы
Нужно подсчитать количество групп, которое вы видите на Рис. 3. Это количество мы будем называть «сочетанием».
Сколько существует семизначных телефонных номеров, в которых все цифры различные и первая цифра отлична от нуля?
Общее число семизначных комбинаций определяется по формуле перестановок. Всего цифр – , из них выбираем по . Получаем .
Вычислим количество комбинаций, в которых на первом месте 0. Остается цифр, и из них можем варьировать . Количество комбинаций с нулем получается равным .
Количество номеров, в которых первая цифра не равна нулю, равно:
Сочетанием из элементов по называется любое множество, составленное из элементов, выбранных из данных элементов.
В отличие от размещений, в сочетаниях для нас совершенно не важен порядок следования элементов. Два сочетания отличаются друг от друга хотя бы одним элементом, то есть составом.
– число сочетаний
В рассмотренном примере число вариантов равно (число различных профессий, которые мы сможем идентифицировать при помощи автомобильных номеров).
Выражение для числа сочетаний.
Докажем, что
Допустим, имеется множество, содержащее элементов, из его элементов составлены все возможные сочетания по элементов. Число таких сочетаний равно . В каждом таком сочетании можно выполнить ровно перестановок. В результате получим все размещения, которые можно составить из элементов по . Их число равно .
Получаем .
Пользуясь формулой для числа размещений, где , находим, что число сочетаний из по равно:
Вычислим количество сочетаний из 4 по 3, полученное в предыдущей задаче:
interneturok.ru
Онлайн калькулятор: Факториал
Факториал числа n (обозначается n!) — произведение всех натуральных чисел до n включительно:
По определению полагают 0! = 1. Факториал определён только для целых неотрицательных чисел.
Поскольку в вычислениях иногда бывает довольно трудно перемножать все числа входящие в факториал, используется так называемая формула Стирлинга:
приближенная формула для вычисления факториала.
Во многих случаях для упрощения рассматривают только главный член формулы
При этом утверждается, что
Калькулятор рассчитывает «честный» факториал, факториал по формуле Стирлинга, а также нижнюю и верхнюю границу (из неравенства). К сожалению, из-за ограниченных вычислительных способностей Javascript максимально возможный факториал для калькулятора — 170!
Знаков после запятой: 2
Граница снизу
Формула Стирлинга
Граница сверху
Сохранить share extension
planetcalc.ru
Факториал. Объясните, пожалуйста! n! — n факториал можно…
потому, что перед факториалом указывается последний множитель (натуральное число). А (n+1) — уже больше n и в n! не входит .
Далее в формуле расписали n! и (n+2)! через факториалы, которые стоят в знаменателях, чтобы потом произвести сокращение.
Ну, и конечно, в конце сократили на .
Оцени ответ
shkolniku.com