Более сложные задачи по комбинаторике Выполнила: учитель математики Дмитровской сош 1 им В.И. Кузнецова Кизьякова Елена Борисовна

Цели занятия: рассмотреть более сложные задачи по комбинаторике на 1.Раскладки; 2.Разбиения; 3.Смещения и субфакториалы; дать понятие о блужданиях и фигурных числах, рекуррентных отношениях. рассмотреть более сложные задачи по комбинаторике на 1.Раскладки; 2.Разбиения; 3.Смещения и субфакториалы; дать понятие о блужданиях и фигурных числах, рекуррентных отношениях.

Вспомним и повторим… Задача 1. На блюде лежат 3 яблока и 2 груши. Сколькими способами можно взять один фрукт? Задача 1. На блюде лежат 3 яблока и 2 груши. Сколькими способами можно взять один фрукт?

Вспомним и повторим… Задача 1. На блюде лежат 3 яблока и 2 груши. Сколькими способами можно взять один фрукт? Ответ: 5 способами. Задача 1. На блюде лежат 3 яблока и 2 груши. Сколькими способами можно взять один фрукт? Ответ: 5 способами.

Какое правило использовали? Правило суммы: Если некоторый объект А можно выбрать m способами, а другой объект B можно выбрать n способами, то выбор «либо А, либо В» можно осуществить m + n способами. Правило суммы: Если некоторый объект А можно выбрать m способами, а другой объект B можно выбрать n способами, то выбор «либо А, либо В» можно осуществить m + n способами.

Вспомним и повторим… Задача 2. Имеется 5 видов конвертов и 4 вида марок. Сколькими способами можно выбрать конверт с маркой для посылки письма? Задача 2. Имеется 5 видов конвертов и 4 вида марок. Сколькими способами можно выбрать конверт с маркой для посылки письма?

Вспомним и повторим… Задача 2. Имеется 5 видов конвертов и 4 вида марок. Сколькими способами можно выбрать конверт с маркой для посылки письма? Ответ: Задача 2. Имеется 5 видов конвертов и 4 вида марок. Сколькими способами можно выбрать конверт с маркой для посылки письма? Ответ:

Какое правило использовали? правило произведения: Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А; В) в указанном порядке можно осуществить mn способами. правило произведения: Если объект А можно выбрать m способами и если после каждого такого выбора объект В можно выбрать n способами, то выбор пары (А; В) в указанном порядке можно осуществить mn способами.

Вспомним и повторим… Задача 3. У англичан принято давать ребенку несколько имен. Сколькими способами в Англии можно назвать ребенка, если общее число имен равно 300, а ему дают не более трех имен? Задача 3. У англичан принято давать ребенку несколько имен. Сколькими способами в Англии можно назвать ребенка, если общее число имен равно 300, а ему дают не более трех имен?

Вспомним и повторим… Задача 3. У англичан принято давать ребенку несколько имен. Сколькими способами в Англии можно назвать ребенка, если общее число имен равно 300, а ему дают не более трех имен? Ответ: * *299*298 = Задача 3. У англичан принято давать ребенку несколько имен. Сколькими способами в Англии можно назвать ребенка, если общее число имен равно 300, а ему дают не более трех имен? Ответ: * *299*298 =

Вспомним и повторим… Задача 4. Сколькими способами можно разложить в два кармана девять монет различного достоинства? Задача 4. Сколькими способами можно разложить в два кармана девять монет различного достоинства?

Вспомним и повторим… Задача 4. Сколькими способами можно разложить в два кармана девять монет различного достоинства? Ответ: Каждая монета может попасть в один из двух карманов. Поэтому имеем 2 9 способов. Задача 4. Сколькими способами можно разложить в два кармана девять монет различного достоинства? Ответ: Каждая монета может попасть в один из двух карманов. Поэтому имеем 2 9 способов.

