Комбинаторика – это интересно!

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

Министерство образования и науки Республики Казахстан

Казахский агротехнический университет им. С.Сейфуллина

Исследовательская работа на тему:

«Комбинаторика - это интересно!»

Работу выполнила:

Ученица 113 группа

Абишева Салтанат

Руководитель проекта:

Учитель математики

Аруова Алия Боранбаевна

Астана 2013 г.

Содержание

Введение

1. Понятие о науке «Комбинаторика»

2. Основы комбинаторики

2.1 Размещения

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

2.3 Сочетания

2.4 Практическая часть

2.5 Задача для самостоятельного решения

3. Комбинаторика в различных областях жизнедеятельности

3.1 Комбинаторика в литературе

3.2 Математика на шахматной доске и в играх

3.3 Фигурные числа

3.4 Старинные задачи

Заключение

Введение

"Число, положение и комбинация -

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

различные сферы мысли, к которым

можно отнести все математические

идеи".

Дж. Сильвестр (1844 г.)

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

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

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

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

Комбинаторика становится наукой лишь в 17 в. - в период, когда возникла теория вероятностей. Чтобы решать теоретико-вероятностные задачи, нужно было уметь подсчитывать число различных комбинаций, подчиненных тем или иным условиям. После первых работ, выполненных в 16 в. итальянским учеными Дж. Кардано, Н. Тартальей и г. Галилеем, такие задачи изучали французские математики Б. Паскаль и П. Ферма. Первым рассматривал комбинаторику как самостоятельную ветвь науки немецкий философ и математик Г. Лейбниц, опубликовавший в 1666 г. работу «Об искусстве комбинаторики», в которой впервые появляется сам термин «комбинаторный». Замечательные достижения в области комбинаторики принадлежат Л. Эйлеру.

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

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

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

Объект исследования: область математики - комбинаторика.

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

Гипотеза: комбинаторика интересна и имеет широкий спектр практической направленности.

Задачи исследования:

- собрать, изучить и систематизировать материал о комбинаторике;

- рассмотреть, как элементы комбинаторики используются при решении различных жизненных ситуаций;

- использование комбинаторики в различных сферах жизнедеятельности.

1. Понятие о науке «Комбинаторика»

«Вперёд поедешь -- голову сложишь,

направо поедешь -- коня потеряешь,

налево поедешь -- меча лишишься».

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

В знаменитой басне Крылова «Квартет» «Проказница Мартышка, Осёл, Козёл да косолапый Мишка» устроили любопытный эксперимент, они исследовали влияние взаимного расположения музыкантов на качество исполнения. И если бы не вмешался Соловей, участники квартета, наверное, перепробовали бы все возможные варианты.

Зададимся вопросом: сколько существует способов, чтобы рассадить, например в один ряд, четырех музыкантов?

Другой случай. Воспетый Маяковским «молоткастый» советский паспорт имел серию и номер, состоящие в общей сложности из трёх частей:

1) Некоторое число, записанное римскими цифрами;

2) Две русские буквы;

3) Шесть арабских цифр.

Например, IV - АВ № 057982. Разумеется, все паспорта должны иметь разные номера. Сколько может быть различных паспортов?

Третья ситуация. Нас приглашают сыграть в Лото-Миллион. Суть игры в том, что нужно из 49 номеров угадать 6, которые выпадут во время тиража. Для участия в игре следует приобрести специальную карточку и вычеркнуть в ней 6 любых квадратов, пронумерованных числами от 1 до 49. Чтобы выиграть наверняка, можно было бы запастись таким количеством карточек, какое необходимо для вычеркивания 6 номеров всеми возможными способами. Сколько этих способов?

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

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

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

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

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

Основными и типичными операциями и связанными с ними задачами комбинаторики являются следующие:

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

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

3) образование упорядоченных подмножеств - составление размещений.

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

2. Основы комбинаторики

