Материал для самостоятельной теоретической подготовке по теме "Комбинаторика"

Материал для самостоятельной теоритической подготовки по теме:

КОМБИНАТОРИКА

Комбинаторные соединения

            Прежде чем перейти к определению комбинаторных соединений, введем понятия, которые нам потребуются в дальнейшем.

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

            Некоторая совокупность элементов данного n- множества называется выборкой. Число элементов в выборке называется длиной выборки.

Пример 1. Пусть дано множество Х – множество цифр, т.е.  .

Это множество состоит из 10 элементов. Любой набор цифр, состоящий, например, из 4 цифр будет являться выборкой длины 4.

Замечание. Некоторую совокупность элементов из данного конечного множества можно выбирать по-разному:

1)      если при составлении выборки учитывается порядок следования элементов в выборке, тогда выборка называется упорядоченной; если же при составлении выборки не учитывается порядок следования элементов в ней, то выборка называется неупорядоченной;

2)      если при составлении выборки в нее может быть включен один и тот же элемент множества несколько раз, то выборка называется выборкой с повторениями; если же элементы множества входят в выборку только по одному разу, то выборка называется выборкой без повторений.

Пример 2. Пусть дано множество Х – множество цифр, т.е.  . Составить из цифр пятизначное число, цифры в котором не повторяются.

 Этим пятизначным числом может быть, например, число 54321. Переставим цифры в данном числе, например, так 45321, в результате получим другое число (другую выборку). Таким образом, при изменении порядка следования элементов в выборке, изменяется сама выборка, поэтому каждое пятизначное число является упорядоченной выборкой. Так как оба составленных числа не имеют в своем составе одинаковых цифр, то обе эти выборки являются выборками без повторений. Однако пятизначное число, например,  554331 является упорядоченной выборкой, но с повторениями.

Пример 3. Пусть имеются  открытки 6 видов. Составить из этих открыток набор, состоящий из 4 открыток.

            Каждый набор из 4 открыток будет являться выборкой. Если мы поменяем в наборе местами две открытки, то от этого набор открыток не измениться, т.е. выборка останется прежней. Таким образом, при изменении порядка следования элементов в выборке выборка не меняется, следовательно, в данном случае выборка неупорядоченная. Если в составленном наборе будут одинаковые открытки, то он будет выборкой с повторениями, если же все открытки в наборе будут различными, то набор будет являться выборкой без повторений.

Замечание. Набор свойств, которыми обладает выборка (упорядоченность, неупорядоченность, с повторениями или без повторений) будем называть характером выборки. Установление характера выборки очень важно для решения комбинаторной задачи.

            Рассмотрим три основных вида комбинаторных соединений: размещения, перестановки и сочетания.

Определение 1. Размещением с повторениями из m элементов данного n- множества называется упорядоченная выборка с повторениями длины m из элементов данного множества.

            Таким образом, если характер выборки: 1) упорядоченная; 2) с повторениями, то выборка является размещением с повторениями.  Число размещений с повторениями из m элементов данного n- множества обозначается  , и вычисляется по формуле:          =………………………………………(1)

Задача 4. Секретный замок сейфа состоит из 5 дисков, на каждом из которых написано по 12 букв. Сейф открывается, если на каждом из дисков выбрана определенная буква. Сколько неудачных попыток может быть сделано человеком, не знающим кода и подбирающим его наудачу?

Решение. 1) Человек должен выбирать из 12 букв, т.е. множество из которого производится выборка, состоит из  n = 12 элементов.

2) Так как на каждом диске нужно выбрать по одной букве, а дисков всего 5, то мы должны осуществить выборку длины m = 5.

3) Определим характер выборки. Так как на каждом из дисков выбирается определенная буква, то при таком выборе появляется некоторое слово, и если хотя бы две буквы этого слова переставить местами, мы получим другое слово, т.е. другую выборку, поэтому в данном случае мы имеем дело с упорядоченной выборкой. Так как  в условии ничего не говориться о том, что буквы должны быть различными, то имеем выборку с повторениями.

4) По характеру выборки делаем вывод что, каждое набранное слово является размещением с повторениями. По формуле (1) вычислим число таких слов:

                                = 248832

5) Значит, неудачных попыток может быть 248832 – 1 =248831.

Ответ: 248831.

Определение 2. Размещением без повторений из m элементов данного n- множества называется упорядоченная выборка без повторений длины m из элементов данного множества.