Использовали формулу: Размещения с повторениями из n элементов по k. (k мест нужно заполнить элементами одного из n видов, элементы могут повторяться)

Задача 5. В 2004 году в России давали автомобильные номера типа 77х451хо, в которых употреблялись цифры и кириллические буквы, имеющие аналог в латинском алфавите (таких 12). Первые два элемента – цифры(код региона), затем идет буква, затем трехзначное число и под конец еще две буквы. А) сколько таких автомобильных номеров могли выдать в России? Б) На Москву были выделены коды региона 77, 97 и 99. Сколько номеров могли выдать в Москве? В 2004 году в России давали автомобильные номера типа 77х451хо, в которых употреблялись цифры и кириллические буквы, имеющие аналог в латинском алфавите (таких 12). Первые два элемента – цифры(код региона), затем идет буква, затем трехзначное число и под конец еще две буквы. А) сколько таких автомобильных номеров могли выдать в России? Б) На Москву были выделены коды региона 77, 97 и 99. Сколько номеров могли выдать в Москве?

Задача 5. В 2004 году в России давали автомобильные номера типа 77х451хо, в которых употреблялись цифры и кириллические буквы, имеющие аналог в латинском алфавите (таких 12). Первые два элемента – цифры(код региона), затем идет буква, затем трехзначное число и под конец еще две буквы. А) сколько таких автомобильных номеров могли выдать в России? Б) На Москву были выделены коды региона 77, 97 и 99. Сколько номеров могли выдать в Москве? В 2004 году в России давали автомобильные номера типа 77х451хо, в которых употреблялись цифры и кириллические буквы, имеющие аналог в латинском алфавите (таких 12). Первые два элемента – цифры(код региона), затем идет буква, затем трехзначное число и под конец еще две буквы. А) сколько таких автомобильных номеров могли выдать в России? Б) На Москву были выделены коды региона 77, 97 и 99. Сколько номеров могли выдать в Москве?

Ответы: а) 10 2 *12*10 3 *12 2 = номеров. б) 3*12*10 3 *12 2 = Ответы: а) 10 2 *12*10 3 *12 2 = номеров. б) 3*12*10 3 *12 2 =

Размещения без повторений: Размещение на k местах некоторые из n элементов, причем элементы не могут повторяться.

Вспомним и повторим… Задача 6. В правление избрано 9 человек. Из них надо выбрать председателя, заместителя председателя и секретаря. Сколькими способами это можно сделать? Задача 6. В правление избрано 9 человек. Из них надо выбрать председателя, заместителя председателя и секретаря. Сколькими способами это можно сделать?

Вспомним и повторим… Задача 6. В правление избрано 9 человек. Из них надо выбрать председателя, заместителя председателя и секретаря. Сколькими способами это можно сделать? Ответ: Задача 6. В правление избрано 9 человек. Из них надо выбрать председателя, заместителя председателя и секретаря. Сколькими способами это можно сделать? Ответ:

Вспомним и повторим… Задача 7. Сколькими способами можно выбрать из полной колоды карт, содержащей 52 карты, по одной карте каждой масти? А если среди вынутых карт нет ни одной пары одинаковых, т.е. двух королей, двух десяток и т.д.? Задача 7. Сколькими способами можно выбрать из полной колоды карт, содержащей 52 карты, по одной карте каждой масти? А если среди вынутых карт нет ни одной пары одинаковых, т.е. двух королей, двух десяток и т.д.?

Вспомним и повторим… Задача 7. Сколькими способами можно выбрать из полной колоды карт, содержащей 52 карты, по одной карте каждой масти? А если среди вынутых карт нет ни одной пары одинаковых, т.е. двух королей, двух десяток и т.д.? Ответ: 13 4 способов. Если среди карт не должно быть пар, то имеем размещения без повторений Задача 7. Сколькими способами можно выбрать из полной колоды карт, содержащей 52 карты, по одной карте каждой масти? А если среди вынутых карт нет ни одной пары одинаковых, т.е. двух королей, двух десяток и т.д.? Ответ: 13 4 способов. Если среди карт не должно быть пар, то имеем размещения без повторений

