УДК 372.851

И. В. Игнатушина

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

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

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

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

Часто при решении задач практики приходится выбирать из некоторой совокупности объекты, обладающие тем или иным свойством, располагать их в определенном порядке и т. д. Такие задачи называют комбинаторными, поскольку в них речь идет о конкретных комбинациях объектов. Раздел математики, посвященный комбинаторным задачам, называется комбинаторикой [2, 10].

Элементы комбинаторики были известны еще в древности. В индийской математике II века до н.э. встречается таблица биномиальных коэффициентов, которая сейчас известна как треугольник Паскаля. Аналогичный результат содержится и в математических рукописях древнего Китая [1].

Общая теорема о разложении бинома была известна Омару Хайяму (1048—1131). К началу XVII столетия в работах Н. Тартальи (1499—1557), Г. Галилея (1564—1642), П. Эригона (1580—1643) и других были накоплены многочисленные сведения комбинаторного характера. Благодатной почвой для расцвета комбинаторики являлись азартные игры, шифры и анаграммы, астрология. Таким образом, первые комбинаторные задачи относились в большей мере к области математических развлечений.

Рождение комбинаторики как раздела математики связано в первую очередь с работами П. Ферма (1601—1665) и Б. Паскаля (1623—1662), в которых содержалось описание нахождения числа комбинаций элементов конечного множества. Эти работы стали фундаментом для теории вероятностей.

Название эта область математики получила в работе Г. В. Лейбница (1646—1716) «Рассуждение о комбинаторном искусстве» (1666). В это время были получены новые результаты в связи с решением первых задач теории вероятностей [1,8].

Немалый вклад в развитие комбинаторики сделал Л. Эйлер (1707—1783). Достаточно упомянуть его задачи о кенигсбергских мостах, о 36 офицерах из 6 разных полков, о ходе шахматного коня, которые стали классическими.

Во второй половине XVIII столетия в Германии образовалась комбинаторная школа, основателем и руководителем которой был К. Ф. Гиндербург (1741—1808). Он высказал идею о том, что комбинаторный метод должен оказать «в высшей степени важное влияние на анализ». В настоящее время существует самостоятельный раздел математики под названием «комбинаторный анализ».

В XIX в. комбинаторные исследования были связаны с формированием теории определителей (для подсчета подстановок использовали число перестановок из конкретного числа элементов), математической логики и т.п. При этом комбинаторика долгое время не входила в программу школьного математического образования. Первым в России, кто предпринял попытку ввести комбинаторику и теорию вероятностей с приложениями к статистике в школьный курс математики, был профессор Московского университета П. А. Некрасов (1853—1924) и директор Урюпинского реального училища П. С. Фролов. Но их усилия не нашли поддержки и даже подверглись критике со стороны многих известных отечественных математиков того времени [8].

В середине XX столетия благодаря усилиям в первую очередь Н. Я. Виленкина (1920—1991) комбинаторика вошла в школу в виде факультативных занятий. В конце 1960-х годов этот раздел математики был фрагментарно представлен в советских учебниках для средней школы [8].

В настоящее время, согласно ФГОС ООО [9], комбинаторика является обязательным разделом школьного курса математики.

Изучение комбинаторики часто вызывает определенные затруднения у обучающихся [7]. В большинстве случаев это связано с тем, что ученики путаются в выборе соответствующей комбинаторной формулы при решении задачи. Для устранения этой проблемы предлагаем использовать следующий методический прием.

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

Определение. Кортеж длины к, составленный из элементов множества А, в котором m элементов, называют размещением с повторениями из m элементов по к. Число всех таких кортежей обозначают . Буква А в обозначении выбрана от французского слова arrange — размещение. Возможность повторения элементов обозначается чертой сверху [2, 4].

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

Определение. Упорядоченное множество длины к, элементы которого взяты из данного m-элементного множества А, называют размещением без повторений из m элементов множества А по к Число таких размещений обозначают Акт [2, 6].

Отсюда следует, что в размещениях без повторений важен порядок элементов, но сами элементы не должны повторяться. Кроме того, поскольку составляются упорядоченные множества длины к, элементы которых взяты из данного m-элементного множества A, должно выполняться условие: т> к.

