Исследовательская работа"Комбинаторика и её задачи".
Опубликовано Зашкалова Светлана Ивановна.
вкл 29.05.2013 - 11:51
Автор:
Паранина Екатерина, Назарова Арина.
Исследовательская работа "Комбинаторика и её задачи" состоит из трёх информационных блогов. История развития комдинаторики, правила решения комбинаторных задач, комбинаторика в профессиях. Этот материал позволит подробно познакомиться с комбинаторикой как одним из важных разделов математики. Комбинаторика развивает мыслительную деятельность учеников,используя правила и способы решения комбинаторных задач можно быстро справиться с любой задачей связанной с выбором вариантов и комбинаций. Материал можно использовать при изучении нового материала на уроках математики и на дополнительных занятиях по математике.
Скачать:
| Вложение | Размер |
|---|---|
 issled.rab_.rar | 2.88 МБ |
Подписи к слайдам:
Исследовательская работа. Тема: «Комбинаторика и её задачи». Выполнили учащиеся 5 А класса:Назарова АринаПаранина Екатерина.Руководитель:Зашкалова С.И.2011-2012 учебный год.
МБОУ «Илькинская СОШ»
Проблема.Одним из важных и значимых разделов математики является комбинаторика . Обладать «комбинаторным искусством» должен каждый человек. Люди, владеющие техникой решения комбинаторных задач, а следовательно, умеющие рассуждать, перебирать различные варианты решений, часто находят выход, казалось бы, из самой безвыходной ситуации. Чтобы этому научиться, надо заниматься исследовательской деятельностью, то есть изучать, решать, познавать.
Актуальность.Мы на уроках математики впервые встретились с интересными задачами, которые относятся к одному из разделов математики комбинаторике . Комбинаторные задачи могут дать ответ на многие вопросы, связанные с практической деятельностью людей, решение задач помогает развивать умственные способности, логическое мышление, вычислительные навыки . Знание комбинаторики необходимо представителям самых разных специальностей . С комбинаторными задачами приходится иметь дело физикам, лингвистам, специалистам по теории кодов.Изучив историю развития комбинаторики, мы узнаем, как учёные развивали науку, почему дали ей такое название. Всё это необходимо для всестороннего развития личности . Современный человек должен обладать хорошей математической подготовкой, уметь применить свои знания и навыки на практике. С этой целью мы решили узнать больше о комбинаторике и её развитии.
Цель работы: Исследовать комбинаторику, как один из важных разделов математики.Задачи: Изучить историю развития комбинаторики. Исследовать решение комбинаторных задач, связанных с практической деятельностью человека. Показать практическое применение комбинаторики.
История.Комбинаторика - один из разделов математики. Слово комбинаторика происходит от латинского слова combinare, которое означает соединять, сочетать. Она включает в себя задачи, решая которые приходиться составлять различные комбинации из конечного числа элементов и подсчитывать число комбинаций. Такие задачи называются комбинаторными задачами. Например:1.Сколькими способами можно расположить 50 человек в очереди в кассу кино? 2. Сколькими способами могут быть распределены золотая, серебряная и бронзовая медали на чемпионате мира по футболу?
С аналогичными задачами люди столкнулись в глубокой древности . В Древнем Китае увлекались составлением магических квадратов .http://pochemuha.ru/wp-content/uploads/2010/09/kvadrat.jpgМагические квадраты с давних времен являются прекрасным развлечением. Они составляются обычно с одинаковым количеством рядов и колонок и заполняются различными цифрами, следуя трём условиям: 1. Сумма цифр каждого ряда всегда одна и та же. 2. Сумма цифр каждой колонки всегда одна и та же и равна сумме цифр в каждом ряду. 3. Сумма цифр, расположенных по диагонали, равна сумме цифр в каждом ряду и в каждой колонке.
Альбрехт Дюрер (1471-1528) - известный живописец и график немецкого Возрождения. В одну из своих гравюр, "Меланхолию", он включил магический квадрат. Обрати внимание, что, помимо совпадения сумм в рядах, колонках и диагоналях, совпадают также суммы центрального квадрата и каждого из четырёх квадратов, образованных средними линиями.
http://pochemuha.ru/chto-takoe-magicheskij-kvadrat-albrext-dyurer
В Древней Греции подсчитывали число различных комбинаций длинных и коротких слогов в стихотворных размерах, занимались теорией чисел, изучали фигуры, которые можно составить из частей особым образом разрезанного квадрата. Конкретные комбинаторные задачи, касавшиеся перечисления небольших групп предметов , греки решали без ошибок.
В VIII веке до н.э. начался расцвет арабской науки. Арабы перевели многие творения греческих учёных, изучили их, а затем продвинулись вперёд. Они занимались теорией практических вычислений. Комбинаторика возникла в XII веке . В это время Западная Европа начала пробуждаться после многовековой духовной спячки. Развитие торговли с Востоком привело к проникновению в Европу арабской науки. Леонардо, получивший прозвище Фибоначчи, привёл в систему всю арифметику арабов, некоторые сведения Евклида и добавил к ним результаты своих изысканий.
Труд Фибоначчи содержал и новые комбинаторные задачи, например, об отыскании наименьшего количества гирь, с помощью которых можно получить любой целый вес от 1 до 40 фунтов. Но главной заслугой Леонардо перед комбинаторикой было, то что он сформулировал и решил задачу о кроликах.
Дата рождения: ок. 1170 годаМесто рождения:ПизаДата смерти: ок. 1250 годаМесто смерти: Пиза Научная сфера: математика` Известен как: пропагандист десятичной системы счисления и использования арабских цифр.
Фибоначчи
Задача о кроликах.Спрашивается, сколько пар кроликов родится за год от одной пары, если кролики начинают приносить потомство со второго месяца и каждая пара через месяц производит на свет еще одну пару? Ее решение привело Фибоначчи к открытию едва ли ни самой знаменитой числовой последовательности1, 1, 2, 3, 5, 8, 13, ... ,названной впоследствии его именем и породившей множество исследований, в особенности связанных с изучением свойств золотой пропорции.
http://kombisapsan.ru/kombi/kroliki.html
В XIII веке, в жизни общества большое место занимали азартные игры. Значительный толчок к развитию комбинаторики дали азартные игры, существовавшие ещё в глубокой древности, но получившие особенное распространение после крестовых походов. Наибольшее распространение получила игра в кости- два или три кубика с нанесёнными на них очками выбрасывали на стол, и ставку брал выбросивший большую сумму очков.
http://www.games-review.ru/tags/%E8%E3%F0%E0/
Несмотря на древность игр, в которых применялись кости, они долго не подвергались математическому исследованию. Но игроки, неустанно упражнявшиеся в бросании костей, заметили, что некоторые суммы очков выпадают часто, а другие - редко. Само слово «азартный» происходит от арабского « азар»- трудный, так называли редко выпадавшие комбинации костей.
http://www.megatronica.ru/shownas07_009.htm
Пытаясь понять, в чём тут дело, составляли таблицы, показывающие сколькими способами можно получить то или иное число очков. На первых порах иногда допускались ошибки - подсчитывали лишь число различных сочетаний костей, дававших данную сумму. Например, при бросании двух костей сумма 6 получается как 1+5, 2+4 и 3+3, сумма 7 - из сочетаний 1+6, 2+5 и 3+4, а сумма 8 - из сочетаний 2+6, 3+5 и 4+4.Так как каждый раз получается три различных сочетания с данной суммой, то делается ошибочный вывод, что сумма очков 6, 7 и 8 должны выпадать одинаково часто . Но это противоречило опыту — 7 очков выпадали чаще. Дело в том, что при бросании двух костей сочетаний 3+3 может быть получено единственным образом, а в сочетании 3+4 — двумя способами (3+4 и 4+3).Этим объясняется большая частота выпадения суммы 7. Таким образом, оказалось, что надо учитывать не только сочетания очков, но и их порядок.
Этим вопросом занимались такие известные математики XVI века, как Д. Кардано и Н. Тарталья.
Д. Кардано.Дата рождения: 24 сентября 1501Место рождения: ПавияДата смерти: 21 сентября 1576 (74 года)Место смерти: Рим. Страна: Италия Научная сфера: математик, инженер.
Никколо Тарталья (итал. Niccolт Fontana Tartaglia, 1499—1557) — итальянский математик.
Наиболее полно исследовал сочетания очков и их порядок в XVII веке Галилео Галилей.
Галилео ГалилейДата рождения: 15 февраля 1564Место рождения: Пиза, Герцогство ФлоренцияДата смерти: 8 января 1642 (77 лет)Место смерти: Арчетри, Великое герцогство ТосканскоеНаучная сфера: астроном, физик, философ, математик
Работы Паскаля и Ферма ознаменовали рождение двух ветвей математики – комбинаторики и теории вероятностей.
Блез ПаскальРод деятельности: математик, философ, литератор, физикДата рождения: 19 июня 1623Место рождения: Клермон-Ферран, Овернь
Дата смерти: 19 августа 1662 (39 лет)Место смерти: Париж
Пьер Ферма 1601-1665
«Это был один из наиболее замечательных умов нашего века, такой универсальный гений и такой разносторонний, что если бы все ученые не воздали должное его необыкновенным заслугам, то трудно было бы поверить всем вещам, которые нужно о нем сказать, чтобы ничего не упустить в нашем похвальном слове».
Готфрид Вильгельм ЛейбницВ 1966 году Лейбниц опубликовал « Диссертацию о комбинаторном искусстве»,
Дата рождения: 1 июля 1646Место рождения: Лейпциг, Саксония, Германия,Д ата смерти: 14 ноября 1716 (70 лет)
в которой была заключена идея логических исчислений, математической логики, приобретшей в наши дни огромное теоретическое и практическое значение.
Эйлер много внимания уделял представлению натуральных чисел в виде сумм специального вида и сформулировал ряд теорем для вычисления числа разбиений . Он исследовал алгоритмы построения магических квадратов методом обхода шахматным конем. При решении комбинаторных задач он глубоко изучил свойства сочетаний и перестановок.
Леонард ЭйлерДата рождения: 4 (15) апреля 1707Место рождения: Базель,,ШвейцарияДата смерти: 7 (18) сентября 1783 76 лет)Место смерти: Санкт-Петербург.
Леонард Эйлер
ОБЩИЕ ПРАВИЛА КОМБИНАТОРИКИ
Комбинаторные задачи бывают самых разных видов. Однако, большинство задач решается с помощью двух основных правил — правила суммы и правила произведения.
ПРАВИЛО СУММЫ
Если некоторый объект A можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить (m+n) способами. При использовании правила суммы надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-либо способом выбора объекта В. Если такие совпадения есть, правило суммы утрачивает силу, и мы получаем лишь (m + n - k) способов выбора, где k—число совпадений.
ПРАВИЛО ПРОИЗВЕДЕНИЯ
Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А,В) в указанном порядке можно осуществить m·n способами.При этом число способов выбора второго элемента не зависит от того, как именно выбран первый элемент.
ФАКТОРИАЛ ЧИСЛА
Факториал числа — это произведение всех натуральных чисел до этого числа включительно.Обозначается с восклицательным знаком в конце. n! = 1 · 2 · 3 · 4 · … · (n-2) · (n-1) · n Случай 0! определен и имеет значение 0!=1, соответствующее комбинаторной интерпретации комбинации нуля объектов, другими словами, есть единственная комбинация нуля элементов, а именно: пустое множество. Ниже приведены значения факториалов от 0 до 10. 0! = 1 1! = 1 2! = 1 · 2 = 23! = 1 · 2 · 3 = 6
Свойство факториала
(n + 1)! = (n + 1) · n! Например: (5 + 1)! = (5 + 1) · 5! Действительно 6! = (1 · 2 · 3 · 4 · 5) · 6 = 720 А значение (1 · 2 · 3 · 4 · 5) = 5! = 120
КОМБИНАТОРНЫЕ СОЕДИНЕНИЯ
Комбинаторные соединения — это такие комбинации из каких-либо элементов.
Перестановки
Размещения
Сочетания
Типы соединений
Две схемы выбора элементов
Без повторений
С повторениями
Решение комбинаторных задач
Задачу можно назвать комбинаторной, если ее решением является перебор элементов некоторого конечного множества. Особая примета комбинаторных задач – вопрос, который можно сформулировать таким образом, что он начинался бы словами: • Сколькими способами…? • Сколько вариантов…? Для того, чтобы решить задачу по комбинаторике, необходимо сначала понять её смысл, то есть, представить мысленно процесс или действие, описанное в задаче. Нужно чётко определить тип соединений в задаче, а для этого надо, составив несколько различных комбинаций, проверить повторяются ли элементы, меняется ли их состав, важен ли порядок элементов. Если же комбинаторная задача содержит ряд ограничений, налагающихся на соединения, то нужно понять, как влияют или не влияют эти ограничения на соединения. В том случае, если трудно сразу определить какие-либо важные моменты задачи, то не плохо было бы попытаться разобраться в более лёгкой задаче, например в той, в которой не учитываются ограничения, если они есть в исходной задаче, или же в задаче, в которой рассматривается меньшее количество элементов, тогда проще будет понять принцип образования выборок. Когда комбинаторная задача состоит из различных комбинаций элементарных задач, то нужно просто разбить задачу на подзадачи.
Примеры комбинаторных задач и способы их решения.
1.Перебор возможных вариантов.№1. Из группы теннисистов, в которую в входят четыре человека – Иванов, Петров, Сидоров и Федоров, тренер выделяет пару для участия в соревнованиях. Сколько существует вариантов выбора такой пары?Решение: Составим все пары, в которые входит ИвановИП, ИС, ИФ. Выпишем пары в которые входит Петров, но не входит Иванов.ПС,ПФ.Далее составим пары в которые входит Сидоров но не входят Иванов и Петров.СФ.Других пар вариантов составления пар нет, так как все пары, в которые входит Фёдоров, уже составлены.Итак, мы получили 6 пар: ИП,ИС,ИФ,ПС,ПФ,СФ.
2. Дерево возможных вариантов.№2. Составте все возможные трёхзначные числа из указанных цифр,используя в записи числа каждую из них не более одного раза:1, 3, 6, 8.Решение: Составим схему(дерево возможных вариантов).Ответ: 136,138,163,168,183,186,316,318,361,368,381,386,613,618,631,638,681,683,813,816,831,836,861,863.
1
3
6
8
3
6
8
1
6
8
1
3
8
1
3
6
6
8
3
8
3
6
6
8
1
8
1
6
3
8
1
8
1
3
3
6
1
6
1
3
3.Комбинаторное правило умножения.№3. У Арины пять подруг: Катя, Юля, Лиза, Алёна и Таня. Она решила пригласить двух из них в кино. Укажите все возможные варианты выбора подруг. Сколько таких вариантов?Решение:Все возможные варианты находим используя способ переборавозможных вариантовАКЮ, АКЛ, АКА, АКТ, АЮЛ, АЮА, АЮТ, АЛА, АЛТ, ААТ.Используя правило умножения найдём количество вариантов.Количество подруг :5Нужно выбрать 2 из 52∙5=10Ответ: АКЮ, АКЛ, АКА, АКТ, АЮЛ, АЮА, АЮТ, АЛА, АЛТ, ААТ; 10.
№4. Из города А в город В ведут две дороги, из города В в город С – три дороги, из города С до пристани – две дороги. Туристы хотят проехать из города А через города В и С к пристани. Сколькими способами они могут выбрать маршрут?Решение:А В С ПристаньПуть из А в В туристы могут выбрать двумя способами. Далее в каждом случае они могут проехать из В в С тремя способами. Значит, имеются 2 ∙ 3 вариантов маршрута из А в С. Так как из города С на пристань можно попасть двумя способами, то всего существует 2 ∙ 3 ∙ 2, т.е. 12, способов выбора туристами маршрута из города А к пристани. Ответ: 12 способов.
4.Перестановки.Перестановкой из n элементов называется каждое расположение этих элементов в определённом порядке.Число перестановок из n элементов обозначают символом Pn ( читается « Р из n» ).Рn = n!Задача. Сколькими способами Миша, Витя, Зоя и Лиза могут встать в очередь за мороженым?Решение:Р4 = 4!=1·2·3·4=24Ответ: 24 способа.
5.Размещения.Размещением из n элементов по k (k ≤ n) называется любое множество, состоящее из k элементов, взятых в определённом порядке из данных n элементов.=Число размещений из n элементов по k обозначают ( читается : «А из n по k»)№5. Учащиеся второго класса изучают 9 предметов . Сколькими способами можно составить расписание на один день, чтобы в нём было 4 различных предмета?Решение: Любое расписание на один день, составлено из 4 различных предметов, отличается от другого либо набором предметов, либо порядком их следования. Значит , в этом примере речь идёт о размещениях из 9 элементов по 4. ИмеемОтвет: 3024
=
=
=
=3024
6.Сочетания.Сочетанием из n элементов по k называется любое множество, составленное из k элементов, выбранных из данных n элементов.Число сочетаний из n элементов по k обозначают ( читается : «С из n по k»)=№6. Из 15 членов туристической группы надо выбрать трёх дежурных. Сколькими способами можно сделать такой выбор.Каждый выбор отличается от другого хотя бы одним дежурным. Значит, здесь речь идёт о сочетаниях из 15 элементов по 3. Имеем = = = =455Ответ: 455
Комбинаторные задачи.
1.С днём рождения!Маша на свой день рождения пригласила в гости трех лучших подруг - Дашу, Глашу и Наташу. Когда все собрались, то по случаю дня рождения Маши решили обняться - каждая пара по одному разу. Сколько получилось разных пар?2.Две шашки. На пустую шашечную доску надо поместить две шашки разного цвета. Сколько различных положений могут они занимать на доске?3. Яблоки.Укажите все способы , какими можно разложить три яблока в две вазы (учтите при этом случаи когда одна из ваз окажется пустой).4.Футбол.В соревнованиях по футболу участвовало 12 команд. Каждая команда провела с каждой из остальных по одной игре на своём поле и по одной игре на поле соперника. Сколько всего игр сделано?
Комбинаторные задачи.
5. Магический квадрат. 6. 8 точек. На плоскости отмечены 8 точек, никакие три из которых не лежат на одной прямой. Сколько прямых можно провести через эти точки ? 7. Поезда. На станции семь запасных путей. Сколькими способами можно расставить на них 4 поезда? 8. Телефон.Сколько существует семизначных телефонных номеров, в которых все цифры различные и первая цифра отлична от нуля.
Области применения комбинаторики
учебные заведения ( составление расписаний)https://sites.google.com/site/2ojaklass/raspisanieсфера общественного питания (составление меню)http://blog.i.ua/user/5067519/987471/лингвистика (рассмотрение вариантов комбинаций букв)
http://www.pglu.ru/images/news/fp2.jpg
биология (расшифровка кода ДНК) http://ru.wikipedia.org/wiki/Файл:Genetickэ_kуd.jpg военное дело (расположение подразделений) http://ru.wikipedia.org/wiki/Файл:Russian_paratroopers_9_may_2005_a.jpg астрология (анализ расположения планет и созвездий
http://otvetin.ru/uploads/posts/2010-03/1267993220_syssol21.jpg
экономика (анализ вариантов купли-продажи акций)http://taganrog-avia.com/wp-content/uploads/2012/04/ekonomika.jpgкриптография (разработка методов шифрования)http://t0.gstatic.com/images?q=tbn:ANd9GcQgctR8GwfuSb1djf2q_cgHPDNImKuTE45h1vSt80F-fNvJiPtr_wдоставка почты (рассмотрение вариантов пересылки)
http://t2.gstatic.com/images?q=tbn:ANd9GcSSrscC7QPteOam6TeY2MyZO7mlTHYxa0DgtlLzfZDWDLqefiL85w
география (раскраска карт) http://www.maps-world.ru/fizic.htmспортивные соревнования (расчёт количества игр между участниками) http://www.munsolncevo.ru/images/sport/51.jpg производство (распределение нескольких видов работ между рабочими)
http://www.solo.com.ru/img/baner_index.jpg
агротехника (размещение посевов на нескольких полях) http://mw2.google.com/mw-panoramio/photos/medium/12937304.jpgазартные игры (подсчёт частоты выигрышей) химия (анализ возможных связей между химическими элементами)
http://www.casinotips.ru/i/oddsmaker_slots.JPG
http://www.calc.ru/img/m.gif
Вывод.
В ближайшем будущем мы научимся решать более сложные задачи комбинаторики, а наши знания по теме будут востребованы при решении задач олимпиадного типа, задач из ЕГЭ. Комбинаторика играет большую роль в практической деятельности человека.
http://mat.1september.ru/view_article.php?ID=201000202
http://pochemuha.ru/chto-takoe-magicheskij-kvadrat-albrext-dyurer
http://yunc.org/КОМБИНАТОРИКА
http://kombisapsan.ru/kombi/kroliki.html
Задачи.http://www.smekalka.pp.ru/math_combination.html
Решение комбинаторных задач. http://combinatoric.ru.gg/%26%231056%3B%26%231045%3B%26%231064%3B%26%231045%3B%26%231053%3B%26%231048%3B%26%231045%3B-%26%231050%3B%26%231054%3B%26%231052%3B%26%231041%3B%26%231048%3B%26%231053%3B%26%231040%3B%26%231058%3B%26%231054%3B%26%231056%3B%26%231053%3B%26%231067%3B%26%231061%3B-%26%231047%3B%26%231040%3B%26%231044%3B%26%231040%3B%26%231063%3B.htm
МБОУ «Илькинская СОШ»
Проблема.Одним из важных и значимых разделов математики является комбинаторика . Обладать «комбинаторным искусством» должен каждый человек. Люди, владеющие техникой решения комбинаторных задач, а следовательно, умеющие рассуждать, перебирать различные варианты решений, часто находят выход, казалось бы, из самой безвыходной ситуации. Чтобы этому научиться, надо заниматься исследовательской деятельностью, то есть изучать, решать, познавать.
Актуальность.Мы на уроках математики впервые встретились с интересными задачами, которые относятся к одному из разделов математики комбинаторике . Комбинаторные задачи могут дать ответ на многие вопросы, связанные с практической деятельностью людей, решение задач помогает развивать умственные способности, логическое мышление, вычислительные навыки . Знание комбинаторики необходимо представителям самых разных специальностей . С комбинаторными задачами приходится иметь дело физикам, лингвистам, специалистам по теории кодов.Изучив историю развития комбинаторики, мы узнаем, как учёные развивали науку, почему дали ей такое название. Всё это необходимо для всестороннего развития личности . Современный человек должен обладать хорошей математической подготовкой, уметь применить свои знания и навыки на практике. С этой целью мы решили узнать больше о комбинаторике и её развитии.
Цель работы: Исследовать комбинаторику, как один из важных разделов математики.Задачи: Изучить историю развития комбинаторики. Исследовать решение комбинаторных задач, связанных с практической деятельностью человека. Показать практическое применение комбинаторики.
История.Комбинаторика - один из разделов математики. Слово комбинаторика происходит от латинского слова combinare, которое означает соединять, сочетать. Она включает в себя задачи, решая которые приходиться составлять различные комбинации из конечного числа элементов и подсчитывать число комбинаций. Такие задачи называются комбинаторными задачами. Например:1.Сколькими способами можно расположить 50 человек в очереди в кассу кино? 2. Сколькими способами могут быть распределены золотая, серебряная и бронзовая медали на чемпионате мира по футболу?
С аналогичными задачами люди столкнулись в глубокой древности . В Древнем Китае увлекались составлением магических квадратов .http://pochemuha.ru/wp-content/uploads/2010/09/kvadrat.jpgМагические квадраты с давних времен являются прекрасным развлечением. Они составляются обычно с одинаковым количеством рядов и колонок и заполняются различными цифрами, следуя трём условиям: 1. Сумма цифр каждого ряда всегда одна и та же. 2. Сумма цифр каждой колонки всегда одна и та же и равна сумме цифр в каждом ряду. 3. Сумма цифр, расположенных по диагонали, равна сумме цифр в каждом ряду и в каждой колонке.
Альбрехт Дюрер (1471-1528) - известный живописец и график немецкого Возрождения. В одну из своих гравюр, "Меланхолию", он включил магический квадрат. Обрати внимание, что, помимо совпадения сумм в рядах, колонках и диагоналях, совпадают также суммы центрального квадрата и каждого из четырёх квадратов, образованных средними линиями.
http://pochemuha.ru/chto-takoe-magicheskij-kvadrat-albrext-dyurer
В Древней Греции подсчитывали число различных комбинаций длинных и коротких слогов в стихотворных размерах, занимались теорией чисел, изучали фигуры, которые можно составить из частей особым образом разрезанного квадрата. Конкретные комбинаторные задачи, касавшиеся перечисления небольших групп предметов , греки решали без ошибок.
В VIII веке до н.э. начался расцвет арабской науки. Арабы перевели многие творения греческих учёных, изучили их, а затем продвинулись вперёд. Они занимались теорией практических вычислений. Комбинаторика возникла в XII веке . В это время Западная Европа начала пробуждаться после многовековой духовной спячки. Развитие торговли с Востоком привело к проникновению в Европу арабской науки. Леонардо, получивший прозвище Фибоначчи, привёл в систему всю арифметику арабов, некоторые сведения Евклида и добавил к ним результаты своих изысканий.
Труд Фибоначчи содержал и новые комбинаторные задачи, например, об отыскании наименьшего количества гирь, с помощью которых можно получить любой целый вес от 1 до 40 фунтов. Но главной заслугой Леонардо перед комбинаторикой было, то что он сформулировал и решил задачу о кроликах.
Дата рождения: ок. 1170 годаМесто рождения:ПизаДата смерти: ок. 1250 годаМесто смерти: Пиза Научная сфера: математика` Известен как: пропагандист десятичной системы счисления и использования арабских цифр.
Фибоначчи
Задача о кроликах.Спрашивается, сколько пар кроликов родится за год от одной пары, если кролики начинают приносить потомство со второго месяца и каждая пара через месяц производит на свет еще одну пару? Ее решение привело Фибоначчи к открытию едва ли ни самой знаменитой числовой последовательности1, 1, 2, 3, 5, 8, 13, ... ,названной впоследствии его именем и породившей множество исследований, в особенности связанных с изучением свойств золотой пропорции.
http://kombisapsan.ru/kombi/kroliki.html
В XIII веке, в жизни общества большое место занимали азартные игры. Значительный толчок к развитию комбинаторики дали азартные игры, существовавшие ещё в глубокой древности, но получившие особенное распространение после крестовых походов. Наибольшее распространение получила игра в кости- два или три кубика с нанесёнными на них очками выбрасывали на стол, и ставку брал выбросивший большую сумму очков.
http://www.games-review.ru/tags/%E8%E3%F0%E0/
Несмотря на древность игр, в которых применялись кости, они долго не подвергались математическому исследованию. Но игроки, неустанно упражнявшиеся в бросании костей, заметили, что некоторые суммы очков выпадают часто, а другие - редко. Само слово «азартный» происходит от арабского « азар»- трудный, так называли редко выпадавшие комбинации костей.
http://www.megatronica.ru/shownas07_009.htm
Пытаясь понять, в чём тут дело, составляли таблицы, показывающие сколькими способами можно получить то или иное число очков. На первых порах иногда допускались ошибки - подсчитывали лишь число различных сочетаний костей, дававших данную сумму. Например, при бросании двух костей сумма 6 получается как 1+5, 2+4 и 3+3, сумма 7 - из сочетаний 1+6, 2+5 и 3+4, а сумма 8 - из сочетаний 2+6, 3+5 и 4+4.Так как каждый раз получается три различных сочетания с данной суммой, то делается ошибочный вывод, что сумма очков 6, 7 и 8 должны выпадать одинаково часто . Но это противоречило опыту — 7 очков выпадали чаще. Дело в том, что при бросании двух костей сочетаний 3+3 может быть получено единственным образом, а в сочетании 3+4 — двумя способами (3+4 и 4+3).Этим объясняется большая частота выпадения суммы 7. Таким образом, оказалось, что надо учитывать не только сочетания очков, но и их порядок.
Этим вопросом занимались такие известные математики XVI века, как Д. Кардано и Н. Тарталья.
Д. Кардано.Дата рождения: 24 сентября 1501Место рождения: ПавияДата смерти: 21 сентября 1576 (74 года)Место смерти: Рим. Страна: Италия Научная сфера: математик, инженер.
Никколо Тарталья (итал. Niccolт Fontana Tartaglia, 1499—1557) — итальянский математик.
Наиболее полно исследовал сочетания очков и их порядок в XVII веке Галилео Галилей.
Галилео ГалилейДата рождения: 15 февраля 1564Место рождения: Пиза, Герцогство ФлоренцияДата смерти: 8 января 1642 (77 лет)Место смерти: Арчетри, Великое герцогство ТосканскоеНаучная сфера: астроном, физик, философ, математик
Работы Паскаля и Ферма ознаменовали рождение двух ветвей математики – комбинаторики и теории вероятностей.
Блез ПаскальРод деятельности: математик, философ, литератор, физикДата рождения: 19 июня 1623Место рождения: Клермон-Ферран, Овернь
Дата смерти: 19 августа 1662 (39 лет)Место смерти: Париж
Пьер Ферма 1601-1665
«Это был один из наиболее замечательных умов нашего века, такой универсальный гений и такой разносторонний, что если бы все ученые не воздали должное его необыкновенным заслугам, то трудно было бы поверить всем вещам, которые нужно о нем сказать, чтобы ничего не упустить в нашем похвальном слове».
Готфрид Вильгельм ЛейбницВ 1966 году Лейбниц опубликовал « Диссертацию о комбинаторном искусстве»,
Дата рождения: 1 июля 1646Место рождения: Лейпциг, Саксония, Германия,Д ата смерти: 14 ноября 1716 (70 лет)
в которой была заключена идея логических исчислений, математической логики, приобретшей в наши дни огромное теоретическое и практическое значение.
Эйлер много внимания уделял представлению натуральных чисел в виде сумм специального вида и сформулировал ряд теорем для вычисления числа разбиений . Он исследовал алгоритмы построения магических квадратов методом обхода шахматным конем. При решении комбинаторных задач он глубоко изучил свойства сочетаний и перестановок.
Леонард ЭйлерДата рождения: 4 (15) апреля 1707Место рождения: Базель,,ШвейцарияДата смерти: 7 (18) сентября 1783 76 лет)Место смерти: Санкт-Петербург.
Леонард Эйлер
ОБЩИЕ ПРАВИЛА КОМБИНАТОРИКИ
Комбинаторные задачи бывают самых разных видов. Однако, большинство задач решается с помощью двух основных правил — правила суммы и правила произведения.
ПРАВИЛО СУММЫ
Если некоторый объект A можно выбрать m способами, а другой объект В можно выбрать n способами, то выбор «либо А, либо В» можно осуществить (m+n) способами. При использовании правила суммы надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-либо способом выбора объекта В. Если такие совпадения есть, правило суммы утрачивает силу, и мы получаем лишь (m + n - k) способов выбора, где k—число совпадений.
ПРАВИЛО ПРОИЗВЕДЕНИЯ
Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А,В) в указанном порядке можно осуществить m·n способами.При этом число способов выбора второго элемента не зависит от того, как именно выбран первый элемент.
ФАКТОРИАЛ ЧИСЛА
Факториал числа — это произведение всех натуральных чисел до этого числа включительно.Обозначается с восклицательным знаком в конце. n! = 1 · 2 · 3 · 4 · … · (n-2) · (n-1) · n Случай 0! определен и имеет значение 0!=1, соответствующее комбинаторной интерпретации комбинации нуля объектов, другими словами, есть единственная комбинация нуля элементов, а именно: пустое множество. Ниже приведены значения факториалов от 0 до 10. 0! = 1 1! = 1 2! = 1 · 2 = 23! = 1 · 2 · 3 = 6
Свойство факториала
(n + 1)! = (n + 1) · n! Например: (5 + 1)! = (5 + 1) · 5! Действительно 6! = (1 · 2 · 3 · 4 · 5) · 6 = 720 А значение (1 · 2 · 3 · 4 · 5) = 5! = 120
КОМБИНАТОРНЫЕ СОЕДИНЕНИЯ
Комбинаторные соединения — это такие комбинации из каких-либо элементов.
Перестановки
Размещения
Сочетания
Типы соединений
Две схемы выбора элементов
Без повторений
С повторениями
Решение комбинаторных задач
Задачу можно назвать комбинаторной, если ее решением является перебор элементов некоторого конечного множества. Особая примета комбинаторных задач – вопрос, который можно сформулировать таким образом, что он начинался бы словами: • Сколькими способами…? • Сколько вариантов…? Для того, чтобы решить задачу по комбинаторике, необходимо сначала понять её смысл, то есть, представить мысленно процесс или действие, описанное в задаче. Нужно чётко определить тип соединений в задаче, а для этого надо, составив несколько различных комбинаций, проверить повторяются ли элементы, меняется ли их состав, важен ли порядок элементов. Если же комбинаторная задача содержит ряд ограничений, налагающихся на соединения, то нужно понять, как влияют или не влияют эти ограничения на соединения. В том случае, если трудно сразу определить какие-либо важные моменты задачи, то не плохо было бы попытаться разобраться в более лёгкой задаче, например в той, в которой не учитываются ограничения, если они есть в исходной задаче, или же в задаче, в которой рассматривается меньшее количество элементов, тогда проще будет понять принцип образования выборок. Когда комбинаторная задача состоит из различных комбинаций элементарных задач, то нужно просто разбить задачу на подзадачи.
Примеры комбинаторных задач и способы их решения.
1.Перебор возможных вариантов.№1. Из группы теннисистов, в которую в входят четыре человека – Иванов, Петров, Сидоров и Федоров, тренер выделяет пару для участия в соревнованиях. Сколько существует вариантов выбора такой пары?Решение: Составим все пары, в которые входит ИвановИП, ИС, ИФ. Выпишем пары в которые входит Петров, но не входит Иванов.ПС,ПФ.Далее составим пары в которые входит Сидоров но не входят Иванов и Петров.СФ.Других пар вариантов составления пар нет, так как все пары, в которые входит Фёдоров, уже составлены.Итак, мы получили 6 пар: ИП,ИС,ИФ,ПС,ПФ,СФ.
2. Дерево возможных вариантов.№2. Составте все возможные трёхзначные числа из указанных цифр,используя в записи числа каждую из них не более одного раза:1, 3, 6, 8.Решение: Составим схему(дерево возможных вариантов).Ответ: 136,138,163,168,183,186,316,318,361,368,381,386,613,618,631,638,681,683,813,816,831,836,861,863.
1
3
6
8
3
6
8
1
6
8
1
3
8
1
3
6
6
8
3
8
3
6
6
8
1
8
1
6
3
8
1
8
1
3
3
6
1
6
1
3
3.Комбинаторное правило умножения.№3. У Арины пять подруг: Катя, Юля, Лиза, Алёна и Таня. Она решила пригласить двух из них в кино. Укажите все возможные варианты выбора подруг. Сколько таких вариантов?Решение:Все возможные варианты находим используя способ переборавозможных вариантовАКЮ, АКЛ, АКА, АКТ, АЮЛ, АЮА, АЮТ, АЛА, АЛТ, ААТ.Используя правило умножения найдём количество вариантов.Количество подруг :5Нужно выбрать 2 из 52∙5=10Ответ: АКЮ, АКЛ, АКА, АКТ, АЮЛ, АЮА, АЮТ, АЛА, АЛТ, ААТ; 10.
№4. Из города А в город В ведут две дороги, из города В в город С – три дороги, из города С до пристани – две дороги. Туристы хотят проехать из города А через города В и С к пристани. Сколькими способами они могут выбрать маршрут?Решение:А В С ПристаньПуть из А в В туристы могут выбрать двумя способами. Далее в каждом случае они могут проехать из В в С тремя способами. Значит, имеются 2 ∙ 3 вариантов маршрута из А в С. Так как из города С на пристань можно попасть двумя способами, то всего существует 2 ∙ 3 ∙ 2, т.е. 12, способов выбора туристами маршрута из города А к пристани. Ответ: 12 способов.
4.Перестановки.Перестановкой из n элементов называется каждое расположение этих элементов в определённом порядке.Число перестановок из n элементов обозначают символом Pn ( читается « Р из n» ).Рn = n!Задача. Сколькими способами Миша, Витя, Зоя и Лиза могут встать в очередь за мороженым?Решение:Р4 = 4!=1·2·3·4=24Ответ: 24 способа.
5.Размещения.Размещением из n элементов по k (k ≤ n) называется любое множество, состоящее из k элементов, взятых в определённом порядке из данных n элементов.=Число размещений из n элементов по k обозначают ( читается : «А из n по k»)№5. Учащиеся второго класса изучают 9 предметов . Сколькими способами можно составить расписание на один день, чтобы в нём было 4 различных предмета?Решение: Любое расписание на один день, составлено из 4 различных предметов, отличается от другого либо набором предметов, либо порядком их следования. Значит , в этом примере речь идёт о размещениях из 9 элементов по 4. ИмеемОтвет: 3024
=
=
=
=3024
6.Сочетания.Сочетанием из n элементов по k называется любое множество, составленное из k элементов, выбранных из данных n элементов.Число сочетаний из n элементов по k обозначают ( читается : «С из n по k»)=№6. Из 15 членов туристической группы надо выбрать трёх дежурных. Сколькими способами можно сделать такой выбор.Каждый выбор отличается от другого хотя бы одним дежурным. Значит, здесь речь идёт о сочетаниях из 15 элементов по 3. Имеем = = = =455Ответ: 455
Комбинаторные задачи.
1.С днём рождения!Маша на свой день рождения пригласила в гости трех лучших подруг - Дашу, Глашу и Наташу. Когда все собрались, то по случаю дня рождения Маши решили обняться - каждая пара по одному разу. Сколько получилось разных пар?2.Две шашки. На пустую шашечную доску надо поместить две шашки разного цвета. Сколько различных положений могут они занимать на доске?3. Яблоки.Укажите все способы , какими можно разложить три яблока в две вазы (учтите при этом случаи когда одна из ваз окажется пустой).4.Футбол.В соревнованиях по футболу участвовало 12 команд. Каждая команда провела с каждой из остальных по одной игре на своём поле и по одной игре на поле соперника. Сколько всего игр сделано?
Комбинаторные задачи.
5. Магический квадрат. 6. 8 точек. На плоскости отмечены 8 точек, никакие три из которых не лежат на одной прямой. Сколько прямых можно провести через эти точки ? 7. Поезда. На станции семь запасных путей. Сколькими способами можно расставить на них 4 поезда? 8. Телефон.Сколько существует семизначных телефонных номеров, в которых все цифры различные и первая цифра отлична от нуля.
Области применения комбинаторики
учебные заведения ( составление расписаний)https://sites.google.com/site/2ojaklass/raspisanieсфера общественного питания (составление меню)http://blog.i.ua/user/5067519/987471/лингвистика (рассмотрение вариантов комбинаций букв)
http://www.pglu.ru/images/news/fp2.jpg
биология (расшифровка кода ДНК) http://ru.wikipedia.org/wiki/Файл:Genetickэ_kуd.jpg военное дело (расположение подразделений) http://ru.wikipedia.org/wiki/Файл:Russian_paratroopers_9_may_2005_a.jpg астрология (анализ расположения планет и созвездий
http://otvetin.ru/uploads/posts/2010-03/1267993220_syssol21.jpg
экономика (анализ вариантов купли-продажи акций)http://taganrog-avia.com/wp-content/uploads/2012/04/ekonomika.jpgкриптография (разработка методов шифрования)http://t0.gstatic.com/images?q=tbn:ANd9GcQgctR8GwfuSb1djf2q_cgHPDNImKuTE45h1vSt80F-fNvJiPtr_wдоставка почты (рассмотрение вариантов пересылки)
http://t2.gstatic.com/images?q=tbn:ANd9GcSSrscC7QPteOam6TeY2MyZO7mlTHYxa0DgtlLzfZDWDLqefiL85w
география (раскраска карт) http://www.maps-world.ru/fizic.htmспортивные соревнования (расчёт количества игр между участниками) http://www.munsolncevo.ru/images/sport/51.jpg производство (распределение нескольких видов работ между рабочими)
http://www.solo.com.ru/img/baner_index.jpg
агротехника (размещение посевов на нескольких полях) http://mw2.google.com/mw-panoramio/photos/medium/12937304.jpgазартные игры (подсчёт частоты выигрышей) химия (анализ возможных связей между химическими элементами)
http://www.casinotips.ru/i/oddsmaker_slots.JPG
http://www.calc.ru/img/m.gif
Вывод.
В ближайшем будущем мы научимся решать более сложные задачи комбинаторики, а наши знания по теме будут востребованы при решении задач олимпиадного типа, задач из ЕГЭ. Комбинаторика играет большую роль в практической деятельности человека.
http://mat.1september.ru/view_article.php?ID=201000202
http://pochemuha.ru/chto-takoe-magicheskij-kvadrat-albrext-dyurer
http://yunc.org/КОМБИНАТОРИКА
http://kombisapsan.ru/kombi/kroliki.html
Задачи.http://www.smekalka.pp.ru/math_combination.html
Решение комбинаторных задач. http://combinatoric.ru.gg/%26%231056%3B%26%231045%3B%26%231064%3B%26%231045%3B%26%231053%3B%26%231048%3B%26%231045%3B-%26%231050%3B%26%231054%3B%26%231052%3B%26%231041%3B%26%231048%3B%26%231053%3B%26%231040%3B%26%231058%3B%26%231054%3B%26%231056%3B%26%231053%3B%26%231067%3B%26%231061%3B-%26%231047%3B%26%231040%3B%26%231044%3B%26%231040%3B%26%231063%3B.htm
Учимся ткать миленький коврик
Простые летающие модели из бумаги
Сказка "Узнай-зеркала"
Осенняя паутина
О чем поет Шотландская волынка?