Перестановки Перестановки Размещения, которые отличаются друг от друга лишь порядком входящих в них элементов, называются перестановками из n элементов.

Вспомним и повторим… Задача 8. На званый вечер приглашены 5 мужчин и 5 женщин. Напротив каждого места на круглый стол необходимо поставить табличку с именем того, кто будет на этом месте сидеть, но никакие два лица одного пола не должны сидеть рядом. Сколькими способами можно расставить таблички? Задача 8. На званый вечер приглашены 5 мужчин и 5 женщин. Напротив каждого места на круглый стол необходимо поставить табличку с именем того, кто будет на этом месте сидеть, но никакие два лица одного пола не должны сидеть рядом. Сколькими способами можно расставить таблички?

Вспомним и повторим… Ответ: Разделение мест на мужские и женские можно сделать двумя способами. После этого мужчин можно посадить на выбранные места способами. Столько же способов рассадить женщин. Всего получаем 2*(5!) 2 = способов. Ответ: Разделение мест на мужские и женские можно сделать двумя способами. После этого мужчин можно посадить на выбранные места способами. Столько же способов рассадить женщин. Всего получаем 2*(5!) 2 = способов.

Перестановки с повторениями где. где.

Вспомним и повторим… Задача 9. Сколькими способами можно расставить белые фигуры (короля, ферзя, две ладьи, двух слонов и двух коней) на первой линии шахматной доски (не соблюдая шахматные правила)? Задача 9. Сколькими способами можно расставить белые фигуры (короля, ферзя, две ладьи, двух слонов и двух коней) на первой линии шахматной доски (не соблюдая шахматные правила)?

Вспомним и повторим… Ответ:

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

Сочетания с повторениями Сочетания с повторениями

Вспомним и повторим… Задача 10. Сколько существует треугольников, у которых длина каждой стороны принимает одно из значений 4, 5, 6, 7? Задача 10. Сколько существует треугольников, у которых длина каждой стороны принимает одно из значений 4, 5, 6, 7?

Вспомним и повторим… Задача 10. Сколько существует треугольников, у которых длина каждой стороны принимает одно из значений 4, 5, 6, 7? Ответ: по формуле Задача 10. Сколько существует треугольников, у которых длина каждой стороны принимает одно из значений 4, 5, 6, 7? Ответ: по формуле

Раскладки Раскладки В задачах на раскладки элементы раскладываются в несколько «ящиков» и надо найти число способов это сделать.

РаскладкиРаскладки Задача 1. Шары и лузы. Скольким способами могут распределиться 15 перенумерованных бильярдных шаров в 6 лузах? Задача 1. Шары и лузы. Скольким способами могут распределиться 15 перенумерованных бильярдных шаров в 6 лузах?

Вторая строка этой схемы не что иное, как бланк длины 15, заполненный цифрами 1, 2, 3, 4, 5 и 6. Поэтому число таких распределений шаров равно числу размещений с повторениями из 6 элементов по 15, т. е. -

РаскладкиРаскладки Вывод: Число способов размещения n различных предметов по m различным «ящикам» равно Вывод: Число способов размещения n различных предметов по m различным «ящикам» равно

РаскладкиРаскладки Задача 2. Сбор яблок. Трое ребят собрали с яблони 40 яблок. Сколькими способами они могут их разделить, если все яблоки считаются одинаковыми? Задача 2. Сбор яблок. Трое ребят собрали с яблони 40 яблок. Сколькими способами они могут их разделить, если все яблоки считаются одинаковыми?

РаскладкиРаскладки Мы имеем дело с сочетаниями с повторениями - есть 3 типа предметов (мальчики) и надо делать из них комбинации из 40 элементов (по числу яблок, какое - кому), порядок элементов не учитывается, разные комбинации отличаются количеством предметов хотя бы одного типа (т.е. как раз числом яблок, достающимся хотя бы одному мальчику)

