ХКОИС
ХРРЦ
Регистрация
Забыли пароль?
Логин:
Пароль:
Поиск
Справочные сведения о системе образования Хабаровского края
Новости образования Хабаровского края
Информация и документы из министерства образования и науки Хабаровского края
Хабаровская краевая заочная физико-математическая школа
РЕГИОНАЛЬНАЯ ОЛИМПИАДА ШКОЛЬНИКОВ
Подготовка к олимпиадам по информатике
Подготовка к олимпиадам по информатикеТеоретические материалы > Элементы комбинаторики
Элементы комбинаторики
 
В практической жизни мы часто решаем проблему подсчета количества различных комбинаций. Такие задачи называются комбинаторными, и соответствующий раздел математики называется комбинаторикой. Математическая энциклопедия определяет комбинаторику следующим образом: «Комбинаторная математика, комбинаторика – раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. Каждое правило определяет способ построения некоторой конструкции из элементов исходного множества, называемой комбинаторной конфигурацией».
 
Правила суммы и произведения
 
Решение многих комбинаторных задач основывается на двух основных правилах – правиле суммы и правиле произведения.
1. Правило суммы. Если некоторый объект x можно выбрать m способами, а объект y можно выбрать n способами, причем любой способ выбора объекта  x  отличен от любого способа выбора объекта  y, то выбор «x или y» можно осуществить m+n способами.
Правило суммы можно сформулировать в терминах теории множеств. Пусть X и Y- два непересекающихся конечных множества. Тогда число элементов,  содержащихся в объединении этих множеств, равно сумме чисел элементов в каждом из этих множеств.
Например, пусть в классе учатся 12 мальчиков и 8 девочек. Тогда выбор «мальчик или девочка» можно осуществить 20 способами.
2. Правило произведения. Если некоторый объект x можно выбрать m способами, и независимо от этого объект y можно выбрать n способами, то упорядоченную пару (x, y) можно выбрать  способами.
Это правило может распространяться и на большее количество объектов. Пусть элемент  может быть выбран  способом; при каждом выборе  элемент  может быть выбран  способами; при каждом выборе пары  элемент  может быть выбран  способами и т.д., и при каждом выборе упорядоченного набора  элемент  может быть выбран  способами. Тогда количество упорядоченных наборов  равно произведению .
Например, на день рождения собрались три мальчика – Женя, Юра, Сергей и две девочки – Настя и Маша. Они хотят сфотографироваться парами. Сколько таких пар получится?
Решение. Можно рассуждать двумя способами – перебрать все возможные варианты или воспользоваться правилом произведения. Каждый мальчик может сфотографироваться с двумя девочками.  Поэтому все возможные пары будут (Ж, Н), (Ж,М), (Ю,Н), (Ю,М), (С,Н), (С,М). Всего таких пар – 6. Тот же результат получим, рассуждая по правилу произведения: выбор мальчика можно осуществить 3 способами, после каждого такого выбора выбор девочки можно осуществить 2 способами, выбор пары (мальчик, девочка) можно осуществить   способами.
 
Размещения и перестановки
 
Начнем с задач.
Задача 1. Сколько различных трехзначных чисел можно составить из цифр , если цифры в числе не повторяются?
Решение. Будем рассуждать следующим образом. Цифру, стоящую в разряде «сотни» можно выбрать 4 способами из цифр  . После этого цифру, стоящую в разряде «десятки» можно выбрать уже из трех цифр, так как по условию цифры в числе не должны повторяться, а одну из четырех цифр мы уже использовали в предыдущем разряде. После выбора упорядоченной пары («сотни», «десятки»), цифру в разряде «единицы» можно выбрать двумя способами. По правилу произведения, упорядоченную тройку цифр (трехзначное число) можно выбрать  способами. Таким образом, существует 24 различных трехзначных чисел, составленных из цифр , если цифры в числе не повторяются.
Изобразим решение наглядно в виде графа:
 
 
Двигаясь по стрелкам, можно выписать все полученные числа: 123, 124, 132, 134, 142, 143, 213, 234, 231, 234,241, 243, 312, 314,321, 324, 241, 342, 412,413, 421, 423, 431, 432. Всего получилось 24 таких числа.
Задача 2. Сколько различных трехзначных чисел можно составить из цифр , если цифры в числе могут повторяться?
Решение. Посмотрим, чем эта задача отличается от предыдущей. Первую цифру (в разряде сотен) мы также можем выбрать из 4 цифр, вторую цифру (в разряде десяток), в отличие от предыдущей задачи, также выбираем из четырех цифр, так как по условию цифры могут повторяться. Третью цифру также выбираем из четырех. Поэтом по правилу произведения количество различных трехзначных чисел будет рано . Это можно проверить, изобразив решение в виде графа:
Проделайте это до конца, выпишите все такие числа и убедитесь, что их количество равно 64.
Задача 3. Сколькими способами 5 человек могут встать друг за другом в очередь?
Решение. Первого человека в очереди можно поставить 5 способами, после этого, второго человека в очереди можно выбрать 4 способами, после этого третьего – 3 способами, после этого четвертого – 2 способами и после этого пятого – одним способом. По правилу произведения получим, что общее количество способов равно .
В этой задаче мы использовали понятие факториала (обозначается «!»). Определим это понятие. По определению n! (читается «эн — факториал») задается рекуррентным соотношением:
0!=1, 1!=1,
.
Таким образом,   равен произведению последовательных натуральных чисел от 1 до n:
Проанализируем условия трех задач и определим, что в них одинакового и чем они отличаются. В каждой из трех задач требуется выбрать из множества, состоящего из n  элементов, упорядоченные подмножества, состоящие изm элементов. При этом в первой задаче элементы в подмножестве не повторялись и n < m. Во второй задаче элементы в подмножестве могли повторяться и n < m. В третьей задаче элементы в подмножестве не повторялись и nm. Для каждой из таких комбинаций в комбинаторике существует определенное  понятие. Дадим определения.
Определение(размещения без повторений). Размещением без повторений из nэлементов по m элементов называется упорядоченный набор, состоящий из m элементов, выбранных из данных n элементов, причем элементы в этом упорядоченном наборе не повторяются.
Число всех размещений без повторений обозначается  и вычисляется по формуле:
.
Эту же формулу можно записать, используя понятие факториала:
Определение (размещения с повторениями). Размещением с повторениями из nэлементов по m элементов называется упорядоченный набор, состоящий из m элементов, выбранных из данных n элементов, причем элементы в этом упорядоченном наборе могут повторяться.
Число всех размещений с повторениями обозначается  и вычисляется по формуле:
.
Определение(перестановки).  Перестановкой из nэлементов называется упорядоченный набор, состоящий из n элементов, выбранных из данных n элементов, причем элементы в этом упорядоченном наборе не повторяются.
Число всех перестановок обозначается  и вычисляется по формуле:
.
Учитывая формулу числа перестановок, можно записать формулу числа размещений без повторений в виде:
 и .
 
