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

Формулу для получаем из выражения (2) при :

. (3)

Пример 3. Сколькими способами можно посадить на скамейку 9 человек?

Ответ: =9!=362880.

К перестановкам с повторениями приводит следующая задача.

Имеется -множество , состоящее из различных элементов ( ). Сколько перестановок можно сделать из элементов первого типа, элементов второго типа,…, элементов -го типа?

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

, (4)

где .

Пример 4. Сколько перестановок можно сделать из букв слова «Миссисипи»?

В данном случае , («М»), («и»), («с»), («п»). По формуле (4)

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

Сколько -элементных подмножеств с различными элементами можно составить из элементов -множества ?

Такие подмножества называют сочетаниями без повторений из элементов по или короче -сочетаниями, а их число обозначают (от французского слова combinaison – сочетание). Другими словами, сочетаниями без повторений называется неупорядоченная -выборка, в которой элементы не повторяются.

Формулу для числа сочетаний легко получить из формулы (2) для числа размещений. Выберем какое-нибудь -элементное подмножество . Его можно упорядочить способами, а число таких подмножеств есть . Тогда справедлива формула

, (5)

откуда

. (6)

Пример 5. Сколько всего партий играется в шахматном турнире с участниками?

Ответ: , так как каждая партия однозначно определяется двумя ее участниками.

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

,

где – мощность мультимножества.

---

Число мультимножеств мощности , составленных из элементов -множества , называют сочетаниями с повторениями и обозначают . Другими словами, сочетаниями с повторениями называется неупорядоченная -выборка, в которой элементы могут повторяться.Зашифруем каждую комбинацию из элементов с помощью нулей и единиц: для каждого типа напишем столько единиц, сколько элементов этого типа входит в комбинацию, а различные типы отделим друг от друга нулями. Если элементы какого-нибудь типа не вошли в комбинацию, то надо писать два или большее число нулей. При этом получим единиц и нулей. Тогда число будет равно числу перестановок с повторениями из единиц и нулей: . Так как , то. (7)Встречаются задачи, в которых на сочетания с повторениями налагается дополнительное условие – в них обязательно должны входить элементы фиксированных типов . В этом случае . В частности, если и требуется, чтобы в -подмножество с повторениями входил по крайней мере один элемент каждого из типов , то получим мультимножеств.Пример 6. В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?Решение. Мощность мультимножества , число различных элементов . Число способов покупки пирожных равно .9. Свойства чисел C k/n. Треугольник Паскаля.Числа обладают целым рядом замечательных свойств, которые выражают различные соотношения между -подмножествами -множества .1) .2) .3) .Это свойство можно доказать также формально, используя формулу (6).При имеем . Так как , то полагают . Кроме того, придерживаются соглашения при . Тогда свойство 3) позволяет последовательно вычислить числа при . Вычисления представляют в виде треугольника Паскаля. Этот треугольник имеет вид:11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1……………………………………………..10. Задача о беспорядках.Сколькими способами можно разместить элементов множества в ячеек множества (по одному в каждой) так, чтобы никакой элемент не попал в ячейку ?Перестановку без повторений можно представить как биекцию множества на себя:.Перестановку называют беспорядком, если в ней каждый элемент стоит не на своем месте, то есть , .Задача о беспорядках состоит в том, чтобы подсчитать число перестановок-беспорядков. Например, , . Обозначим через множество все перестановок , в которых элемент стоит на -ом месте:

---

.Множество состоит из перестановок, в которых хотя бы один элемент стоит на своем месте, а все остальные перестановки будут беспорядками. Тогда по формуле обращения. (8)Подсчитаем число перестановок в каждом из множеств и в их пересечениях. Если , то сужение отображения на множество является биекцией этого множества на себя. Следовательно, .Множество составлено из перестановок , в которых , . Сужение отображения на множество является биекцией этого множества на себя. Следовательно, .По индукции находим, что .По формуле включений и исключенийВ каждой из этих сумм слагаемые не зависят от индекса суммирования, поэтому для вычисления надо знать только их количество. В первой сумме слагаемых, число слагаемых во второй сумме равно количеству всевозможных пар , которые можно составить из индексов , то есть . Аналогично в -ой сумме имеем слагаемых. Отсюда.После подстановки в уравнение (8) и несложных преобразований находим.Выражение, стоящее в скобках, представляет собой частичную сумму ряда, сходящегося к , поэтому . Можно показать, что равно целому числу, ближайшему к : , где – целая часть числа .11. Определение рекуррентного соотношения, его частного и общего решения. Примеры: числа Фибоначчи, число правильных n -разрядных двоичных слов, задача о расстановке скобок в выражении с неассоциативной бинарной операцией.Рекуррентным соотношением -го порядка между элементами последовательности чисел называется формула вида(1)Частным решением рекуррентного соотношения является любая последовательность , обращающая соотношение (1) в тождество. Соотношение (1) имеет бесконечно много частных решений, так как первые элементов последовательности можно задать произвольно. Например, последовательность является решением рекуррентного соотношения , так как имеет место тождество .Решение рекуррентного соотношения -го порядка называется общим , если оно зависит от произвольных постоянных , и путем подбора этих постоянных можно получить любое решение данного соотношения. Например, для соотношения(2)общим решением будет. (3)Действительно, легко проверить, что последовательность (3) обращает соотношение (2) в тождество. Поэтому надо только показать, что любое решение соотношения (2) можно представить в виде (3). Но любое решение этого соотношения однозначно определяется значениями и . Поэтому надо доказать, что для любых чисел и найдутся такие значения и , что

