Учебно-методический комплекс дисциплины опд. В 1 дополнительные главы дискретной математики основная образовательная программа подготовки специалиста по специальности 010200 (010501) «Прикладная математика и информатика»

РАЗДЕЛ 2. Методические указания по изучению дисциплины (или ее разделов) и контрольные задания для студентов заочной формы обучения. Нет заочной формы обучения по данной дисциплине. РАЗДЕЛ 3. Содержательный компонент теоретического материала. Примерное содержание лекционного материала. ГЛАВА I. ПРОИЗВОДЯЩАЯ ФУНКЦИЯ § 1. Треугольник Паскаля. Бином Ньютона Рассмотрим строку чисел: d0, d1,..., dn (n=0,1,2,...). Образуем из неё новую строку: s0, s1,..., sn, sn+1 (n=0,1,2,...) по правилу (1.8) Преобразование (1.8) называют преобразованием Паскаля. Пример. Если исходная строка имеет вид 5,0,-5, то строка, полученная из неё по закону Паскаля, будет выглядеть так: 5, 5,-5,-5, а следующая за ней: 5,10,0,-10,-5. Строка чисел d0, d1, dn (n=0,1,2,...) называется симметричной, если dk=dn-k (0kn). Например, строки 7,9,-1,9,7 и 3,0,6,6,0,3 являются симметричными, а строки 7,9,-1,9,-7 и 3,0,6,6,3,0 симметричными не являются. Свойства преобразования Паскаля 1. Если строка  получена из строки  с помощью преобразования (1.8), то сумма членов строки  равна удвоенной сумме членов строки .  Пусть строка  имеет вид d0, d1,..., dn, а строка  получена по формуле (1.8) и имеет вид: s0, s1, sn, sn+1. Тогда s0+s1+...+ sn+sn+1= d0+(d0+d1)+(d1+d2)+...+(dn-1+ dn)+ dn=2(d0+d1+d2+...+dn-1+dn).  Если строка  получена из симметричной строки  с помощью преобразования (1.8), то строка  также является симметричной.  Пусть строка  : d0, d1,..., dn, - симметричная. Тогда s0=d0=dn=sn+1. (*) Кроме того, при 1kn sk=dk -1+dk=dn-(k -1)+dn-k=dn-k +1+dn-k=sn-k +1=s(n+1)-k . (**)  Рассмотрим теперь строку, состоящую из одного числа, - 1. Назовём эту строку нулевой строкой Паскаля. Начиная с этой строки, будем строить треугольник Паскаля, в котором каждая последующая строка получается из предыдущей с помощью преобразования (1.8). Так как при переходе к каждой следующей строке число членов этой строки увеличивается на единицу, то в n-й строке будет n+1 число. Ниже приведены несколько начальных строк треугольника Паскаля: Строка 0 1 Строка 1 1 1 Строка 2 1 2 1 Строка 3 1 3 3 1 Строка 4 1 4 6 4 1 Строка 5 1 5 10 10 5 1 ... ... Нумерация в треугольнике Паскаля осуществляется с нулевой строки, а в строке - с нулевого элемента. Обозначим число, стоящее на m-м месте в n-й строке, через , например, . Свойства треугольника Паскаля 1. Сумма чисел n-й строки равна 2n: = 2n. Это следует из первого свойства преобразования Паскаля с учётом того, что сумма чисел в нулевой строке треугольника равна 1. 2. Все строки треугольника Паскаля симметричны: . Это следует из второго свойства преобразования Паскаля и симметричности нулевой строки треугольника. Докажем, что равно числу сочетаний из n элементов по m: (1.9)  При n=0, m=0 = 1; при m = 0 = 1; при m = n = 1. Кроме того, Таким образом, есть нулевая строка треугольника Паскаля, а n+1-я строка получается из n-й строки по закону Паскаля. Это значит, что при любом m=0,1,2,... строка совпадает с m-й строкой треугольника Паскаля и .  Бином Ньютона Рассмотрим степени суммы (a+b): (a+b)0=1; (a+b)1=1a +1b; (a+b)2=1a2+2ab+1b2; (a+b)3=1a3+3a2b+3ab2+1b3. Легко заметить, что коэффициенты при a и b в правых частях этих равенств для m-й степени (m=0,1,2,3) совпадают с числами в m-й строке треугольника Паскаля. Докажем, что (a+b)n можно вычислить по формуле (a+b)n = Cn0 an + Cn1 an−1b + Cn2 an−2b2 + … + Cnn−1 a bn−1 + Cnn bn = Cnk an−kbk, (1.10) которая называется формулой бинома Ньютона или просто биномом Ньютона.  Доказательство проведём методом математической индукции. Выше было показано, что при n=0,1,2,3 формула (1.10) верна. Предположим, что она верна при n=m : (a+b)m = Cm0 am + Cm1 am−1b + Cm2 am−2b2 + … + Cmm−1 a bm−1 + Cmm bm = Cmk am−kbk и докажем, что она будет верна и при n = m+1. В самом деле, (a+b)m+1 = (a+b) (a+b)m = (a+b) Cmk am−kbk = = Cmk am−k+1 bk + Cmk am−kbk+1 = Cmk am−k+1 bk +Cmk−1 am−k+1 bk = = Cm0 am+1 + Cmk am−k+1 bk + Cmk−1 am−k+1 bk + Cmm bm+1 = = am+1 + (Cmk + Cmk−1 )am−k+1 bk + bm+1 = = Cm+10 am+1 + Cm+1k am−k+1 bk + Cm+1 m+1 bm+1 = Cm+1k am+1−k bk .  § 2. Формальный степенной ряд (ФСР) Производящей функцией числовой последовательности an наз. степенной ряд вида: а(x) = аn xn. Экспоненциальной производящей функцией числовой последовательности an наз. степенной ряд вида: аe(x) = ( аn / n!) xn. Если радиус сходимости радов в правых частях данных формул нулевой, то оперировать с ними можно, рассматривая их как формальные объекты в рамках формального исчисления − алгебры формальных степенных рядов. Аксиомы равенства ( аn xn = bn xn )  (аn = bn) для n = 0, 1, 2, …, (( аn / n!) xn = ( bn / n!) xn)  (аn = bn) для n = 0, 1, 2, …; суммы аn xn + bn xn = (аn + bn) xn , ( аn / n!) xn + ( bn / n!) xn = [ (аn + bn) / n!] xn; произведения аn xn  bn xn = kn xn , где kn = аi bn-i, ( аn / n!) xn  ( bn / n!) xn = ( dn / n!) xn, где dn = Cni аi bn-i; умножения на скаляр  аn xn =  аn xn ,  ( аn / n!) xn = ( аn / n!) xn для  R. Вычитание двух ФСР определим, как сложение первого ряда со вторым, помноженным на (−1). Ноль-ряд − тот, у которого аn = 0 для n = 0, 1, 2, …; единица-ряд − тот, у которого а0 = 1, аn = 0 для n = 1, 2, … Пусть A − множество всех ФСР вида аn xn, Aе − множество всех ФСР вида ( аn / n!) xn. Алгебра (А, +, , −, 0, 1) наз. алгеброй отношений; алгебра (Aе, +, , −, 0, 1) наз. биномиальной алгеброй. Теорема. Биномиальная алгебра и алгебра отношений являются целостными кольцами. Композиция ФСР Теорема. Если а0 = 0, то выражение: bn ( аk xk) n является формальным степенным рядом. Обратимость ФСР Ряд bn xn называется обратным к ряду аn xn, если их произведение равно 1. Теорема. Ряд, обратный к ряду аn xn существует, тогда и только тогда, когда а0  0. Чтобы найти обратный ряд, надо составить вспомогательный ряд g(x) = 1 − (1/ а0) аn xn; обратный ряд найти по формуле: ( аn xn)−1 = (1/ а0) (1 + g(x) + g2(x) +… ). Деление двух ФСР определим, как умножение первого ряда на ряд, обратный ко второму (если обратный существует). Аксиомы дифференцирования аn xn = (n+1) аn+1 xn, ( аn / n!) xn = ( аn+1 / n!) xn . интегрирования  (аn xn ) dx = ( аn−1 / n) xn,  ( ( аn / n!) xn ) = ( аn−1 / n!) xn . Для ФСР выполняются все элементарные свойства производных. § 3. Операции над производящими функциями Основной принцип теории производящих функций: пусть имеется некоторое равенство, содержащее степенные ряды, которое выполняется, если считать ряды сходящимися в некоторой окрестности нуля. Принято считать, что это равенство остаётся верным, если его рассматривать как соотношение между ФСР (лишь бы операции, участвующие в равенстве, имели смысл для ФСР). Операции над производящими функциями 1. Линейные. Пусть ,   R. ( c(n) =  a(n) +  b(n) )  ( c(x) =  a(x) +  b(x), ce(x) =  ae(x) +  be(x) ). 2. Изменение масштаба. ( b(n) = n a(n) )  ( b(x) = xa(x), be (x) = xae (x) ). 3. Сдвиг начала. а) b(n) =  b(x) = a(x) xk, be(x) = … ae(x) dx (k раз). б) b(n) = a(n+k)  b(x) = [ a(x) − аi xi ] x−k, be(x) = ae (x). 4. Подобие. Пусть   R. ( b(n) = n a(n) )  ( b(x) = a(x), be(x) = ae(x) ). 5. Свёртка. ( kn = аi bn-i )  ( k(x) = a(x)  b(x) ). Таблица простейших производящих функций № п/п аn а(x) аe(x) 1 1 1 / (1−x) ex 2  n 1 / (1−x) ex 3 1 / n! ex − 4  n / n! ex − 5 Cn (1+x)  − 6 C n n+  −1 (1−x) − − 7  n C n n+  −1 (1−x) − − 8 n x / (1−x)2 x ex § 4. Производящие функции числа основных комбинаторных объектов 4.1. Сочетания Пусть М = {e1, e2, … em}. Рассмотрим произведение: (1+ e1x) (1+ e2x) … (1+ em x) = 1 + x (e1+ e2 + … + em) + + x2 (e1e2 + e1e3 + … + em−1 em) + … + xm e1 e2 … em. Каждое слагаемое коэффициента при xk соответствует одному сочетанию. Положим e1 = e2 = …= em = 1, получим: (1+x) m = Cm0 + Cm1 x + Cm2 x2 + … + Cmm xm. 4.2. Сочетания с повторениями Пусть М = {e1, e2, … em}. Количество вхождений объекта в комбинацию называется кратностью. Пусть кратность объекта ei может составлять k1(ei) или k2(ei) или … Рассмотрим произведение: (xk1 (e1) + xk2 (e1) + … ) (xk1 (e2) + xk2 (e2) + … ) …(xk1 (em) + xk2 (em) + … ). После раскрытия скобок и приведения подобных коэффициент при xk равен числу требуемых сочетаний с повторениями. Теорема. Число сочетаний с повторениями из m по k без всяких ограничений на кратность элементов в данном сочетании составляет C k m+ k −1. 4.3. Размещения Составим экспоненциальную производящую функцию последовательности a(k) = Akm: A0m + (A1m / 1!) x + (A2m / 2!) x2 + … = Cm0 + Cm1 x + Cm2 x2 + …= (1+x) m. 4.4. Размещения с повторениями Пусть  − такая выборка из М = {e1, e2, … em}, что объект e1 входит в  t1 раз, e2 входит в  t2 раз,… em входит в  tm раз, причём t1 + t2 + … + tm = k. Тогда  называется k–выборкой состава t1, t2, … , tm . Обозначим: P (t1, t2, … , tm) = k! / ( t1! t2! … tm ! ). Пусть кратность объекта ei может составлять k1(ei) или k2(ei) или … Составим экспоненциальную производящую функцию: (xk1 (e1) / k1(e1)! + xk2 (e1) / k2(e1)! + … )   (xk1 (e2) / k1(e2)! + xk2 (e2) / k2(e1)! + … )  …  (xk1 (em) / k1(em)! + xk2 (em) / k1(em)! + … ). Предположим, что скобки раскрыли. Проанализируем состав одного слагаемого в коэффициенте при xk, соответствующего выборке (k(e1), k(e2), …, k(em)): [ x (e1) / k(e1)! ]  [x(e2) / k(e2)! ]  …  [x (em) / k(em)! ] = = xk / [k(e1)! k(e2)! … k(em)!] * (k! / k!) = = P (k(e1), k(e2), … k(em))  xk / k!. Теорема. Число k–выборок без ограничения на количество повторений составляет mk . 4.5. Композиции числа k – это суммы вида: zi = k, где m, k, zi  N, причём суммы, отличающиеся порядком слагаемых, считаются различными. Обозначим zk (m) – количество композиций числа k на m частей; zk – количество композиций числа k на произвольное количество частей. zk(m) равно числу способов разместить m–1 разделитель в k–1 ячейках между k единицами, т.е. . Доопределим z(x) = 0, если k < m. Пусть ak = = . Тогда a(x) = 1/ (1–x)m . Очевидно, что zk(m) =  z(m)(x) = a(x) xm = xm / (1–x)m . Перейдём к определению zk: zk = zk(m) = = 2k−1. Пусть bk = 2k. Тогда b(x) = 1/ (1–2x). Очевидно, что zk =  z(x) = b(x) x = x / (1–2x) . 4.5. Разбиения числа k – это суммы вида: zi = k, где m, k, zi  N, причём суммы, отличающиеся порядком слагаемых, считаются одинаковыми. Обозначим rk (m) – количество разбиений числа k на m частей; R(m,k) – количество разбиений числа k на части, максимальная из которых не превышает m. Лемма. Число решений уравнения 1 x1 + 2 x2 + … m  xm = k в целых неотрицательных числах равно R(m,k). Теорема. Количество разбиений числа k на m частей равно количеству разбиений числа k на части, максимальная из которых равна m, т.е. rk (m) = R(m,k) – R(m–1,k). Теорема. Пусть R(m,x) – производящая функция последовательности R(m,k). Тогда R(m,x) = (1+x+x2+…) (1+x2+x4+…) (1+x m +x2 m +…) = (1/ (1– x)) (1/ (1– x2)) …(1/ (1– xm)).

