Принцип включения и исключения
⇐ ПредыдущаяСтр 2 из 2 1.1. Вывод формулы. Пусть имеем N объектов и некоторый набор свойств а1, …, аn, которыми могут обладать эти объекты. Обозначим N(i) – число объектов, обладающих свойством аi, и вообще N(i1, …, ik) – число объектов, обладающих одновременно всеми свойствами N(0) = N – + (– 1)k Символ 1 £ i1 < i2 <…< ik £ n под знаком суммы означает, что суммирование ведется по всем комбинациям i1, i2,…, ik так, чтобы выполнялось указанное соотношений. Доказательство проведем с помощью индукции по n – число свойств. 10. n = 1. N(0) = N – N(1). Всего существует одно свойство. От общего числа объектов отнимем количество объектов, обладающих этим свойством – узнаем, сколько объектов этим свойством не обладают. 20. Пусть для n – 1 свойств справедлива формула N(0) = N – + (– 1)k Пусть теперь имеем множество, все элементы которого обладают свойством аn, и, возможно, обладают свойствами а1, …, аn–1. Очевидно, для этого множества формула (3.2) также верна и имеет вид: N(0, n) = N(n) – +(–1)n–2 В (3.3) везде в скобках дописано n, т.к. все элементы множества свойством аn обладают. Вычтем (3.3) из (3.2): N(0) – N(0, n) = N – Отсюда N(0) – N(0, n) = N – Справа мы получили требуемую формулу. А что слева? N(0) – число элементов, не обладающих свойствами а1, …, аn–1, но, возможно, обладающих свойством аn. N(0, n) – число элементов, не обладающих свойствами а1, …, аn–1, но обязательно обладающих свойством аn. Следовательно, N(0) – N(0, n) – число элементов, не обладающих ни одним из свойств а1, …, аn, т.е. требуемая величина. Формула доказана.
Пример 3.1. Староста класса подал следующие сведения о классе. Всего в классе 45 учеников, из них 25 мальчиков. 30 человек учится без троек, из них – 16 мальчиков; 28 человек занимаются спортом, из них – 18 мальчиков и 17 хорошистов и отличников; 15 мальчиков учатся без троек и одновременно занимаются спортом. Классный руководитель внимательно посмотрел список и сказал, что в сведениях есть ошибка. Как он это узнал? Решение. Обозначим a1 – свойство принадлежности к мужскому полу; a2 – хорошая успеваемость; a3 – занятие спортом. Тогда N = 45, N(1) = 25, N(2) = 30, N(3) = 28, N(1, 2) = 16, N(1, 3) = 18, N(2, 3) = 17, N(1, 2, 3) = 15. Итого N(0) = 45 – 25 – 28 + 16 + 18 + 17 – 15 = – 2 – ошибка. 1.2. Модификации формулы включения и исключения 2.а. Формулу (2.1) можно обобщить для определения числа элементов, обладающих в точности k свойствами (0 £ k £ n): N(k) = + (–1)n–k Пример 3.2. В отделе НИИ каждый сотрудник владеет хотя бы одним иностранным языком. Известно, что английским языком владеют 6 человек, немецким – 6, французским – 7, английским и немецким – 4, немецким и французским – 3, английским и французским – 2, все три языка знает 1 человек. Определить, сколько всего человек в отделе, сколько человек владеют только английским, только немецким, только французским, и сколько человек знает только 1 иностранный язык. Решение. Согласно условиям задачи N(0) = 0, т.к. в отделе нет сотрудников, не владеющих иностранными языками. Следовательно, по формуле (3.1) получаем: N = N = 6 + 6 + 7 – 4 – 3 – 2 + 1 = 11 человек всего в отделе. Для вычисления остальных показателей также воспользуемся формулой (3.5). Найдем, например N(только А) – число человек, не владеющих никаким другим языком, кроме английского. Для этого формулу (3.5) надо применить только к множеству людей, владеющих английским языком. В этом случае n = 2. Тогда N = N(A), N(1) и N(2) – число людей, владеющих помимо английского еще немецким и французским, соответственно, N(1, 2) – число людей, владеющих помимо английского еще одновременно немецким и французским. Отсюда
N(только A) = N(A) – N(А и Н) – N(А и Ф) + N(А и Н и Ф) = 6 – 4 – 2 + 1 = 1. Аналогично N(только Н) = N(Н) – N(А и Н) – N(Н и Ф) + N(А и Н и Ф) = 6 – 4 – 3 + 1 = 0. N(только Ф) = N(Ф) – N(Ф и А) – N(Ф и Н) + N(А и Н и Ф) = 7 –2 – 3 + 1 = 3. Вычислим теперь N(1) – число людей, владеющих только 1 языком. Воспользуемся формулой (3.4) при k = 1. N(1) = N(А) + N(Н) + N(Ф) + (–1)2–1× Такой же результат получим, если сложим N(только A) + N(только Н) + N(только Ф). 2.б. Формулу (3.1) можно также интерпретировать, как подсчет мощностей пересечений различных множеств, т.е. дать теоретико-множественное представление принципа включения и исключения. Пусть имеем некоторое конечное множество А и его подмножества Аj, j = 1,…, n. Тогда теоретико-множественный аналог формулы (3.1) будет иметь вид:
+ (– 1)k
Формулы обращения 2.1. Теорема обращения. Пусть имеем два семейства комбинаторных чисел {an,k} и {bn,k}, зависящих от целочисленных параметров n, k, причем 0 £ k £ n. Теорема 3.1. Пусть для любых n и k, 0 £ k £ n справедливы зависимости Тогда для всех k £ n имеет место формула обращения:
Доказательство.
что и требовалось доказать. 2.2. Примеры использования формулы обращения. Зависимость между числами ln,k,i и mn,k,i, фигурирующая в условиях теоремы 3.1, по сути означает, что эти числа образуют систему взаимно обратных матриц, т.е. смысл теоремы весьма прост, если не сказать – тривиален. Для произвольных чисел an,k и bn,k она не дает никакой ценной информации, поскольку найти требуемые числа mn,k,i в общем случае столь же трудно, как и решить исходную систему уравнений относительно bn,k. Однако, для многих специальных случаев, в частности, комбинаторных чисел, удается найти mn,k,i в явном виде. В этом особенность данной формулы. Рассмотрим ее применение для обращения биномиальных коэффициентов. Лемма 3.1. Доказательство. Имеем:
= Следовательно,
Так как при k < 0 и при k > n В = Но при m < n имеем:
Последнее равенство следует из свойства 5 чисел сочетания. А при m = n имеем:
что и требовалось доказать. Теорема 3.2. Если Доказательство. Здесь
Это означает, что выполнены условия теоремы 3.1, а, следовательно, теорема доказана. Теорема 3.3. Если Доказательство аналогично.
Рекуррентные соотношения В комбинаторных задачах искомым решением часто является числовая последовательность u1, u2, …, un, … Например, если мы ищем число подмножеств m-элементного множества, то un + k + b1 un + k – 1 + b2 un + k – 2 +…+ bk un = 0, (3.6) где b1, b2, …, bk – некоторые коэффициенты. Выражение (3.6) называется еще разностным линейным уравнением k-го порядка с постоянными коэффициентами. Одной из наиболее известных последовательностей, задаваемых линейным рекуррентным соотношением, является последовательность Фибоначчи {Fn}, определяемая следующими условиями: F0 = 0; F1 = 1; Fn+2 = Fn+1 + Fn. Отсюда получаем F2 = 1; F3 = 2; F4 = 3; F5 = 5; F6 = 8 и т.д. Воспользовавшись уравнением (2.8) всегда можно вычислить значения un для любых n, если знать первые k членов последовательности. Однако, часто необходимо знать явную формулу для вычисления un. Теорема 3.4. Пусть l1, l2,…, ls – корни соответствующих кратностей m1, m2,…, ms характеристического уравнения для выражения (3.6): lk + b1 lk–1 + b2 lk–2 +…+ bk = 0 (3.7) Тогда общее решение уравнения (3.6) определяется по формуле: un = (C11 + C12 ×n + C13×n2 + … + (C21 + C22 ×n + C23×n2 + … + (Cs,1 + Cs,2 ×n + Cs,3×n2 + … + где C11,…, Пример 3.3. Решим уравнение Фибоначчи Fn+2 – Fn+1 – Fn = 0. Его характеристическое уравнение имеет вид: l2 – l – 1 = 0. Корни равны
Из начальных условий F0 = 0; F1 = 1 получаем систему уравнений для вычисления С1 и С2 = 1:
Отсюда С1 = – С2 = Использование рекуррентных соотношений дает эффективный метод решения многих комбинаторных задач. Пример 3.4. Найти число бинарных n-последовательностей, в которых никакие две единицы не стоят рядом. Решение. Обозначим: zn – число искомых последовательностей; хn – число последовательностей, заканчивающихся 0; уn – число последовательностей, заканчивающихся 1. Назовем для краткости последовательность, заканчивающуюся 0 – х-последовательностью, а заканчивающихся 1 – у-последовательностью. Очевидны следующие их свойства. 1) х-последовательность длиной n можно получить, приписав 0 в конец либо у-последовательности либо х-последовательности длиной n – 1. 2) у-последовательность длиной n можно получить, приписав 1 только в конец х-последовательности длиной n – 1. Отсюда имеем следующую систему уравнений:
Уравнение (a) отражает свойство 1), уравнение (b) – свойство 2), а уравнение (а) соответствует очевидному равенству. Из уравнения (b) при замене n на n – 1 имеем: уn–1 = хn–2. Подставим это равенство в (a), получим: хn = хn–1 + хn–2, т.е. числа хn образуют последовательность Фибоначчи. Вычтем (b) из (a), получим: хn – уn = уn–1 Þ хn = уn + уn–1 Þ уn+1 = уn + уn–1 – тоже последовательность Фибоначчи. В соответствие с формулой общего решения и уравнением (c) получим:
Для нахождения констант запишем начальные условия. z1 = 2, т.к. существует 2 последовательности длиной 1: 0 и 1. z2 = 3, т.к. существует 3 последовательности длиной 2: (0 0), (0 1), (1 0). Отсюда Например, z9 = 89, z19 = 10946.
Производящие функции 4.1. Определение производящих функций. Последовательности {un}, фигурирующей в какой-либо задаче, например, комбинаторной, удобно поставить в соответствие формальный степенной ряд u(x) = который называется производящей функцией данной последовательности. Слова “формальный ряд” означает, что эту формулу мы трактуем только как удобную запись последовательности. Для нас сейчас несущественно, при каких значениях х ряд сходится и сходится ли вообще, т.к. вычислять значение u(x) мы никогда не будем. Пример 3.5. Известно, что Пример 3.6. Согласно формуле бинома Ньютона (1 + х)n = 4.2. Операции с производящими функциями. Рассмотрим основные технические приемы, применяемые в работе с производящими функциями. 4.2.а. Линейная комбинация. Если функция u(x) соответствует последовательности {un}, а v(x) – последовательности {vn}, то функция a×u(x) + b×v(x) (a и b – константы) является производящей для последовательности { a×un + b×vn}.
4.2.б. Сдвиг. Если функция u(x) соответствует последовательности {un}, то функции хm×u(x) соответствует последовательность Аналогично, функция 4.2.в. Умножение. Если функция u(x) соответствует последовательности {un}, а v(x) – последовательности {vn}, то функции u(x)×v(x) соответствует последовательность {wn}, где
Пример 3.7. Пусть u(x) соответствует последовательности {un}, а v(x) =
является производящей для последовательности частичных сумм. 4.2.г. Дифференцирование и интегрирование. Если u(x) соответствует последовательности {un}, то по правилу дифференцирования рядов u¢(x) = 0 + u1 + 2 u2 x + 3 u3 x2 + …. То есть u¢(x) является производящей функцией для последовательности {k uk}. Аналогично Пример 3.8. Далее,
Следовательно, Сопоставляя (3.10) с (3.9) получаем
где 4.3. Пример использования производящих функций Решим с помощью производящих функций следующую комбинаторную задачу. Пример 3.9. На окружности находится 2n точек. Сколькими способами можно их попарно соединить так, чтобы полученные отрезки не соединялись друг с другом? Решение. Обозначим un – число способов соединить 2n точек. Построим рекуррентное соотношение. Формально положим u0 = 1 (нет точек, нет пересечений, следовательно, способ единственный). u1 = 1 – очевидно, т.к. две точки соединяются единственным способом, и пересечений нет. u2 = 2. Способы соединения изображены на рис. 3.1.
Пусть n > 1. Выберем одну из 2(n + 1) точек, обозначим ее А. Соединим А с вершиной В, выбрав ее так, чтобы с обеих сторон от соединяющей их линии находилось четное число точек. Пусть слева будет 2k точек, справа – 2(n – k). 2k точек можно соединить между собой uk способами, 2(n – k) точек – un–k способами. При этом линии не пересекутся, т.к. 2k и 2(n – k) точек расположены по разные сторона от АВ. Следовательно, при фиксированном k получим uk×un–k способов соединения. Но k меняется от 0 до n. Следовательно, un +1 = u0×un + u1×un–1 + … + un×u0. (3.11) Получили искомое нелинейное рекуррентное соотношение, формула общего решения которого нам, к сожалению, неизвестна. Чтобы получить явную формулу для un, построим для этой последовательности производящую функцию. u(x) = u0 + u1х + u2 x2 + u3 x3 + …. (3.12)
Имеем, согласно формуле Коши: [ u(x) ]2 = (u0)2 + (u0×u1 + u1×u0) х + (u0×u2 + u1×u1 + u2×u0)х2 + … Видно, что коэффициенты для разложения [ u(x) ]2 можно получить с помощью формулы (3.11). Из (3.12) имеем: Подставим в эту формулу выражение uk согласно (3.11). С учетом того, что u1 = (u0)2 получим: По формуле бинома имеем: +
Умножим каждое k-е слагаемое на 1 =
Отсюда
Для того, чтобы коэффициенты ряда были положительными, надо перед корнем в формуле u(x) брать знак “–”. Заменим индекс суммирования k на k +1. В результате получим: u(x) = Окончательно
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|