Дискретная математика (стр. 6 )

Пересчитаем одночлены вида x… x, где n+n+ … +n = n. Каждая из n пронумерованных скобок даёт в этот одночлен один и только один некий x. Получаем разбиение множества скобок на подмножества мощности n, n, … ,n. Подмножество скобок мощности n даёт в выбранный одночлен x, подмножество скобок мощности n даёт в выбранный одночлен x, … , подмножество скобок мощности n даёт в выбранный одночлен x.

Число таких разбиений равно C и равно коэффициенту перед одночленом x… x в полиномиальной формуле.

Например, для n = 10 и k=3 в полиномиальной формуле коэффициент перед xxx равен C = 10!/(3! 4! 3!).

Производящая функция

Производящая функция получается по различным правилам из последовательности чисел. Пусть, например, есть последовательность a, где k = 0..n. Производящая функция последовательности a f(z) = a + az + az + … + az. Существуют производящие функции других типов. Возьмём, например, функцию e(z) = (1+az) (1+az)

(1+az) … (1+az). Коэффициенты e(z) дают перечисление (n, r) – сочетаний без повторений. Это энумератор сочетаний.

Положим теперь a = a = … = a= 1. Тогда производящая функция d(z) = (1 + z) это денумератор сочетаний и его коэффициенты дают пересчёт (n, r) – сочетаний без повторений.

Производящие функции позволяют без компьютера получить элементы бесконечных последовательностей с большими номерами. Рассмотрим, например, бесконечную последовательность чисел Фибоначчи F. В ней F = F = 1 и для k > 1 F = F+ F. Начало этой последовательности имеет вид: 1, 1, 2, 3, 5, 8, 13 и так далее. Чтобы найти F, можно просто написать несложную программу, вычисляющую последовательность Фибоначчи до заданного её элемента.

Производящая функция для последовательности Фибоначчи F(x) удовлетворяет условию F(x) = = 1 + x + = 1 + x + = 1 + x + x+ x = 1 + x + x+ x = 1 + x + xF(x) + x = 1 + x + xF(x) + x (F(x) – 1) = 1 + (x + x) F(x). Отсюда F(x) = 1/(1 – x - x).

Берём корни уравнения 1 – x - x = 0 и получаем разложение: 1 – x - x = (1 - ax) (1 - bx), где a = (1 + )/2 и b = (1 - )/2. Используя метод неопределённых коэффициентов A и B, найдем a и b. 1/((1 - ax) (1 - bx)) = A/(1 - ax) + B/ (1 - bx) = (A + B – (Ab+Ba) x) / ((1 - ax) (1 - bx)). Отсюда получаем систему уравнений: . И окончательно A = a/(a - b) и B = b/(b - a). Значит, F(x) = A/(1 - ax) + B/ (1 - bx) = A + B = . При выводе предыдущей формулы использовано то, что 1/(1 - ax) = 1 + ax + ax + … так как (1 - ax) (1 + ax + ax + …) = 1+ ax - ax+ ax - ax+ … = 1. Получаем, что F= (((1 + )/2) - ((1 - )/2) )/ .

Последовательность Фибоначчи является частным случаем последовательности Лукаса, в которой первые два элемента могут быть любыми, а все остальные элементы вычисляются так же, как и в последовательности Фибоначчи.

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

Рассмотрим два конечных множества X1 и X2. /X1X2/ = /X1/ + /X2/ - /X1X2/, так как все элементы из пересечения множеств посчитаны дважды при суммировании мощности самих множеств.

Для примера рассмотрим следующую задачу: в группе 25 студентов (множество Ст. - прямоугольник), из них 20 сдали сессию (множество Ус. – левый овал), 12 занимаются спортом (множество Сп. – правый овал). Из 12 спортсменов 10 сдали сессию (пересечение овалов). Сколько не спортсменов ещё и плохо учатся? Ответом является мощность множества Ст./(Ус. Сп.) = Ст. (Ус. Сп.). Поскольку объединение множеств Ус. и Сп. является подмножеством множества Ст., то ответом является /Ст./ - /Ус. Сп./. По вышеприведённой формуле /Ус. Сп./ = /Ус./ + /Сп./ - /Ус. Сп./ = 20 + 12 – 10 = 22. Ответ: 25 – 22 = 3, трое не спортсменов ещё и плохо учатся.

Рассмотрим три конечных множества X1, X2 и X3. /X1X2X3/ = /X1A/, где A = X2X3. По вышеприведённому /X1A/ = /X1/ + /A/ - /X1A/, а /A/ = /X2X3/ = /X2/ + /X3/ - /X2X3/. /X1A/ = /X1( X2X3)/ = /(X1X2) (X1X3)/ =/X1X2/ + /X1X3/ - /X1X2X1X3/ = /X1X2/+/X1X3/ - /X1X2X3/. Окончательно /X1X2X3/ = (/X1/ + /X2/ + /X3/) - /X1X2/ - /X1X3/ - /X2X3/ + /X1X2X3/ = S1 – S2 +S3. Сначала идёт сумма мощностей единичных множеств (S1), далее с минусом сумма всех мощностей всех пересечений пар множеств(S2), а потом прибавляется мощность тройного пересечения (S3). Это так называемая знакопеременная сумма.