По мере развития комбинаторики выяснилось, что, несмотря на внешнее различие изучаемых вопросов, многие из них имеют одно и то же математическое содержание и сводятся к задачам о конечных множествах и их подмножествах. Постепенно выявилось несколько типов задач, к которым сводится большинство комбинаторных проблем. Важную область комбинаторики составляет теория перечислений. С ее помощью можно подсчитать число решений различных комбинаторных задач. В основе этой теории лежат «правило суммы» и «правило произведения». Они гласят: «если множество А состоит из m элементов, а множество В - из n элементов, причем эти множества не имеют общих элементов, то их объединение АUВ, т.е. совокупность всех элементов; множество А х В, состоящие из всевозможных пар (а, b), где элемент а принадлежит множеству А, а элемент b принадлежит множеству В, содержит mn элементов».

Например:

Задача 1. Сколько чётных двузначных чисел можно составить из цифр: 0, 1, 2, 4, 5, 9

Решение: Так как первая цифра искомого числа любая из перечисленных, кроме 0, а вторая может быть только 0,2,4, то получается, что вариантов всего 5•3 = 15

Ответ: 15 чисел.

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

Решение: Так как набор составляется из 2 компонентов, то каждый из 3 напитков можно варьировать 4 раза и тогда существует 4•3 = 12 вариантов.

Ответ: 12 вариантов.

Мы видим, что, хотя задачи 1 и 2 очень разные, их решения совершенно одинаковые. Основаны они на общем правиле умножения.

Задача 3. Ученик должен выполнить практическую работу по математике. Ему предложили на выбор 17 тем по алгебре и 13 тем по геометрии. Сколькими способами он может выбрать одну тему для практической работы?

Решение: X=17, Y=13

По правилу суммы X U Y=17+13=30 тем.

Задача 4. Имеется 5 билетов денежно-вещевой лотереи, 6 билетов спортлото и 10 билетов автомотолотереи. Сколькими способами можно выбрать один билет из спортлото или автомотолотереи?

Решение: Так как денежно-вещевая лотерея в выборе не участвует, то всего 6+10=16 вариантов.

Если конечные множества не пересекаются, то число элементов

X U Y {или} равно сумме числа элементов множества X и числа элементов множества Y.

2.1 Размещения

Пусть имеется множество, содержащее n элементов. Каждое упорядоченное подмножество, состоящее из k элементов, называется размещением из n элементов по k элементов.

Из определения вытекает, что n ? k ? 0 и что размещения из n элементов по k элементов - это всё k - элементные подмножества, отличающиеся составом элементов или порядком их следования. Для множества, состоящего из 4-х элементов а, б, с, д, размещения по 3 элемента составляют: 24 варианта, и они отличаются друг от друга либо составом элементов, либо порядком их расположения.

В комбинаторных задачах необходимо уметь подсчитывать число всех возможных размещений из n элементов по k элементов. Для обозначения этого числа применяется специальный символ А_n^k (читается: «число размещений из n по k» или «А из n по k»).

А - первая буква французского слова arrangement, что означает размещение, приведение в порядок. Следовательно, в задаче 1 требовалось найти число размещений из 30 элементов по 2 элемента, и из решения этой задачи следует, что А₃₀² = 870.Также следует помнить, что А_n⁰ = 1, так как существует только одно подмножество n- элементного множества, не содержащее элементов (пустое множество).

В общем случае на вопрос о числе размещений из n элементов по k элементов даёт ответ следующая формула:

А_n^k = n (n - 1) (n - 2) …(n - k + 1), k› 0, (1)

т.е. число размещений из n элементов по k элементов равно произведению k последовательных натуральных чисел от n до n - k + 1 включительно.

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

n - k + 1 способом, так как к моменту выбора k-го элемента осталось n - (k - 1) элементов.

Произведение всех натуральных чисел от n до единицы, обозначают символом n! (читается «эн факториал»). Используя знак факториала, можно, например, записать:

1! = 1,

2! = 2•1 = 2,

3! = 3 •2 •1 = 6,

4! = 4 •3 •2 •1 = 24,

5! = 5 •4 •3 •2 •1 = 120.

Для нахождения числа размещений из n элементов по k элементов можно также применять следующую формулу:

n(n - 1)(n - 2)…(n - k + 1)(n - k)!

A ^k_n ⁼ (n - k)!

или

n!

A^k_n ⁼ (n - k)! (2)

Формулой (2) можно пользоваться при k = 0, так как она в этом частном случае даёт следующий результат:

n!

A⁰_n= (n - 0)! ⁼ n!/ n! =1

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

Решение: Различных способов составления графика, очевидно, столько, сколько существует двухэлементных упорядоченных подмножеств у четырнадцатиэлементного множества. Следовательно, число способов равно числу размещений из 14 элементов по 2, т.е. равно А₁₄². По формуле (1), полагая в ней n = 14, k = 2, находим

А₁₄² = 14 •13 = 182 (варианта)

Ответ: 182 варианта графика

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

Решение: В условии задачи предложено подсчитать число всевозможных комбинаций из трех цифр, взятых из предположенных девяти цифр, причём порядок расположения цифр в комбинации имеет значение (например, числа 132 и 231 различные). Иначе говоря, нужно найти число размещений из девяти элементов по три.

По формуле числа размещений находим:

А₉³ = 9 (9 - 1)(9 - 2) = 9 ·8·7 = 504

Ответ: 504 трехзначных чисел.

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

Размещения из n элементов по n элементов называются перестановками из n элементов.

Перестановки являются частным случаем размещений. Так как каждая перестановка содержит все n элементов множества, то различные перестановки отличаются друг от друга только порядком элементов. Число перестановок из n элементов обозначают через Р_n. Р - первая буква французского слова permutation - перестановка.

В общем случае число перестановок из n элементов Р_n = А_nⁿ, и следовательно, его можно найти по формуле (1) или по формуле (2), положив в каждой из них k = n. Действительно, формула (2) даёт

n! n!

Р_n= А_nⁿ = (n - n)! = 0! = n!,

Из формулы (1) находим

Р_n = А_nⁿ = n (n - 1) (n - 2) …(n - n + 1) = n!.

Итак, число перестановок из n элементов равно n!

Таким образом в множестве, содержащем n элементов, установить определённый порядок следования элементов или, как говорят, упорядочить такое множество можно n! Способами.

Например, список учеников класса, в котором 15 человек и нет однофамильцев, можно составить

15! = 15·14·13·12·11·10·9·8·7·6·5·4·3·2·1=1 307 674 368 000 способами.

Задача 9. Сколькими способами можно разместить на полке 7 книг?

Решение: Задача сводится к подсчёту числа перестановок из семи элементов:

Р₇ = 7! = 1 •2 •3 •4 •5 · 6 · 7 = 5040 способов.

Ответ: 5040 способов

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

Решение: Р₅ = 5!= 1 •2 •3 •4 •5 = 120 способов.

Ответ: 120 способов забега.

2.3 Сочетания

Пусть имеется множество, состоящее из n элементов. Каждое его подмножество, содержащее k элементов, называется сочетанием из n элементов по k элементов.

Сочетания из n элементов по k элементов - это все k-элементные подмножества n-элементного множества, причём различными подмножествами считаются только те, которые имеют неодинаковый состав элементов. Подмножества, отличающиеся друг от друга только порядком следования элементов, не считаются различными. Например, для четырёхэлементного множества a, b, c, d сочетаниями по 3 элемента являются следующие подмножества:

abc, abd, acd, bcd.

Число всех сочетаний из n элементов по k элементов обозначается символом С_n^k (читается: «число сочетаний из n по k»). С - первая буква французского слова combinasion - сочетание. Число сочетаний из 5 элементов по 2 элемента будет С₅² = 10.

