Задачи комбинаторного анализа. Лекция 7

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

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

Арифметический квадрат

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

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

Неравенство Бернулли
c > 1 + n (c – 1), где с – произвольное число, большее 1, n – натуральное число, большее 1.
Доказательство.
Для каждого натурального n и чисел a = 1 и b = c-1 верны равенства
По условию b > 0 и n >=2. Следовательно, каждое слагаемое (их по меньшей мере три) в полученной сумме строго положительно. Значит,
> 1 + nb
и доказываемое неравенство верно.

Неравенство Бернулли
Неравенство Бернулли утверждает, что если х>-1, то для всех натуральных значений n выполняется неравенство
Неравенство может применяться для выражений вида
Кроме того, очень большая группа неравенств может быть легко доказана с помощью теоремы Бернулли.

Пример 1. Доказать, что для любых n ϵ N
Доказательство. Положив х=0,5 и применив теорему Бернулли для выражения
получим требуемое неравенство.
Пример 2. Доказать, что для любых n ϵ N
Доказательство.
по теореме Бернулли, что и требовалось.

Задача 1. Из данной пропорции
найти x и y.
Решение.
Записав отдельно отношение первого члена пропорции ко второму и второго к третьему, после сокращения получим:
В силу условия задачи мы приходим к системе:
Решая её, получаем x=5 и =1.

Задача 2

Задача
Доказать, что
делится нацело на 64 при любом натуральном n.
Доказательство.
Обозначив выражение в скобках через а, а N, имеем:
Полученная сумма делится на 64, что и требовалось доказать.

Принцип Дирихле

Принцип Дирихле
Если k+1 или более объектов расположены в k коробках, тогда есть по крайней мере одна коробка, содержащая два или более из объектов.

Реализация принципа Дирихле
Если n объектов расположены в k коробках, то как минимум одна коробка содержит как минимум n/k объектов.
Доказательство:
Предположим, что ни одна коробка не содержит более чем [n/k]–1 объектов. Общее количество элементов в коробках :
k([n/k]-1)
Причем, [n/k]<(n/k)+1.

Принцип Дирихле
Пример
Сколько человек из 100 родились в одном месяце?
Среди 100 человек есть по крайней мере [100/12] =9, которые родились в одном и том же месяце

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

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

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

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

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

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

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

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

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

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

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

Раскладки

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

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

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

Раскладки

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

Разбиения и полиномиальная теорема
Разбиением множества A на k частей называется семейство его подмножеств, такое, что
1) при ;
2) .

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

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

Величина обозначается
Через или
и называется
полиномиальным коэффициентом.

Полиномиальная формула:
Где сумма распространена на всевозможные разбиения n1+n2+…+nk числа n на k целых неотрицательных слагаемых.
Доказательство:
Запишем
в виде произведения n сомножителей и раскроем скобки, выписывая все сомножители в порядке их появления.

Получим всевозможные перестановки с повторениями, составленные из букв х1, х2,..., хk такие, что в каждую перестановку входит n букв.
Чтобы найти коэффициент при
надо сосчитать, сколько перестановок с повторениями содержат n1 раз букву х1, - n2 раз букву х2 и т.д.
Число таких перестановок
где n1+n2+...+nk=n, так как в каждый член разложения входит по одному элементу из каждой скобки, а общее число перемножаемых скобок
равно n. ♦

Пример 1
Написать разложение полинома третьей степени
Задание: определить полиномиальные коэффициенты в данном разложении

Пример 2
Найти разложение степени тринома

Пример. Найти коэффициент при из разложения степени
Коэффициент при из разложения
степени равен
Имеем член разложения
При получаем

Пример.

Формула включений и исключений

Формула включений и исключений
Пусть даны N объектов (предметов), каждый из которых может обладать или не обладать одним или несколькими из свойств a1,a2,...,an .
Через обозначим отсутствие свойства ai;
через N(a) – количество предметов, обладающих свойством а (а – любое из свойств аi или );
через N(a,b,c,…,k) – количество предметов, обладающих попарно различными свойствами а,b,c,..,,k

Формула включений и исключений
Если все свойства ai попарно не совместимы (т.е. N(aiak)=0 при i ≠k), то формула имеет вид:

Формула включений и исключений
Тогда, очевидно,
т.к. при вычитании N(а1) и N(a2) из общего числа предметов
число N(ala2) вычитается дважды.

Формула включений и исключений

Формула включений и исключений
При произвольном n справедлива формула включений и исключений:

Формула включений и исключений
Сколько положительных целых чисел, не превышающих 1000, делятся на 7 или на 11?
делится на 7
делится на 11

Пример.

11
22
33

Рекуррентные соотношения

