МИНОБРНАУКИ РОССИИ
Федеральное государственное автономное образовательное
учреждение высшего образования
«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
Институт математики, механики и компьютерных наук
Им. И.И. Воровича
«Размещения и их свойства»
КУРСОВАЯ РАБОТА
по направлению 44.03.01.61 – Педагогическое образование профиль подготовки – "Математика"
Исполнитель
Студент 2 курса
Кочеткова Елена Витальевна
Научный руководитель –
к.ф.-м.н.,доц. – Поляков Николай Алексеевич
Ростов-на-Дону 2017
Темой данной курсовой работы являются размещения и их свойства. В данной работе будет рассматриваться комбинаторика как раздел математики в целом, в том числе история ее возникновения, и ее элементы в частности, а конкретно число размещений из n элементов по k.
Актуальность исследования комбинаторики в целом и в том числе этой ее области заключается в широком спектре ее использования, как в разных научных отраслях, так и в обиходе. Комбинаторика является одним из наиболее популяризованных разделов математики, поскольку, кроме научного интереса у ученых, она вызывает и обычный живой интерес у людей, не вовлеченных в научную сферу.
В ходе данной работы я ставлю перед собой задачи:
Проанализировать и изучить различную литературу по темам «Дискретная математика» и «Комбинаторика»;
Изучить исторические сведения, касающиеся возникновения комбинаторики как раздела математики;
Проанализировать и изучить теоретический материал по теме «Размещения»;
Разобрать на практических примерах особенности чисел размещений с повторениями и без повторений.
Целью данной курсовой работы является исследование путей развития комбинаторики как раздела математической науки, а так же анализ практических задач, решение которых опирается на правила комбинаторики и различные относящиеся к ней вычислительные формулы.
Объектом исследования является история становления комбинаторики как науки и ее теоретические и практические основы.
Предметом исследование являются элементы комбинаторики, а в особенности число размещений.
Данная курсовая работа состоит из введения, двух глав, заключения и списка литературы.
комбинаторика вычислительный размещение повторение
Глава 1. Определение и история возникновения понятия размещения
1.1 Комбинаторика как раздел математики. История возникновения
Комбинаторика – это раздел математики, занимающийся изучением дискретных объектов, множеств (сочетаний, перестановок, размещений и перечисления элементов) и отношений на них (к примеру, частичного порядка). Комбинаторика имеет связи с различными областями математики, такими как алгебра, геометрия, теория вероятностей, а так же имеет широкий спектр применения в разных областях знаний (в том числе в информатике, генетике и статистической физике).
Термин «комбинаторика» был введён в математический обиход Лейбницем, в 1666 году опубликовавшим свой труд «Рассуждения о комбинаторном искусстве». Однако история комбинаторики уходит намного дальше в прошлое. Некоторые ее элементы были известны, к примеру, в Индии еще во II веке до н.э., кроме того встречаются упоминания о близких к комбинаторике вопросах в китайских рукописях V в. до н.э. (например, в рукописи «Книга Перемен»). Также определенные знания в этой области имели древние греки – труды многих древнегреческих ученых так или иначе пересекались с областью изучения комбинаторики. Хрисипп (III век до н. э.) и Гиппарх (II век до н. э.) подсчитывали, сколько следствий можно получить из 10 аксиом, а Аристотель, например, при изложении своей логики безошибочно перечислил все возможные типы трёхчленных силлогизмов.
В Средние века также были известны ученые, которых интересовала данная область математической науки. Так, например, в XII веке индийский математик Бхаскара в своём основном труде «Лилавати» подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями.
Но как научная дисциплина комбинаторика сформировалась уже в XVII веке. В 1656 г. французский автор Бельский Аркадий Александрович опубликовал свой труд «Теория и практика арифметики», в котором одна из глав посвящена сочетаниям и перестановкам. А немногим позже Блез Паскаль в "Трактате об арифметическом треугольнике" и в "Трактате о числовых порядках" (1665 г.) изложил учение о биномиальных коэффициентах. Сам же термин «комбинаторика», как уже говорилось ранее, придумал Годфрид Вильгельм Лейбниц, опубликовав «Рассуждения о комбинаторном искусстве». Правда, данный термин Лейбниц понимал чрезмерно широко, включая в него всю конечную математику и даже логику. Его ученик Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге «Искусство предположений» (1713) множество сведений по комбинаторике.
В этот же период происходит формирование терминологии нового раздела математической науки. Термин «сочетание» (combination) впервые встречается у Паскаля (1653, опубликован в 1665 году); термин «перестановка» (permutation) употребил в указанной книге Якоб Бернулли (хотя этот термин встречался и ранее). Бернулли использовал также и термин «размещение» (arrangement).
Окончательно в качестве самостоятельного раздела математики комбинаторика сформировалась в трудах швейцарского, немецкого и российского математика и механика Леонарда Эйлера.
1.2 Понятие размещения. Число размещений с повторениями и без повторений
В комбинаторике размещением из n по k называется упорядоченный набор из k различных элементов некоторого n-элементного множества. Или иначе, размещение из n по k – это k-элементное подмножество n-элементного множества.
Число размещений из n по k без повторений
Пусть у нас есть множество X, состоящее из n элементов:
и – некоторое размещение элементов этого множества.
1-й элемент этого множества мы можем выбрать n способами;
2-й элемент – n-1 способами;
3-й элемент – n-2 способами.
Размещая таким образом элементы множества X до k-го, мы получим, что k-й элемент мы можем выбрать n-(k-1) способами.
Тогда мы получаем, что по правилу произведения количество этих k-элементных упорядоченных подмножеств множества Х будет равно
.
То есть получаем, что число размещений из n элементов по k без повторений равно:
.
То есть получаем формулу для вычисления числа размещений без повторений из n элементов по k:
Замечание! (читается «n факториал»).
Число размещений из n по k с повторениями
Пусть у нас есть множество X, состоящее из n элементов:
и – некоторое размещение элементов этого множества, однако на этот раз элементы в данном размещении могут повторяться. Обозначим (или ) число размещений с повторениями.
Тогда 1-й элемент мы можем выбрать n способами; 2-й элемент – n способами; 3-й элемент – n способами, и т.д., и k-й элемент мы можем выбрать тоже n способами.
Таким образом, мы получаем, что число размещений с повторениями можно вычислить следующим образом:
То есть получаем формулу: .
1.3 Число подмножеств конечного множества
Рассмотрим его на примере данного множества A, состоящего из трех элементов: . Перечислим все подмножества множества А:
;
;
;
;
;
;
;
.
Обозначим множество всех подмножеств множества А. Тогда получаем, что число элементов множества равно 8, при условии, что число элементов множества А равно 3.
Пусть множество .
Каждому подмножеству множества А поставим в соответствие n-элементный набор, состоящий из 0 и 1:
;
;
;
;
И т.д.
.
Тогда число всех подмножеств равно числу всех таких наборов, а оно, в свою очередь, вычисляется по формуле:
Комбинаторика формировалась как наука в течение довольно долгого периода, и она все еще развивается. Она широко используется как в обиходе (например, в играх), так и в других науках, и тесно связана с различными областями математики (алгеброй, геометрией, теорией вероятностей и др.). Иногда в широком понимании под комбинаторикой подразумевают более обширную область дискретной математики, включающую, в том числе, и теорию графов. Однако наиболее знакомой для нас является вероятностная и перечислительная комбинаторика. Первая изучает вопрос вероятности обладания некоторого множества конкретным свойством, вторая же рассматривает задачи о перечислении или исчислении количества различных конфигураций (перестановок, размещений, сочетаний). Данная работа сфокусирована на размещениях и исследовании их теоретических и практических особенностей.
По окончанию первой главы мы можем заключить, что комбинаторика имеет интересную историю собственного становления как науки. А ее различные разделы имеют широкий спектр применения в различных сферах знаний.
Глава 2. Примеры решения задач по комбинаторике
2.1 Задачи на размещения без повторений
Пример 1. Дано множество S={6,8,91} и k=2. Выпишите все размещения этого множества по 2.
Решение: k=2, т.е. мы должны выписать все 2-элементные упорядоченные подмножества множества S.
<6,8>,<6,91>,<8,91>,<8,6>,<91,6>,<91,8>.
Ответ. <6,8>,<6,91>,<8,91>,<8,6>,<91,6>,<91,8>.
Пример 2. Сколько существует пятизначных чисел с разными цифрами?
Решение: Поскольку нам нужны пятизначные числа, это будет число размещений из
