Размещения и их свойства

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

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

МИНОБРНАУКИ РОССИИ

Федеральное государственное автономное образовательное

учреждение высшего образования

«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

Институт математики, механики и компьютерных наук

Им. И.И. Воровича

«Размещения и их свойства»

КУРСОВАЯ РАБОТА

по направлению 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:

;

;

;

;

И т.д.

.

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

Выводы к главе 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. Сколько существует пятизначных чисел с разными цифрами?

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

Воспользуемся формулой (2):

.

Мы могли воспользоваться формулой (1) и сразу получить

Ответ. пятизначных чисел.

Пример 3. Сколькими способами можно расставить 17 книг на 3 книжных полках?

Решение: Воспользуемся формулой (2):



.

Ответ. 4080 способами.

Пример 4. Сколько можно составить трехзначных чисел из цифр 0,4,5,6,7,9, кратных 5? Кратных 2?

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

Посчитаем числа, последней цифрой которых будет 0, для этого зафиксируем его на последнем месте. В этом случае мы получаем размещения из 5 по 2.

Найдем количество чисел, оканчивающиеся на 5. Аналогично получаем число размещений из 5 по 2.

Суммируем полученные числа и отнимаем от суммы (количество чисел с 0 на месте первой цифры).

.

б). Чтобы получить числа, кратные 2, нужно, чтобы последняя цифра у них была четной. Нам даны 6 цифр, 3 из которых четные, т.е.:

.

Ответ. а) 20 чисел; б) 40 чисел.

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

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

.

Ответ. 1008 способов.

Замечание! Сочетанием из n по k называется k-элементное подмножество n-элементного множества. Число сочетаний без повторений вычисляется по формуле: .

2.2 Задачи на размещения с повторениями

Пример 1. Множество Р={2,4,5}. Перечислите все размещения этого множества по 2 с повторениями.

Решение: <2,2>,<2,4>,<4,2>,<2,5>,<5,2>,<4,4>,<4,5>,<5,4>,<5,5>.

Мы можем проверить себя, вычислив число данных размещений, воспользовавшись формулой (3):

.

Число размещений, которое мы получили, равно 9.

Ответ. <2,2>,<2,4>,<4,2>,<2,5>,<5,2>,<4,4>,<4,5>,<5,4>,<5,5>.

Пример 2. Сколько пятизначных чисел мы можем получить из цифр 2,4,9?

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

.

Ответ. 243 числа.

Пример 3. Сколько трехзначных чисел, кратных 5, можно составить из цифр 0,1,4,5,8 (цифры могут повторяться)? А кратных 2?

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

.

Мы могли посчитать это другим способом. Нам необходимо получить трехзначное число, кратное 5, т.е. на первое место мы можем поставить 1 из 4 цифр (все, кроме 0), на второе - 1 из 5 цифр и на третье - 1 из 2 цифр (0 или 5), т.е.:

.

Вычислим количество чисел, кратных 2. На первом месте у нас может стоять любая цифра, кроме 0, т.е. , на втором - любая из пяти цифр, т.е. , и на третьем месте может стоять 0,4 и 8, т.е. . Тогда искомое число мы можем вычислить следующим образом:

.

Ответ. 40 чисел, кратных 5; 60 чисел, кратных 2.

Пример 4. Сколько двузначных чисел можно составить из четных цифр, исключая 0.

Решение: {2,4,6,8}, n=4.

.

Ответ. 16 чисел.

Пример 5. В автобусе по маршруту №210 сидит 6 пассажиров. До конечной осталось 10 остановок. Сколькими способами пассажиры могут выходить из автобуса на каждой остановке, начиная с 10 с конца?

Решение: 6 пассажиров, т.е. n=6; осталось 10 остановок и конечная, т.е. в сумме 11, т.е. k=11. Распределим 6 пассажиров по 11 остановкам. Пассажиры могут выходить как по одному, так и все вместе, т.е. будем искать число размещений с повторениями:

.

Ответ. 177156 способами.

Пример 6. Сколькими способами можно разместить 4 кресла по трем комнатам дома, если каждая из комнат может вместить все 4?

.

Ответ. 81 способом.

Выводы к главе 2

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



Заключение