Рекуррентные соотношения
При решении многих комбинаторных задач используется метод сведения данной задачи к аналогичной задаче, касающейся меньшего числа предметов.
Такой метод называется методом рекуррентных соотношений. Пользуясь рекуррентным соотношением можно свести задачу об n предметах к задаче об (n–1) предметах, потом об (n–2) предметах и т.д. Последовательно уменьшая число предметов, доходим до задачи, которую уже легко решить. Во многих случаях удается получить из рекуррентного отношения явную формулу для решения комбинаторной задачи.

Примеры рекуррентных формул

Линейные рекуррентные соотношения
Рекуррентное соотношение вида
an=b1(n)an-1+b2(n)an-2+b3(n)an-3+…+bp(n)ap
называется линейным рекуррентным соотношением порядка р , т.к. аn выражается через р элементов вида
Соотношение линейно-рекуррентное, т.к. показатель каждой степени аі равен 1.

Рекуррентные соотношения
Примеры
1)
2)
3) an+2=an·an+1-3an+1+1 - нелинейное рекуррентное соотношение порядка 2, т.к. зависит от an и an+1
4) an+3=6an·an+2+an+1 - нелинейное рекуррентное соотношение порядка 3, т.к. зависит от an, an+1 и an+2
5) an+2=3an+1-2an - линейное рекуррентное соотношение порядка 2, т.к. зависит от an и an+1
- нелинейное, т.к. аn-1 в 3-ей степени
- линейное

Линейные рекуррентные соотношения
Решением рекуррентного соотношения является последовательность, при подстановке которой соотношение тождественно выполняется.
Решение рекуррентного соотношения р-го порядка называется общим, если оно зависит от р произвольных постоянных С1,С2,…,Ср и путем подбора этих постоянных можно получить любое решение данного соотношения.
Пример
an+2=3an+1-an
an=2n; an+1=2n+1 ; an+2=2n+2
2n+2=3·2n+1-2·2n=3·2n·21-2·2n
2n- решение данного рекуррентного соотношения

Линейные рекуррентные соотношения с постоянными коэффициентами
Линейное рекуррентное соотношение вида
an=b1an-1+b2an-2+b3an-3+…+bpaр, bp≠0
c постоянными коэффициентами bi при 1≤і≤p называется линейным однородным рекуррентным соотношением с постоянными коэффициентами.

Числа Фибоначчи

Последовательность (числа) Фибоначчи
Числовая последовательность, в которой каждое число равно сумме двух предыдущих, называется последовательностью Фибоначчи (числами Фибоначчи).
F(n+1) = F(n) + F(n–1).
Выражение чисел Фибоначчи через имеет вид:
F(n) =
где , если n нечетно (р - целая часть числа ______
, если n четно

Числа Фибоначчи. Пример
Пара кроликов приносит раз в месяц приплод из двух крольчат (самки и самца), причем новорожденные крольчата через 2 месяца после рождения уже приносят приплод. Сколько кроликов появится через год, если в начале года была одна пара кроликов?
Решение:
Через месяц будет 2 пары кроликов.
Через 2 месяца приплод даст только первая пара кроликов и получится 3 пары.
Через 3 месяца приплод дадут и исходная пара, и пара, появившаяся 2 месяца тому назад. Всего будет 5 пар кроликов.

Числа Фибоначчи. Пример
Fn – количество пар кроликов через n месяцев.
Через n+1 месяцев будет Fn пар и еще столько новорожденных пар кроликов, сколько было в конце месяца n-1, т.е. Fn-1.
⇓
Fn+1= Fn +Fn-1
По условию: F0=1, F1=2 ⇒
F2=1+2=3
F3=2+3=5
F4=3+5=8 и т.д.
где Fn – числа Фибоначчи

Отношения вида an+2=b1an+1+b2an
Решение данных отношений основано на следующих утверждениях:
1) a1(n) и a2(n) – решения данного рекуррентного отношения, тогда для любых чисел А и В последовательность an=А·a1(n)+В·a2(n) также решение этого отношения.
2) Если число r1 – корень квадратного уравнения r2=b1r+b2 , то последовательность 1, r, r2, ... , rn-1, ... есть решение рекуррентного отношения an+2=b1an+1+b2an

Решение отношений вида an+2=b1an+1+b2an
1) Составляем квадратное уравнение r2=b1r+b2, которое является характеристическим для данного отношения.
2) Если квадратное уравнение имеет 2 различных корня r1 и r2, то общее решение отношения an+2=b1an+1+b2an имеет вид:

Общее решение для рекуррентного отношения для чисел Фибоначчи
Fn= Fn-1 +Fn-2
Характеристическое уравнение:
r2=r+1
Корни уравнения:
числа и
Общее решение:

Числа Фибоначчи для начальных условий F0=0, F1=1