26. Комбинаторика и лингвистические множества. Понятие факториала. Комбинаторика и лингвистические множества.
Языковеду постоянно приходится решать задачи, в которых рассматриваются комбинации и расположения элементов, принадлежащих определенному лингвистическому множеству.
Так, например, синтаксисту важно знать, сколько позиционных вариантов может давать в устно-разговорной речи предложение сегодня идет дождь. Фонетисту и специалисту в области кодирования текста нужно знать, сколько двухбуквенных, трехбуквенных и т.д. комбинаций может дать русский алфавит.
Иногда при этом нужно выяснить, какая часть этих комбинаций образует слова и их формы, использующиеся в современном русском языке. Задачи, в которых требуется ответить на вопрос «сколько?» или «сколькими способами?», называются комбинаторными, а раздел математики, занимающийся решением подобных задач, именуется комбинаторикой.
Комбинаторика (комбинаторный анализ, комбинаторная математика) – раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами.
Простейшие задачи комбинаторики можно решать перебором всех возможных вариантов. Так, например, путем перебора нетрудно установить, что предложение сегодня идет дождь имеет в русской разговорной речи 6 вариантов: сегодня идет дождь; сегодня дождь идет; дождь сегодня идет; дождь идет сегодня; идет сегодня дождь; идет дождь сегодня. Однако число комбинаций быстро растет с увеличением числа составляющих их элементов. Так, например, четыре слова (увы, сегодня, дождь, идет) дают 24, пять слов – 120, шесть – 720 позиционных вариантов и т. д. Не все из этих вариантов допустимы с точки зрения норм современного литературного языка.
Определить допустимые варианты путем простого перебора оказывается зачастую невозможным. Поэтому, сталкиваясь с такими комбинаторными задачами, прибегают к типовым схемам решения, учитывающим лингвистические или какие-либо другие ограничения.
Понятие факториала
Произведение натуральных чисел от единицы до какого-либо данного натурального числа n, то есть 1•2•3•......•n , называется «факториалом» (англ. factorial, от лат. factor – делающий, производящий) и обозначается n!Термин ввёл Л. Арбогаст (1800), обозначение n! –К. Крамп (1808).
27. Размещения, размещения с повторениями
Размещение (из n элементов по k) – соединение, каждое из которых отличается или самим элементом, или их порядком.
В комбинаторике размеще́нием (из n по k) называется упорядоченный набор из k различных элементов из некоторого множества различных n элементов. В отличие от сочетаний, размещения учитывают порядок следования предметов.
Размещение с повторениями или выборка с возвращением — это размещение «предметов» в предположении, что каждый «предмет» может участвовать в размещении несколько раз.
28. Перестановки, перестановки с повторениями. Сочетания.
Перестановка (из n элементов) – соединения, каждое из которых содержит все элементы и отличается от других только порядком их расположения.
Pn = n!
Последовательность длины n, составленная из k разных символов, первый из которых повторяется n1 раз, второй — n2 раз, третий — n3 раз,…, k-й — nk раз (где n1+ n2+ … + nk = n) называется перестановкой с повторениями из n элементов.
Число перестановок с повторениями длины n из k разных элементов, взятых соответственно по n1, n2, …, nk раз каждый обозначается P(n1, n2, …, nk) и равно n! / (n1! n2! … nk!).
Сочетание (из n элементов по k) – соединения, каждое из которых отличается хотя бы одним элементом.
В комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данного множества, содержащего n различных элементов. Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.
Сочетанием с повторениями называются наборы, в которых каждый элемент может участвовать несколько раз.
