Курсовая теория на тему Комбинаторика

Содержание:

Введение. 3

1.Базовые определения. 4

2. Комбинаторные принципы.. 18

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

Заключение. 29

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

Введение:

Комбинаторика или
комбинаторная математика — это раздел математики, который занимается счетом
вещей. Задачи, связанные с комбинаторикой, изначально изучались математиками из
Индии, Аравии и Греции. Некоторые из выдающихся математиков, изучавших эти
проблемы, — это Блез Паскаль, Леонард Эйлер и Якоб Бернулли. Хотя комбинаторика
полезна во многих других областях математики, однако наиболее известными из них
являются кодирование, криптография, теория графов и вероятность.

Можно сказать, что
комбинаторика — это математика расстановки и подсчета элементов множества. Мы
знаем, что подсчет объектов прост, однако комбинаторика полезна для подсчета
количества или расположения, которые слишком сложны, если они подсчитываются
традиционным способом.

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

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

Заключение:

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

Иногда говорят, что
комбинаторика — это раздел математики, который занимается счетом; и это правда,
но не в том смысле, в котором вы научились считать в детском саду. Хотя
комбинаторика занимается нумерацией и выяснением количества членов в наборах,
она предназначена для поиска способов сделать это без фактического,
потенциально утомительного подсчета.

Перечисление — это способ
подсчета, который включает в себя организацию предметов для подсчета в полный и
систематизированный список.

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

Перестановки мало чем
отличаются от комбинаций, но здесь набор, который вы выбираете, представляет
собой упорядоченный набор или список без повторений. (В комбинаторике мы
определяем список как упорядоченную последовательность объектов). Если вы
выбираете не просто трех студентов, например, но президента студенческого
совета, вице-президента и секретаря, вы выбираете упорядоченный список и
работаете с перестановками.

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

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

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

Важные обозначения в комбинаторике

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

Это n k такое
же, как n k, с которым вы привыкли работать в алгебре:
n 4 = n * n * n * n

(n) k подсчитывает
количество списков с k элементами — без повторений — взятых из набор из n
элементов (подумайте о перестановках).

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

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

Фрагмент текста работы:

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

Первые комбинаторные
задачи изучали математики Древней Индии, Арабской и Греции. Интерес к
этому предмету возрос в XIX и XX веках, вместе с развитием теории
графов и таких проблем, как теорема о четырех
цветах. Среди ведущих математиков — Блез Паскаль (1623–1662), Якоб
Бернулли (1654–1705) и Леонард Эйлер (1707–1783).

Некоторые типы
комбинаторных задач привлекали внимание математиков с давних времен. Например,
магические квадраты, представляющие собой квадратные массивы чисел со
свойством, что строки, столбцы и диагонали складываются в одно и то же число,
встречаются в И Цзин, китайской книге, датируемой XII веком ДО нашей ЭРЫ .
Биномиальные коэффициенты, или целые коэффициенты в разложении ( a + b ) n ,
были известны индийскому математику XII века.Бхаскара , который в своей «
Лилавати» (« Милостивый »), посвященной красивой женщине, дал правила их
расчета вместе с наглядными примерами. «Треугольник Паскаля», треугольный
массив биномиальных коэффициентов, преподавал персидский философ 13-го века
Накир ад-Дин ат-Туси [11].

На Западе можно считать,
что комбинаторика началась в 17 веке с Блеза Паскаля и Пьера де Ферма , оба из
Франции, которые открыли многие классические комбинаторные результаты в связи с
развитием теории вероятностей . Термин комбинаторный впервые был использован в
современном математическом смысле немецким философом и математиком Готфридом
Вильгельмом Лейбницем в его Dissertatio de Arte Combinatoria («Диссертация о
комбинированных искусствах»). Он предвидел применение этой новой дисциплины во
всем диапазоне наук. Швейцарский математик Леонард Эйлер был, наконец,
ответственен за развитие школы аутентичной комбинаторной математики, начиная с
18 века. Он стал отцом теории графов, когда решил проблему Кенигсбергского
моста , и его знаменитая гипотеза о латинских квадратах не была решена до 1959
года.

