Элементы комбинаторики


Основные определения и правила комбинаторикиКомбинаторика – раздел математики, изучающий вопрос о том, сколько различных комбинаций, подчинённых некоторым условиям, можно составить из конечного числа заданных объектов.
Примеры:
1. Сколькими способами можно расставить на полке 5 книг?
2. Сколькими способами можно выбрать 2-х дежурных из нашего класса в 29 человек.
3. Сколько различных двузначных чисел можно составить из цифр 1, 2, 3, 4?
4. Каких чисел больше среди первых 100, натуральных чисел: содержащих в своей записи цифру 7 или нет?
Выбором объектов и расположением их в том или ином порядке приходится заниматься чуть ли не во всех областях человеческой деятельности, например конструктору, разрабатывающему новую модель механизма, ученому-агроному, планирующему распределение сельскохозяйственных культур на нескольких полях, химику, изучающему строение органических молекул, имеющих данный атомный состав.
С аналогичными задачами, получившими название комбинаторных, люди столкнулись в глубокой древности. Уже несколько тысячелетий назад в Древнем Китае увлекались составлением магических квадратов, в которых заданные числа располагали так, что их сумма по всем горизонталям, вертикалям и главным диагоналям была одной и той же. В Древней Греции подсчитывали число различных комбинаций длинных и коротких слогов в стихотворных размерах, занимались теорией фигурных чисел, изучали фигуры, которые можно составить из частей особым образом разрезанного квадрата, и т.д.
Комбинаторные задачи возникали и в связи с такими играми, как шашки, шахматы, домино, карты, кости и т.д. Комбинаторика становится наукой лишь в XVII в. – в период, когда возникла теория вероятностей. Чтобы решать теоретико-вероятностные задачи, нужно было уметь подсчитывать число различных комбинаций, подчиненных тем или иным условиям. После первых работ, выполненных в XVI в. итальянскими учеными Дж. Кардано, Н. Тартальей и Г. Галилеем, такие задачи изучали французские математики Б. Паскаль и П. Ферма. Первым рассматривал комбинаторику как самостоятельную ветвь науки немецкий философ и математик Г. Лейбниц, опубликовавший в 1666 г. работу «Об искусстве комбинаторики», в которой впервые появляется сам термин «комбинаторный». Замечательные достижения в области комбинаторики принадлежат Л. Эйлеру. Комбинаторными задачами интересовались и математики, занимавшиеся составлением и разгадыванием шифров, изучением древних письменностей. Теперь комбинаторика находит приложения во многих областях науки: в биологии, где она применяется для изучения состава белков и ДНК, в химии, механике сложных сооружений и т.д.
Основными задачами комбинаторики являются: 1) определение вида соединения; 2) подсчет числа соединений.
По мере развития комбинаторики выяснилось, что, несмотря на внешнее различие изучаемых ею вопросов, многие из них имеют одно и то же математическое содержание и сводятся к задачам о конечных множествах и их подмножествах. Постепенно выявилось несколько основных типов задач, к которым сводится большинство комбинаторных проблем. Важную область комбинаторики составляет теория перечислений. С ее помощью можно подсчитать число решений различных комбинаторных задач. В основе этой теории лежат «правило суммы» и «правило произведения».
Правила суммы и произведения
1.Правило суммы: если объект А может быть выбран n способами, а объект В – m способами, то выбор «А или В» может быть осуществлен n+m способами.
Пример. Если на одной полке книжного шкафа стоит 30 различных книг, а на другой - 40 различных книг (и не таких, как на первой полке), то выбрать одну книгу из стоящих на этих полках можно 30+40=70 способами.
При использовании правила сложения нужно следить, чтобы ни один из способов выбора объекта А не совпадал с каким-нибудь способом выбора объекта В, т. е. чтобы ни одна комбинация не попала сразу в два класса. Если такие совпадения имеются, правило сложения в ранее сформулированной форме утрачивает силу, и мы получаем m + n – k способов выбора, где k — число совпадений.
2. Общее правило суммы: Если объект А можно выбрать m способами, а объект В — n способами, причем при k способах одновременно выбираются и А и В, то выбор «А или В» можно осуществить m + n – k способами.
Пример. Сколько чисел в первой сотне, не делящихся ни на 2, ни на 3?
Решение: Легче вычислить сначала количество чисел первой сотни, делящихся на 2 или на 3. Каждое второе число в натуральном ряде делится на 2, каждое третье— на 3. Поэтому в первой сотне есть 50 чисел, делящихся на 2, и 33 числа (неполное частное от деления 100 на 3), делящихся на 3. Но среди первых и вторых имеются числа, делящиеся и на 2, и на 3, т. е. делящиеся на 6. На 6 делится каждое шестое число в натуральном ряде. Если 100 разделить на 6, то неполное частное будет равняться 16, т. е. 16 чисел в первой сотне делится на 6. Итак, количество чисел в первой сотне, делящихся на 2 или на 3, равно 50 + 33 – 16 = 67. Все остальные не делятся ни на 2, ни на 3. Этих чисел 100 – 67 = 33.
3.Правило произведения: если объект А может быть выбран n способами и после каждого из таких выборов объект В – m способами, то выбор «А и В» в указанном порядке может быть осуществлен n*m способами.
Пример. В школьной столовой на первое можно заказать борщ, солянку, грибной суп, на второе - мясо с макаронами, рыбу с картошкой, курицу с рисом, а на третье - чай и компот. Сколько различных обедов можно составить из указанных блюд?
Решение: Первое блюдо можно выбрать одно из трех (борщ, солянку или грибной суп), второе блюдо тоже одно из трех (мясо с макаронами, рыбу с картошкой или курицу с рисом), на десерт только два варианта (чай или компот). Используя правило произведения, получаем: 3х3х2=18.
Пример. В классе 25 человек. Сколькими способами:
а) можно распределить между ними два различных учебника;
б) можно распределить между ними два различных учебника так, чтобы никто не получил оба учебника;
Решение: а) Первый учебник может получить любой из 25 учащихся.Кто бы ни получил первый учебник, второй может достаться снова любому из 25, ведь в условии не сказано, что каждый должен получить не более одного учебника. Всего имеем 25* 25 = 625 способов.
б) В отличие от предыдущего задания, никто не должен получить оба учебника. Поэтому для каждого из 25 вариантов выбора обладателя первого учебника есть 24 способа выбора обладателя второго учебника. Всего имеем 25*24 = 600 способов.
Рассмотрим примеры, использующие правила суммы и произведения.
Пример. Сколькими способами из 28 костей домино можно выбрать две кости так, чтобы их можно было приложить друг к другу (т.е. чтобы какое-то число очков встретилось на обеих костях)?
Решение. Сначала выберем одну кость. Это можно сделать 28 способами. При этом в случаях выбранная кость окажется "дублем", т.е. костью вида 00, 11, 22, 33,44 , 55 ,66, а в 21 случае - костью с различными числами очков (например, 05, 13 и т.д.).В первом случае вторую кость можно выбрать 6 способами (например, если на первом шагу выбрана кость 11, то на втором шагу можно взять одну из костей 01, 12, 13, 14, 15, 16).Во втором же случае вторую кость можно выбирать 12 способами (для кости 35 подойдут кости 03, 13, 23, 33, 34, 36, 05, 15, 25, 45, 55, 56). По правилу произведения в первом случае получаем 7*6=42 выбора, а во втором 21*12=252 выбора. Значит по правилу суммы получаем 42+252=294 способов выбора пары.
Пример. Сколько существует четырехзначных чисел, у которых все цифры нечетные? Сколько существует четырехзначных чисел, в записи которых есть хотя бы одна четная цифра?
Решение. Всего нечетных цифр - пять, поэтому выбор k-й цифры числа может быть сделан nк=5 способами (к=1, 2, 3, 4), а количество четырехзначных чисел, у которых все цифры нечетные, равно 5*5*5*5=625. Чтобы ответить на второй вопрос, проще не определять последовательно, сколько существует чисел, в записи которых ровно одна четная цифра, две цифры, три цифры, четыре цифры, а воспользоваться полученным ответом на первый вопрос. Все четырехзначные числа, а их 9999-999=9000, делятся на две группы: те, в записи которых все цифры нечетные, и те, в записи которых есть хотя бы одна четная цифра. Следовательно, количество чисел второго типа равно 9000-625=8375.
Пример. Из города А в город В ведут пять дорог, а из города В в город С — три дороги. Пусть, кроме того, из города А в город D можно попасть двумя путями, из D в C — четырьмя (рис.1). Сколькими способами можно добраться из А в С?

