Комбинаторника и комбинаторные задачи

Из глубокой древности до современного человечества дошли сведения о том, что выбором объектов и расположения их в том или ином порядке люди занимались и увлекались составлением различных комбинаций, составлением «магических» и «латинских» квадратов. Так, например, в Древнем Китае увлекались составлением квадратов, в которых заданные числа располагали так, что их сумма по всем горизонталям, вертикалям и главным диагоналям была одной и той же (современная игра – задача «Судоку»).

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

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

Впервые термин «комбинаторный» появился в научно – исследовательской работе немецкого ученого и математика Г. Лейбниц в 1666 году «Об искусстве комбинаторики».

Замечательные достижения в области комбинаторики принадлежат А. Эйлеру.

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

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

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

Чтобы решать теоретико-вероятностные задачи, нужно уметь подсчитывать число различных комбинаций, подчинённых тем или иным условиям. После первых работ выполненных итальянскими учеными Д. Кардано, Н. Тартальей, Галилео Галилеем, такие задачи изучали Б. Паскаль, П. Ферма.

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

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

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

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

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

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

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

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

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

Комбинаторика – самостоятельная ветвь математической науки.

Понятия комбинаторики как науки

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

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

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

Через час занятий, проверив, что же дети построили, она обнаружила, что некоторые фигурки отличаются от изображений на картинках. Что это? Неумение?

Вовсе нет! Это результат мышления пятилетнего ребенка, т. е. он (ребенок) построил свой вариант фигурки, отличный от рисунка.

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

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

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

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

Правило умножения(основной принцип): если из некоторого конечного множества первый объект (x) можно выбрать n1 способами и после каждого такого выбора второй объект (y) можно выбрать n2 способами, то оба объекта (x и y) в указанном порядке можно выбрать (n1 и n2) способами.

Приведем пример: представим, что ученик зашел в школьную столовую пообедать, причем из трех блюд. Он посмотрел в меню и увидел в перечне первых блюд борщ, суп и щи (Б, С, Щ), в перечне вторых блюд – гуляш, котлеты, оладьи и рыбу (Г, К, О, Р) и, наконец, на третье – морс или чай (М, Ч).

Все представленные ученику возможности, он быстренько изобразил в виде схемы:

На этой схеме ученик представил все варианты выбора обеда, Три строчки схемы соответствуют тому, что выбор осуществляется в три шага.

Первый шаг – выбор первого блюда (Б, С, Щ). Независимо от принятого решения на первом шаге, у ученика есть четыре возможности выбора второго блюда. На схеме эта независимость выражается в том, это из букв первой строчки (шага – букв Б, С, Щ) попадает поровну стрелок (по четыре) во вторую строчку – Г, К, О, Р. Независимо от того, какие блюда (вторые) ученик выбрал на

1-ом и 2-ом шагах, у него есть возможности (две) выбрать 3-е блюдо – М или Ч. На схеме из каждой буквы второй строчки попадают две стрелки в третью строчку.

Таким образом, каждому варианту обеда соответствует путь на схеме, идущий по стрелкам из верхней строчки в нижнюю. Так, путь С – К – М соответствует обед Суп – Котлета – Морс и т. д. Последний вариант Щи – Рыба – Чай.

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

Так как в первой строчке три буквы, то во второй вчетверо больше (3 4), а в третьей вдвое больше, чем во второй (3 4 2), произведение будет равно 24, т. е. 24варианта обеда.

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

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

Правило суммы (сложение):

Если некоторый объект X можно выбрать n1 способами, а объект Y можно выбрать n2 способами, причем первые и вторые способы не пересекаются, то любой из указанных объектов (Х или Y) можно выбрать ( n1 + n2) способами.

Приведем пример:

В классе 14 мальчиков и 6 девочек. Сколькими способами можно выбрать двух школьников одного пола для выполнения работ в школьном саду?

Решение:

По правилу умножения (см. выше) двух мальчиков можно выбрать 1413=182 способами, а двух девочек – 65=30 способами.

В задаче нужно узнать всего сколько способов? Согласно правилу сложения таких способов будет 182+30=212.

Следует учитывать, что правило умножения распространяется на случаи (задачи) для 3-х и более объектов, тогда как правило суммы распространяется на любое конечное число объектов.

Иными словами, рассуждения об основных правилах комбинаторики можно усложнить математическим языком: в основе теории лежать должны такие понятия, как «сумма» и «произведение». Они гласят: «Если множество А состоит из m элементов, а множество В – из n элементов, причем эти множества не имеют общих элементов, то их объединение (совокупность) из А и В содержит сумму элементов (m+n); состоящее же из всевозможных пар (а и в), множество из А и В, где элемент а принадлежит множеству А, а элемент в принадлежит множеству

В, - содержит произведение элементов m n. »

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

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