Сочетания. Бином Ньютона
 
1.     Сочетания
Начнем с задачи.
Задача 4. Девочка хочет составить букет из трех астр, имея по одной астре белого, розового, сиреневого и красного цвета. Сколькими способами она может это сделать?
Решение. В отличие от предыдущих задач, в которых порядок элементов в выбранном наборе имел значение, в этой задаче не имеет значение, в каком порядке девочка расположит цветы в букете. Поэтому среди всех возможных комбинаций нужно оставить только те, которые различаются своими элементами. Проделаем это на графе:
Выпишем все комбинации и выделим те, в которых элементы не повторяются:
(б,р,с), (б,р,к), (б,с,р), (б,с,к), (б,к,р), (б,к,с), (р,б,с), (р,б,к), (р,с,б), (р,с,к), (р,к,б), (р,к,с),
(с,б,р), (с,б,к), (с,р,б), (с,р,к), (с,к,б), (с,к,р), (к,б,р), (к,б,с), (к,р,б), (к,р,с), (к,с,б), (к,с,р). Все остальные комбинации получаются из выделенных жирным шрифтом путем перестановок букв внутри набора. Количество таких комбинаций равно 4.
Дадим определение.
Определение (сочетаний). Сочетанием из nэлементов по m элементов называется неупорядоченный набор, состоящий из m элементов, выбранных из данных n элементов, причем элементы в этом неупорядоченном наборе не повторяются.
          Число всех сочетаний из nэлементов по m элементов обозначается  и вычисляется по формуле:
         
Учитывая формулы для вычисления  и , получим:
Числа   обладают рядом замечательных свойств. Перечислим их, не приводя доказательств:
1.
2.
3. Для любого  имеет место равенство
    
Существует еще один способ вычисления , основанный на свойстве 3. Рассмотрим арифметический треугольник Паскаля, имеющий такую конструкцию: в каждой следующей строке, начиная с третьей, между цифрами предыдущей строки пишется их сумма:
 
 
 
 
 
1
 
 
 
 
 
 
 
 
 
1
 
1
 
 
 
 
 
 
 
1
 
2
 
1
 
 
 
 
 
1
 
3
 
3
 
1
 
 
 
1
 
4
 
6
 
4
 
1
 
1
 
5
 
10
 
10
 
5
 
1
В первой строке стоит значение , во второй строке – значения  и  , в третьей — , ,  и так далее. Способ вычислений этих значений опирается на рассмотренные выше свойства 1 и 3.
2. Бином Ньютона
В школьном курсе математики рассматривают следующие формулы сокращенного умножения:
,
.
Эти формулы являются частным случаем общей формулы – бинома Ньютона:
,
где n– любое натуральное число, числа называются биномиальными коэффициентами.
Формулу бинома Ньютона можно записать в компактной форме:         
          .
С помощью бинома Ньютона можно получать различные равенства. Например, если положить a=1 и b=1, то можно доказать свойство 2 для чисел .
          Нужно отметить, что формулы комбинаторики применяются очень широко, например, в теории вероятностей для вычисления вероятностей случайных событий.
 
 
Copyright © 2005–2017 ХабЦНИТ ТОГУ Отправить письмо
Создание сайтов в Хабаровске
в ресторане карнизы для римских штор серого и белого цвета. . насос grundfos sq 3-80