РаскладкиРаскладки Вывод: Число способов размещения n одинаковых предметов по m различным ящикам равно Вывод: Число способов размещения n одинаковых предметов по m различным ящикам равно

РаскладкиРаскладки Задача 3. Тайным голосованием 30 человек голосуют по 5 предложениям. Сколькими способами могут распределиться голоса, если каждый голосует только за одно предложение и учитывается лишь количество голосов, поданных за каждое предложение? Задача 3. Тайным голосованием 30 человек голосуют по 5 предложениям. Сколькими способами могут распределиться голоса, если каждый голосует только за одно предложение и учитывается лишь количество голосов, поданных за каждое предложение?

РаскладкиРаскладки Ответ: Так как не учитывается порядок голосов, а учитывается только их количество, то надо распределить 30 неразличимых бюллетеней по 5 «ящикам». То это сочетание с повторением. Ответ: Так как не учитывается порядок голосов, а учитывается только их количество, то надо распределить 30 неразличимых бюллетеней по 5 «ящикам». То это сочетание с повторением.

РаскладкиРаскладки Задача 4. Сколькими способами можно расположить в 9 лузах 7 белых шаров и 2 черных шара? Часть луз может быть пустой, а лузы считаются различными. Задача 4. Сколькими способами можно расположить в 9 лузах 7 белых шаров и 2 черных шара? Часть луз может быть пустой, а лузы считаются различными.

РаскладкиРаскладки 7 белых шаров можно разместить в 9 лузах способами 2 черных шара - способами. Всего имеем способов. 7 белых шаров можно разместить в 9 лузах способами 2 черных шара - способами. Всего имеем способов.

РаскладкиРаскладки Задача 5. Двое ребят собрали 10 ромашек, 15 васильков и 14 незабудок. Сколькими способами они могут разделить эти цветы? Задача 5. Двое ребят собрали 10 ромашек, 15 васильков и 14 незабудок. Сколькими способами они могут разделить эти цветы?

РаскладкиРаскладки Решение: Так как цветы каждого вида можно делить независимо от цветов другого вида, то по правилу произведения получаем 11*16*15 = 2640 способов раздела цветов. Решение: Так как цветы каждого вида можно делить независимо от цветов другого вида, то по правилу произведения получаем 11*16*15 = 2640 способов раздела цветов.

РаскладкиРаскладки Введем ограничение, что каждый из ребят должен получить не менее 3 цветков каждого вида. Общее число способов деления равно 5*10*9 = 450. Введем ограничение, что каждый из ребят должен получить не менее 3 цветков каждого вида. Общее число способов деления равно 5*10*9 = 450.

РаскладкиРаскладки В общем случае, если имеется n 1 одинаковых предметов одного вида, n 2 одинаковых предметов другого вида, … n k одинаковых предметов k-того вида, то их можно разделить между двумя людьми (n 1 +1)(n 2 +1)…(n k +1) способами. В общем случае, если имеется n 1 одинаковых предметов одного вида, n 2 одинаковых предметов другого вида, … n k одинаковых предметов k-того вида, то их можно разделить между двумя людьми (n 1 +1)(n 2 +1)…(n k +1) способами.

РаскладкиРаскладки Задача 6. Сколькими способами можно разделить 10 белых грибов, 15 подберезовиков и 8 подосиновиков между 4 ребятами (грибы одного вида считаются одинаковыми)? Задача 6. Сколькими способами можно разделить 10 белых грибов, 15 подберезовиков и 8 подосиновиков между 4 ребятами (грибы одного вида считаются одинаковыми)?