Таким образом, если характер выборки: 1) упорядоченная; 2) без повторений, то выборка является размещением без повторений.  Число размещений без повторений из m элементов данного n- множества обозначается  , и вычисляется по формуле:                     =   ………………………………(2)

Замечание. Символ  читается как n – факториал и означает произведение первых n натуральных чисел: .

Задача 5.  Сколько различных четырехбуквенных слов можно составить из букв слова  ученик, написанных на отдельных карточках?

Решение. 1) Множество из которого производится выборка – множество букв слова ученик, в котором n = 6 букв.

2) Составляют четырехбуквенные слова, поэтому каждое такое слово есть выборка длиной m = 4.

3) Определим характер выборки: 1) так как составляем слова, в которых порядок букв существенен, то выборка является упорядоченной; 2) так как все буквы данного слова различные, то выборка происходит без повторений.

3) По характеру выборки делаем вывод что, каждое составленное слово является размещением без повторений. По формуле (2) найдем число размещений без повторений из 6 элементов по 4:  == = 360.

Ответ: из букв слова ученик можно составить 360 четырехбуквенных слов.

Определение 3. Перестановкой без повторений из n элементов данного n- множества называется упорядоченная выборка без повторений длины n из элементов данного множества.

            Таким образом, если характер выборки: 1) упорядоченная; 2) без повторений, и выбирают все элементы n- множества, то выборка является перестановкой без повторений.  Число перестановок без повторений из n элементов обозначается  , и вычисляется по формуле:      ………………………….(3)

Задача 6. Сколькими способами очередей можно составить из 10 человек.

Решение. 1) Множество из которого выбирают, состоит из n = 10 элементов;

2)Выбирают все 10 человек, поэтому длина выборки m = 10, т.е. m = n.

3)      Определим характер выборки: выбираем упорядоченно и без повторений.

4)      По характеру выборки делаем вывод, что каждая составленная очередь это перестановка без повторений. По формуле (3) вычислим число перестановок без повторений из n элементов:  .

Ответ: можно составить 3628800 очередей.

            Используя формулу (3) можно вычислить, сколько четырехзначных цифр можно составить из цифр 1,2,3,4: . В слове мама тоже четыре буквы, поставим задачу: сколько различных четырёхбуквенных слов можно составить из букв слова мама. В отличие от предыдущего случая таких слов будет не 24, а всего 6 (мама, маам, ммаа, амам, аамм, амма). Дело в том, что в слове мама есть одинаковые буквы, т.е. при составлении слов происходит упорядоченная выборка с повторениями. Однако в отличие от размещения с повторениями, в этом случае элементы множества повторяются не произвольно, а в определенном составе: 2 раза буква м и 2 раза буква а.

            Рассмотрим общий случай. Пусть составлена упорядоченная выборка длины m из элементов множества . Причем элемент  входит в выборку раз, элемент  входит в выборку  раз, …, элемент  входит в выборку  раз, ясно, что . Набор чисел  называется составом выборки длины m. В соответствии с данным определением состав слова мама – (2, 2).

Определение 4. Перестановкой с повторениями данного состава  называется упорядоченная выборка с повторениями из  элементов данного множества.

            Таким образом, если характер выборки: 1) упорядоченная; 2) с повторениями данного состава , то выборка является перестановкой из m элементов с повторениями.  Число перестановок с повторений из m элементов данного состава обозначается  , и вычисляется по формуле:

……………………(4)

Задача 7. Сколько чисел можно составить из цифр числа 55121213?

Решение. 1) Из цифр данного числа составляем составлять выборку длины m=8;

2) Так как составляем числа, то выборка упорядоченная. В данном числе есть одинаковые цифры, поэтому выборка будет с повторениями, но не произвольными: цифра 5 повторяется 2 раза, цифра 1 повторяется 3 раза, цифра 2 – 2 раза, цифра 3 – 1 раз, т.е. выборка будет иметь состав (2, 3, 2. 1). Таким образом, каждое составленное число есть размещение длины 8 с повторениями данного состава. Используя формулу (4), получим:

= 1680.

Ответ: можно составить 1680 чисел.

Определение 5. Сочетанием без повторений из m элементов данного n- множества называется любое подмножество из m элементов данного n- множества.

            Таким образом, если характер выборки: 1) неупорядоченная; 2) без повторений, то выборка является сочетанием без повторений.  Число сочетаний без повторений из m элементов данного n- множества обозначается  , и вычисляется по формуле:

=   ………………………………(5)

