Дискретная математика для будущего учителя математики (стр. 2 )

В нулевом столбце этой таблицы располагаются единицы, а каждая строка, начиная с первой, получается из предыдущей строки умножением на n и сдвигом на один столбец вправо. Для простоты ячейки, содержащие 0, не прорисовываются.

Таблица 1. Числа размещений

n	k
0	1	2	3	4	5	6	7
0	1
1	1	1
2	1	2	2
3	1	3	6	6
4	1	4	12	24	24
5	1	5	20	60	120	120
6	1	6	30	120	360	720	720
7	1	7	42	210	840	2520	5040	5040

Так как =Pn=n!=n(n–1)!=nPn-1, то числа перестановок Pi, где i=0, 1, ..., 7, в этой таблице расположены по диагонали.

Аналогично можно находить и числа сочетаний.

В самом деле, пусть задано некоторое сочетание k элементов из n-элементного множества М. Если элемент an входит в это сочетание, то ему будет соответствовать такое сочетание (k–1) элементов из множества М\{an}, в которое входят те же элементы, что и в данное сочетание, за исключением элемента an. Если же это сочетание не содержит an, то ему соответствует сочетание k элементов из множества М\{an}, которое содержит те же самые элементы (без исключений).

Таким образом, получается рекуррентное соотношение (12).

Используя это соотношение, легко построить для чисел таблицу, которая называется треугольником Паскаля по имени французского математика Блеза Паскаля (), в трудах которого она встречается.

Более точное ее название – арифметический треугольник.

Как вытекает из равенства (12), в такой таблице сумма любых двух рядом стоящих чисел расположена под вторым числом. Таблица 2 построена для n, k=0, 1, 2, …, 7. Сумма чисел в n-ой строке этой таблицы равна 2n ввиду тождества (5).

Таблица 2. Числа сочетаний

n	к
0	1	2	3	4	5	6	7
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
6	1	6	15	20	15	6	1
7	1	7	21	35	35	21	7	1

Рекуррентные соотношения часто применяются и для вывода новых формул.

Задача 2.1. Вывести формулы суммы m-ых степеней первых n натуральных чисел: Sm(n)=1m+2m+...+nm.

Решение: Следует представить числа 2, 3, ..., n, (n+1) в виде суммы двух слагаемых, n раз применить формулу бинома Ньютона, а затем почленно сложить полученные равенства.

.

Тогда получится следующее рекуррентное соотношение:

(n+1)m+Sm(n)–1=Sm(n)+Sm-1(n)+Sm-2(n)+...+S0(n) или

(n+1)m=1+Sm-1(n)+Sm-2(n)+...+S1(n)+S0(n) (13).

Из этого соотношения легко выводятся формулы суммы первых степеней, квадратов, кубов и так далее.

Действительно, если взять в (13) m=1, то S0(n)=n.

При m=2 получается (n+1)2=n2+2n+1=1+2S1(n)+n. Отсюда: 2S1(n)=n(n+1) или S1(n)==1+2+...+n.

При m=3 из того же равенства (13) выводится формула для суммы квадратов: (n+1)3=n3+3n2+3n+1=1+3S2(n)+3S1(n)+n=1+3S2(n)++n.

3S2(n)=n3+3n2+3n––n=n=n=

=n(n+1)=n(n+1).

Теперь следует выразить S2(n)=1+22+32+...+n2=.

При m=4 аналогично получается формула суммы кубов:

(n+1)4=n4+4n3+6n2+4n+1=1+4S3(n)+6S2(n)+4S1(n)+n.

Отсюда, 4S3(n)=n4+4n3+6n2+4n–n(n+1)(2n+1)–2n(n+1)–n=n4+2n3+n2=

=n2(n2+2n+1)=n2(n+1)2. S3(n) = 1 + 23 + 33 + ... + n3 = .

Тем же способом можно получить формулы для сумм четвёртых степеней, пятых степеней и так далее. Интересно, что из последней формулы вытекает совсем неожиданное равенство: 1+23+33+...+n3=(1+2+...+n)2.

Рекуррентным соотношением k-го порядка называется условие

аn+k=F(n,аn+k–1,...аn) (14),

которым задаётся зависимость k-го и последующих членов последовательности {аn} от её предыдущих k членов при любом n=0, 1, 2…. Здесь F – функция (k+1) переменной. Решением рекуррентного соотношения (14) называется последовательность {an}, для которой равенство (14) выполняется при любом n.

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

Общим решением соотношения (14) называется последовательность {Фn(c1,c2,...ck)} от k независимых параметров c1,c2,...ck, если:

а) последовательность {Фn(c1,c2,...ck)} является решением этого соотношения при любом выборе параметров c1,c2,...ck;

б) для любого решения {bn} соотношения (14) можно подобрать такие значения c10,c20,...ck0 параметров c1,c2,...ck, что для всех n=0,1,2,... будет выполняться равенство bn=Фn(c10,c20,...ck0).

При задании конкретных значений параметров c1,c2,...ck из общего решения соотношения (14) получается частное решение.

Таким образом, пользуясь рекуррентным соотношением и начальными условиями, можно один за другим выписывать члены последовательности, причем рано или поздно мы получим любой ее член.

Такой метод называется методом последовательного вычисления элементов решения рекуррентного соотношения.

Довольно часто по известному рекуррентному соотношению для комбинаторного числа требуется найти общий член последовательности, задающей это число, то есть решить рекуррентное соотношение.

Существует весьма часто встречающийся класс соотношений, решаемых единообразным простым методом. Этот класс образуют соотношения вида

(15),

которые называют линейными однородными рекуррентными соотношениями с постоянными коэффициентами, где .

Последовательности, являющиеся решениями соотношения (15) называются возвратными. Этот термин предложил французский математик А. де Муавр.

Например, решением линейного соотношения аn+1=qаn является известная из школьного курса математики возвратная последовательность a0=a, a1=aq, a2=aq2, ..., an=aqn, ... (геометрическая прогрессия). Решением соотношений аn+2=2аn+1–аn или аn+1=аn+d является арифметическая прогрессия a0=a, a1=a+d, a2=a+2d, ..., an=a+nd, ...

Возвратной является и последовательность чисел Фибоначчи.

Методика решения таких соотношений основана на следующей теореме:

Пусть дано рекуррентное соотношение (15).

Составим уравнение , которое называется характеристическим уравнением рекуррентного соотношения (15).

Если все корни этого уравнения различны, то общее решение соотношения (15) имеет вид , где - некоторые константы.