В ходе исследования темы «Размещения» были изучены и проанализированы найденные исторические сведения и теоретический материал, благодаря чему было выявлено, что комбинаторика формируется и развивается в течение уже очень долгого времени. Ее история насчитывает много веков. Хотя в качестве раздела науки она начала развиваться сравнительно недавно. Значительный вклад в ее развитие внесли известные ученые-математики, такие как Паскаль, Лейбниц, Бернулли, Эйлер и многие другие задолго до них, к примеру, в Древней Греции и Индии.

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

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

К тому же, как уже говорилось ранее, комбинаторика достаточно популяризованная наука на данный момент. Так, к примеру, в книге Н. Я. Виленкина «Популярная комбинаторика» (1975 г.) [6] научно-популярным, доступным и понятным языком рассказывается история возникновения комбинаторики, ее основы, а также в книге представлены комбинаторные задачи. В целом ее можно считать очень понятным учебником по комбинаторике с подробной и интересной исторической справкой. На примере этой книги можно показать, что популяризация комбинаторики проходит достаточно успешно. Кроме того это наука действительно интересна не только для ученых, но и для людей не вовлеченных в науку тоже.

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



Список литературы

http://hijos.ru/izuchenie-matematiki/algebra-10-klass/18-kombinatorika-razmeshheniya-perestanovki-sochetaniya/

Айгнер М. Комбинаторная теория. М.: Мир, 1982.

Андерсон, Джеймс. Дискретная математика и комбинаторика = Discrete Mathematics with Combinatorics. -- М.: «Вильямс», 2006. -- С. 960. -- ISBN 0-13-086998-8.

Белешко Дмитрий Дискретная математика: алгоритмы.- СПб: Изд-во СПбНИУ ИТМО, 2004.

Бородин А.И., Бугай А.С. Биографический словарь деятелей в области математики. Киев: Ряданська школа, 1979.

Виленкин Н. Я. Популярная комбинаторика . -- М.: Наука, 1975.

Грэхем Р., Кнут Д., Паташник О. Конкретная математика. М.: Мир, 1998.

Ерош И. Л. Дискретная математика. Комбинаторика -- СПб.: СПбГУАП, 2001. -- 37 c.

Ерусалимский Я. М. Дискретная математика: теория, задачи, приложения. 10-е изд., перераб. и доп.- М.: Вузовская книга, 2009, 288 с.

История математики с дрвнейших времён до начала XIX столетия / Под ред. А.Н. Колмогорова, А.П. Юшкевича. М: Наука, 1970-1972. T.1-3.

Клейн Ф. Лекции о развитии математики в XIX столетии. М.: Наука, 1989.

Липский В. Комбинаторика для программиста. -- М.: Мир, 1988. -- 213 с.

Райгородский А. М. Линейно-алгебраические и вероятностные методы в комбинаторике . -- Летняя школа «Современная математика». -- Дубна, 2006.

Раизер Г. Дж. Комбинаторная математика. -- пер. с англ. -- М., 1966.

Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. -- М.: Мир, 1980. -- 476 с.

Риордан Дж. Введение в комбинаторный анализ. -- пер. с англ. -- М., 1963.

Романовский И.В. Дискретный анализ. -- 3-е изд. -- СПб: Невский Диалект; БХВ Петербург, 2003.

Рыбников К.А. Введение в комбинаторный анализ.- М.: Изд-во МГУ, 1985

Рыбников К.А. История математики. М.: МГУ, 1994.

Сачк пов В.Н Введение в Комбинаторные методы дискретной математики.- М.: Наука, 1982

Стенли Р. Перечислительная комбинаторика = Enumerative Combinatorics. -- М.: «Мир», 1990. -- С. 440. -- ISBN 5-03-001348-2.

Стенли Р. Перечислительная комбинаторика. Деревья, производящие функции и симметрические функции = Enumerative Combinatorics. Volume 2. -- М.: «Мир», 2009. -- С. 767. -- ISBN 978-5-03-003476-8.

Степанов В. Элементы комбинаторики.- СПб., 2004.

Холл М. Комбинаторика.- М.: Мир, 1970

Яблонский С.В. Введениев дискретную математику: Учеб. Пособие для вузов.- 2-е изд., перераб. И доп.- М.: Наука, 1986. Гл. ред. Физ.-мат. аЛит.- 384 с..

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