Основные элементы комбинаторики

Размещено на http://www.allbest.ru/

Лекция

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

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

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

Этот раздел математики тесно связан с рядом других разделов математики: теорией вероятностей, теорией графов, теорией чисел, теорией групп и т. д. .

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

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

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

Из Китая к нам пришла интересная комбинаторная головоломка танграм. Квадрат разрезают на 7 частей. В результате пулучается 2 больших, 1 средний и 2 маленьких треугольника, квадрат и параллелограмм. Из полученных фигур складывают различные силуэты,

,

что тоже требует комбинаторных навыков.

Комбинаторика развивалась и в Древней Греции. Хотя говорить об уровне комбинаторных знаний древних греков затруднительно, поскольку Александрийская библиотека, в которой были собраны большинство научных книг - практически все научное наследие того времени, насчитывающее много тысяч томов, погибла при взятии Александрии. И мы можем только догадываться о содержании тех книг по кратким пересказам и намекам в сохранившихся рукописях. По этим намекам все же можно судить о том, что определенные представления о комбинаторике у греческих ученых все же были. Аристотель описал без пропусков все виды трехчленных силлологизмов, а его ученик Аристоксен из Тарента перечислил все возможные комбинации длинных и коротких слогов в стихотворных размерах. Живший в 4 в. н.э. математик Папп рассматривал число пар и троек, которые можно получить из трех элементов, допуская их повторения.

По мнению Гиппарха, из 10 утверждающих аксиом можно составить 103049 сочетаний, а добавив к ним отрицающие, 310 952. Приводимые Гиппархом числа слишком точны, чтобы считать их результатом грубой оценки. По видимому, у древних греков все таки были какие то правила комбинаторных расчетов.

Комбинаторикой занимались также кабаллисты и мистики. Большое развитие получили различные числовые суеверия и толкования, связанные с заменой букв соответствующими цифрами. Были ученые, называвшиеся кабаллистами, которые подвергали такому анализу слова Библии и других священных писаний и делали на основе своих изысканий пророчества о будущем мира. Во время богословских споров, начавшихся после победы христианства, старались получить из имен еретиков число 666 - ведь по Апокалипсису это было число зверя, символ антихриста. В романе Л.Н. Толстого «Война и мир» Пьер Безухов пытался вывести это число из имени Наполеона Бонапарта. Такого рода исследования при всей своей бесплодности давали толчок к дальнейшему развитию комбинаторики. Наряду с кабаллистами и мистиками комбинаторикой занимались астрологи.

Их интересовал вопрос о движении планет и их влиянии на судьбы людей. Особое значение они придавали сочетаниям планет - встречам различных планет в одном знаке Зодиака. Астролог бен Эзра в 1140 г. рассчитал количество сочетаний семи планет по две, по три и т.п. Он знал, что число сочетаний планет по две равно числу их сочетаний по пять,а число их сочетаний по три равно числу их сочетаний по четыре. Окончательную формулу для подсчета числа сочетаний вывел математик Гершон, живший в начале 14 в. Однако его работа, написанная на малодоступном большинству ученых древнееврейском языке, осталась почти незамеченной. Вновь эту формулу вывел в начале 17в. Французский математик Эригон.

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

