Учебно-методический комплекс дисциплины ОПД. В.1.1 Дополнительные главы дискретной математики (стр. 3 )

§ 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. Если строка b получена из строки a с помощью преобразования (1.8), то сумма членов строки b равна удвоенной сумме членов строки a.

ÿ Пусть строка a имеет вид d0, d1,..., dn, а строка b получена по формуле (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). ÿ

Если строка b получена из симметричной строки a с помощью преобразования (1.8), то строка b также является симметричной.

ÿ Пусть строка a : 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, …;