Существуют две схемы выбора m элементов (0

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

Соединения элементов, каждое из которых состоит из m элементов, взятых из данных n элементов, называются РАЗМЕЩЕНИЯМИ из n элементов по m

0 < m < n

В данном случае размещения отличаются друг от друга как самими элементами, так и их порядком.

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

=n(n-1)(n-2) (n-m+1) или

(Используется знак ФАКТОРИАЛ - !)

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

После этого второй элемент уже можно выбрать из оставшихся (n - 1) элементов (n - 1) способами. Для выбора третьего элемента имеется (n - 2) способа, для четвертого (n – 3) способа и, наконец, для последнего m элемента – n-(m - 1) способов.

Таким образом, по правилу умножения, существует n(n-1)(n-2) (n-m+1) способа выбора m элементов из данных n элементов, т. е.

=n(n-1)(n-2) (n-m+1)

Пример: Составить различные размещения по 2 из элементов множества (a, b, c) и подсчитать их число.

Решение: Из трех элементов (a, b, c) можно образовать следующие размещения по 2 элемента (a, b), (b, a), (a, c), (c, a), (b, c), (c, b).

Согласно формуле их число можно записать как решение задачи – A32 = 3x2=6

Теперь рассмотрим следующую формулу – ПЕРЕСТАНОВКИ.

Перестановками из n элементов называются размещения из n элементов по n элементов, отличающихся друг от друга лишь порядком элементов. Число перестановок из n элементов обозначается символом Pn и вычисляется по формуле

Пример: составить различные перестановки из элементов множества {2, 7, 8} и подсчитать их число.

Решение:

Из элементов данного множества можно составить следующие перестановки: (2, 7, 8), (2, 8, 7), (7, 2, 8), (7, 8, 2), (8, 2, 7), (8, 7, 2) – таких оказалось 6.

По формуле имеем P3= 3!=1 x 2 x 3=6

Последнюю формулу, которую мы рассмотрим на начальной стадии изучения формул комбинаторики – это формула СОЧЕТАНИЯ

Сочетаниями из n элементов по m 0 < m < n элементов называются соединения, каждое из которых состоит из m элементов, взятых из данных n элементов.

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

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

Пример: Составить различные сочетания по два элемента из множества {a, b, c} и подсчитать их число.

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

С32=(3x2)/(1x2)=3

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

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

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

Я думаю, что некоторым уже захотелось проявить полученные знания на деле. И поэтому представляю вам ряд задач по всем выше указанным темам. Также вам в помощь я предоставляю очень краткий теоретический материал. Но сначала я хочу дать вам одну задачу, которая заинтересует вас.

Задачи.

Задача №1. Сколькими способами можно составить список учеников класса, в котором 20 человек и нет однофамильцев?

Ответ: 201918 321 = 2432902008176640000

Большое число, правда? А каким самым большим числом приходилось иметь дело на практике? Физики считают, что во всей Вселенной количество элементарных частиц, из которых состоят атомы находящегося в ней вещества, не больше чем 1080. Поэтому нет практической необходимости пользоваться числами, большими, чем 10100. Для этого числа придумано специальное название – гугол. Кажется, невозможным представить себе такую громадину. Но все – таки попробуем.

Представьте себе табло из 400 лампочек, расположенных в виде квадрата 2020. Это представить легко, подобные табло встречаются в аэропортах и на вокзалах: там с помощью загорающихся лампочек высвечиваются объявления о прибытие и отправлении самолетов и поездов. А теперь подумаем, сколько различных способов существует, чтобы зажечь табло размером 2020.

Начнем считать количество состояний нашего табло. Для порядка пронумеруем лампочки от 1 до 400. Первая лампочка может быть в двух состояниях: потушенной и зажженной. Две лампочки могут уже быть в четырех состояниях. Если использовать для обозначения потушенной лампочки значок x, а для зажженной значок *, то эти четыре состояния можно вычислить: xx; x*; *x; **. Для трех лампочек будет восемь состояний: xxx; x**; *x*; **x; xx*; *xx; x*x; ***. Количество состояний удвоилось потому, что оно равно количеству состояний для первых двух лампочек при потушенной третьей лампочке плюс то же самое количество состояний при зажженной третьей. Нетрудно заметить, что при добавлении четвертой лампочки количество состояний вновь удвоится и станет равным 24 = 16, при пяти лампочках количество состояний будет 25 = 32, при десяти – уже 210 = 1024, а при 400 лампочках – 2400.

Покажем, что это число больше гугола. Обратим внимание, что 210 = 1024 > 103, поэтому 2400 = 210 40 > 10340 = 10120. Итак, с помощью нашего нехитрого табло мы смогли превзойти гугол.

Сколько же времени понадобится для того, чтобы реализовать все имеющиеся возможности? Пусть у нас есть электронное реле, которое меняет данные табло со скоростью 100 раз в секунду. Поскольку в каждом часе 3600 с, в сутках 86400 с, а в году 31536000 с, то за год табло успеет сделать 3153600000, или 3,1536 109, миганий. Разделив 10120 на это число, получим около 3 10110 лет – число, в миллиарды раз большее гугола

Задача №2

Сколькими способами 4 человека могут разместиться на четырехместной скамейке? Задача №3

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