Значительный толчок к развитию комбинаторики дали азартные игры, существовавшие еще в глубокой древности, но получившие свое распространение после крестовых походов. Наибольшее распространение получила игра в кости - два или три кубика с нанесенными на них очками выбрасывали на стол, и ставку брал выбросивший большую сумму очков игрок. В кости играли повсюду, выигрывая и проигрывая в них золото, замки, драгоценные камни и лошадей. Атос - один из героев «Трех мушкетеров» - умудрился проиграть в кости даже своего слугу Гримо. Несмотря на запреты церкви, игроки неустанно упражнялись в выбрасывании костей. И они заметили, что некоторые суммы выпадали редко, а другие чаще. Пытаясь понять. В чем дело, составляли таблицы, показывающие сколькими способами можно получить то или иное число очков. На первых порах иногда допускалась ошибка - подсчитывали лишь число различных сочетаний костей, дававших данную сумму. Например, при бросании двух костей сумма 6 получается из сочетаний (1,5),(2,4),(3,3), а сумма 7 - из сочетаний (1,6),(2,5),(3,4). Так как в обоих случаях получается три различных сочетания с данной суммой, то можно сделать ошибочный вывод, что суммы очков 6,7 и 8 (также получаемая из сочетаний трех костей) должны выпадать одинаково часто. Но это противоречит опыту - 7 очков выпадает чаще. Дело в том, что при бросании двух костей сочетание (3,3) может быть получено единственным способом, а сочетание (3,4)-двумя способами. Этим объясняется большая частота выпадения суммы 7.

Таким образом, оказалось, что надо учитывать не только сочетания очков, но и их порядок. Более сложными оказались исследования для трех костей. Здесь при учете порядка костей оказывается 216 различных комбинаций, а без учета порядка 56. Этими вопросами занимались такие известные итальянские математики 16 в. Как Кардано, Тарталья и др. Наиболее полно исследовал этот вопрос Галилео Галилей в 17 в.

Вопросами комбинаторики занимались Паскаль, Ферма, Лейбниц, Гиденбург.

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

Навыки в разгадке шифров помогли ученым, когда археологи стали откапывать камни и черепки с таинственными знаками - письменностью замолкшей несколько тысячелетий тому назад. Археологи подвергали тексты комбинаторному анализу. И лишь Шампольону - ученому, сочетавшему незаурядный комбинаторный дар с глубочайшим знанием филологии , удалось прочесть иероглифы. Сложность задачи заключалась в том, что Шампольону не были известны ни язык надписей, ни смысл знаков. Однако, выделив знаки, которые в греческом тексте обозначали имена царей, Шампольон обнаружил, что некоторые знаки, которые в греческом тексте обозначали имена царей и некоторые знаки в именах фараонов Птолемея и Клеопатры совпадают. Так были найдены звучания иероглифов, означающих буквы «п» и «л». Затем Шампольон прочел имена римских императоров Тиберия и Траяна, древних фараонов Рамсеса и Тутмоса - ключ к чтению иероглифов, утерянный несколько тысячелетий тому назад, был вновь обретен. Это было торжество комбинаторного метода в чтении забытых письменностей, основанных на наблюдениях над текстом, на сопоставлении повторяемости комбинаций слов и грамматических форм с соображениями, связанными с назначением надписи, временем и условиями ее составления.

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

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

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

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

Немного найдется дней в истории науки, сравнимых по своему значению с 17 февраля 1869г. В этот день из хаоса химических элементов, каждый из которых имел свои свойства, возникла стройная таблица - был открыт периодический закон. Это открытие было сделано Д.И. Менделеевым, профессором Петербургского университета. Готовя курс лекций по общей химии, он задумался над порядком в котором следовало рассказывать об элементах. Менделеев попробовал группировать друг с другом не только похожие элементы, но и попробовал расположить в правильном порядке и сами группы. Он стал подбирать, написав на отдельных- карточках элементы с их атомными весами и коренными свойствами, сходные элементы и близкие атомные веса. Раскладывая свой химический пасьянс, великий ученый после напряженных измышлений нашел правильное расположение элементов. Говорят, что окончательная форма таблицы пришла к нему во сне, когда, утомленный непрерывным обдумыванием ее, он прилег отдохнуть. Удивительно, что эта работа, имевшая неисчислимые последствия для развития химии и физики, была выполнена Менделеевым за один день - 17 февраля 1869г.

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

В качестве резюме хотелось бы перечислить некоторые области применения комбинаторики:

в производстве это распределение видов работ между рабочими; в агротехнике - размещение посевов на нескольких полях; в учебных заведениях это составление расписаний; в химии - анализ возможных связей между химическими элементами; в лингвистике это рассмотрение вариантов комбинаций букв; для азартных игр это подсчёт частоты выигрышей; в экономике - анализ вариантов купли-продажи акций; в криптографии это разработка методов шифрования; при доставке почты это рассмотрение вариантов пересылки; в спортивных соревнованиях - расчёт количества игр между участниками; в биологии - расшифровка кода ДНК; в военном деле -расположение подразделений; в астрологии -анализ расположения планет и созвездий. Как видите, комбинаторика необходима практически во всех областях нашей жизни. Область применения комбинаторных методов настолько велика, что даже перечисление всех возможных мест использования комбинаторного языка является нереальным

Материалы для Исторической справки взяты из книги Н.Я. Виленкина «Популярная комбинаторика» Изд. «Наука» Москва 1975 г.

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

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

Основные правила комбинаторики.

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

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

Правило суммы: Если элемент а1 может быть выбран n1 способом, элемент а2 может быть выбран другими n2 способами, элемент а3 может быть выбран отличными от первых двух n3 способами и т.д., элемент аk - nk способами, отличными от первых (k-1) способа, то выбор одного из элементов: или а1, или а2,…, или ак может быть осуществлен n1+n2+…+nk способами.

Примеры 1.2.1.

1. В ящике 300 деталей. Известно, что 180 из них - 1-го сорта, 100 - 2 -го сорта, а остальные - 3-го сорта. Сколько существует способов извлечения из ящика детали 1-го или 2-го сорта?

Решение. Деталь первого сорта может быть извлечена n1=180 способами, 2-го сорта - n2=100 способами. По правилу суммы существует n1+n2=280 способов извлечения из ящика детали 1-го или 2-го сорта.

2. В корзине 12 роз, 13 пионов и 23 гвоздики. Сколькими способами можно выбрать один цветок из корзины?

Решение. Роза может быть извлечена n1=12 способами, пион - n2=13 способами, а гвоздика - n3=23 способами. По правилу суммы существует n1+n2+ n3=48 способов, которыми можно выбрать один цветок из корзины.

Правило произведения: Если элемент а1 может быть выбран n1 способом, после каждого такого выбора элемент а2 может быть выбран n2 способами, и т.д., элемент аk - nk способами, то выбор всех элементов а1,а2,…, ак может быть осуществлен n1n2…nk способами.

Примеры 1.2.2.

а) при подбрасывании трёх монет возможно 2 · 2 · 2=8 различных результата

б) бросая дважды игральную кость, получим 6 · 6=36 различных результатов

в) трёхзначных чисел бывает 9 · 10 · 10 = 900;

г) трёхзначных чисел, все цифры которых различны, существует 9 · 9 · 8;

д) чётных трёхзначных чисел возможно 9 · 10 · 5;

Пример 1.2.3.

В группе 24 человека. Необходимо выбрать старосту, его заместителя и профорга. Сколько существует способов это сделать?

Решение. Старостой может быть выбран любой из 24 учащихся, его заместителем - любой из 23 оставшихся , а профоргом - любой из оставшихся 22 учащихся, т.е. n1=24 , n2=23, а n3=22 . По правилу произведения общее число способов выбора старосты, его заместителя и профорга равно n1n2n3=24 2322=12 144 способов.

Главная теорема комбинаторики

Теорема о включениях и исключениях

На предприятии работает 70 человек. Из них 50 знают английский, 35 - немецкий и 25 - оба языка. Сколько человек не знают ни английского, ни немецкого?

Решение:Построим диаграмму, на которой изобразим прямоугольник, соответствующий общему числу работающих (70) и две пересекающиеся области A и B по 50 и 35 человек ( знающих английский и немецкий языки). На диаграмме общая часть этих двух областей соответствует 25 - количеству работающих, которые знают оба языка. Требуется найти область прямоугольника, не входящую ни в область A, ни в область B.