Задача 8.  Сколько различных хорд можно провести через 6 точек, лежащих на данной окружности? 

Решение. 1) Будем выбирать из множества, состоящего из n = 6 элементов.

2) Хорда определяется двумя точками, поэтому будем из 6 элементов составлять выборку длиной m = 2.

3) Определим характер выборки: порядок выбора точек для построения каждой хорды не имеет значения, поэтому имеем неупорядоченную выборку; так как одну и туже точку в выборку из двух точек брать нельзя (т.к. через одну прямую проходит множество прямых), то выборка  –  без повторений. Таким образом, имеем сочетание без повторений.

4)      По формуле (5) находим: = =15.

Ответ: через 6 точек, лежащих на окружности можно провести 15 хорд.

Определение 6. Сочетанием с повторениями называется неупорядоченная выборка с повторениями из m элементов данного n- множества.

Таким образом, если характер выборки: 1) неупорядоченная; 2) с повторениями, то выборка является сочетанием с повторениями.  Число сочетаний с повторениями из m элементов данного n- множества обозначается  , и вычисляется по формуле:  

                   ………………………………(6)

Задача 9. В кондитерском магазине продаются пирожные 4 сортов: наполеоны, песочные, эклеры и слоёные. Сколькими способами можно купить 7 пирожных?

Решение. 1) Множество из которого будем выбирать – это множество пирожных 4 видов, т.е. число элементов в множестве из которого выбираем n = 4.

2) Так как надо купить 7 пирожных , то длина выборки m = 7.

3) Определим характер выборки: при покупке пирожных неважно, в каком порядке мы их будем выбирать, т.е. выборка неупорядоченная; так как мы составляем всевозможные наборы пирожных, то среди таких наборов будут и наборы, где есть одинаковые пирожные, поэтому выборка с повторениями.

4) По характеру выборки определяем комбинаторное соединение, в данном случае это сочетания с повторениями. По формуле (6) вычисляем искомое число:

 = =120.

Ответ: существует 120 способов, которыми можно купить 7 пирожных.

Как видно из определений (1) – (6) классификация комбинаторных соединений ведётся по характеру выборки, поэтому при решении конкретной задачи очень важно определить характер выборки. Задачи, которые были разобраны после каждого определения комбинаторного соединения решались по единому алгоритму, приведем этот алгоритм в общем виде:

1)                              Определить множество, из которого производится выборка и число элементов n в этом множестве.

2)                              Определить выборку и число элементов m в выборке.

3)                              Определить характер выборки.

4)                              По характеру выборки определить, с каким комбинаторным соединением мы имеем дело, и выбрать формулу для вычисления.

5)                              По выбранной формуле произвести вычисления.

Однако есть задачи, для которых этот алгоритм решения не подходит. Например:

Задача 10.  На прямой взято 5 точек, а на параллельной ей прямой взято 3 точки. Сколько существует различных треугольников, вершинами которых являются эти точки?

            Прежде чем переходить к решению этой задачи попробуем составить алгоритм решения задач такого типа. Первое, что надо заметить это то, что выбирать нам придется из двух множеств: из множества точек первой прямой и из множества точек второй прямой. Таким образом, эту задачу можно разбить на более простые задачи, в каждой из которых выбор происходит из одного множества, причем каждую такую задачу можно решить по приведённому выше алгоритму. После решения этих задач мы будем знать, сколькими способами можно выбрать элемент из каждого множества. Далее, чтобы ответить на первоначальный вопрос задачи, нужно определить по какому принципу выбираются элементы этих множеств: сначала элемент из первого множества, и после каждого такого выбора элемент из второго множества, причем нужно выбрать оба элемента или нужно выбрать из двух элементов только один, т.е. нужно определить какой комбинаторный принцип (ПрΣ или ПрП) нужно применить, для ответа на вопрос задачи.

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

            Алгоритм решения сложной комбинаторной задачи.

1.      По условию задачи определить сложную или простую задачу мы имеем.

2.      Разбить сложную комбинаторную задачу на несколько простых задач.

3.      Решить каждую простую задачу по приведенному выше алгоритму.

4.      Определить какой комбинаторный принцип нужно применить в этой задаче:

-          если выбираем несколько элементов по принципу «сначала… потом…», то необходимо применить ПрП;

-          если выбираем один элемент из нескольких по принципу или первый или второй или …, то применяем ПрΣ.

5.      В соответствии с выбранным принципом проводим вычисления.

Теперь вернемся к решению задачи 10.

