 |
Рекуррентные соотношения.
|
|
|
|
· Правило суммы, правило произведения.
Все мы довольно часто говорим «это невероятно», «более вероятно, что…», «это маловероятно», «можно утверждать со стопроцентной вероятностью, что…», когда пытаемся спрогнозировать наступление того или иного события. При этом обычно опираемся на интуицию, жизненный опыт, здравый смысл и т. п. Но очень часто такие приблизительные оценки оказываются недостаточными: бывает важно знать, на сколько или во сколько раз совершение одного случайного события вероятнее другого. Иными словами, нужны точные количественные оценки, надо уметь численно характеризовать возможность наступления того или иного события. Раздел математики, посвященный исследованию количественных оценок случайных событий, называется теорией вероятностей.
Приведем пример, который иллюстрирует все вышесказанные слова.
Пример: [8] На завтрак студент экологического факультета Владимир может выбрать пиццу, бутерброд, пирожок или кекс, а запить их он может кофе, соком или кефиром. Из скольких вариантов завтрака Владимир может выбирать?
Здесь, с помощью прямоугольной таблицы, был осуществлен полный перебор всех возможных вариантов, или, как обычно говорят в таких случаях, всех возможных комбинаций. Поэтому подобные задачи называют комбинаторными.
Этот пример основан на правиле произведения: «Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары объектов (А, В) в указанном порядке можно осуществить 
способами».
Пример: [8] В коридоре висят три лампочки. Сколько имеется различных способов освещения коридора?
Кроме правила произведения при решении комбинаторных задач часто используется правило суммы: «Если некоторый объект А может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать либо А, либо В можно 
способами».
|
|
|
Пример: От Дальнего Засвияжья до Нового города можно проехать по новому и старому мостам через Волгу. В первом случае количество дорог равно 5, а во втором – 3. Сколькими способами можно добраться от Дальнего Засвияжья до Нового города?
При использовании правила суммы надо следить, чтобы ни один из способов выбора объекта А не совпадал с каким-либо способом выбора объекта В. Если такие совпадения есть, то правило суммы утрачивает силу, и мы получаем 
способов выбора, где k – число совпадений.
· Перестановки, сочетания, размещения с повторениями элементов и без повторения.
Комбинаторика изучает количества комбинаций, подчиненных определенным условиям, которые можно составить из элементов заданного конечного множества. Приведем наиболее употребительные формулы комбинаторики.
А) Перестановки.
Перестановками называют комбинации, состоящие из одних и тех же различных элементов и отличающиеся только порядком их расположения.
Сколько всего возможно перестановок из n предметов? Число перестановок обозначают 
, подчеркивая тем самым, что оно зависит от количества предметов n.
Если n =1, то 
.
Если n =2, то 
(АБ и БА).
Если n =3. К каждой из перестановок двух объектов А и Б можно пристроить третий предмет В тремя различными способами: поставить его спереди, между ними либо сзади. Перестановка АБ, таки образом, порождает три перестановки ВАБ, АВБ, АБВ, аналогично БА 
ВБА, БВА, БАВ, и все они – разные. Тогда 
.
Вообще из каждой перестановки n -1 предметов можно получить n дополнительных перестановок, добавляя n -й предмет либо спереди, либо сзади, либо между имеющимися предметами (между n -1 предметами существует n -2 промежутка; 1+1+ n -2= n). Тогда при переходе от n -1 к n предметам количество перестановок увеличивается в n раз. Получаем формулу 
(n! – n -факториал – произведение всех натуральных чисел от 1 до n включительно).
|
|
|
Пример: [8] В семье – 6 человек, и за столом в кухне стоят 6 стульев. В семье решили каждый вечер, ужиная, рассаживаться на эти 6 стульев по-новому. Сколько дней члены семьи смогут делать это без повторений?
Особый вид перестановок – перестановки с повторениями. В них среди прочих участвуют предметы, неразличимые между собой, - «близнецы». Замена одного «близнеца» другим не приводит к новой расстановке.
Общая формула количества перестановок с повторениями для случая, когда имеется n групп «близнецов», состоящих соответственно из 
неразличимых элементов:
.
Пример: [8] В семье – 6 человек, из них двое детей. За столом в кухне стоят 6 стульев. В семье решили каждый вечер, ужиная, рассаживаться на эти 6 стульев по-новому, детей между собой при этом принято не различать. Сколько дней члены семьи смогут делать это?
Пример: Сколько различных шестизначных чисел можно составить из цифр 1,1,1,5,5,9?
Пример: Сколько различных слов можно получить, переставляя буквы слова «математика»?
Б) Размещения.
Размещениями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком. Обозначим искомое число 
. Сначала возьмем любую перестановку всех n объектов и рассмотрим первые m из них. Они образуют размещение m объектов из n имеющихся, тогда как последние n-m объектов совершенно не влияют на это размещение, как их не переставляй. Но эти n-m «хвостовых» объектов могут быть переставлены 
способами. Значит, каждому размещению можно «пришить» 
различных «хвостов», что порождает столько же перестановок всех n объектов. Общее число перестановок всех объектов 
в таком случае равно произведению искомого числа и , т.е. 
. Откуда 
.
Пример: [4] Предположим, что проходит некий конкурс красоты с 8 участниками. Одновременно проводится викторина: нужно угадать, кто займет в конкурсе 1, 2 и 3 места. Сколько всего существует вариантов ответа?
Как вы думаете, сколькими способами можно выбрать 0 объектов из n имеющихся, или, другими словами, сколькими способами можно не выбрать ни одного объекта? Вопрос странный, но формально получается 
. Пожалуй, это логично: есть единственный способ не выбрать ни одного объекта из n имеющихся – ничего не делать.
|
|
|
Второй вопрос: сколькими способами можно сделать упорядоченный выбор из n объектов всех n? Получается обыкновенная перестановка всех n объектов, и число таких перестановок . С другой стороны, согласно приведенной формуле, это же число равняется 
. Появилось новое выражение 0!. Предположим, что 0! – это какое-то неизвестное число, и найдем его из равенства 
. Тогда 
и мы получаем 
.
Пусть имеется n различных объектов. Выберем из них m штук, действуя по следующему принципу. Возьмем любой, но не будем устанавливать его в какой-то ряд, а просто запишем под номером 1 его название, сам же объект после этого вернем к остальным. Затем опять из всех n объектов выберем один (в том числе, возможно, и тот, который был только что взят), запишем его название, пометив под номером 2, и снова вернем объект обратно. И так далее, пока не получим m названий. Размещения с повторениями обозначаются 
и их число равно 
. Заметим, что здесь допустим случай, когда m>n, т.е. выбранных объектов больше, чем их всего имеется. Это неудивительно: каждый объект после «использования» возвращается обратно и может быть «использован» повторно.
Пример: [4] Сколько может быть паспортов с зафиксированными двумя первыми цифрами серии и остальными изменяющимися двумя цифрами серии и шестью цифрами номера? (с повторениями и без повторений)
В) Сочетания.
Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом. При этом порядок расположения объектов значения не имеет.
Число всевозможных сочетаний из n элементов по m обозначается 
. Найдем это число.
Сначала из n элементов выделим какие-либо m элементов с учетом очередности выбора. Это – размещение, и число таких размещений . Очевидно, что различные размещения, в которые входят те же объекты, но в ином порядке, будут соответствовать одному сочетанию. Другими словами, любая перестановка выбранных m элементов порождает то же самое сочетание. Но таких перестановок 
. Поэтому число сочетаний из n элементов по m в 
раз меньше числа размещений: 
.
|
|
|
Пример: [8] «Вороне где-то Бог послал кусочек сыра», брынзы, колбасы, сухарика и шоколада. «На ель Ворона взгромоздясь, позавтракать совсем уж было собралась, да призадумалась»:
а) если есть кусочки по очереди, то из скольких вариантов придется выбирать;
б) сколько получится «бутербродов» из двух кусочков.
Число сочетаний с повторениями из n элементов по m: 
.
Пример: [4] Кости домино можно рассматривать как цифры 0,1,2,3,4,5,6. Найдите число сочетаний (с повторениями, без повторений).
Пример: [10] Решите уравнение 
.
· Формулы включений и исключений.
Пусть имеется N предметов, некоторые из которых обладают свойствами 
. Обозначим через 
количество предметов, обладающих свойствами 
(и, может быть, еще некоторыми из других свойств).
Если надо подчеркнуть, что берутся предметы, не обладающие некоторым свойством, то это свойство пишется со штрихами. Например: 
- количество предметов, обладающих свойством 
, но не обладающих свойством 
.
В самом простом случае при одном свойстве 
, где N – общее число элементов.
Если имеются два свойства , то 
. Действительно, каждый элемент, обладающий свойствами 
и 
одновременно, вычитается дважды, следовательно, к этой разности нужно добавить 
.
Обобщением этого правила является следующий принцип включения-исключения:
Пример: [4] Сколько чисел в первой сотне, которые не делятся ни на 2, ни на 3, ни на 5?
Пример: [4] На фирме есть переводчики со знанием английского или немецкого языка, причем 12 человек, знающих английский язык, и 8 человек, знающих немецкий язык, но 3 человека из них знают два языка. Глава фирмы решил дать премию одному из переводчиков. Сколько у него вариантов выбора?
· Рекуррентные соотношения.
При решении многих комбинаторных задач пользуются методом сведения данной задачи к задаче, касающейся меньшего числа предметов. Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений (от латинского «recurrere» - «возвращаться»).
Понятие рекуррентных соотношений проиллюстрируем классической проблемой, которая была поставлена около 1202 года Леонардо из Пизы, известным как Фибоначчи. Важность чисел Фибоначчи для анализа комбинаторных алгоритмов делает этот пример весьма подходящим.
Фибоначчи поставил задачу в форме рассказа о скорости роста популяции кроликов при следующих предположениях. Всё начинается с одной пары кроликов. Каждая пара становится фертильной через месяц, после чего каждая пара рождает новую пару кроликов каждый месяц. Кролики никогда не умирают, и их воспроизводство никогда не прекращается.
|
|
|
Пусть 
- число пар кроликов в популяции по прошествии n месяцев, и пусть эта популяция состоит из 
пар приплода и 
«старых пар», т.е. 
. Таким образом, в очередном месяце произойдут следующие события: 
. Старая популяция в (n +1)-й момент увеличится на число родившихся в момент времени n: 
. Каждая старая пара в момент времени n производит пару приплода в момент времени n +1. В последующий месяц эта картина повторяется:
, 
.
Объединяя эти равенства, получим следующее рекуррентное соотношение:
, 
.
Выбор начальных условий для последовательности чисел Фибоначчи не важен; существенное свойство этой последовательности определяется рекуррентным соотношением. Будем предполагать 
, 
(иногда 
).
|
|
|