В общем случае число сочетаний из n элементов по k элементов определяется следующей формулой:

n!

С^k_n = (n - k)! K!

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

n (n - 1) (n - 2)…( n - k + 1) (4)

С^k_n = k!

Т.е. число сочетаний из n-элементов по k элементов равно произведению всех натуральных чисел от n до n - k + 1 включительно, делённому на k!

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

Решение: Очевидно, столько, сколько существует трехэлементных подмножеств у десятиэлементного множества. По формуле (4)находим:

10! 10•9•8

С³₁₀ = (10 -3)!· 3 = 6 =120

Ответ: 120 способов

2.4 Практическая часть

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

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

5 •3 = 15 способов.

Ответ: 15 способов.

Задача 13. В соревновании участвуют 12 команд. Сколько существует вариантов распределения призовых (1, 2, 3) мест?

Решение: А₁₂³ = 12 •11 •10 = 1320 вариантов распределения призовых мест.

Ответ: 1320 вариантов.

Задача 14. На соревнованиях по лёгкой атлетике нашу школу представляла команда из 10 спортсменов. Сколькими способами тренер может определить, кто из них побежит в эстафете 4100 м на первом, втором, третьем и четвёртом этапах?

Решение: Выбор из 10 по 4 с учётом порядка: способов.

Ответ: 5040 способов.

Задача 15. Сколькими способами можно выложить в ряд красный, черный, синий и зеленый шарики?

Решение: На первое место можно поставить любой из четырех шариков (4 способа), на второе - любой из трех оставшихся (3 способа), на третье место - любой из оставшихся двух (2 способа), на четвертое место - оставшийся последний шар. Всего 4 · 3 · 2 · 1 = 24 способа.

Р₄ = 4! = 1 · 2 · 3 · 4 = 24.

Ответ: 24 способа.

Задача 16. Учащимся дали список из 10 книг, которые рекомендуется прочитать во время каникул. Сколькими способами ученик может выбрать из них 6 книг?

Решение: Выбор 6 из 10 без учёта порядка: способов.

Ответ: 210 способов.

Задача 17. Володя идёт на день рождения к одноклассникам, двойняшкам Юле и Ире. Он хочет подарить каждой из них по мячу. В магазине остались для продажи только 3 мяча разных цветов: белый, чёрный и в полоску. Сколькими способами, купив 2 мяча, Володя может сделать подарки сестрам?

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

Ответ: 6 способов.

Задача 18. В 9 классе учатся 7 учащихся, в 10 - 9 учащихся, а в 11 - 8 учащихся. Для работы на пришкольном участке надо выделить двух учащихся из 9 класса, трех - из 10, и одного - из 11. Сколько существует способов выбора учащихся для работы на пришкольном участке?

Решение: Выбор из трёх совокупностей без учёта порядка, каждый вариант выбора из первой совокупности (С₇²) может сочетаться с каждым вариантом выбора из второй (С₉³) и с каждым вариантом выбора третьей (С₈¹) по правилу умножения получаем:

7·6 9·8·7 8

С₇² · С₉³· С₈¹ =------ · -------- · ---- = 14 112 способов выбора учащихся.

1·2 1·2·3 1

Ответ: 14 112 способов.

Задача 19. Девятиклассники Женя, Сережа, Коля, Наташа и Оля побежали на перемене к теннисному столу, за которым уже шла игра. Сколькими способами подбежавшие к столу пятеро девятиклассников могут занять очередь для игры в настольный теннис?

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

5· 4321=120 способов занять очередь.

Ответ: 120 способов.

2.5 Задачи для самостоятельного решения

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

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

3. Сократите дробь:

п!

-----

п-1

4. Решите уравнение: п.!=7х(п-1)!

5. Встретились 6 друзей, и каждый пожал руку каждому своему другу. Сколько было рукопожатий?