РаскладкиРаскладки Решение: Применяя формулу Число способов размещения n одинаковых предметов по m различным ящикам равно Получаем Если же каждый должен получить хотя бы по одному грибу каждого вида, то ответом будет Решение: Применяя формулу Число способов размещения n одинаковых предметов по m различным ящикам равно Получаем Если же каждый должен получить хотя бы по одному грибу каждого вида, то ответом будет

Подобная формула верна и в общем случае. Подобная формула верна и в общем случае. Если имеется n 1 предметов одного вида, n 2 предметов другого вида, …, n k предметов k-того вида, причем предметы одного и того же вида неотличимы друг от друга, то число способов распределения этих предметов по m различным ящикам равно

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

РазбиенияРазбиения Имеются марки достоинством в n 1, n 2, …, n k рублей (все числа n i различны, а запас марок неограничен). Сколькими способами, наклеивая марки в ряд, можно оплатить с их помощью сумму в N рублей, если два способа, отличающиеся порядком следования различных марок, считаются разными? F(N)=F(N-n 1 )+F(N-n 2 )+…+F(N-n k ) (1) При этом F(N)=0, если N

РазбиенияРазбиения Задача 1. (о наклейке марок) За пересылку бандероли надо уплатить 18 рублей, наклеивая на нее марки. На почте есть по одному виду марок достоинством в 4, 6 и 10 рублей (зато в неограниченном количестве). Сколькими способами можно оплатить пересылку бандероли, если два способа, отличающиеся номиналом или порядком наклеивания марок, считаются различными (марки наклеиваются в один ряд)? Задача 1. (о наклейке марок) За пересылку бандероли надо уплатить 18 рублей, наклеивая на нее марки. На почте есть по одному виду марок достоинством в 4, 6 и 10 рублей (зато в неограниченном количестве). Сколькими способами можно оплатить пересылку бандероли, если два способа, отличающиеся номиналом или порядком наклеивания марок, считаются различными (марки наклеиваются в один ряд)?

РазбиенияРазбиения Решение: Обозначим через F(N) число способов, которыми можно наклеить марки достоинством в 4, 6 и 10 рублей, так чтобы общая стоимость этих марок равнялась N. По формуле (1) получаем F(18) = F(14) + F(12) + F(8). F(14) = F(10) + F(8) + F(4) F(12) = F(8) + F(6) + F(2) F(8) = F(4) + F(2) + F(-2) Решение: Обозначим через F(N) число способов, которыми можно наклеить марки достоинством в 4, 6 и 10 рублей, так чтобы общая стоимость этих марок равнялась N. По формуле (1) получаем F(18) = F(14) + F(12) + F(8). F(14) = F(10) + F(8) + F(4) F(12) = F(8) + F(6) + F(2) F(8) = F(4) + F(2) + F(-2)

РазбиенияРазбиения F(14) = = 5 F(12) = = 2 F(8) = 1 Итак, сумму 18 можно получить 8 способами. F(14) = = 5 F(12) = = 2 F(8) = 1 Итак, сумму 18 можно получить 8 способами.

Такой способ задач, при котором сразу не дается окончательной формулы ответа, а указывается лишь процесс, позволяющий сводить задачу ко все меньшим и меньшим числовым данным, встречается в комбинаторике очень часто. Равенства вида (1) называют рекуррентными формулами.

РазбиенияРазбиения Задача 2. Сколькими способами можно наклеить на конверт в одну линию марки на 40 рублей, используя марки достоинством в 5, 10, 15 и 20 рублей (расположения, отличающиеся порядком марок, считаются как различные; число марок не ограничено)? Задача 2. Сколькими способами можно наклеить на конверт в одну линию марки на 40 рублей, используя марки достоинством в 5, 10, 15 и 20 рублей (расположения, отличающиеся порядком марок, считаются как различные; число марок не ограничено)?

РазбиенияРазбиения F(40) = F(35) + F(30) + F(25) + F(20) F(40) = 108 F(40) = F(35) + F(30) + F(25) + F(20) F(40) = 108

