Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015
Свидетельство о публикации

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Математика / Научные работы / Интуитивная комбинаторика. Доклад для НПК
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 28 июня.

Подать заявку на курс
  • Математика

Интуитивная комбинаторика. Доклад для НПК

библиотека
материалов

Аннотация



Султанянов Александр, Тимербулатов Данил

Г. Уфа, МБОУ Лицей №60, 8 класс.

«Интуитивная комбинаторика»

Руководитель: Протасова Людмила Ивановна, учитель математики

Научный руководитель: Протасов Андрей Олегович, учитель математики.

Цель научной работы: Изучить методы решения комбинаторных задач, используемые в школьной программе, обратить внимание на недостатки изучения комбинаторики в школьной программе.

Введение



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

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

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

Основное содержание:



Цели и задачи:

  1. Изучить школьные методы решения комбинаторных задач.

  2. Изучить комбинаторные формулы.

  3. Научиться анализировать задачи и подбирать к ним наиболее рациональный метод решения.





История появления. Комбинаторные мотивы можно заметить в символике китайской «Книги Перемен» (V век до н. э.). По мнению её авторов, всё в мире комбинируется из различных сочетаний мужского и женского начал, а также восьми стихий: земля, горы, вода, ветер, гроза, огонь, облака и небо. Историки отмечают также комбинаторные проблемы в руководствах по игре в Го и другие игры. Большой интерес математиков многих стран с древних времён неизменно вызывали магические квадраты.

Классическая задача комбинаторики: «сколько есть способов извлечь m элементов из N возможных» упоминается ещё в сутрах древней Индии (начиная примерно с IV века до н. э.). Индийские математики, видимо, первыми открыли биномиальные коэффициенты и их связь с биномом Ньютона. Во II веке до н. э. индийцы знали, что сумма всех биномиальных коэффициентов степени n равна .Античные греки также рассматривали отдельные комбинаторные задачи.

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

  1. Задачи на перечисление. В этих задачах ставится вопрос о числе конфигураций того или иного вида. Примером может служить задача о числе сочетаний из n элементов по k. Здесь конфигурации - это все подмножества, состоящие из k элементов, данного множества, состоящего из n элементов. Их число равняется биномиальному коэффициенту.

  2. Задачи существования и построения. Эти задачи сводятся к доказательству существования достаточно редких конфигураций с какими-либо интересными свойствами, а именно к построению магических и латинских квадратов.

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





Задачи и решение через школьную программу: Перебор возможных вариантов

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

Задача 1. 
В финальном забеге на 400 м участвуют Алкин, Булкин и Васильев. Назовите возможные варианты распределения призовых мест.

Ответ:
Вариант 1: 1)Алкин, 2)Булкин, 3)Васильев.
Вариант 2: 1) Алкин, 2) Васильев, 3) Булкин.
Вариант 3: 1) Васильев, 2) Алкин, 3) Булкин.
Вариант 4: 1) Васильев, 2) Булкин, 3)Алкин.
Вариант 5: 1) Булкин, 2) Васильев, 3) Алкин.
Вариант 6: 1) Булкин, 2) Алкин, 3) Васильев.

Дерево возможных вариантов

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



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

Решение. Построим дерево возможных вариантов, обозначив М — моделирование, Р — риторика, И — игра на гитаре, А — английский язык, Ф — фортепьяно.



Ответ: Всего 24 возможных варианта:

Составление таблиц

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

Задача 8. 
Сколько нечетных двузначных чисел можно составить из цифр 1, 3, 4, 6, 7, 8, 9?

Решение. Составим таблицу: слева первый столбец — первые цифры искомых чисел, вверху первая строка — вторые цифры.



Ответ: 28.




Комбинаторные формулы:



Задача 1. Дано: яблоко / груша / банан

Вопрос первый: сколькими способами их можно переставить?

Одна комбинация уже записана выше и с остальными проблем не возникает:

яблоко / банан / груша 
груша / яблоко / банан
груша / банан / яблоко
банан / яблоко / груша 
банан / груша / яблоко

Итого: 6 комбинаций или 6 перестановок.

Хорошо, здесь не составило особого труда перечислить все возможные случаи, но как быть, если предметов больше?  Уже с четырьмя различными фруктами количество комбинаций значительно возрастёт!



Никаких мучений – 3 объекта можно переставить  способами.

Вопрос второй: сколькими способами можно выбрать а) один фрукт, б) два фрукта, в) три фрукта, г) хотя бы один фрукт?

а) Один фрукт можно выбрать, очевидно, тремя способами – взять либо яблоко, либо грушу, либо банан. Формальный подсчёт проводится по формуле количества сочетаний:


Запись  в данном случае следует понимать так: «сколькими способами можно выбрать 1 фрукт из трёх?»

б) Перечислим все возможные сочетания двух  фруктов:

яблоко и груша;
яблоко и банан;
груша и банан.

Количество комбинаций легко проверить по той же формуле:


Запись  понимается аналогично: «сколькими способами можно выбрать 2 фрукта из трёх?».

в) И, наконец, три фрукта можно выбрать единственным способом:
 

Кстати, формула количества сочетаний сохраняет смысл и для пустой выборки:
 

способом можно выбрать ни одного фрукта – собственно, ничего не взять и всё.

г) Сколькими способами можно взять хотя бы один фрукт? Условие «хотя бы один» подразумевает, что нас устраивает 1 фрукт (любой) или 2 любых фрукта или все 3 фрукта:
 способами можно выбрать хотя бы один фрукт.



Вопрос третий: сколькими способами можно раздать по одному фрукту Данилу и Саше?

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

яблоко и груша;
яблоко и банан;
груша и банан.

Но комбинаций сейчас будет в два раза больше. Рассмотрим, например, первую пару фруктов: 
яблоком можно угостить Данила, а грушей – Сашу;
либо наоборот – груша достанется Данилу, а  яблоко – Саше.

И такая перестановка возможна для каждой пары фруктов.

В данном случае работает формула количества размещений:


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

Остановимся на каждом виде комбинаций подробнее:

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

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

Отличительной особенностью перестановок является то, что в каждой из них участвует ВСЁ множество, то есть, все  объектов. Например, дружная семья:

Задача 2

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

Решение: используем формулу количества перестановок:



Ответ: 120 способами

Сочетания

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

Задача 3

В ящике находится 15 шаров. Сколькими способами можно взять 4 шара?

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

В задаче речь идёт о выборке из 4-х шаров, в которой не имеет значения их «дальнейшая судьба» – грубо говоря, «просто выбрали 4 штуки и всё». Таким образом, у нас имеют место сочетания шаров. Считаем их количество:



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

 способами можно взять 4 шара из ящика.

Ещё раз: что это значит? Это значит, что из набора 15-ти различных шаров можно составитьь одну тысячу триста шестьдесят пять уникальных сочетания 4-х шаров. То есть, каждая такая комбинация из 4-х шаров будет отличаться от других комбинаций хотя бы одним шаром.

Ответ: 1365 способами

Формуле  необходимо уделить самое пристальное внимание, поскольку она является «хитом» комбинаторики. При этом полезно понимать и без всяких вычислений записывать «крайние» значения: . Применительно к разобранной задаче:

 – единственным способом можно взять ни одного шара;
 способами можно взять 1 шар (любой из 15-ти);
 способами можно взять 14 шаров (при этом какой-то один из 15-ти останется в ящике);
 – единственным способом можно взять все пятнадцать шаров.

Размещения

Или «продвинутые» сочетания. Размещениями называют различные комбинации из объектов, которые выбраны из множества  различных объектов, и которые отличаются друг от друга как составом объектов в выборке, так и их порядком. Количество размещений рассчитывается по формуле 



Правило сложения и правило умножения комбинаций

Данные правила весьма напоминают алгебру событий, и многие читатели уже ознакомились с пунктом  №4 справочного материала Основные формулы комбинаторики, где они изложены в общем виде. Постараюсь повторить принципы максимально кратко:

1) Знак «плюс» следует понимать и читать как союз ИЛИ. Вспоминаем демонстрационную задачу с яблоком, грушей и бананом:

 способами можно выбрать хотя бы один фрукт.

То есть, можно взять 1 фрукт (любой из 3-х) ИЛИ какое-нибудь сочетание 2-х фруктов ИЛИ все три фрукта. Заметьте, что сложение комбинаций предполагает безразличие выбора (без разницы будет ли выбран один, два или 3 фрукта).

Рассмотрим более основательный пример:

Правило умножения комбинаций:

2) Знак «умножить» следует понимать и читать как союз И.

Правило умножения комбинаций распространяется и на большее количество множителей:

Задача 4

Сколько существует трёхзначных чисел, которые делятся на 5?

Решение: для наглядности обозначим данное число тремя звёздочками: ***

Комбинации будем считать по разрядам – слева направо:

В разряд тысяч можно записать любую из  цифр (1, 2, 3, 4, 5, 6, 7, 8 или 9).  Ноль не годится, так как в этом случае число перестаёт быть трёхзначным.

А вот в разряд десятков («посерединке») можно выбрать любую из 10-ти цифр: .

По условию, число должно делиться на 5. Число делится на 5, если оно заканчивается на 5 либо на 0. Таким образом, в младшем разряде нас устраивают 2 цифры.

Итого, существует:  трёхзначных чисел, которые делятся на 5.

При этом произведение  расшифровывается так: «9 способами можно выбрать цифру в разряд тысяч и 10 способами выбрать цифру в разряд десятков и 2 способами вразряд единиц»

Или ещё проще: «каждая из 9-ти цифр в разряде тысяч комбинируется с каждой из 10-ти цифр разряда десятков и с каждой из двух цифр в разряде единиц».

Ответ: 180

Задача 5

