Классы
Предметы

Комбинаторные задачи

Этот видеоурок доступен по абонементу
Подробнее об абонементе, платных и бесплатных уроках

У вас уже есть абонемент? Войти

Оплатить абонементот 75 руб. в месяц
У вас уже есть абонемент? Войти
Комбинаторные задачи

Тема урока: «Комбинаторные задачи». Человеку часто приходится сталкиваться с задачами, когда ему нужно посчитать число способов реализации некоторого действия. Например: вы забыли пароль на вашем компьютере, сколько вариантов вам придется перебрать, прежде чем вы сможете восстановить доступ? На данном уроке рассматривается раздел математики, который позволяет ответить на вопросы: сколькими способами, сколько вариантов и так далее. Этот раздел носит имя «комбинаторика».

Пример об автомобильных номерах

Для начала рассмотрим простой пример. Пусть в некотором регионе решили ввести формат номера автомобиля в виде числа. Вопрос: какое количество автомобилей мы сможем снабдить различными номерами? Внимательный учащийся сразу заметит неполноту формулировки задачи, не правда ли? И действительно, во-первых, не указано, какое количество знаков должно находиться в номере автомобиля, во-вторых, какие значения могут принимать отдельные цифры такого номера. Ну и конечно, как принято при решении подобных задач, начнем мы решение с рассмотрения самых простых случаев.

Пусть приняты только трехзначные номера, причем формируются они только цифрами 1, 2 и 3. Также вводится несколько нестандартное требование: пусть одна и та же цифра в номере будет встречаться не более одного раза. Это нужно для упрощения решения. В этом случае ответить на вопрос задачи совсем просто. Нужно перечислить все возможные комбинации из трех цифр. Вот они: , , .

Всего 6 штук. Согласитесь, маловато для автомобильных номеров. Давайте теперь будем нумеровать машины четырехзначными числами. Причем каждая цифра числа будет меняться в диапазоне от одного до четырех. Также сохраним требование к однократному присутствию каждой цифры в номере. Здесь перебирать номера вручную уже заметно тяжелее, если не верите, убедитесь самостоятельно. А пока воспользуемся следующим приемом:

первая цифра номера – 4 значения;

вторая – 3 значения;

третья – 2 значения.

У последней цифры остается только одна возможность. Тогда общее количество вариантов равно произведению . Этот перебор можно проиллюстрировать при помощи так называемого дерева возможных вариантов (Рис. 1.). Номера машин можно получить, если прочитать каждую ветку данной схемы сверху вниз.

Рис. 1. Дерево вариантов автомобильных номеров

24 – это уже значительно лучше, чем 6, однако все равно нам этого мало. В предыдущем примере мы воспользовались так называемым правилом умножения.

Правило умножения

Если, независимо друг от друга, элемент  можно выбрать  способами, элемент  –  способами и так далее, то комбинацию  можно выбрать  способами.

Пример об автомобильных номерах. (Продолжение)

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

Факториал

Факториал (обозначается ) – произведение подряд идущих первых  натуральных чисел.

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

Приведем несколько первых значений для n-факториала:

Следует обратить внимание на еще одно важное свойство факториала: значение факториала очень быстро возрастает с увеличением . Так, значение  уже больше чем , а  превышает  триллиона.

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

Для дальнейшего будет полезно знать еще одно важное свойство факториала:

Доказательство:

По определению, факториал равен:

.

Сгруппировав все сомножители, кроме последнего, получим:

При этом в скобках, снова, по определению факториала, имеем  

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

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

Перестановка из  элементов – каждое расположение этих элементов в определенном порядке.

На основании предыдущих рассуждений можно сформулировать такое утверждение:  различных элементов можно расставить по одному на  различных мест ровно  способами.

 – число перестановок.

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

Размещения

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

 – число размещений.

Опираясь на правило умножения, можно найти выражение для .

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

первая цифра может принимать 5 возможных значений;

вторая – 4 значения;

третья – 3.

Общее число вариантов .

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

Если рассмотреть подобные примеры при различных  и , то можно убедиться, что все они описываются одной формулой:

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

Умножим и разделим правую часть этого равенства на факториал числа :

Заменив  произведением :

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

В числителе дроби записано произведение всех натуральных чисел . Это произведение по определению равно . Следовательно, число размещений  равно:

Мы получили формулу для вычисления числа размещений из  элементов по , при

Формула для числа размещений остается справедливой и в случае, когда . В этом случае мы имеем формулу для числа размещений из  элементов по : .

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

Мы пришли к уже известной формуле числа перестановок. 

Пример об автомобильных номерах. (Продолжение2)