---

Так как эта система имеет решение при любых значениях и , то решение (3) действительно является общим решением соотношения (2).Пример 1.Числа Фибоначчи. Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов?Из условия задачи следует, что через месяц будет две пары кроликов. Через два месяца приплод даст только первая пара кроликов, и получится 3 пары. A еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов и т. д.Обозначим через количество пар кроликов по истечении месяцев с начала года. Тогда через месяцев будут эти пар и еще столько новорожденных пар кроликов, сколько было в конце -го месяца, то есть еще пар. Таким образом, имеет место рекуррентное соотношение. (4)Так как , то последовательно находим: и т. д. Эти числа составляют последовательность1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,…,которую называют рядом Фибоначчи, а его члены – числами Фибоначчи. Найти число двоичных слов длины , в которых никакие две единицы не идут подряд.Будем называть такие слова правильными и обозначим их число через . Разобьем множество этих правильных слов на два класса: слова, оканчивающиеся на ноль, и слова, оканчивающиеся на единицу. Обозначим количество слов в этих классах и соответственно. По правилу сложения (5)Очевидно, что у слова, оканчивающегося на ноль, первые символов образуют правильное слово длины , или другими словами, имеется биекция между множеством правильных слов длины , оканчивающихся на ноль, и множеством правильных слов длины , то есть .Если правильное слово длины оканчивается на единицу, то предыдущий символ этого слова должен быть нулем, а первые символа должны образовывать правильное слово длины . Как и в предыдущем случае, снова имеем биекцию между множеством правильных слов длины , оканчивающихся на единицу, и множеством правильных слов длины . Следовательно. . Из формулы (5) получаем рекуррентное соотношение. (6)Для использования рекуррентного соотношения необходимы для данного вычисления всех предыдущих значений. Например, если нам нужно знать количество правильных слов из 10 символов, то его можно найти, последовательно заполняя следующую таблицу:

---

Таблица 1

	1	2	3	4	5	6	7	8	9	10
	2	3	5	8	13	21	34	55	89	144

Первые два значения находятся непосредственно ( – слова 0 и 1; – слова 000, 010, 101), а остальные – по формуле (6).Пример 2.Задача о расстановке скобок в выражении с неассоциативной бинарной операцией.Пусть “ ” обозначает некоторую бинарную операцию. Рассмотрим выражение , в котором символ обозначает некоторую бинарную неассоциативную операцию. Сколько имеется различных способов расстановки скобок в этом выражении?Как пример неассоциативной операции можно привести векторное произведение. Другой пример – обычное сложение и умножение, выполняемое на компьютере. В силу того, что представление каждого числа в памяти компьютера ограничено определенным количеством разрядов, при выполнении каждой операции возникает погрешность и суммарный результат этих погрешностей зависит от расстановки скобок. Пусть – машинный ноль. Это означает, что . Тогда , в то время как .Обозначим число всевозможных способов расстановки скобок через . Тогда; .Назовем операцию условно произведением. Для произвольного разобьем все способы расстановки скобок на классы, включив в -ый класс способы, при которых сначала вычисляется произведение первых и последних операндов с какой-то расстановок скобок, а потом вычисляется их произведение:(7)где .По определению количество способов расстановки скобок для вычисления первых операндов равно , последних – . По правилу произведения число расстановок скобок для выражения (4) равно . По правилу сложения, (8)Например, .12. Линейные рекуррентные соотношения с постоянными коэффициентами.

---

Смотрите также файлы

• Компоненты интегрированной среды разработки программ.docx

• Доклад по теме самообразования Развитие творческих способностей на уроках в начальной школе.docx

• Инструкция по охране труда для учителя физики. Инструкция по охране труда и технике безопасности для лаборанта кабинета физики.odt

• Учебное пособие Москва 2021 Одобрено редакционноиздательским советом Академии управления мвд россии Рецензенты.pdf

• Изучение технологии и оборудования шовной контактной сварки (на примере машины мш1601).docx