6. В классе 27 человек. К доске нужно вызвать двоих. Сколькими способами это можно сделать, если:

а) первый ученик должен решить задачу по алгебре, а второй по геометрии?

б) они должны стереть с доски?

7. Имеется 5 видов конвертов и 4 вида марок. Сколькими способами можно выбрать конверт и марку для посылки письма?

8. Десять разных писем раскладывают по одному в десять конвертов. Сколько существует способов такого раскладывания?

9. Собрание из 80-ти человек выбирает председателя и трех человек редакционной коллегии. Сколькими способами это можно сделать?

10. Найти число различных способов, которыми можно записать в один ряд 6 плюсов и 4 минуса.

11. Курьер должен разнести пакеты в 7 различных учреждений. Сколько маршрутов может он выбрать?

12. В библиотеке Саше предложили на выбор из новых поступлений 10 книг и 4 журнала. Сколькими различными способами он может выбрать из них 3 книги и 2 журнала?

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

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

3. Комбинаторика в различных областях жизнедеятельности человека.

3.1 Комбинаторика в литературе

В басне Ивана Андреевича Крылова «Квартет»: «проказница Мартышка, Осёл, Козёл да косолапый Мишка» устроили любопытный эксперимент, они исследовали влияние взаимного расположения музыкантов на качество исполнения.

Проказница-Мартышка, Осёл, Козёл, да косолапый Мишка

Затеяли сыграть Квартет.

Достали нот, баса, альта, две скрипки

И сели на лужок под липки -- пленять своим искусством свет.

Ударили в смычки, дерут, а толку нет.

«Стой, братцы, стой! -- кричит Мартышка. -- Погодите!

Как музыке идти? Ведь вы не так сидите.

Ты с басом, Мишенька, садись против альта,

Я, прима, сяду против вторы;

Тогда пойдёт уж музыка не та: у нас запляшут лес и горы!»

Расселись, начали Квартет;

Он всё-таки на лад нейдёт.

«Постойте ж, я сыскал секрет, --

Кричит Осёл: -- мы, верно, уж поладим, коль рядом сядем».

Послушались Осла: уселись чинно в ряд;

А всё-таки Квартет нейдёт на лад.

Вот пуще прежнего пошли у них разборы

И споры, кому и как сидеть.

Случилось Соловью на шум их прилететь.

Тут с просьбой все к нему, чтоб их решить сомненье:

«Пожалуй, -- говорят: -- возьми на час терпенье,

Чтобы Квартет в порядок наш привесть:

И ноты есть у нас, и инструменты есть;

Скажи лишь, как нам сесть!» --

«Чтоб музыкантом быть, так надобно уменье

И уши ваших понежней, --

Им отвечает Соловей: -- А вы, друзья, как ни садитесь,

Всё в музыканты не годитесь».

Мартышка, Осёл, Козёл и Мишка пересаживались, считая, что от этого зависит звучание музыки. И если бы не вмешался Соловей, участники квартета, наверное, перепробовали бы все возможные варианты.

Зададимся вопросом: сколько существует способов, чтобы рассадить, например в один ряд, четырех музыкантов?

Число перестановок можно посчитать по формуле:

Р₄ = n! = 4! = 4 3 2 = 24 способа.

Ответ: 24 способа.

3.2 Математика на шахматной доске и в играх

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

Задача: Обойти конем все поля доски, посетив каждое из них по одному разу.

Этой задачей занимались многие математики XVIII и XIX вв., в том числе и Л. Эйлер. Хотя задача была известна и до Эйлера, лишь он впервые обратил внимание на ее математическую сущность. Доказано, что таких маршрутов не более 30 млн. Задачи о маршрутах составлены и для других фигур.

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