Очевидно, что N = 70 - 50 - 35 + 25 = 10.

Главная теорема комбинаторики (Теорема о включениях и ис- ключениях) Пусть имеется множество из N объектов произвольной природы. На этом множестве пусть задано n свойств. Каждый объект может обладать либо не обладать некоторыми из этих свойств. Сами свойства обозначим: . Будем обозначать N( ) - количество объектов точно обладающих свойством и может быть какими-то другими, а N () - число объектов не обладающих ни свойством , ни свойством . Тогда число объектов, не обладающих ни одним из перечисленных свойств:

Продолжение примера. Пусть теперь 21 человек знают французский, 12 - английский и французский, 10 - английский и немецкий и 5 - все три языка. Тогда в соответствии с теоремой количество человек, не знающих ни одного из трех перечисленных языков (но может быть знающих китайский язык), равно N = 70 - 50 - 35 - 21 + 25 + 12 + 10 - 5 = 6.

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

Определение: Перестановки - это выборки (комбинации), состоящие из n элементов и отличающиеся друг от друга порядком следования элементов. Число перестановок из n элементов обозначается символом Pn («пэ из эн») и вычисляется по формуле

Рn = n! ,

где n! - произведение n(n - 1)(n - 2)(n - 3)…3*2*1.

Доказательство: У нас есть n способов выбрать (взять и поставить в ряд) первый предмет (назовем это первым этапом выбора). Далее у нас есть, независимо от того, как выбран первый предмет, n-1 способов взять второй предмет - в любом случае, это может быть какой угодно предмет, кроме первого выбранного. Затем есть n-2 способа взять третий предмет - он может быть какой угодно, кроме первых двух выбранных... и так далее. Итого, мы имеет n этапов выбора, на каждом из которых число вариантов равно (независимо от того, как сделан выбор на предыдущих этапах), соответственно, n, n-1, n-2,..., 1. Поэтому, согласно правилу произведения, мы получаем общее число перестановок из n элементов n(n - 1)(n - 2)(n - 3)…3*2*1., ч.т.д.

Комбинаторный смысл числа перестановок прост : сколькими способами можно упорядочить конечное n-элементное множество.

Примеры 1.4.1.

1.Сколько перестановок можно составить из 2-х-элементного множества? Р2= 2!=2. Действительно, существует две такие перестановки: (a,b), (b,a).

Из трехэлементного множества можно составить Р3=3!=6 перестановок: (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a).

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

Искомое число способов равно числу перестановок из 5 элементов, т.е. Р5=5!=120. Определение: Если в перестановке из общего числа элементов n есть к различных элементов, при этом 1-й элемент повторяется n1 раз, 2-й элемент повторяется n2 раз, k-й элемент - nk раз, причем n1+n2+…+nk=n, то такие перестановки называются перестановками с повторениями из n элементов. Число перестановок с повторениями из n элементов равно



Примеры 1.4.2.

1.Сколько существует пятизначных чисел, состоящих из цифр 7,8,9, в которых цифра 8 повторяется 3 раза, а цифры 7 и 9 по одному разу.

Решение. Каждое пятизначное число отличается от другого порядком следования цифр, причем n1=1 , n2=3, а n3=1, а их количество равна 5, т.е. является перестановкой с повторениями из 5 элементов. Их число находим по формуле (3) .

2. На карточках написаны буквы М,А,Т,Е,М,А,Т,И,К,А. Сколько различных 10-ти буквенных «слов» можно составить из этих карточек? (здесь и далее словом считается любая последовательность букв русского алфавита)

Решение. Перестановка двух букв М, осуществляемая Р2= 2 способами, трех букв А, осуществляемая Р3= 3!=6 способами и перестановка двух букв Т, осуществляемая Р2= 2 способами не меняет составленное из карточек слово. слов.

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

