Дискретно-непрерывная математика (стр. 38 )

Доказать это.

39. Пусть Q — множество, которое состоит из п элементов, А1, ... ..., Ak — коллекция Шпернера этого множества, i1, ..., ik — соответственно числа элементов множеств А1, ..., Ak. Доказать, что

40. Получить из утверждение задачи 39 утверждение задачи 38.

41. Пусть Ап - число различных коллекций Шпернера для множества из п элементов. Доказать, что

где

42. Пусть х1, .... , хп - действительные числа, | хі| ≥ 1. Доказать, что в любом интервале длины 2 есть не более чем сумм вида ∑εkxk, где εk = ±1.

43. Доказать тождества:

Микромодуль 17

Методы комбинаторики

5.9. Метод рекурентних соотношений

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

Проиллюстрируем метод рекурентних соотношений на примерах.

Пример 1. (Соединение с повторениями.) Соединение из п предметов по r с повторениями — это группы по r предметов, взятых из данных п предметов, причем каждый предмет может повторяться какое угодно число раз (порядок предметов в группе безразличен). Например, все сочетания из четырех чисел 1, 2, 3, 4 по два с повторениями имеют вид 11, 12, 13, 14, 22, 23, 24, 33, 34, 44. Таким образом, число сочетаний из 4 по 2 с повторениями равно 10.

Обозначим число ссочетаний из п предметов {а1, ..., ап} по r с повторениями через f rn. Каждое сочетание из п по r или содержит, или не содержит а1. Число сочетаний, которые не содержат а1 равно frn-1 (это сочетание из предметов а2, ..., ап по r). Каждое сочетание, которое содержит а1 может быть получено присоединениям к а1 некоторого сочетания из п предметов по r— 1 (число таких сочетаний равно f r-1n ). Следовательно,

frn = frn-1+ fr-1n . (5.28)

Мы получили рекурентне соотношение, из которого можно найти frn. Последовательно применяя (5.28), получим

(5.29)

Очевидно,

f1n=п, fr1=1. (5.30)

Считая в (5.29) r = 2, получим

(5.31)

При r = 3 из равенства (5.29) получим,

(мы использовали равенство (4.16) из п. 4.8.3). Повторяя эти же соображения далее, на ( r- 1)-м шаге будем иметь

(5.32)

Пример 2. Найдем число частей, на которые п окружностей делят плоскость, если каждые две окружности имеют общую хорду и никакие три окружности не пересекаются в одной точке. Пусть Ап — искомое число частей. На сколько увеличится число частей, если провести (п + 1)-ю окружность так, чтобы она пересекало все окружности и не проходила через точку пересечения каких-нибудь двух других окружностей? Поскольку (п + 1)-я окружность пересекается с каждой окружностью в двух точках, то она разделится точками пересечения на 2n дуг, каждая из которых делит пополам одну из частей, которая имеется в Ап. Следовательно, число частей увеличится на 2п;

An+1= An + 2n. (5.33)

Из этого рекуррентного соотношение получим

Но А1 = 2, и поэтому Ап = п2 — п + 2.

5.10. Метод производящих функций

Метод производящих функций не является элементарным, так как при его использовании приходится иметь дело с некоторыми понятиями математического анализа. Остановимся коротко на этом методе, поскольку он есть одним из наиболее эффективных методов решения комбинаторных задач.

Дальшее будем рассматривать суммы бесконечного числа слагаемых. В математическом анализе такие суммы называются рядами.

Пусть имеем бесконечную сумму

а1+а2+ ... + ak + ... (5.34)

Как правило такие суммы записывают в виде

Приймем следующее определение. Пусть

sn = а1 +…+ап. (5.35)

Если существует , то ряд (5.34) называется сходящимся

и число s называется суммой этого ряда:

а1 +…+аk + ... =s.

Если же не существует, то ряд называется расходящимся

5.11. Метод включения и исключение

Пусть N(A) - число элементов множества А. В 5.2 была установлена формула

(5.36)

Метод подсчета по формуле (5.36), состоящий в поочередном сложении и вычитании, называется методом включения и исключения.

Равенство (5.36) можно записать в виде

где

— сумма всех тех

у которых индексы i1, ..., ik удовлетворяют неравенству

Например,

Равенство (5.36) доказано в п. 5.2 с помощью метода математической индукции. Рассмотрим еще одно доказательство этого важного равенства.

Чтобы доказать (5.36), докататочно доказать, что каждый элемент из А1 ... Ап учитывается в правой части равенства (5.36) ровно один раз. Рассмотрим произвольный элемент а из А1 ... Ап и предположим, что а входит ровно в m множеств Аі. Тогда элемент а подсчитывается в правой части (5.36)

раз. Но

Следовательно, каждый элемент а из А1 ... Ап учитывается в правой части равенства (5.36) один раз. Это и доказывает равенство (5.36).

Пример 1. Рассматриваются все перестановки п чисел 1, 2, ..., п. Пусть Dn — число тех перестановок, в которых по крайней мере одно число стоит на своем месте. Найти Dn.

Обозначим через Ak совокупность тех перестановок, в которых на k-м месте стоит k. Тогда

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

а

Из равенства (5.36) следует, что

Пример 2. Пусть а1, .., ап — взаимно простые натуральные числа, а N — некоторое натуральное число. Найти число натуральных чисел, которые не превышают N и не делятся ни на одно из чисел а1, …, ап .

Пусть Аі — множество натуральных чисел, которые не превышают N и делятся на а1. Тогда количество чисел, которые делятся по крайней мере на одно из чисел а1, .... ,ап, равно

Очевидно,

где [х] — наибольшее целое число, не превосходящее х.

Множество

— это множество тех чисел, которые делятся на .

Поскольку числа взаимно простые, то

В силу равенства (5.36) количество чисел, которые не превышают N и делятся по крайней мере на одно из чисел а1, .., ап, равно