Доказано, что существует 92 требуемых расстановки. Подобные задачи ставятся для всех шахматных фигур. Исследование конкретных позиций или их классов в игре применяется для достижения определенных результатов, например матовой позиции за определенное число ходов. Так как борьба за уменьшение времени на «обдумывание» хода всей программой является принципиальным фактором, то математики затрачивают массу усилий на создание входящих в нее приложений (задач, решаемых при поиске нужного хода), работающих наиболее быстро, а также требующих по минимуму оперативной памяти. Это направление породило множество изящных логико-вычислительных проблем. Некоторые из них и по сей день предлагаются на различных математических и программистских олимпиадах, а также для развлечения на досуге.

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

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

Необыкновенно популярной головоломкой стал кубик Рубика, изобретенный в 1975 году преподавателем архитектуры из Будапешта Эрне Рубиком для развития пространственного воображения у студентов.

Кубик Рубика - это куб, как бы разрезанный на 27 одинаковых кубиков. В исходном положении каждая грань куба окрашена в один из 6 цветов. Остроумный механизм позволяет поворачивать любой слой из 9 кубиков, примыкающий к одной грани куба, вокруг ее центра. При этом цвета граней смешиваются. Задача состоит в том, чтобы вернуть разноцветные грани кубика в исходное положение. Теоретически из любого состояния кубика можно вернуться в исходное не более чем за 23 хода. Лучшее время, показанное на чемпионате мира 1982 г. по скоростной сборке кубика Рубика, составило всего 22,95 секунды.

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

3.3 Фигурные числа

Про числа 25, 49, 100 говорят, что они являются квадратами. А почему? Потому что они получаются , если возвести числа 5, 7, 10 в квадрат. Но имеет ли это название отношение к геометрической фигуре - квадрату?

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



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

Нетрудно заметить, что квадратное число равно n², а треугольное число равно сумме всех целых чисел от 1 до n, т. е.

n(n - 1).

2

Пятиугольные числа изображены на рисунке в среднем ряду.

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

n(n - 1)

n + 3 ----------

2

Подобным образом можно образовывать любые многоугольные числа. Формула для вычисления n - го k - угольного числа такова:

n(n - 1)

P_n^k = n + (k - 2)-----------

2

При k = 3 мы получаем треугольные числа, при k = 4 - квадратные.

Аналогично можно представить число в виде прямоугольника. Для числа 12 это можно сделать различными способами. На рисунке представлено в нижнем ряду. Причем такое число должно быть составным.

3.4 Старинные задачи

1. Задача: «Волк, козел и капуста»

Крестьянину нужно перевезти через реку волка, козла и капусту. Лодка так мала, что в ней кроме крестьянина может поместиться только или волк, или козел, или капуста. Но если оставить волка с козлом, он его съест, а если оставить козла с капустой, то будет съедена капуста. Как быть крестьянину?

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

2. Задача-игра: «Крестики-нолики»

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

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

3. Задача-игра: «Ним»

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

Заключение

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

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

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

Литература:

1. Андреева Е.В. «Комбинаторные задачи», Москва «Чистые пруды»,2005 г.

2. Грэхем Р., Кнут Д.А., Паташник О. Конкретная математика. Москва «Мир», 1998 г.

3. Кутасов А.Д., Пиголкина Т.С., Чехлов В.И., Яковлева Т.Х. Пособие по математике для поступающих в вузы. Москва «Наука», 1988 год.

4. Перельман Я.И. «Занимательная алгебра. Занимательная геометрия» Москва, АСТ «Астрель»,2002 год.

5. Савин А.П. «Энциклопедический словарь юного математика», Москва «Педагогика», 1985 г.

6. Сканави М.И. «Сборник задач по математике для поступающих в вузы», Москва «Высшая школа», 1998 г.

7. Фадеев Д.К., Никулин М.С., Соколовский. Элементы высшей математики для школьников. Москва «Наука», 1987 год.

8. Элементы теории вероятностей. Математика. Приложение к газете "Первое сентября", 1999 год, № 41, 42.

9. http//portfolio.1september.ru

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

...