В строчку можно разместить 3 различных элемента 6-ю различными способами - их мы рассматривали выше ((a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a)), а по кругу получим только две различных возможности:

a a

b O c c O b

Тождественные перестановки Различные перестановки

c a a a

b O a c O b b O с c O b

Заметим, что n предметов можно переставлять n! способами, но так как

перестановки, отличающиеся поворотом круга, считаются одинаковыми , то поэтому число перестановок по кругу из n элементов равно

Примеры 1.4.3.

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

Решение: Так как всего за круглым столом сидело 7 человек: 6 гостей и сам хозяин, то число перестановок равно =720. Т.е. 720 совместных ужинов.

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

Решение: Если некий человек будет сидеть на постоянном месте, то оставшихся 6 можно размещать как бы в строчку, поэтому число возможностей по прежнему равно 6! = 720.

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

Решение: Найдем сначала число возможностей, при которых два определенных человека будут (“таки да!”) сидеть рядом друг с другом. Их можно считать за одного человека, т.е. нам надо как бы рассадить 6 человек по кругу. Это можно сделать 5! различными способами. Но двое особых людей, кроме того, тоже можно менять местами, поэтому полученное число следует умножить на 2!, всего получим 2!Ч5!. Это есть общее число возможностей разместить по кругу 7 человек, чтобы двое определенных из них всегда сидели рядом. Вычтем полученное число из общего числа возможностей и получим нужное число возможностей: 6! - 2!Ч5! = 720 - 240 = 480.

Размещения.

Определение: Размещениями из n элементов по k элементов будем называть упорядоченные подмножества, состоящие из k элементов, множества , состоящего из n элементов. Число размещений из n элементов по k элементов обозначается (читается "А из n по k").

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

1) Сколькими способами можно выбрать из 15 человек 5 кандидатов и назначить их на 5 различных должностей?

2) Сколькими способами можно из 20 книг отобрать 12 и расставить их в ряд на полке?

В задачах о размещениях полагается k<n. В случае, если k=n, то легко получить

Число размещений из n элементов по k элементов вычисляется по формуле

Доказательство: Для подсчета используем тот же метод, что использовался для подсчета Pn ,только здесь возьмем лишь k предметов. Первый предмет можно выбрать n способами (любой из n данных предметов), второй, при выбранном первом, можно выбрать n-1 способам. Можно продолжать этот процесс до выбора последнего k-го предмета. Этот предмет при выбранных первых k-1 предметов можно выбрать n-(k-1) способами (или n-k+1). Таким образом все k предметов выбираются числом способов, равным n(n-1)(n-2). . . (n-k+1).Что и требовалось доказать.

Примеры 1.5.1.

1. Студенты второго курса изучают 10 различных дисциплин. Определить - сколькими способами можно составить расписание на понедельник, если в понедельник планируется поставить 5 пар?

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

2. Сколько существует различных вариантов выбора 4-х кандидатур из 9-ти специалистов для поездки в 4 различных страны?

Решение: .

Определение: Пусть даны n различных видов предметов, которые можно разместить по k различным местам, причем выбирать предметы можно с повторениями (т.е. можно выбрать несколько предметов одного вида). Такие выборки называются размещениями с повторениями, а их количество вычисляется по формуле:

Примеры 1.5. 2.

1. Среди 15 студентов второго курса проводился конкурс на «Самого умного», «Самого доброго», «Самого смелого» и «Самого умелого». Сколько существует вариантов распределения призов, если по каждой номинации установлены различные призы?

Решение: Каждый из вариантов распределения призов представляет собой комбинацию 4 участников из 15, отличающуюся от других комбинаций как составом номинантов, так и их порядком, причем один и тот же участник может быть номинантом несколько раз. Т.е. мы имеем дело с размещением с повторениями из 15 элементов по 4. Их число находим по формуле (6)

.