Похожие:

	Учебно-методический комплекс дисциплины опд. В. 4 Математические... Целями изучения дисциплины являются: формирование профессиональных навыков по изучению, анализу и оптимизации экономических процессов...		Рабочая программа для студентов очной формы обучения, направление... Иванов Д. И. Дополнительные главы дискретной математики. Учебно-методический комплекс. Рабочая программа для студентов очной формы...
	Учебно-методический комплекс дисциплины дс компьютерные сети и системы... Рецензенты: кандидат физико-математических наук, доцент Маренич А. С., кандидат технических наук, доцент Ланина Н. Р		Учебно-методический комплекс дисциплины опд. Ф. 25 (опд. Ф. 13) «Специальная психология» Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины опд. Ф. 25 (опд. Ф. 13) «Специальная психология» Основная образовательная программа подготовки специалиста по специальности (специальностям)		Учебно-методический комплекс дисциплины опд. Ф. 11 Основы коммуникативной... Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины опд. Ф. 10, Опд. Ф. 12, Опд.... А. В. Прялухина, кандидат психологических наук, доцент, зав кафедрой психологии Российского государственного социального университета...		Учебно-методический комплекс дисциплины опд. Ф. 21 Методы географических... Основная образовательная программа подготовки специалиста по специальности (специальностям)
	Учебно-методический комплекс дисциплины опд. В 2 опд. В 1 Современный... Педагогика и методика начального образования со специализацией «Обучение информатике в начальной школе»		Учебно-методический комплекс гсэ. В 1 история математической науки... Автор программы: кандидат физ мат наук, доцент кафедры математики и мом локоть Наталья Васильевна
	Учебно-методический комплекс фтд: универсальная алгебра основная... ...		Учебно-методический комплекс дисциплины опд. Ф. 8 Религиоведение... Пащенко Л. В., к ф н., старший преподаватель кафедры связей с общественностью и лингвистики мгту
	Учебно-методический комплекс дисциплины математическая логика Основная... Автор программы: Шиманский Сергей Александрович, ст преподаватель кафедры информатики и отд		Учебно-методический комплекс дисциплины опд. Ф. 4 История религии... ...
	Учебно-методический комплекс дисциплины фтд. 1 Основы кинезиологии... Основная образовательная программа подготовки специалиста по специальности (специальностям)		Учебно-методический комплекс дисциплины опд. Ф. 2 Геоморфология основная... Цель дисциплины. В соответствии с Государственным образовательным стандартом высшего профессионального образования по специальности...