Получим аналогичную формулу для n множеств: X1, … , Xn. Доказательство индукцией по n. Для n = 2 и n = 3 доказали – это первый шаг индукции. Делаем индуктивное предположение, что формула (знакопеременная сумма) верна для (n – 1) подмножества. Получим из этого, что она верна и для n множеств.

Аналогично доказательству для трёх множеств X1, X2 и X3 множество A возьмём равным X2X3…Xn. Тогда /X1X2…Xn/ = /X1A/ = /X1/ + /A/ - /X1A/. По индуктивному предположению (в множестве A объединено (n – 1) множеств) /A/ = / X2X3…Xn / = (/X2/ + /X3/ + … +/Xn/) – (/X2X3/ + … +/Xn-1Xn/) + (/X2X3X4/ + … /Xn-2Xn-1Xn/) - … +(-1)/X2…Xn/ = S1 – S2 +S3 - … +(-1) S(n-1) (только суммы S(j) здесь уже другие, не такие как для трёх множеств. Общего у этих сумм только то, что S1 – это сумма единиц, S2 – это сумма двоек и так далее).

X1A = X1(X2X3…Xn) = (X1X2) (X1X3) … (X1Xn), и опять можно применить индуктивное предположение для объединения (n – 1) множества. /X1A/ = /X1(X2X3…Xn)/ = /(X1X2) (X1X3) … (X1Xn)/ = (/X1X2/+/ X1X3/ + … +/X1Xn/) – (/X1X2X3/+/ X1X2X4/ + … +/X1Xn-1Xn/) + …+(-1) /X1…Xn/. При пересечении нескольких множеств X1 (X1X1 …X1) оно заменялось одним X1.

Окончательно: /X1X2…Xn/ = (/X1/ + /X2/ + … +/Xn/) – (/X1X2/ + … +/Xn-1Xn/) + (/X1X2X3/ + … + /Xn-2Xn-1Xn/) - … +(-1)/X1…Xn/ = S1 – S2 +S3 - … +(-1) Sn. Это формула включений и исключений (знакопеременная сумма).

Часто формула включений и исключений используется в другом виде. Пусть на конечном N-элементном множестве определены n свойств, которыми элементы этого множества могут и обладать, и не обладать. Каждое свойство определяет подмножество элементов, обладающих этим свойством. К этим подмножествам применяется формула включений и исключений с целью определить число элементов, не обладающих ни одним из этих свойств.

N(a, … ,a) – это количество элементов в множестве, обладающих одновременно свойствами a, … ,a. N- количество элементов в множестве, не обладающих ни одним из n свойств. N = N - S+ S- … + (-1) S. S= N(a, … ,a), j=1, 2, … , n.

Например, сколько целых чисел от 100 до 200 не делится ни на 3, ни на 4, ни на 5? Здесь n=3, три свойства: делиться нацело на 3, на 4 и на 5 (быть кратным 3, 4 и 5). Поэтому N = N - S+ S- S. N=101-(33+25+20)+(8+6+5)-(1)=41. Здесь в первой скобке (S) 33 – это количество чисел от 100 до 200, делящихся на 3 (33=[101/3]); 25 – это количество чисел от 100 до 200, делящихся на 4 (25=[101/4]); 20 – это количество чисел от 100 до 200, делящихся на 5 (20=[101/5]). [x] – целая часть числа x.

Во второй скобке (S) 8 - это количество чисел от 100 до 200, делящихся на 3 и на 4, т. е. на 12=34 (8=[101/12]); 6 - это количество чисел от 100 до 200, делящихся на 3 и на 5, т. е. на 15=35 (6=[101/15]); 5 - это количество чисел от 100 до 200, делящихся на 4 и на 5, т. е. на 20=45 (5=[101/20]). Если в первой скобке суммы находятся все наборы из трёх свойств по одному, а во второй – из трёх свойств по два, то в третьей - один-единственный набор из трёх свойств по трём. В третьей скобке (S) 1 - это количество чисел от 100 до 200, делящихся на 3, на 4 и на 5, т. е. на 60=345 (1= [101/60]).

Применим формулу включений и исключений для определения количества целочисленных решений системы: x+x+ … +x=r, bxa, b a, i=1, 2, … , n. a, b - целые неотрицательные числа. Воспользуемся n свойствами: для каждого i xb+1 (не ограничены сверху). Исходное множество решений (N) – это количество целочисленных решений системы, когда x не ограничены сверху (xa для каждого i), а N - количество целочисленных решений этой системы, не обладающих ни одним из n свойств (для каждого i xb+1).

Для примера определим количество двузначных чисел, в которых сумма цифр равна 14. x и x - это первая и вторая цифры в двузначном числе. x+x=14, 9x1, 9x0. x не может быть нулём (более того, не может быть меньше пяти), так как 9x. N – количество целочисленных решений системы без ограничений сверху: x+x=14, x1, x0, где n=2 r’=14-1=13. N=C=C=14. Введём два свойства: x10 и x10. В S два слагаемых и первое определяется при n=2 r’=14-10=4 (x10 и x0), а второе – при n=2 r’=14-1-10=3 (x1 и x10). S = C+C = C+C = 5 + 4 = 9.