Рис. 1. Варианты перемещения между городами
Решение: Возможны два случая: путь из А в С проходит через город В или через город D. В каждом из этих случаев число возможных маршрутов легко подсчитать, воспользовавшись правилом произведения. В первом случае имеется 5*3 = 15 маршрутов; во втором — 2*4 = 8. Складывая, получаем общее число маршрутов: 15 + 8 = 23.
Правило суммы и произведения – это общие правила решения комбинаторных задач. Кроме них в комбинаторике пользуются формулами для подсчета числа отдельных видов соединений, которые встречаются наиболее часто.
Соединения без повторенийПри определении вида соединения удобно пользоваться следующей схемой (рис.2):

Рис. 2. Схема выбора вида соединения
Пусть дано множество М, состоящее из n элементов.
Определение. Перестановки – всевозможные упорядоченные множества, составленные из всех элементов данного множества. Число всевозможных перестановок из n элементов обозначают Рn и находят по формуле
Рn= n! (1),
где n!= 123 … n, 0!=1 по определению.
Пример. Сколько перестановок можно составить из трех букв а, в, с?
Решение: Р3=123=6. Действительно: авс, вас, асв, сав, вса, сва.
Пример. Сколькими способами можно переставить буквы в слове «треугольник»?
Решение: Т.к. все буквы в данном слове разные, т.е. нет повторений, то можно воспользоваться формулой (1): Р11=11!=39916800.
Определение. Размещениями из n по m называются всевозможные упорядоченные подмножества, содержащие m элементов из данных n. Обозначаются и вычисляются по формуле:
(2)
Пример. Сколько можно составить четырехзначных чисел, содержащих различные цифры из 5 цифр.
Решение: Четырехзначное число – это упорядоченная последовательность цифр, т.е. имеем дело с размещениями без повторений:
=5432=120.
Пример. В классе 10 учебных предметов и 5 разных уроков в день. Сколькими способами может быть составлено расписание на 1 день?
Решение: .
Определение. Сочетаниями из n по m называются всевозможные неупорядоченные подмножества данных n элементов, состоящие из m элементов. Для подсчета их числа используются следующие обозначение и формула:
(3)
Пример. Сколькими способами можно из 7 различных открыток выбрать три?
Решение: Совокупность трех открыток является неупорядоченным подмножеством семи открыток, поэтому имеем дело с сочетаниями:
.
Пример. Из группы в 25 человек нужно выбрать троих для работы на субботнике.
Решение: Если выбирать их последовательно, сначала первого, потом второго, потом третьего, то получим 25 * 24 * 23. Но так как нас не интересует порядок выбора, а только количество выбранных человек:
25!/(3!*22!)
Соединения с повторениямиОпределение. Перестановками с повторениями называются перестановки из n элементов, в каждую из которых входит n1 элементов а, n2 элементов b, …, nk элементов l, где n=n1+n2+…+nk. Число перестановок с повторениями вычисляется по формуле:
(4)
Пример. Сколькими способами можно переставить буквы в слове “математика”.
В слове “математика” есть повторяющиеся буквы: “м” – 2 раза, “а” – 3 раза, “т” – 2 раза, “е” – 1 раз, “и” – 1 раз, “к” – 1 раз. Порядок расположения элементов имеет значение (это очевидно, так как если переставить местами 2 буквы, то получатся разные слова) и все элементы используются, следовательно, это перестановка с повторениями.