В лифт 12-этажного дома сели 3 пассажира. Каждый независимо от других с одинаковой вероятностью может выйти на любом (начиная со 2-го) этаже. Сколькими способами:

1) пассажиры могут выйти на одном этаже; 
2) два человека могут выйти на одном этаже, а третий – на другом;
3) люди могут выйти на разных этажах;
4) пассажиры могут выйти из лифта?



Перестановки, сочетания и размещения с повторениями

Перестановки с повторениями

В перестановках с повторениями, как и в «обычных» перестановках, участвует сразу всё множество объектов, но есть одно но: в данном множестве один или большее количество элементов (объектов) повторяются. Встречайте очередной стандарт:

Задача 6

Сколько различных слов (не обязательно осмысленных) можно получить перестановкой карточек со следующими буквами: К, О, Л, О, К, О, Л, Ь, Ч, И, К?

Решение: в том случае, если бы все буквы были различны, то следовало бы применить тривиальную формулу , однако совершенно понятно, что для предложенного набора карточек некоторые перестановки будут срабатывать «вхолостую», например, если переставить любые две карточки с буквами «К», то получится то же самое слово. Причём, физически карточки могут сильно отличаться: одна быть круглой с напечатанной буквой «К», другая – квадратной с нарисованной буквой «К». Но по смыслу задачи даже такие карточки считаются одинаковыми, поскольку в условии спрашивается о словах (а точнее, о буквосочетаниях).

Всё предельно просто – всего: 11 карточек, среди которых буква:

К – повторяется 3 раза;
О – повторяется 3 раза;
Л – повторяется 2 раза;
Ь – повторяется 1 раз;
Ч – повторяется 1 раз;
И – повторяется 1 раз.

Проверка: 3 + 3 + 2 + 1  + 1 + 1 = 11, что и требовалось проверить.


 различных слов (буквосочетаний) можно получить. Больше полумиллиона!

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

Но предварительные комментарии о повторяющихся буквах обязательны!

Ответ: 554400

Задача 7

Алексей занимается спортом, причём 4 дня в неделю – лёгкой атлетикой, 2 дня – силовыми упражнениями и 1 день отдыхает. Сколькими способами он может составить себе расписание занятий на неделю?

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

Сочетания с повторениями

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

Сегодня все хорошо потрудились, поэтому настало время подкрепиться:

Задача 8

В школьной столовой продают сосиски в тесте, ватрушки и пиццу. Сколькими способами можно приобрести пять пирожков?

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

Что может быть в выборке? Прежде всего, следует отметить, что в выборке обязательно будут одинаковые пирожки (т.к. выбираем 5 штук, а на выбор предложено 3 вида). Варианты тут на любой вкус: 5 хот-догов, 5 ватрушек, 5 пончиков, 3 хот-дога + 2 ватрушки, 1 хот-дог + 2 + ватрушки + 2 пиццы и т.д.

Как и при «обычных» сочетаниях, порядок выбора и размещение пирожков в выборке не имеет значения – просто выбрали 5 штук и всё.

Используем формулу  количества сочетаний с повторениями:
 способом можно приобрести 5 пирожков.

Ответ: 21

Какой вывод можно сделать из многих комбинаторных задач?

Порой, самое трудное – это разобраться в условии.

Аналогичный пример для самостоятельного решения:

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

Размещения с повторениями

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

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

Задача 9

Сколько существует четырёхзначных пин-кодов?

Решение: на самом деле для разруливания задачи достаточно знаний правил комбинаторики:  способами можно выбрать первую цифру пин-кода и  способами – вторую цифру пин-кода и столькими же способами – третью и столькими же – четвёртую. Таким образом, по правилу умножения комбинаций, четырёхзначный пин-код можно составить:  способами.

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

Ответ: 10000

Эта задача имеет применение в жизни, вроде бы всего 4 цифры но зато сколько способов! Можно не бояться за свои сбережения.



Заключение

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

Список литературы



  1. Н. Б. Алфутова, А. В. Устинов, Алгебра и теория чисел. Сборник задач для математических школ. — М.: МЦНМО, 2009.

  2. Н. Я. Виленкин, А. Н. Виленкин, П. А. Виленкин, Комбинаторика. — М.: ФИМА, МЦНМО, 2010.

  3. Коробков С.С. Элементы математической логики и теории вероятности. — Екатеринбург, 1999.

  4. Лыскова В.Ю., Ракитина Е.А. Логика в информатике. — М. “Информатика и образование”. 1999 г.







Подайте заявку сейчас на любой интересующий Вас курс переподготовки, чтобы получить диплом со скидкой 50% уже осенью 2017 года.


Выберите специальность, которую Вы хотите получить:

Обучение проходит дистанционно на сайте проекта "Инфоурок".
По итогам обучения слушателям выдаются печатные дипломы установленного образца.

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ

Автор
Дата добавления 11.01.2017
Раздел Математика
Подраздел Научные работы
Просмотров63
Номер материала ДБ-086124
Получить свидетельство о публикации
Похожие материалы

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