Определение. Перестановками без повторений из m элементов называются комбинации, состоящие из m различных элементов, отличающиеся друг от друга только расположением элементов [3]. Число таких перестановок из m элементов обозначают Рm. Буква Р является начальной буквой французского слова permutation — перестановка [4].

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

Определение. Если из данного m-элементного множества А составить k-элементные подмножества, то их называют сочетаниями без повторений из m элементов этого множества по к. Их число обозначают С* . Буква С выбрана от французского слова combination — комбинация [2, 6].

Следовательно, в сочетаниях без повторений не важен порядок расположения элементов, а сами элементы не повторяются. Следует также отметить, что поскольку из данного /77-элементного множества составляются к-элементные подмножества, то т> к .

Определение. Перестановкой с повторениями состава {кр ... , к ) из букв {ар ... а ) называют любой кортеж длины к = &у + ... + кт, в который буква а{ входит к{ раз, ..., буква ат — кт раз. Число таких перестановок обозначают Р(кр ..., к ) [2, 4].

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

Определение. Сочетанием с повторениями из m различных элементов по к называется всякое множество А, содержащее к элементов, каждый из которых является одним из заданных m элементов [2, 6].

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

Итак, во всех этих определениях ключевыми являются два фактора:

- важность/неважность порядка элементов;

- возможность/невозможность повторения элементов.

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

Таблица 1

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

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

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

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

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

Задача. Сколько кортежей длины пять можно составить из данной совокупности элементов: 1) 1, 2, 3, 4, 5; 2) 1, 1, 2, 1, 2?

Решение. Поскольку в задаче речь идет о составлении кортежей, то здесь важен порядок элементов и их повтор возможен («+», «+»). В первом случае выбор элементов для кортежа осуществляется из множества {1, 2, 3, 4, 5}, в котором 5 различных элементов. Приведем примеры таких кортежей: (1,1,1,1,1), (2,2,2,2,2), (1,2,1,1,1) и т.д. Следовательно, здесь применяем формулу для подсчета числа размещений с повторениями из 5 элементов по 5 элементов, т.е. используем первую строку таблицы: = 55 = 3125 .

Во втором случае выборка осуществляется из совокупности с повторяющимися элементами — 1, 1, 2, 1, 2, общее число которых равно пяти. Составляются кортежи, в каждом из которых тоже пять элементов. Приведем примеры таких кортежей: (1,1,2,1,2), (1,1,1,2,2), (2,1,1,1,2) и т.д. Замечаем, что эти кортежи различаются только порядком расположения элементов, состав же кортежей остается неизменным: 1 повторяется 3 раза, 2 — 2 раза. Следовательно, здесь речь идет о перестановках с повторениями с заданным составом и нужно использовать формулу из пятой строки таблицы:

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

Задача. Сколько упорядоченных множеств длиной к можно составить из элементов множества А = {1, 2, 3, 4, 5}, если 1) к = 3; 2) к = 5?

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

Заметим, что во втором случае число элементов в составляемом упорядоченном множестве совпадает с числом элементов в исходном множестве, поэтому все эти упорядо-

ченные множества будут отличаться друг от друга только порядком располагаемых элементов:

{1, 2, 3, 4, 5}, {2, 1, 3, 4, 5}, {5, 1, 2, 3, 4} и т.д.

Поэтому можно воспользоваться формулой для подсчета числа перестановок без повторений, расположенной в пятой строке таблицы: Р5 = 5!= 120 .

Здесь важно еще раз отметить, что перестановки без повторений из m элементов являются частным случаем размещений без повторений из m элементов по т, откуда следует, что Рт = Al.

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

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

1) одновременно нажать три кнопки;

2) последовательно нажать три различные кнопки;

3) последовательно нажать три кнопки? [5].

Решение. Поскольку в первом случае нужно одновременно нажать три кнопки, то все они разные и их порядок внутри комбинации не важен. Следовательно, нам подходит четвертая строка таблицы и здесь речь идет о сочетании без повторений из 10 элементов по 3:

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

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