Смещения, субфакториалы «Девушка спешит на свидание» Сформулируем задачу в общем виде: найти число перестановок n элементов, при которых ни один из элементов не стоит на своем месте. Такие перестановки называют смещениями, а их число обозначают. «Девушка спешит на свидание» Сформулируем задачу в общем виде: найти число перестановок n элементов, при которых ни один из элементов не стоит на своем месте. Такие перестановки называют смещениями, а их число обозначают.

Смещения, субфакториалы Решение проводится с помощью формулы включений и исключений. свойство перестановки, заключающееся в том, что число p стоит на своем месте N(p) – количество перестановок, обладающих этим свойством N(pq) обозначим количество перестановок, одновременно обладающих свойствами и, т.е. таких что и p, и q стоят на своих местах, и т.д. Через обозначим N(, т.е. число перестановок, в которых ни одно число не стоит на своем месте. Решение проводится с помощью формулы включений и исключений. свойство перестановки, заключающееся в том, что число p стоит на своем месте N(p) – количество перестановок, обладающих этим свойством N(pq) обозначим количество перестановок, одновременно обладающих свойствами и, т.е. таких что и p, и q стоят на своих местах, и т.д. Через обозначим N(, т.е. число перестановок, в которых ни одно число не стоит на своем месте.

Смещения, субфакториалы В данном случае задача облегчается тем, что свойства совершенно равноправны Ответ: В данном случае задача облегчается тем, что свойства совершенно равноправны Ответ:

Общая задача о смещении Найти число перестановок из n элементов, при которых ни один элемент не остается в первоначальном положении.

Обобщая формулу (2) на случай n=0, получаем, что естественно принять Число перестановок, при которых ровно r элементов остаются на первоначальных местах, а остальные n-r элементов меняют свое положение, выражается формулой Обобщая формулу (2) на случай n=0, получаем, что естественно принять Число перестановок, при которых ровно r элементов остаются на первоначальных местах, а остальные n-r элементов меняют свое положение, выражается формулой

Смещения, субфакториалы Найдем, во скольких случаях ровно один адресат получит свой паспорт. общее число способов, при которых в точности один человек получит свой паспорт, равно 5*9=45. (т.к. ) Найдем, во скольких случаях ровно один адресат получит свой паспорт. общее число способов, при которых в точности один человек получит свой паспорт, равно 5*9=45. (т.к. )

Смещения, субфакториалы Найдем, во скольких случаях в точности двое получат свои паспорта. 2*10=20 Найдем, во скольких случаях в точности двое получат свои паспорта. 2*10=20

Смещения, субфакториалы Числа называют субфакториалами Числа называют субфакториалами

Блуждания, фигурные числа Задача 1. Путник хочет попасть из пункта А в пункт В кратчайшим путем, т.е. двигаясь все время или «слева направо», или «снизу вверх». Сколькими путями он может добраться из А в В? (На рисунке изображен план города (примерно такой вид имеет план Канберры – столицы Австралии) Задача 1. Путник хочет попасть из пункта А в пункт В кратчайшим путем, т.е. двигаясь все время или «слева направо», или «снизу вверх». Сколькими путями он может добраться из А в В? (На рисунке изображен план города (примерно такой вид имеет план Канберры – столицы Австралии) А В k n

Блуждания, фигурные числа Сопоставим каждому пути из А в В последовательность из нулей и единиц – если на очередном перекрестке выбран путь вправо, ставим цифру 0, а если выбран путь вверх, ставим цифру 1. Число перестановок из k нулей и n единиц равно Сопоставим каждому пути из А в В последовательность из нулей и единиц – если на очередном перекрестке выбран путь вправо, ставим цифру 0, а если выбран путь вверх, ставим цифру 1. Число перестановок из k нулей и n единиц равно

Блуждания, фигурные числа Арифметический квадрат Напишем на каждом поле доски число путей, ведущие из углового поля в данное поле доски. Ясно, что на пересечении k-й вертикали и n-й горизонтали стоит число Арифметический квадрат Напишем на каждом поле доски число путей, ведущие из углового поля в данное поле доски. Ясно, что на пересечении k-й вертикали и n-й горизонтали стоит число

Блуждания, фигурные числа Мы получим таблицу. Эту таблицу называют арифметическим квадратом.

Блуждания, фигурные числа Достаточно было использовать элементы предыдущей строки. Существует формула сочетаний: Такой метод вычисления арифметического квадрата связан с восходящим к древнегреческим математикам Пифагору и Никомаху учением о фигурных числах. Достаточно было использовать элементы предыдущей строки. Существует формула сочетаний: Такой метод вычисления арифметического квадрата связан с восходящим к древнегреческим математикам Пифагору и Никомаху учением о фигурных числах.

Блуждания, фигурные числа Дело в том, что числа 1, 2, 3, … можно изображать строками из одной, двух, трех и т.д. точек, а эти строки объединить в треугольники (рис 46). Тогда число точек в каждом треугольнике будет равно соответствующему числу во второй строке арифметического квадрата. Поэтому числа 1, 3, 6, 10, 15, 21 и т.д. называют треугольными числами, k-е треугольное число равно.

Блуждания, фигурные числа Треугольники, изображенные на рис 46, можно объединять в пирамиды (рис. 47). Число точек в каждой пирамиде равно соответствующему числу в третьей строке арифметического квадрата. Поэтому числа 1, 4, 10, 20, 35 и т.д. называют пирамидальными. Их общий вид такой: Треугольники, изображенные на рис 46, можно объединять в пирамиды (рис. 47). Число точек в каждой пирамиде равно соответствующему числу в третьей строке арифметического квадрата. Поэтому числа 1, 4, 10, 20, 35 и т.д. называют пирамидальными. Их общий вид такой:

Рекуррентные соотношения При решении многих комбинаторных задач часто пользуются методом сведения данной задачи к задаче, касающейся меньшего числа предметов. Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений (от латинского recurrere – возвращаться) При решении многих комбинаторных задач часто пользуются методом сведения данной задачи к задаче, касающейся меньшего числа предметов. Метод сведения к аналогичной задаче для меньшего числа предметов называется методом рекуррентных соотношений (от латинского recurrere – возвращаться)

Кролики Фибоначчи Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорожденные крольчата через два месяца после рождения уже приносят приплод. Сколько пар кроликов появится через год, если в начале года была одна пара кроликов и ни одна пара кроликов не погибла.

Кролики Фибоначчи Обозначим через u n число пар кроликов в начале n-го месяца. Тогда U 1 = 1 U 2 = 1 U 3 = 2 (появится приплод) U 4 = 3 (к началу 4 – го месяца первая пара даст приплод, а новорожденные кролики приплода еще не дадут) U 5 = 5 (т.к. приплод даст и первоначальная пара и новорожденная) Обозначим через u n число пар кроликов в начале n-го месяца. Тогда U 1 = 1 U 2 = 1 U 3 = 2 (появится приплод) U 4 = 3 (к началу 4 – го месяца первая пара даст приплод, а новорожденные кролики приплода еще не дадут) U 5 = 5 (т.к. приплод даст и первоначальная пара и новорожденная)

Кролики Фибоначчи U k =U k-1 +U k-2 U 13 = 233 Числа U 1, U 2, …, U n,… называют числами Фибоначчи (обычно полагают еще U 0 = 0, чтобы выполнялось равенство U 2 = U 1 + U 0 ) U k =U k-1 +U k-2 U 13 = 233 Числа U 1, U 2, …, U n,… называют числами Фибоначчи (обычно полагают еще U 0 = 0, чтобы выполнялось равенство U 2 = U 1 + U 0 )

СПАСИБО ЗА ВНИМАНИЕ!