Будем снова считать, что каждая цифра номера лежит в диапазоне . Для простоты снова рассмотрим трехзначные номера без повторения цифр. Представим себе такую ситуацию: нам необходимо разделить автомобили на группы по профессиональной принадлежности владельца. Например, врачам будем выдавать лишь номера, состоящие из цифр 1, 2 и 3. Учителям – только номера, состоящие из цифр 1, 2 и 4, и т. д. Вопрос: сколько различных профессий мы сможем идентифицировать таким способом?

В чем отличие такой задачи от той, где мы подсчитывали число размещений? А разница в том, что здесь для нас не имеет значения порядок следования цифр. Т. е., к примеру, если мы видим автомобиль с номером , или автомобиль с номером , или автомобиль с номером , то мы однозначно утверждаем, что за рулем этой машины сидит врач. Если мы видим автомобиль с номерами ,  или  то мы говорим: «Это едет учитель».
Теперь, как же ответить на вопрос задачи? 

Для этого нам просто необходимо перебрать все варианты группировок из 4 цифр по 3 (Рис. 2).

Рис. 2. Автомобильные номера

После чего, объединить в группы номера, отличающиеся только порядком цифр (Рис. 3).

Рис. 3. Автомобильные номера, объединенные в группы

Нужно подсчитать количество групп, которое вы видите на Рис. 3. Это количество мы будем называть «сочетанием».

Задача на размещение элементов

Сколько существует семизначных телефонных номеров, в которых все цифры различные и первая цифра отлична от нуля?

Общее число семизначных комбинаций определяется по формуле перестановок. Всего цифр – , из них выбираем по . Получаем .

Вычислим количество комбинаций, в которых на первом месте 0. Остается  цифр, и из них можем варьировать . Количество комбинаций с нулем получается равным .

Количество номеров, в которых первая цифра не равна нулю, равно:

Сочетание

Сочетанием из  элементов по  называется любое множество, составленное из  элементов, выбранных из данных  элементов.

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

 – число сочетаний

В рассмотренном примере число вариантов равно  (число различных профессий, которые мы сможем идентифицировать при помощи автомобильных номеров).

Выражение для числа сочетаний.

Докажем, что

Допустим, имеется множество, содержащее  элементов, из его элементов составлены все возможные сочетания по  элементов. Число таких сочетаний равно . В каждом таком сочетании можно выполнить ровно  перестановок. В результате получим все размещения, которые можно составить из  элементов по . Их число равно .

Получаем

Пользуясь формулой для числа размещений, где , находим, что число сочетаний из  по  равно:

Вычислим количество сочетаний из 4 по 3, полученное в предыдущей задаче:

Это совпадает с ранее посчитанным количеством групп. 

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

Задача на сочетание элементов

В классе учатся 12 мальчиков и 10 девочек. Для уборки территории школы необходимо выделить трех мальчиков и двух девочек. Сколькими способами можно это сделать?

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

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

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

 

Заключение

В заключение резюмируем основные моменты урока.

Как вы могли заметить, большинство из рассмотренных примеров имеют вполне ощутимое отношение к реальной жизни. Ведь в жизни нам часто приходится сталкиваться с ситуациями, когда необходимо подсчитать число каких-либо вариантов. Мы обычно начинаем просто перечислять эти варианты, многое упуская из виду. Комбинаторика как раз позволяет нам избавиться от такого прямого пересчета вариантов, заранее вычислив их количество. 

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

 

Список литературы

  1. Решение задач по статистике, комбинаторике и теории вероятностей 7–9 класс. Изд-во: Учитель, 2010.
  2. Алгебра. Элементы статистики и теории вероятностей. Учебное пособие для учащихся 7–9 классов общеобразовательных учреждений. Макарычев Ю.Н., Миндюк Н.Г. Под ред. С.А. Теляковского. – М.: 2003.
  3. События. Вероятности. Статистика. Дополнительные материалы к курсу алгебры для 7–9 классов. Мордкович А.Г., Семенов П.В. – М.: Мнемозина, 2002.
  4. Ткачев М.В., Федоров М.Е. Алгебра 7–9. Элементы статистики и вероятности. – М.: Просвещение, 2003.

 

Дополнительные рекомендованные ссылки на ресурсы сети Интернет

  1. Nsportal.ru (Источник).
  2. Yaklass.ru (Источник).
  3. Mathematics-tests.com (Источник).

 

Домашнее задание

  1. В знаменитой басне Крылова «Квартет» проказница Мартышка, Осел, Козел да косолапый Мишка исследовали влияние взаимного расположения музыкантов на качество исполнения. Сколько существует способов, чтобы рассадить четырех музыкантов?
  2. В группе ТД–21 обучается 24 студента. Сколькими способами можно составить график дежурства по техникуму, если группа дежурных состоит из трех студентов?
  3. Сколько трехкнопочных комбинаций существует на кодовом замке (все три кнопки нажимаются одновременно), если на нем всего 10 цифр?
  4. Сколькими способами можно наугад зачеркнуть 6 чисел из 49?