ÄfQ = 103 = 1000.

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

Задача. На конференции должны выступить 5 человек. Сколькими способами их можно расположить в списке ораторов? [4]

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

Р5 = 5! = 120.

Задача. Буквы слова «комбинаторика» написаны на карточках. Сколько «слов» можно получить, переставляя их? [5]

Решение. Слово «комбинаторика» представляет собой кортеж длины 13 с повторяющимися элементами, который имеет состав (2, 2, 2, 2, 1, 1, 1, 1, 1): буквы «к», «о», «и», «а» встречаются в нем 2 раза, буквы «м», «б», «н», «т», «р» — один раз. Необходимо определить, сколькими способами мы можем поменять их порядок. Значит, речь идет

об изменении только порядка элементов, причем сами элементы повторяются, поэтому применяем пятую строку таблицы, а именно формулу для подсчета числа перестановок с повторениями состава (2, 2, 2, 2, 1, 1, 1, 1, 1):

Задача. Сколько разных новогодних подарков можно составить из 15 конфет в каждом, если в продаже имеются 5 видов конфет? [4]

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

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

Теорема 1. Число отображений1 к-элементного множества X в т-элементное множество Y равно тк.

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

Задача. Имеется 6 монет разного достоинства. Сколькими способами их можно разложить по трем карманам? [6]

Решение. Каждый способ раскладки является отображением множества монет во множество карманов. Число таких отображений равно 36, т.е. 729.

Задача. Какая может быть наибольшая численность населения некоторого сказочного государства, если в нем все жители имеют разные наборы зубов, а максимальное число зубов у человека 32? [2]

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

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

Список использованной литературы

1. Александрова Н. В. История математических терминов, понятий, обозначений : словарь-справочник. М. : Изд-во ЛКИ, 2007. 248 с.

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

3. Выгодский М. Я. Справочник по элементарной математике. М. : Наука, 1986. 320 с.

4. Игнатушина И. В. Множества, кортежи, элементы комбинаторики : учеб.-метод, пособие для студ. ин-та физической культуры и спорта пед. ун-та. Оренбург : Изд-во ОГПУ, 2008. 31 с.

5. Игнатушина И. В. Сборник задач к учебно-методическому пособию «Элементы комбинаторики, теории вероятностей и математической статистики». Оренбург : Изд-во ОГПУ, 2006. 58 с.

1 Отображение — закон, по которому каждому элементу х некоторого заданного множества X сопоставляется однозначно определенный элементу другого заданного множества Y. Такое соотношение между элементами хеХ и у е Y записывается в виде y = f(x). Отображение множества X во множество Y обозначают X —» Y.

6. Игнатушина И. В. Элементы комбинаторики, теории вероятностей и математической статистики : учеб.-метод, пособие для студ. ин-та физической культуры и спорта пед. ун-та. Оренбург : Изд-во ОГПУ, 2005.111 с.

7. Лебедев В. В. Эффективное обучение комбинаторике и теории вероятностей // Школьные технологии. М, 2012. № 2. С. 126—134 .

8. Мельников Р. А. Из истории комбинаторики // Вестник Елецкого государственного университета им. И. А. Бунина. Елец : ЕГУ им. И. А. Бунина, 2011. Вып. 28: Сер. «Педагогика» (История и теория математического образования). С. 30—32.

9. Федеральный государственный образовательный стандарт основного общего образования. Утвержден приказом Министерства образования и науки Российской Федерации от 17 декабря 2010 г. № 1897. URL: http://минобрнауки.рф/документы/938.

10. Шихова А. П. Обучение комбинаторике и ее приложениям в средней школе. Киров : ИУУ, 1994. 63 с.

11. Щербатых С. В. Актуализация проблемы формирования стохастического мышления у старшеклассников // Вестник Брянского государственного университета. 2013. № 1. С. 148—150.

Поступила в редакцию 28.10.2016

Игнатушина Инесса Васильевна, кандидат физико-математических наук, доцент Оренбургский государственный педагогический университет Российская Федерация, 460014, г. Оренбург, ул. Советская, 19 E-mail: streleec@yandex.ru

