Развитие мышление школьников средствами математики

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

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

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

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

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

 

При решении  практических задач часто приходится выбирать из некоторого конечного множества  объектов подмножество элементов, обладающих теми или иными свойствами, размещать  элементы множеств в определенном порядке  и т. д. Эти задачи принято называть комбинаторными задачами. Многие из комбинаторных задач решаются с помощью двух основных правил — суммы и произведения. Если удается разбить множество объектов на классы и каждый объект входит в один и только один класс, то общее число объектов равно сумме числа объектов во всех классах (правило сложения). Правило умножения чуть сложнее. Даны два произвольных конечных множества объектов А и В. Количество объектов в А равно N, в В – M. Составляются упорядоченные пары аb, где (апринадлежит А) и Количество таких пар (объектов) равно N*M. Правило обобщается и на большее количество множеств объектов.

Перестановки (обозначение – число перестановок). Классической задачей комбинаторики является задача о числе  перестановок – сколькими способами можно переставить n различных предметов, расположенных на n различных местах.

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

Размещения (обозначение - ). Задача формулируется следующим образом: сколькими способами можно выбрать и разместить по М различным местам М из N различных предметов?

Число размещений вычисляется по одной из следующих  формул:

.

Сочетания (выборки) — обозначение . Другой классической задачей комбинаторики является задача о числе выборок: сколькими способами можно выбрать m из n различных предметов?

Сочетание можно определить и как подмножество из m различных натуральных чисел, принадлежащих множеству чисел из интервала от 1 до n. Число сочетаний вычисляется по формуле:

= .

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

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

.

Перестановки с повторениями. Выше рассмотрены перестановки из различных предметов. В том случае, когда некоторые переставляемые предметы одинаковы, часть перестановок совпадает друг с другом. Перестановок становится меньше. Задача формулируется следующим образом. Имеются предметы k различных типов. Сколько перестановок можно сделать из предметов первого типа, n₁ предметов первого типа, n₂ – второго, . . . , n_k – k-го типа.

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

.

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

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

.

 

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

 

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

Правило суммы. Если элемент A может быть выбран k₁ способами, а элемент В другими k₂ способами, причем выборы А и В являются взаимно исключающими, то выбор «либо А, либо В» может быть осуществлен k₁+k₂ способами.

Например, из множества 1, 2, 3, 4, 5, 7, 9 (n=7) выбрать  четную цифру можно k₁ = 2 разными способами (2 или 4), а выбрать нечетную цифру можно k₂ = 5 способами. Тогда выбор четной или нечетной цифры может быть осуществлен k₁+k₂=2+5=7 различными способами.

Правило произведения. Если элемент А может быть выбран k₁ способами, и после каждого из таких выборов элемент В может быть выбран k₂ способами, то выбор «А и В» может быть осуществлен k₁*k₂ способами.

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

Например, из множества 1, 2, 3, 4, 5, 7, 9 (n=7) выбрать  два элемента так, чтобы образовать четное двузначное число без повторения цифр, можно следующим образом. Сначала  берем четную цифру, которую поставим в младший разряд числа, это можно  сделать k₁ = 2 способами; после этого выбираем в старший разряд – k₂ = 6 способов; всего можно составить k₁*k₂=2*6=12 четных двухзначных чисел без повторения цифр.

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

1. При выборе первой цифры будет извлечена нечетная цифра; тогда k₁=5; после этого вторую цифру можно выбрать из двух оставшихся четных, т.е. k₂=2; количество вариантов k₁*k₂=10.
2. При выборе первой цифры будет извлечена четная цифра, тогда

k₁=2, а вторую цифру можно выбрать единственным способом: взять оставшуюся четную цифру, т.е. k₂=1; количество вариантов k₁*k₂=2.

Используя правило суммы, получаем общее число  вариантов

5*2+2*1=12,

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

 

 

3.4 Некоторые приемы, используемые при решении комбинаторных задач

 

а) «Обратимость» выбор.

Традиционно простейшая комбинаторная задача об одной комбинации ставится следующим  образом.

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

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

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

n*(n-1)*(n-2)*n* . . . *(n-m+2)*(n-m+1)=(n)_m

Можно считать, что, составив комбинацию из m элементов, мы установим соответствие между какими-то m элементами из исходного множества и местами в формируемой комбинации.

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

П р и м е р.

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

Р е ш е н и е.

Считаем элементами исходного множества  цифры (n=6), а местами комбинации – разряды составляемого числа (m=3). Выбираем элементы на каждое место поочередно; всего можно составить 6*5*4=120 различных чисел.

б) «Фиксирование» элементов.

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

П р и м е р.

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

Р е ш е н и е.

Исходное  множество содержит 6 элементов (цифр), из которых только 2 нечетных. Эти  две цифры должны стоять в двух старших разрядах составляемого  числа. На два остающихся места могут  быть выбраны любые 2 из оставшихся 4 цифр; количество способов равно 4*3=12. Две первые нечетные цифры могу быть переставлены 2 способами (13 и 31), поэтому  общее количество четырехзначных чисел  равно 2*12=24.

в) «Склеивание» элементов.

В некоторых  задачах требуется, чтобы два  или более элементов в составляемой комбинации всегда стояли рядом. В таких  случаях мы рассматриваем все  эти элементы как один новый («склеенный»), уменьшаем n и m на k-1 и находим количество способов расположения оставшихся        n-(k-1) элементов на оставшихся m-(k-1) местах. Найденное количество способов умножаем на число перестановок «склеенных» элементов между собой ( в склейке).

П р и м е р.

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

Р е ш е н и е.

В данном случае n = 5, m = 5. «Склеиваем» цифры 4 и 5 и находим число способов размещения 4 элементов (один из них склеенный) на 4 местах (одно из них двойное):  4*3*2*1*=24.

Цифры 4 и 5 можно переставить между собой 2 способами (45 и 54), поэтому общее  число пятизначных чисел равно 2*24=48.

г) Подсчет «ненужных» вариантов.

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

П р и м е р.

Сколько есть пятизначных чисел, в записи которых есть хотя бы одна четная цифра?

Р е ш е н и е.

Исходное множество состоит из n = 10 десятичных цифр; количество мест в формируемой комбинации m = 5. По условию задачи допускается повторение цифр.

Общее количество пятизначных чисел по правилу  произведения равно 9*10*10*10*10=90000. Из пяти нечетных цифр 1, 3, 5, 7, 9 можно составить 5*5*5*5*5=3125 пятизначных чисел, состоящих  только из нечетных цифр. Это и есть «ненужные» варианты.

В каждом из 90000-3125=86875 пятизначных чисел есть хотя бы одна четная цифра (нуль является четной цифрой).

д) Выбор простейшего порядка заполнения мест в формируемой комбинации.

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

П р и м е р.

Сколько есть шестизначных чисел без повторения цифр, в которых вторая и четвертая  цифры нечетны?

Р е ш е н и е.

В данном случае n = 10, m = 6. Если начинать выбор элементов сначала для старшего разряда, то уже следующий выбор окажется зависящим от результатов первого.