Можно было рассуждать иначе: победителем в первой номинации может быть любой из 15 студентов, победителем во второй номинации может быть также любой из 15 студентов, ведь один участник может быть номинантом несколько раз, победителями в третьей и четвертой номинациях опять может быть любой из 15 студентов. Следовательно, общее число вариантов распределения призов существует .

2. Сколько 6-значных чисел можно составить, используя цифры 3,4,5.

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

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

Сочетания.

Определение: Сочетаниями из n элементов по m элементов будем называть любое подмножество, состоящие из m элементов, множества , состоящего из n элементов. Число сочетаний из n элементов по k элементов обозначается (читается "це из эн по ка").

Число сочетаний из n элементов по m вычисляется по формуле

Формула (7) может быть получена следующим образом. Выберем по очереди m предметов из n. Мы это можем сделать способами. Однако нас не интересует в данном случае порядок выбранных предметов. От перестановки этих предметов наш выбор не меняется. Поэтому полученное выражение нужно разделить на m!

Примеры 1.6.1.

1. Из группы 35человек нужно выбрать троих для работы в колхозе. Сколькими способами это можно сделать?

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

2. В середине 60 годов в России появилась лотерея, которая была названы “Спортлото”: лотерея 5/36 . Играющий покупал билет, на котором имелось 36 клеточек. Каждая клеточка соответствовала какому-либо виду спорта. Нужно было выделить (зачеркнуть) 5 из этих клеточек и отправить организаторам лотереи. После розыгрыша лотереи объявлялись пять выигравших номеров. Награждался угадавший все пять номеров, четыре номера и даже угадавший три номера. Соответственно, чем меньше угадано номеров (видов спорта), тем меньше был выигрыш.

Подсчитаем, сколько существует разных способов заполнения карточек “Спортлото” при условии, что используется лотерея 5/36. Казалось бы, заполняя последовательно номер за номером, получим: . Но ведь порядок заполнения не имеет значения, тогда получаем:

.

Данный результат означает, что если все участники лотереи заполняют карточки по-разному, то в среднем один из примерно 377 тысяч человек угадает все 5 номеров.

А сколько человек в среднем угадают 4 номера?

.

Итого, в среднем 155 человек из примерно 377 000 угадают 4 номера.

Определение: сочетания, содержащие m элементов, в которых любой элемент может присутствовать некоторое число раз, не превосходящее m, называются сочетаниями из n элементов по m с повторениями.

Например: соединения {a, a}, {a, b}, {a, c}, {b, b}, {b, c}, {c, c} - сочетания из 3 элементов {a, b, с} по два с повторениями (в соединение могут входить два одинаковых элемента).

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

Примеры 1.6.2.

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

Решение: порядок выбора монет неважен, и примерами соединений могут являться {5,5,5,5}, {2,2,2,2}, {5,2,5,5} и т.д. Это задача о числе сочетаний из двух видов монет по четыре с повторениями.

способов.

2. В кондитерской имеется 5 разных сортов пирожных. Сколькими способами можно выбрать набор из 4 пирожных?

Решение: это задача о числе сочетаний из 5 видов пирожных по 4 с повторениями.

способов

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

Решение: это задача о числе сочетаний из 5 цифр по одному, по два, по три, по четыре и по пяти с повторениями в каждом случае.

; ; ;

;

Согласно правилу сложения: 5+15+35+70+126=251 чисел.

Сходства и различия в определениях сочетаний и размещений.

Сходства. Сочетания и размещения - это подмножества, состоящие из m элементов n-элементного множества. В них имеет значение порядок следования элементов последовательности.

Различия. В размещении важен порядок расположения элементов, а в сочетаниях порядок не важен.

Рассмотрим несколько «параллельных» задач:

Сочетания	Размещения
1. Сколько рукопожатий получится, если здороваются 6 человек? {Дима, Антон} = {Антон, Дима} - одно и тоже Значит, порядок неважен, значит это подмножество по два элемента из 6, значит это сочетание из шести по два	1. Сколькими способами шесть человек могут обменяться фотографиями? { Дима, Антон } { Антон, Дима } - разные обмены Значит, порядок важен, значит это последовательность по два элемента из 6, значит это размещение из шести по два
2. Сколько аккордов можно сыграть с помощью трех клавиш из семи? {до, ми, соль} = { до, соль, ми } - одно и тоже Значит, порядок неважен, значит это подмножество по три элемента из семи, значит это сочетание из семи по три	2. Сколько мелодий (трезвучий, проигрышей) можно сыграть с помощью трех клавиш из семи? {до, ми, соль} { до, соль, ми } - разные мелодии Значит, порядок важен, значит это последовательность по три элемента из семи, значит это размещение из семи по три

Свойства сочетаний. Бином Ньютона.

Предполагая, что n и k - целые положительные числа и 0!=1, сформулируем основные свойства сочетаний.

1.. 2. .

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

.

Что и требовалось доказать.

3. .

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

Что и требовалось доказать.

=.

Свойство №3 позволяет описать процедуру последовательного получения числа сочетаний при различных значениях n и m. Используя это свойство, можно представить число сочетаний в виде так называемого треугольника Паскаля. комбинаторика вычислительный бином ньютон

Тогда треугольник Паскаля имеет вид

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

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

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

Определение: Биномом Ньютона называют разложение вида:

Но, строго говоря, всю формулу нельзя назвать биномом, так как «бином» переводится как «двучлен». Кроме того, формула разложения была известна еще до Ньютона, Исаак Ньютон распространил это разложение на случай n<0 и n - дробного.

Цель изучения бинома Ньютона - упрощение вычислительных действий. Компоненты формулы «бином Ньютона»:

ь правая часть формулы - разложение бинома;

ь - биномиальные коэффициенты, их можно получить с помощью треугольника Паскаля

общий член разложения бинома n-й степени:

,

где Т - член разложения; - порядковый номер члена разложения.

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

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

Альтернатива треугольнику Паскаля:

1) перемножить почленно четыре скобки:

;

2) вспомнить разложение бинома Ньютона четвертой степени:

Историческая справка. В 13 в.н.э. начался расцвет арабской науки. Решая вопрос об извлечении корней любой степени, арабские алгебраисты пришли к формуле для степени суммы двух чисел, известной под исторически неверным названием «бином Ньютона». По видимому эту формулу знал, живший в 11-12 вв. н.э. поэт и математик Омар Хайям. Судя по некоторым источникам, восходящим к арабским оригиналам, для отыскания коэффициентов этой формулы брали число 10001 и возводили его во 2-ю, 3-ю,…, 9-ю степени. Получалась таблица

100090036008401260126008400360009001

100080028005600700056002800080001

10007002100350035002100070001

1000600150020001500060001

10005001001000050001

10004000600040001

1000300030001

100020001

10001

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

Арабские ученые знали и основное свойство этой таблицы, которое выражалось формулами .

Интересовались сочетаниями и в Индии. Еще во 2 в.до н.э. индийцы знали числа и такой факт , что . А в 12 в. Индийский математик Бхаскара написал книгу «Лилавати», в которой среди других вопросов математики изучает и проблемы комбинаторики. Он пишет о применениях перестановок к подсчету вариаций в стихосложении, различных расположений в архитектуре и т.д. Он дает также правила для отыскания числа перестановок и сочетаний нескольких предметов, причем рассматривает также случай, когда в этих перестановках есть повторяющиеся элементы.

Типовые задачи по теме «Бином Ньютона».

1.В биномиальном разложении найти член разложения, не содержащий х.

Решение:

Так как в разложении мы ищем член не содержащий х, то

Тогда .

2. Доказать, что при любом натуральном n число делится на 9

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

Что и требовалось доказать.

3. Решить уравнения

а) ; б).

Решение:a) ; ;

; ;

б) ; ; ;

.

Размещено на Allbest.ru

...