UDC 372.851 I. V. Ignatushina

Methodical way of teaching students the solution of combinatorial problems

Often even simple combinatorial problems cause difficulties for students. The main reason for this lies in the fact that students in the course of solving the problem get confused in choosing the desired combinatorial formula of six major. The article presents the author's methodical approach teaching students to solve combinatorial problems, which relies on the use of the classification table of basic formulas of combinatorics. It is obtained by taking into account two factors: "the importance/unimportance of the order of elements", "possibility/impossibility of repeating".

Key words: combinatorics, solving combinatorial problems.

Ignatushina Inessa Vasilyevna, Candidate of Physical and Mathematical Sciences, Associate Professor

Orenburg State Pedagogical University

Russian Federation, 460014, Orenburg, ul. Sovetskaya, 19

E-mail: streleec@yandex.ru

References

1. Aleksandrova N. V. Istoriya matematicheskikh terminov, ponyatii, oboznachenii : slovar'-spravochnik [The history of mathematical terms, concepts, symbols: Dictionary-Directory]. Moscow, LKI Publ., 2007. 248 p. (In Russian)

2. Vilenkin N. Ya., Vilenkin A. N., Vilenkin P. A. Kombinatorika [Combinatorics]. Moscow, FIMA, MTsNMO Publ., 2013. 400 p. (In Russian)

3.Vygodskii M. Ya. Spravochnik po elementarnoi matematike [Handbook of elementary mathematics]. Moscow, Nauka Publ., 1986. 320 p. (In Russian)

4. Ignatushina I. V. Mnozhestva, kortezhi, elementy kombinatoriki [The sets, tuples, elements of combinatorics]. Orenburg, OGPU Publ., 2008. 31 p. (In Russian)

5. Ignatushina I. V. Sbornik zadach к uchebno-metodicheskomu posobiyu "Elementy kombinatoriki, teorii veroyatnostei i matematicheskoi statistiki" [Collection of problems for teaching aids "Elements of combinatorics, probability theory and mathematical statistics"]. Orenburg, OGPU Publ., 2006. 58 p. (In Russian)

6. Ignatushina I. V. Elementy kombinatoriki, teorii veroyatnostei i matematicheskoi statistiki [Elements of combinatorics, probability theory and mathematical statistics]. Orenburg, OGPU Publ., 2005. Ill p. (In Russian)

7. Lebedev V. V. Effektivnoe obuchenie kombinatorike i teorii veroyatnostei [Effective teaching of combinatorics and probability theory]. Shkol'nye tekhnologii, 2012, no. 2, pp. 126—134. (In Russian)

8. MePnikov R. A. Iz istorii kombinatoriki [From the history of combinatorics]. Vestnik Eletskogo gosudarstvennogo universiteta im. 1. A. Bunina, 2011, is. 28: Ser. "Pedagogika" (Istoriya i teoriyamatematicheskogo obrazovaniya), pp. 30—32. (In Russian)

9. FederaVnyi gosudarstvennyi obrazovatel'nyi standart osnovnogo obshchego obrazovaniya. Utverzhden prikazom Ministerstva obrazovaniya i nauki Rossiiskoi Federatsii ot 17 dekabrya 2010 g. № 1897 [Federal state educational standard of general education approved by the Order of RF Ministry of Education and Science of December 17, 2010, no. 1897]. Available at: http://минобрнауки.рф/документы/938. (In Russian)

10. Shikhova A. P. Obuchenie kombinatorike i ее prilozheniyam v srednei shkole [Teaching combinatorics and its applications in high school]. Kirov, IUU Publ., 1994. 63 p. (In Russian)

11. Shcherbatykh S. V. Aktualizatsiya problemy formirovaniya stokhasticheskogo myshleniya u starsheklassnikov [Actualization of problems of forming stochastic thinking in senior high students]. Vestnik Bryanskogo gosudarstvennogo universiteta — The Bryansk State University Herald, 2013, no. 1, pp. 148—150. (In Russian)