Таким образом, в слове “математика” можно переставить буквы 151200 способами.
Определение. Сочетания из n элементов, в каждое из которых входит m элементов, причем один и тот же элемент может повторяться в каждом сочетании любое число раз, но не более m, называются сочетаниями с повторениями. Число сочетаний с повторениями вычисляется по формуле:
(5)
Пример. На почте продаются открытки 10 сортов. Сколько вариантов существует для покупки 12 открыток.
Порядок расположения элементов не имеет значения, следовательно, это сочетание. А так как открытки в наборе могут повторяться, то это сочетание с повторениями.

Таким образом, из 10 открыток можно выбрать набор из 12 штук 293930 способами.
Определение. Размещениями с повторениями из n элементов по k элементов называются упорядоченные множества, каждое из которых содержит k необязательно различных элементов из данного множества n элементов. Число размещений с повторениями вычисляется по формуле:
(6)
Пример. В стену здания вмонтированы 8 гнезд для флажков. В каждое гнездо вставляется либо голубой, либо красный флажок. Сколько различных случаев распределения флажков на здание.
Так как порядок расположения элементов важен и не все элементы используются в данном соединении, то это размещение. А так как всего 8 гнезд, а флажков 2 вида (голубой и красный), то они будут повторяться, т.е. это размещение с повторением.

