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

МБОУ «Комсомольская СОШ № 2» Исследовательская работа на тему: «Элементы комбинаторики».                                                                                                                                                                                          Составила: учитель математьики и физики                                                                                    Совина  Нина Георгиевна. с. Комсомольское  2019 Содержание 1. Введение…………………………………………………………………………………………………3 2. Комбинаторика – самостоятельная ветвь математики…………………………………………..4 2.1.  Решение комбинаторных задач……………………………………………………………………4 3.  Элементы комбинаторики…………………………………………………………………………...5 3. 1.  Перестановки………………………………………………………………………………………..5 3. 2.  Правило сложения………………………………………………………………………………….6 3. 3.  Правило умножения………………………………………………………………………………..6 3. 4.  Размещения……………………………………………………………………………………. …...6 3. 5.  Сочетания……………………………………………………………………………………………7 4.  Заключение…………………………………………………………………………………………...10 5.  Список использованных источников и литературы……………………………………………11 6. Приложение…………………………………………………………………………………………...12 2 Введение В науке и практике часто встречаются задачи, решая которые приходится составлять различные комбинации из конечного числа элементов и подсчитать число комбинаций.  И в  повседневной жизни нередко перед нами возникают проблемы, которые имеют не одно, а несколько   различных   вариантов   решения.   Чтобы   сделать   правильный   выбор,   очень   важно   не уступить ни одной из них. Для этого нужно осуществлять перебор всех возможных вариантов или хотя бы подсчитать их число.  Задачи,   в   которых   идет   речь   о   тех   или   иных   комбинациях   объектов,   называются комбинаторными.  Область математики,  в которой изучаются  комбинаторные задачи, называется комбинаторикой. Сегодня комбинаторика приобрела широкое значение в связи с развитием теории вероятностей, математической логики, информационных технологий.  За последние годы комбинаторика переживает период бурного развития, связанного с общим повышением интереса к проблемам дискретной математики. Комбинаторные методы используются для решения транспортных задач, в частности задач по составлению расписаний; для составления планов   производства   и   реализации   продукции.   Установлены   связи   между   комбинаторикой   и задачами линейного программирования. В настоящее время комбинаторика является одним из важных разделов математической науки. Ее методы широко используются для решения практических и теоретических задач.  Цели и задачи работы: получение представления о комбинаторике – как самостоятельной ветви математики,   комбинаторных   задачах,  знакомство     с  перестановкой,   размещением  и   сочетанием, развитие вычислительных формул, развитие математического мышления. 3 Комбинаторика – самостоятельная ветвь математики. «Число, положение и комбинаторика – три взаимно пересекающиеся, но различные сферы мысли, к которым можно отнести все математические идеи» Джозеф Сильвестр (1844 г.) Комбинаторика   (от   лат.   слова   combinare   –   «соединять,   сочетать»)   ­     раздел   математики,   в котором изучаются вопросы о том, сколько различных комбинаций, подчинённых тем или иным условиям,   можно   составить   из   заданных   объектов.   Термин   «комбинаторика»   был   введён   в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».  Комбинаторные задачи – это задачи выбора и расположения элементов конечного множества, имеющие   в   качестве   исходной   некоторою   формулировку   развлекательного   содержания   типа головоломок.  Особенность комбинаторных задач – вопрос начинается со слов «Сколькими способами…» или «Сколько вариантов…». Решение комбинаторных задач.  Задача 1.  Сколько двузначных чисел можно составить, используя цифры 1, 4 и 7?     4 Схема, изображенная выше, называется дерево возможных вариантов, с помощью которого мы нашли все возможные варианты двузначных  чисел. Элементы комбинаторики. 1. Перестановки. Простейшими   комбинациями,   которые   можно   составить   из   конечного   множества,   являются перестановки.   Рассмотрим   пример.     Допустим,     у   Ольги   имеется   3   бусины   разных   цветов. Обозначим их буквами, соответствующими цвету:  К­красные, З­зеленые, С­синие. Эти бусины на ниточке можно расположить по­разному. Если первой расположить бусину К, то возможны такие расположения бусин:  КСЗ, КЗС. Если первой нанизать бусину С, то возможными являются такие расположения: И, наконец, если первой расположить бусину З, то получим расположения: СЗК, СКЗ. ЗКС, ЗСК Каждое из этих расположений называю перестановкой из трех элементов. Перестановкой из n элементов называется каждое расположение этих элементов в определенном порядке. Число перестановок из n элементов  обозначают символом Рn (читается «Р из n»). В рассмотренном примере мы установили, что Р3=6. Выведем формулу числа перестановок из n элементов. Пусть мы имеем b элементов. На первое место можно   поставить любой из них. Для каждого выбора первого элемента   на второе место можно поставить  один из оставшихся n­1 элементов. Для каждого  выбора первых двух элементов 5 на третье место можно поставить  один из оставшихся n­2 элементов и т.д. В результате получим, что    Для   произведения   первых   n   натуральных   чисел   используют   специальное   обозначение:   n! Рn=n(n­1)(n­2)*…*3*2*1 (читается «n факториал»). Например, 8!=1*2*3*4*5*6*7*8=40320 Таким образом, число всевозможных перестановок из n элементов вычисляется по формуле: Рn=n! Задача 1.   Басня Крылова «Квартет» Проказница Мартышка,  Осёл, Козёл, Да косолапый Мишка Затеяли играть квартет… … Стой, братцы стой! –  Кричит Мартышка, ­ погодите! Как музыке идти? Ведь вы не так сидите… И так, и этак пересаживались – опять музыка на лад не идет. Вот пуще прежнего пошли у них разборы И споры, Кому и как сидеть… Сколькими способами можно рассадить четырех музыкантов? Решение:   n=4,   поэтому   способы     рассаживания   четырех   музыкантов   вычисляем   по формуле: Р4 = 4! = 1*2*3*4=24. Правило сложения. Пример. Сколько различных четырехзначных  чисел, в которых цифры не повторяются, можно составить из цифр 0, 1, 2, 3? 6 Решение: из данных цифр можно получить 4 перестановки (Р4) перестановок. Из этого числа надо исключить перестановки, начинающиеся с 0. А число таких перестановок равно трем   (Р3). Значит, искомое число четырехзначных чисел, которые можно составить из цифр 0, 1, 2, 3, равно Р4­Р3. Р4 ­ Р3 = 4! – 3! = 24 – 6 = 18. Ответ: 18 чисел. Правило умножения. Пример. Имеется 9 различных карандашей, четыре из них – простые. Сколькими способами можно расположить эти карандаши в пенале, чтобы  простые карандаши лежали рядом? Решение:   сначала   рассмотрим   простые   карандаши   как   один   карандаш.   Тогда   в   пеналенадо расставит не 9, а 6 книг. Это можно сделать 6 способами (Р6). В каждой из полученных комбинаций можно   выполнить     4   (Р4)   перестановки   простых   карандашей.   Значит,   искомое   число   способов расположения карандашей в пенале равно произведению Р4 и Р6.  Р4 * Р6 = 6! * 4! = 720 * 24 = 17280 2. Размещения. Пусть имеется 4 кубика и 3 пустых ячейки. Обозначим кубики   цифрами 1, 2, 3, 4. в пустые ячейки можно   по­разному разместить три кубика из этого набора. Если мы поместим кубик 1 в первую   ячейку,   кубик   2   во   вторую   ячейку,   а   кубик     3   в   третью   ячейку,   то   получим   одну   из возможных комбинаций. 1 1 2 2 3 Выбирая по­разному первый, второй, и третий кубик, получим разные тройки шаров, например: 3 3 2 1 3 2 2 1 1 3 Каждую упорядоченную тройку, которую можно составить из 4 элементов, называют  размещением из 4 элементов по 3. Размещением из n элементов по k (k<=n) называется любое множество, состоящее из любых k   элементов, взятых в определенном порядке из данных n элементов. Число размещений из n элементов по k обозначают (читают: «А из n по k»). Для вычисления числа размещений из n элементов по k вывели формулу: А = n(n­1)(n­2)*…*(n­(k­1)) Размещения из   n элементов по n отличаются друг от друга. Для этого случая есть другая формула: 7 А  = n(n­1)(n­2)*…*( n(n­1)), т. е. А  = 1 * 2*…* (n­2)(n­1)n Т. е. мы пришли  к уже известной формуле числа перестановок Рn = n! 3. Сочетания.  Пусть имеется пять гвоздик разного цвета.     1      2  3  4 5   Требуется создать букет из трех гвоздик. Выясним, какие букеты могут быть составлены. Если в букет входит гвоздика 1, то можно составить такие букеты: ,     ,    ,        ,      Если в букет не входит гвоздика 1, и входит гвоздика 2, то получим такое: Если в букет не входит ни 1, ни 2, то возможен только этот вариант:  ,     .      Мы указали все возможные способы составления букетов, в которых по­разному сочетаются 3 гвоздики из данных 5. говорят, что мы составили все возможные сочетания из 5 элементов по 3. Сочетанием из n  элементов по  k называется любое множество, составленное из k элементов, выбранных из данных n элементов. Число сочетаний из n элементов по k  обозначают  С  (читают « С из n по k»). В рассмотренном примере, составив все сочетания из 5 элементов по 3, мы нашли, что С   8 Выведем формулу числа сочетаний  из n  элементов по k, где k<=n.  Отсюда Тогда Отсюда хPС 3 3 5  3 A 5 С  3 5 3 A 5 P 3 A  k n хPC K k n C  k n n A n P k Мы получили формулу: nn (  )(1 С k n   n nхх ( )2 ... ххх 321 хk ...  ( k  ))1 Формулу числа сочетаний   можно записать в другом виде. Умножим числитель и знаменатель дроби на (n­k)!, где n=k. Получим:   )2 n ( nхх ... ххх ( 321 хkх ... nn C k n )(1  (  kn  )!  ( kn k  ))(1 )! Задача 1.   Из фазы с фруктами, в которой лежит 9 яблок, 6 груш, надо выбрать 2 груши  и  3 яблока. Сколькими способами можно сделать такой выбор? Решение: Выбрать 3 яблока из 9 можно С  способами, а выбрать 2 груши из 6   можно С  способами. Так как при каждом выборе яблок груши можно выбрать  С  способами, то сделать  выбор фруктов, о котором говорится в задаче,  можно  С  * С  способами. Тогда:  хСС 3 9 2 6  789 321 хх хх х 56 х 21 х  1260 Значит, указанный набор фруктов можно сделать  1260 способами.  Задача 2. Из кружка юных математиков, состоящих из 15 человек, надо выбрать 3 учащихся для участия в математическом КВНе. Сколькими способами можно сделать выбор? 9 Каждый выбор отличается, от другого хотя бы одним учащимся. Значит, в данном случае, речь идет о сочетаниях из 15 элементов по 3. Имеем:  C 3 15  !15 х !12!3  13 14 х 15 х 321 хх  455 Следовательно, трех учащихся можно выбрать 455 способами. Задача 3. Несколько стран в качестве символа своего государства решили использовать флаг в виде трёх горизонтальных полос одинаковых по ширине, но разных по цвету: белый, синий, красный. Сколько   стран   могут   использовать   такую   символику,   при   условии,   что   у   каждой   страны   свой отличный от других стран флаг? Решим с помощью дерева всех возможных вариантов (См. Приложение 1). Как видно по рисунку 1,  6 стран могут иметь такую символику, отличную от других. Ответ: 6 стран. Заключение. Рассмотрев простейшие комбинаторные задачи, можно прийти к выводу, что комбинаторика часто встречается и в нашей повседневной жизни, а не только на уроках математики. Встречается и в литературе, и в столовой, когда перед нами стоит выбор: что? и с чем? Заказывать. Мы пришли к выводу,   что   комбинаторные   задачи   являются   своего   рода   головоломками,   которые   развивают логическое и математическое мышление. Конечно же,  с комбинаторными задачами мы встречались и ранее, решали их без специальных формул, размышляя логически. А теперь с помощью формул, приведенных выше, я думаю, что если вы встретите задачи данного типа, то  решите их  намного быстрее и легче. 10 Список использованных источников и литературы: 1. http://combinatorica.narod.ru/second.htm 2. http://www.bestreferat.ru/referat­198511.html 3. http://combinatoric.ru.gg/ 4. Еженедельное учебно­методическое приложение к газете «Первое сентября». Математика. № 21, 1997. 5. Еженедельное учебно­методическое приложение к газете «Первое сентября». Математика. № 2, 1997. 6. Макарычев Ю.Н.,   .Миндюк Н.Г, Нешков К.И., С.Б.Суворова.   Алгебра. 9 класс: учеб. для общеобразоват. учреждений – 18­е изд.  – М.: Просвещение, 2011. – 271 с. 7. Макарычев Ю.Н. Алгебра: элементы статистики и теории вероятности: учеб. Пособие для учащихся 7­9 кл. общеобразоват. учреждений / Ю.Н. Макарычев, Н.Г.Миндюк. – 4­е изд.   – М.: Просвещение, 2006. – 78 с. 11 Приложение  12 Рисунок 1. 13