Решение (задача 10). 1) Так как в задаче дано два множества: первое – множество точек, лежащих на  первой прямой, второе – множество точек, лежащих на второй прямой, то мы имеем дело со сложной комбинаторной задачей.

2) Разобьем эту задачу на две простых. Для того чтобы составить треугольник необходимо взять три точки. На одной прямой все три точки взять нельзя, т.к. треугольника не получится, хотя бы одно точка должна лежать на другой прямой. Таким образом нужно решить две задачи:

1. Сколькими способами можно выбрать две точки из 5, лежащих на первой прямой и сколькими способами можно выбрать одну точку из 3, лежащих на второй прямой?

            2. Сколькими способами можно выбрать одну точку из 5, лежащих на первой прямой и сколькими способами можно выбрать две точки из 3, лежащих на второй прямой?

3) Решим каждую сформулированную задачу:

            1. 1) Так как в задаче опять речь идет о выборе из двух множеств, то это задача сложная. Разобьем её на две задачи и решим каждую из них:

1.1. Сколькими способами можно выбрать две точки из 5, лежащих на прямой?

            1.2. Сколькими способами можно выбрать одну точку из 3, лежащих на прямой?

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

1.1.     1) Число элементов в множестве, из которого выбираем n = 5.

2) Число элементов в выборке m = 2.

3) Характер выборки: 1) неупорядоченная (т.к. для составления треугольника неважно в каком порядке будут выбраны точки), 2) без повторений (т.к. одну и туже точку два раза выбирать нельзя)

4) Каждая пара точек является сочетанием без повторений.

5) 10.

1.2.      Так как из множества 3 точек выбираем одну, то это можно сделать 3 способами.

2) Определим принцип, который используется в задаче 1. Так как мы выбираем точки по принципу сначала 2, а потом ещё одну, то для решения этой задачи применим принцип произведения, т.е. перемножим результаты, полученные в задачах 1.1. и 1.2. Получим: 10*3=30.

2. Задачу 2 решим аналогичным образом, в результате получим: 3*5=15.

4) Теперь определим принцип, который нужно применить в первоначальной задаче. Так как вершины треугольников можно выбрать или способом, описанным в задаче 1, или способом, описанным в задача 2, то для того, чтобы посчитать число способов таких выборов воспользуемся принципом суммы. Применяя ПрΣ, получим:   30 + 15 = 45.

Ответ: существует 45 различных треугольников.

Контрольные задания

            Представленные ниже задачи являются контрольным заданием для учащихся 9 классов. Решения необходимо оформить в отдельной тетради и выслать по адресу 680000, г. Хабаровск, ул. Дзержинского, 48, ХКЦТТ, ХКЗФМШ. Для зачета нужно набрать не менее 21 балла (каждая правильно решенная задача оценивается в 3 балла)

М 9.1.1. Сколькими способами можно разместить 5 человек за столом, на котором поставлено 5 приборов?

М 9.1.2. Некто забыл последние 4 цифры телефонного номера, помнит только, что все цифры разные и среди них есть 9. Какое максимальное число номеров ему придется набрать, если он попытается дозвониться до абонента?

М 9.1.3. В цветочном магазине продаются цветы 6 сортов. Сколько можно составить различных букетов из 7 цветов в каждом?

М 9.1.4. Имеется 25 российских и 15 зарубежных марок. Сколькими способами можно выбрать 3 российские и 2 зарубежные марки?

М 9.1.5. Сколько различных слов можно составить из букв слова колокол?

М 9.1.6. Сколько различных автомобильных номеров можно составить из 28 букв и 10 цифр, если каждый номер состоит из 3 букв и 3 цифр?

М 9.1.7. Из группы, состоящей из 7 юношей и 4 девушек надо выбрать 6 человек так, так, чтобы среди них было не менее 2 девушек. Сколькими способами это может быть сделано?

М 9.1.8. У Ивана 7 книг по математике, а у Дмитрия – 9 книг. Сколькими способами они могут обменять 3 книги одного на три книги другого?

М 9.1.9. Сколько словарей надо издать, чтобы можно было непосредственно выполнять переводы с любого из 5 языков: русского, английского, французского, немецкого и итальянского, на любой другой из этих 5 языков?

М 9.1.10. Сколькими способами могут выпасть три игральные кости? Во скольких случаях хотя бы одна кость откроется на 6 очках? Во скольких случаях ровно одна кость откроется на 6 очках? Во скольких случаях одна кость откроется на 6 очках, а одна – на 3 очках?