В Англии Артур Кэли в
конце XIX века внес важный вклад в теорию перечислительных графов, а Джеймс
Джозеф Сильвестр открыл много комбинаторных результатов. Британский математик
Джордж Буль примерно в то же время использовал комбинаторные методы в связи с
развитием символической логики, а также комбинаторные идеи и методы Анри
Пуанкаре , которые развились в начале 20 века в связи с проблемой n тел. ,
привели к дисциплине топологии, который занимает центральное место в
математике. Многие комбинаторные проблемы были поставлены в 19 веке как чисто
развлекательные и идентифицированы под такими названиями, как «проблема восьми
королев» и «проблема школьницы Киркман». С другой стороны, изучение тройных
систем, начатое Томасом П. Киркманом в 1847 году и продолженное Якобом
Штайнером, немецким математиком швейцарского происхождения, в 1850-х годах
стало началом теориидизайн . Среди первых книг, посвященных исключительно комбинаторике,
— Lehrbuch der Combinatorik (1901; «Учебник комбинаторики») немецкого
математика Ойгена Нетто и « Комбинаторный анализ» британского математика Перси
Александра Мак-Магона (1915–16), которые дают представление о комбинаторной
теории как таковой. существовало до 1920 года [22].

Многие факторы
способствовали ускорению темпов развития комбинаторной теории с 1920 года.
Одним из них было развитие статистической теории планирования экспериментов
английскими статистиками Рональдом Фишером и Фрэнком Йейтсом, породившее
множество проблем комбинаторной теории. интерес; методы, изначально
разработанные для их решения, нашли применение в таких областях, как теория
кодирования. Теория информации, зародившаяся примерно в середине века, также
стала богатым источником комбинаторных проблем совершенно нового типа.

Еще один источник
возрождения интереса к комбинаторике — это теория графов, важность которой
заключается в том, что графы могут служить абстрактными моделями для множества
различных схем отношений между множествами объектов. Его приложения
распространяются на исследования операций, химию, статистическую механику ,
теоретическую физику и социально-экономические проблемы. Теорию транспортных
сетей можно рассматривать как раздел теории ориентированных графов. Одна из
самых сложных теоретических проблем, проблема четырех цветов, относится к
области теории графов. Он также имеет приложения к таким другим разделам
математики, как теория групп [3,c.122].

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

Статистическая механика —
один из старейших и наиболее продуктивных источников комбинаторных задач. С
середины 20-го века прикладными математиками и физиками была проделана
значительная комбинаторная работа — например, работа над моделями Изинга.

В чистой математике
комбинаторные методы успешно используются в таких различных областях, как
вероятность, алгебра (конечные группы и поля, матрица и теория решеток), теория
чисел (разностные множества), теория множеств (теорема Спернера) и
математическая логика (теория Рамсея). теорема) [25].

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

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

Комбинаторика — это
количество способов выбора некоторых объектов из коллекции и / или количество
способов их расположения. Например, предположим, что в клубе пять членов,
предположим, что есть имена A, B, C, D и E, и один из них должен быть выбран в
качестве координатора. Очевидно, что можно выбрать любой из них, поэтому
существует 5 способов. Теперь предположим, что на должности координатора и
сокоординатора должны быть выбраны два члена. Теперь мы можем выбрать А в
качестве координатора и одного из остальных 4 в качестве координатора. Точно
так же мы можем выбрать B в качестве координатора и одного из оставшихся 4 в качестве
координатора, и аналогично с C, D и E. Таким образом, всего будет 20 возможных
способов [17,c.90].

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

В первом примере мы
должны найти перестановку выбора 2 членов из 5, а во втором — найти комбинацию
выбора 2 членов из 5.

Давайте обобщим
это. Варианты выбора удаленных объектов R из коллекции
объектов N можно вычислить по следующей формуле:

NPR= fracN!(NR)!

Комбинации выбора
отдельных объектов R из коллекции объектов N можно
вычислить по следующей формуле: $$$ ^ NC_R = \ frac {N!} {(NR)! \ times
R!} $$$R отдаленные объекты из коллекции N объекты можно
рассчитать по следующей формуле:

NPR=N!(N−R)!

Комбинации
выбора R отдельные объекты из коллекции N объекты можно
рассчитать по следующей формуле:

NCR=N!(N−R)!×R!

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

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

Давайте перечислим
возможности — в этом примере 3 разных ученика
представлены стульями трех разных цветов.