Методическое пособие по курсу
“Основы математической лингвистики”
Комбинаторика
Пусть требуется выполнить одно за другим какие-либо m действий. Если первое действие можно выполнить 
способами, второе действие – 
способами и так до m -го действия, которое можно выполнить 
способами, то все m действий могут быть выполнены 
способами. Это называется правилом произведения.
Пусть требуется выполнить одно из каких-либо m действий, взаимно исключающих друг друга. Если первое действие можно выполнить способами, второе действие – способами и так до m -го действия, которое можно выполнить nm способами, то выполнить одно из этих m действий можно 
способами. Это называется правилом суммы.
Рассмотрим некоторое множество S, состоящее из n различныхэлементов. Пусть 
. Назовём множество, состоящее из k элементов, упорядоченным, если каждому элементу этого множества поставлено в соответствие число от 1 до k, причём различным элементам множества соответствуют разные числа.
Размещениями из n элементов по k называются упорядоченные подмножества множества S, состоящие из k различных элементов и отличающиеся друг от друга составом элементов или порядком их расположения.
Число размещений из n элементов по k равно:
(1.1)
Размещениями с повторениями из n элементов по kназываются упорядоченные подмножества множества S, состоящие из k элементов, среди которых могут оказаться одинаковые, и отличающиеся друг от друга составом элементов или порядком их расположения. Число размещений с повторениями из n элементов по k равно:
(1.2)
Сочетаниями из n элементов по k называются подмножества множества S, состоящие из k различных элементов и отличающиеся друг от друга только составом элементов. Число сочетаний из n элементов по k равно:
(1.3)
Перестановками из n элементов называются размещения из n элементов по n, т. е. упорядоченные подмножества множества S, состоящие из всех элементов данного множества и отличающиеся друг от друга только порядком их расположения. Число перестановок из n элементов равно:
P n = n! (1.4)
Число перестановок с повторениями из n элементов, в которые первый элемент множества S входит n1 раз, второй элемент – n2 раз и так до m -го элемента, который входит nm раз(n1 + n2 + … + nm = n)равно:
(1.5)
Теперь обратимся к примерам комбинаторных задач, связанных с лингвистикой. В примерах на образование слов нужно понимать, что эти слова являются просто сочетанием букв и могут не иметь смысла. Число комбинаций всюду обозначено через N. Элементы множества записываются в любом порядке, и при этом множество не содержит повторяющиеся элементы.
Пример 1. Сколькими способами можно выбрать две гласные и одну согласную из множества букв слова “ биограф ”?
Гласные образуют множество: {и, а, о}, а согласные - множество: {б, г, р, ф}. Нам нужно выбрать 2 гласные из 3 и 1 согласную из 4. Поскольку нам не важен порядок выбираемых гласных, то следует найти число сочетаний для согласных и гласных по формуле (1.3), а затем по правилу произведения их перемножить:
Пример 2. Сколькими способами можно выбрать три или четыре различные буквы из множества букв слова “ колонна ”?
Слово содержит только 5 различных букв. Поэтому нужно сложить числа сочетаний, вычисленных по (1.3):
Пример 3. Сколько можно составить двухбуквенных слов из букв слова “ скороход ”, если буквы этих слов a) не повторяются, b) могут повторяться?
Множество содержит 6 различных букв. При составлении слов уже важен порядок букв, поэтому тут используется размещение.
a) Это – размещение без повторения (1.1):
b) Это – размещение с повторением (1.2):
Пример 4. Сколькими способами можно переставить буквы в словах “ март ” и “ колобок ”?
В слове “ март ” буквы не повторяются, поэтому применим формулу (1.4):
N = P4 = 4! = 24
В слове “ колобок ” трижды повторяется буква “ о ” и дважды буква “ к”. А “ л ” и “ б ” встречаются по одному разу. Поэтому здесь используется формула (1.5):
Пример 5. Сколькими способами можно переставить слова во фразе “ Мальчик пришёл из школы, сестра была дома ”, чтоб её смысл не изменился?
Эта фраза делится на две синтагмы, разделённые запятой. В каждой синтагме слова (“ из школы ” рассматривается как один элемент) можно переставить друг с другом 3!=6 способами (в русском языке порядок слов в целом свободный). Кроме того, можно переставить и сами синтагмы. В итоге, N=3!3!2!=72.
Пример 6. Сколькими способами можно переставить слова во фразе “ В четверг директор не опоздал на заседание ”, чтоб её смысл не изменился?
Как и в предыдущей задаче, словосочетания “ в четверг ” и “ на заседание” объединяются в один элемент. Частица “ не ” может перемещаться по фразе, но при этом изменяется её смысл, например: “ В четверг не директор опоздал на заседание”, “Не в четверг директор опоздал на заседание”. Поэтому синтагма “ не опоздал ” также объединяется в один элемент. Тогда N=4!=24.
Примеры для самостоятельного решения.
1.1. Сколькими способами можно выбрать две согласные из множества букв слова “ букинист ”?
1.2. Сколькими способами можно выбрать две гласные из множества гласных букв слова “ гипотенуза ”?
1.3. Сколькими способами можно выбрать две гласные и две согласные из множества букв слова “ соревнование ”?
1.4. Сколькими способами можно выбрать три согласных или две гласных из множества букв слова “ библиотека ”?
1.5. Сколько можно составить трёхбуквенных слов из множества букв слова “ караван ”, если буквы этих слов не повторяются?
1.6. Сколько можно составить четырёхбуквенных слов из множества букв слова “ сад ”, если буквы этих слов могут повторяться?
1.7. Сколько можно составить двухбуквенных слов, состоящих только из гласных или только из согласных букв слова “ преобразование ”, если буквы этих слов не повторяются?
1.8. Сколькими способами можно переставить буквы в словах “ Стамбул ” и “ Душанбе ”?
1.9. Сколькими способами можно переставить буквы в слове “ Гаага ”?
1.10. Сколькими способами можно переставить буквы в слове “ Аддис-Абеба ”, не смешивая две части топонима?
1.11. Сколько долгих слогов ((согласный) + краткий гласный + согласный, (согласный) + долгий гласный) можно составить из букв m, n, t, i, o, ā, ū, если допускаются повторения согласных?
1.12. В неогласованном арабском письме не передаются краткие гласные a, i, u. Сколькими способами можно прочесть слово sjd, если известно, что слово не начинается с гласного, сочетание гласных не допускаются, а в начале слова не может быть больше одного согласного?
1.13. Филолог работает над палимпсестом, предполагая два варианта стёршейся письменности и в каждом случае по три варианта чтения для каждой графемы. Сколькими способами можно прочесть стёртую надпись из четырёх графем?
1.14. Согласно закону сингармонизма, в одном (исконном) слове турецкого языка могут находиться гласные только одного из двух рядов: нёбного (e,i,ö,ü) и ненёбного (a,ı,o,u). Сколькими способами можно составить фонетически правильное двухсложное турецкое слово?
1.15. При передаче географических названий на японский язык после согласного, предшествующего другому согласному или стоящего в конце, вставляется u, согласный l передаётся через r. Например, Липецк – Ripetsuku. Установить, сколькими способами можно понять Homurusuku, выделив правильный вариант.
1.16. Из имеющихся 10 иероглифов 2 могут стоять только слева, 5 только справа и 3 с обеих сторон. Сколько сложных слов можно записать с помощью комбинации из двух разных иероглифов?
1.17. В грамматике пять параграфов, причём третий параграф использует данные первого, а четвёртый – данные первых двух. Сколькими способами можно прочесть грамматику, не нарушая логики повествования?
1.18. У существительного 6 значений. Сколькими способами их можно расположить в одной словарной статье?
1.19. У слова 4 именных и 3 глагольных значения. Сколькими способами их можно расположить в одной словарной статье, если именной цикл предшествует глагольному?
1.20. Сколькими способами можно переставить слова во фразе “Он решал пример в комнате, бабушка готовила на кухне, кот спал”, чтоб её смысл не изменился?
1.21. Сколькими способами можно переставить слова во фразе “Ты ручку, наверно, не со стола взял?”, чтоб её смысл изменился?
1.22. Сколькими способами можно переставить слова во фразе “Вернувшаяся домой Маша уже, наверно, спит”, чтоб её смысл и количество запятых не изменились?
1.23. Логаэдом называют строку, содержащую стопы разного типа, следующие в произвольном порядке. Сколькими способами можно составить логаэд из двух ямбических, двух хореических и одной дактилической стопы?
1.24. Сколькими способами можно срифмовать строчки секстины (шестистрочной строфы), произвольно используя три рифмы?
1.25. Сколькими способами можно переставить слова в строчках и сами строчки, чтобы количество слов в строчке не изменилось, и все строчки были срифмованными:
“В лесах грибы растут,
В морях киты плывут,
В речах слова бегут”?