Таким образом, существует 256 способов украсить здание с 8 гнездами флажками двух цветов.
Если имеются ограничения на количество разных предметов, которые можно помещать на позиции. В этом случае число размещений рассчитываться по формуле:
A = k1 * k2 * k3 *...*kn (5.7)
Пример. В эстафете 100, 200, 400, 800 метров на первую позицию тренер может выставить одного из 3 бегунов, на вторую - одного из 5, на третью - одного из 6, на четвертую - единственного бегуна (на каждую позицию выставляются разные бегуны). Сколько вариантов расстановки участников эстафетного забега может составить тренер?
В соответствии с формулой получаем, что число вариантов равно:
3 * 5 * 6 * 1 = 90.
Пример. Сколько различных трехзначных чисел можно составить из цифр 0, 1, 2, 3?
Решение: На первое место в трехзначном числе можно выбрать любую цифру их трех (кроме нуля), после каждого такого выбора на второе место можно поставить любую цифру из оставшихся трех, на третье – из оставшихся двух. По правилу 2 получим: 332=18 чисел.
Примеры решения задач
3адача 1 Сколькими способами можно раскрасить диаграмму из 4 столбцов четырехцветной ручкой так, чтобы каждый столбец был окрашен в определенный цвет.
Решение: Порядок расположения элементов имеет значение и в диаграмме 4 столбца, а ручка тоже четырехцветная, т.е. все элементы присутствуют в соединении, следовательно, это соединение – перестановка. А так как окраска столбцов не повторяется (в условии сказано, что столбцы имеют разные цвета), то это перестановка без повторения. Итак, Pn = n! = 4! = 1234 = 24
Ответ: столбцы можно закрасить 24 способами.
3адача 2. Имеется 5 кружков: 3 белых и 2 черных. Сколько различных узоров можно получить, располагая кружки в ряд.
Решение: Порядок расположения элементов имеет значение и в узоре 5 кружков, т.е. все элементы присутствуют в соединении, следовательно, это соединение – перестановка. А так как окраска кружков повторяется (в условии сказано, что 3 белых и 2 черных), то это перестановка с повторением. Итак,

Ответ: узор можно составить 10 способами.
3адача 3 Сколько словарей надо издать, чтобы можно было непосредственно выполнить перевод с любого из 5 языков на любой из 5 языков.
Решение: Порядок имеет значение (так как русско-английский и англо-русский словари различны) и не все элементы присутствуют в соединении (а только 2 из 5), значит, это размещение. Так как языки различны, то это размещение без повторения. Итак,
Ответ: надо составить 20 словарей.
3адача 4 Семиклассники написали контрольную работу. Возможные оценки 2, 3, 4, 5. Сколько вариантов расстановки оценок в журнале, если в списке 10 учеников.
Решение: Порядок имеет значение и не все элементы присутствуют в соединении, значит, это размещение. Так как оценки могут повторяться, то это размещение с повторением. Итак,
Ответ: может быть 1048576 различных комбинаций оценок.
3адача 5. 12 человек играли в городки. Сколькими способами они могут разбиться на команды по 4 человека в каждой.
Решение: Порядок расположения игроков в команде не имеет значения, следовательно, это сочетание. А так как игроки не повторяются (все члены команды различные люди), то это сочетание без повторения. Итак,

Ответ: игроки могут разбиться на команды по 4 человека в каждой 495 способами.
3адача 6. На уроке технологии учитель предложил школьникам выбрать для поделки 10 листов цветной бумаги из предложенных 6 цветов. Сколько вариантов выбора есть у учеников (наборы, отличающиеся лишь расположением листов цветной бумаги на парте считать одинаковыми)?
Решение: Порядок расположения листов цветной бумаги на парте не имеет значения, следовательно, это сочетание. А так как цвета повторяются, то это сочетание с повторением. Итак, =3003
Ответ: выбрать цветную бумагу для поделки можно 3003 способами.
3адача 7 В группе 25 студентов, из которых 5 отличников, 11 хорошистов и остальные троечники. Сколькими способами можно выбрать группу для выполнения лабораторной работы, состоящей из 3 хорошистов, 1 отличника и 1 троечника.
Решение: Сначала узнаем сколькими способами можно выбрать 3 хорошистов из 11 человек. Порядок расположения студентов не важен, значит, это сочетание. А так как люди в группе не повторяются, то это соединение – сочетание без повторения. Итак, одного хорошиста можно выбрать способами. Аналогично рассуждая, приходим к тому, что 1 отличника можно выбрать способами и одного троечника можно выбрать способами. Так как команда для выполнения лабораторной работы выбирается одновременно, т.е. 5 хорошистов, затем 1 отличник, затем 1 троечник, то, применив правило произведения, получим: способами.
Ответ: группу для выполнения лабораторной работы можно составить 7425 способами.
3адача 8. Девочки на уроке труда приготовили пирожные и пригласили на чай трех мальчиков. Имеется 4 чашки, 5 блюдец, 6 ложек (все чашки, блюдца, ложки различны). Сколькими способами можно накрыть стол к чаю на 3 человека, если каждый получает 1 чашку, 1 блюдце и 1 ложку.
Решение: Выберем для 3 человек чашки из 4 имеющихся. Порядок расположения элементов имеет значение, и не все элементы входят в соединение, значит, это размещение. Но так чашки не повторяются, то это размещение без повторения. Итак, из 4 чашек 3 можно выбрать способами. Аналогично рассуждая, получим, что из 5 блюдец 3 можно выбрать способами, а из 6 ложек 3 можно выбрать способами. Так как блюдце, чашка и ложка входят в набор одновременно, то стол можно накрыть *=24*60*120=172800 способами.
Ответ: стол можно накрыть 172800 способами.

Приложенные файлы

  • docx 8930557
    Размер файла: 231 kB Загрузок: 0

Добавить комментарий