Введение в математику

Комбинаторика и числовые системы

Разбить на страницы
Показывать лекцию целиком

Комбинаторика и числовые системы

Индукция, индуктивный метод - это метод получения общего заключения (вывода) на основании частных, отдельных фактов, свойств изучаемой системы, процесса. Если общий вывод делается только после рассмотрения всех охватываемых им частных случаев, то индукция называется полной, иначе она называется неполной.

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

Обозначим доказываемое утверждение, зависящее от натурального параметра n, через A(n).

Пусть доказываемое утверждение A(n) проверено для частного значения, например, для n=1, то есть начальное утверждение A(1) - справедливое утверждение. Если предположить, что утверждение справедливо при каком-то значении n-1 (то есть справедливо утверждение A(n-1) ), то отсюда следует, что это утверждение справедливо и для любого n (то есть справедливо и утверждение A(n) ).

Для применения метода математической индукции не обязательно проверять факт именно для случая n=1. Достаточно проверить для какого-то фиксированного значения n=n0, например, для n=2.

Рекурсия, рекуррентность - это ссылка определяемого объекта (при каком-то значении определяющего параметра) на самого себя (при другом значении этого параметра или при других значениях параметров).

Такие ссылки часто используются как в математике, так и, например, в информатике.

Комбинаторика - раздел математики, в котором для конечных множеств рассматриваются различные комбинации, соединения элементов множеств (а также и подмножеств) и их свойства.

Одной из важных классических задач комбинаторики является задача нахождения количества способов размещения какого-то числа заданных объектов в некотором заданном количестве мест ("ящиков") таким образом, чтобы они удовлетворяли при этом некоторым заданным условиям (ограничениям).

Строгая математическая формулировка класса задач размещения такова: для данных двух конечных множеств X, Y определить количество функций $$f:X\to Y$$, удовлетворяющих заданным ограничениям на мощности множеств. Часто используется и такая интерпретация постановки задачи размещения: сколько существует способов покраски объектов X различными цветами (набор Y ), чтобы цвета объектов y=f(x) удовлетворяли определенным ограничениям.

Факториалом числа n (обозначается как n!) называется произведение всех натуральных чисел до n включительно: $$n!=1\cdot 2\cdot 3\cdot \dotsc \cdot (n-1)\cdot n $$ .

Пример. Факториал $$3!= 1\cdot 2\cdot 3=6$$, $$4!= 1\cdot 2\cdot 3\cdot 4=3!\cdot 4=24$$.

Из предыдущего примера можно сделать вывод, что справедлива следующая теорема.

Теорема. Имеет место формула: $$n!=(n-1)!\cdot n$$.

Доказательство. По определению факториала $$\smu (n-1)!=1\cdot 2\cdot 3\cdot \dotsc \cdot (n-1)$$. Подставляя в формулу $$n!=1\cdot 2\cdot 3\cdot \dotsc\cdot (n-1)\cdot n$$ вместо произведения первых n-1 сомножителей равное ему значение (n-1)!, получим доказываемое. Докажите эту теорему методом математической индукции самостоятельно.

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

Пример. Факториал 10!=3628800! (последний восклицательный знак - восклицательный из-за его большого значения, а не знак факториала).

При вычислении выражений с факториалами можно эффективно сокращать.

Пример. Вычислим $$\frac {12!}{10!} = \frac {10!\cdot 11\cdot 12}{10!} =11\cdot 12 = 132$$.

Размещение из n элементов по k элементов - всякое упорядоченное подмножество, состоящее из k элементов множества из n элементов. Два размещения отличны друг от друга, если они отличаются либо составом элементов, либо порядком элементов. Число различных размещений из n элементов по k элементов обозначается символом $$A^k_n$$.

Пример. Размещение $$A^2_5= \frac {5!}{3!} =4\cdot 5=20$$.

Теорема. Число различных размещений из n элементов по k равно$$A^k_n = \frac {n!}{(n-k)!} =(n-k+1)(n-k+2)\dotsc(n-1)n,$$ причем имеет место следующее соотношение:$$A^k_n = (n-k+1)A^{k-1}_n.$$

Размещение n элементов по n элементов называется перестановкой .

Теорема. Число различных перестановок равно Pn=n!.

Подстановкой ( n -ой степени) из n элементов называется взаимно однозначное отображение множества из n символов на себя. Обычно элементы этого множества нумеруются и отождествляются с n числами натурального ряда чисел.

Пример. Вместо подстановки - отображения элементов множества X={a, b, c, g}, - говорят об отображении множества {1, 2, 3, 4} и обозначают эту подстановку как$$\begin{pmatrix} 1 2 3 4 \cr 2 4 1 3 \end{pmatrix}$$

Умножение подстановок - операция, которая ставит в соответствие упорядоченной паре подстановок n -ой степени A и B третью подстановку C той же степени по правилу:$$A= \begin{pmatrix} 1 2 3 \dotsc n\cr i_1 i_2 i_3 \dotsc i_n\cr \end{pmatrix},$$ $$B= \begin{pmatrix} i_1 i_2 i_3 \dotsc i_n\cr j_1 j_2 j_3 \dotsc j_n\cr \end{pmatrix},$$ $$C= \begin{pmatrix} 1 2 3 \dotsc n \cr j_1 j_2 j_3 \dotsc j_n \end{pmatrix} .$$

Часто бывает необходимо найти число всех подмножеств, состоящих из m элементов, каждое из которых можно составить из n элементов данного множества. Это число равно $$C^m_n$$ и называется сочетанием из n элементов по m элементов.

Теорема. Верны равенства $$C^k_n = \frac {n!}{k!(n-k)!}$$, $$C^k_n = \frac {A^k_n}{P_k}$$.

Пример. Найдем число $$C^2_4 = \frac {4!}{2!(4-2)!} = \frac {4!}{2!2!} = \frac {1\cdot 2\cdot 3\cdot 4}{1\cdot 2\cdot 1\cdot 2} =6$$.

Рассмотрим известные формулы

(a+b)1 = a+b , 
 (a+b)2 = a2+2ab+b2, 
 (a+b)3 = a3+3a2b+3ab2+b3.

Аналогично можно вычислять остальные степени, но мы вместо продолжения такой последовательности формул сформулируем общую теорему о них.

Теорема. Справедлива формула (бинома Ньютона):$$(a+b)^n = a^n + \frac {n}{1!}a^{n-1} b + \frac {n(n-1)}{2!}a^{n-2} b^2 + \dotsc \\ \dotsc + \frac {n(n-1)(n-2)\dotsc (n-k+1)}{k!} a^{n-k}b^k + \dotsc + b^n, \\ k! =1\cdot 2\cdot 3 \cdot \dotsc\cdot (k-1)k , \quad k!=(k-1)! k, \quad 0!=1.$$

Эту теорему можно доказать методом математической индукции. Это Ваша непростая и самостоятельная работа.

Используя эти числа $$C^m_n$$, можно записать бином Ньютона: $$(a+b)^n = C^0_n a^n + C^1_n a^{n-1}b + \dotsc + C^k_na^{n-k}b^k + \dotsc + C^n_n b^n$$.

Коэффициент называется биномиальным коэффициентом.

Теорема. Справедливы формулы для биномиальных коэффициентов:

  • $$2^n=C^0_n+C^1_ n +\dotsc+ C^n_n$$ - свойство суммы биномиальных коэффициентов;
  • $$C^m_n=C^{n-m}_n$$ - свойство симметрии;
  • $$C^m_n+C^{m+1}_n = C^{m+1}_{n+1}$$ - свойство сложения.
    •

    Доказательство. Докажем первое равенство. Если в формуле бинома Ньютона положить a=b=1, то непосредственно получаем это равенство. Докажем второе равенство. Так как$$C^m_n = \frac {n!}{m!(n-m)!}, \\ C^{n-m}_n = \frac {n!}{(n-m)!m!},$$ то равенство - очевидное. Равенство 3 можно доказать как прямой подстановкой формул с факториалами для всех участников этого равенства и последующего приведения к общему знаменателю, так и с помощью следующих рассуждений: $$C^{m+1}_{n+1}$$ - число всевозможных (m+1) -элементных подмножеств из (n+1) -элементного множества. Если ограничиться выбором m элементов, то таких случаев будет ровно $$C^m_n$$, а если рассмотреть остальные (исключая выбранные) возможности, то их будет ровно $$C^m_n$$. Складывая их, получаем доказываемое равенство.

    Выше мы уже использовали обозначение $$\sum^n_{k=1} x_k$$ для суммы чисел x1+x2+...+xn.

    Иногда нижний предел суммирования снабжают условием - "ограничителем" суммируемых членов этой последовательности.

    Пример. Если нужно суммировать только числа на четных местах до n, то можно использовать одно из следующих обозначений (лучшее - первое):$$\sum\limits_{k=1}^{[n/2]} x_{2k}, \qquad \sum\limits^n_{\substack {k=2\\k=2m, \ m\in N}} x_k, \qquad \sum\limits^n_{\substack {k=2\\k \mod 2 =0}} x_k, \qquad \sum\limits^n_{k\ \text{--- четное}} x_k.$$

    Здесь [n/2] - целая часть от числа половины числа n.

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

    Пример. Когда Гаусса в десятилетнем возрасте учитель решил, как он предполагал, занять надолго подсчетом суммы Sn=1+2+3+...+n, то будущий математик додумался до уловки, на которой базируется теперь вычисление суммы арифметической прогрессии: Sn + Sn = (1 + 2 + 3 + ... + n-1 + n) + (n + n-1 + n-2 + ... + 2 + 1) = = (1 + n) + (2 + n-1) + (3 + n-2) + ... + (n-1 + 2) + (n + 1) = = (1 + n) + (1 + n) + (1 + n) + ... + (1 + n) + (1 + n) = (1 + n)n. Отсюда получаем известную формулу суммы членов арифметической прогрессии: Sn=(n+1)n/2.

    Рассмотрим некоторые общие методы вычисления конечных сумм.

    Самым простым прагматическим методом является поиск нужной суммы в справочниках "Сумм и интегралов" (человеческим опытом и знаниями нельзя пренебрегать!). Многие часто используемые суммы кем-то наверняка уже давно вычислены и предлагаются в этих справочниках.

    Пример. Важные суммы из, например, известного справочника Двайта "Таблица сумм и интегралов":$$\sum\limits^n_{k=1} k^2 = \frac {n(n+1)(2n+1)}{6}, \\ \sum\limits^n_{k=1} k^3 = \frac {n^2(n+1)^2} 4, \\ \sum\limits^n_{k=0} (-1)^k \frac {1}{2k+1} = \frac {\pi}{4}, \\ \sum\limits^n_{k=1} \frac {1}{k^2} = \frac {\pi^2}{6}.$$

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

    Третий метод можно назвать методом подбора подходящей рекуррентной зависимости. Он базируется на следующей теореме.

    Теорема. Если для суммы вида$$S_n= \sum^n_{k=1}x_k$$ можно найти функцию F(k), для которой при любом k выполнено рекуррентное равенство xk=F(k+1)-F(k), то данную сумму можно вычислить по формуле: Sn=F(n+1)-F(1).

    Пример. Вычислим сумму вида$$\sum^n_{k=1} \frac {1}{k(k+1)}.$$ Здесь $$x_k=\frac {1}{k(k+1)}$$ и, как легко это проверить, справедливо равенство$$x_k = \frac 1k - \frac {1}{k+1}.$$ Поэтому имеем равенство $$F(k)=-\frac {1}{k}$$ для всех натуральных значений k. Тогда можно записать равенство вида$$\sum^n_{k=1} \frac {1}{k(k+1)} = \frac {n}{n+1}.$$

    Сумма$$S_n= \sum^n_{k=1} x_k$$ эквивалентна рекуррентности$$S_0=x_0, \ \ S_n=S_{n-1}+x_n,\quad n>0,$$ а эта связь помогает эффективно вычислять суммы.

    Есть и другие, достаточно сложные методы суммирования.

    Аналогично знаку суммы вводится и знак произведения:$$P_n=\prod\limits^n_{k=1}x_k =x_{1x2} \cdots x_n .$$

    Пример. Факториал числа n>0 можно записать в виде$$n!=\prod^n_{k=1} k.$$ Для n=0 условно полагают 0!=1. Он совпадает с 1!.

    В математике часто используют ряд чисел, имеющих собственные имена в силу их исключительной важности. Примером такого числа является рассмотренное выше натуральное число (число Непера) e. Число $$\pi$$ можно также отнести к таким числам. Рассмотрим некоторые другие важные числа.

    Числа Мерсенна - числа вида Mn=2n-1. Если n - не простое (например, кратно m, то есть n=km ), то эти числа - всегда не простые, так как в этом случае имеет место разложение (2km-1)=(2m-1)(2m(k-1)+2m(k-1)+ ...+1). Эти числа не всегда простые и в том случае, когда n - простое число.

    Числа Ферма имеют вид: $$F_n=2^{2^n}+1$$ и предполагались самим Ферма (кстати, в письме к Мерсенну) простыми $$(n\ge 0)$$, но затем было доказано, что F5=4294967297 - не простое и делится, например, на 641.

    Числа Паскаля или треугольник Паскаля (проявление красоты и симметрии математических объектов):$$\begin{matrix} n C_n^0C_n^1C_n^2C_n^3C_n^4C_n^5C_n^6C_n^7C_n^8C_n^9C_n^{10} \cr 0 1 \cr 1 1 1 \cr 2 1 2 1 \cr 3 1 3 3 1 \cr 4 1 4 6 4 1 \cr 5 1 5 10 10 5 1 \cr 6 1 6 15 20 15 6 1 \cr 7 1 7 21 35 35 21 7 1 \cr 8 1 8 28 56 70 56 28 8 1 \cr 9 1 9 36 84 126 126 84 36 9 1 \cr 10 1 10 45 120 210 252210120 45 10 1 \cr \end{matrix}$$

    Числа Эйлера $$\langle C^m_n\rangle$$ (треугольник Эйлера), связывают обычные степени с биномиальными коэффициентами и удовлетворяют соотношениям:$$x^n =\sum\limits^n_{k=0} \langle C^k_n\rangle C^n_{x+k} , \quad n\ge 0, \\[3pt] \langle C^k_n\rangle =(k+1) \langle C^k_{n-1}\rangle + (n-k) C^{k-1}_{n-1}, \quad \langle C^0_0\rangle =1.$$ Эти числа можно записать в виде, аналогичном треугольнику Паскаля:$$\begin{matrix} n \kern-1pt\langle C_n^0\rangle\kern-1pt \langle C_n^1\rangle \langle C_n^2\rangle \langle C_n^3\rangle \langle C_n^4\rangle \langle C_n^5\rangle \langle C_n^6\rangle \langle C_n^7\rangle \kern-1pt\langle C_n^8\rangle\kern-1pt \kern-1pt\langle C_n^9\rangle\kern-1pt \cr 0 1 \cr 1 1 0 \cr 2 1 1 0 \cr 3 1 4 1 0 \cr 4 1 11 11 1 0 \cr 5 1 26 66 26 1 0 \cr 6 1 57 302 302 57 1 0 \cr 7 1 120 1191 2416 1191 120 1 0 \cr 8 1 247 4293 15619 15619 4293 247 1 0 \cr 9 1 502 14608 88234 156190 88234 14608 502 1 0 \cr \end{matrix}$$

    Пример. Из треугольника Эйлера и приведенного выше рекуррентного соотношения получаем, в частности,$$x^2=C^2_x =C^2_{x+1}, \\[2pt] x^3=C^3_x +4C^3_{x+1} + C^3_{x+2}, \\[2pt] x^4 = C^4_x + 11 C^4_{x+1} +11C^4_x + C^4_{x+1} \ \ \text{и т.д.}$$

    В математике (особенно, в ее разделе - "теория чисел") рассматриваются и другие замечательные числа.

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

    Страницы:

    Комбинаторика и числовые системы

    Индукция, индуктивный метод - это метод получения общего заключения (вывода) на основании частных, отдельных фактов, свойств изучаемой системы, процесса. Если общий вывод делается только после рассмотрения всех охватываемых им частных случаев, то индукция называется полной, иначе она называется неполной.

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

    Обозначим доказываемое утверждение, зависящее от натурального параметра n, через A(n).

    Пусть доказываемое утверждение A(n) проверено для частного значения, например, для n=1, то есть начальное утверждение A(1) - справедливое утверждение. Если предположить, что утверждение справедливо при каком-то значении n-1 (то есть справедливо утверждение A(n-1) ), то отсюда следует, что это утверждение справедливо и для любого n (то есть справедливо и утверждение A(n) ).

    Для применения метода математической индукции не обязательно проверять факт именно для случая n=1. Достаточно проверить для какого-то фиксированного значения n=n0, например, для n=2.

    Рекурсия, рекуррентность - это ссылка определяемого объекта (при каком-то значении определяющего параметра) на самого себя (при другом значении этого параметра или при других значениях параметров).

    Такие ссылки часто используются как в математике, так и, например, в информатике.

    Комбинаторика - раздел математики, в котором для конечных множеств рассматриваются различные комбинации, соединения элементов множеств (а также и подмножеств) и их свойства.

    Одной из важных классических задач комбинаторики является задача нахождения количества способов размещения какого-то числа заданных объектов в некотором заданном количестве мест ("ящиков") таким образом, чтобы они удовлетворяли при этом некоторым заданным условиям (ограничениям).

    Строгая математическая формулировка класса задач размещения такова: для данных двух конечных множеств X, Y определить количество функций $$f:X\to Y$$, удовлетворяющих заданным ограничениям на мощности множеств. Часто используется и такая интерпретация постановки задачи размещения: сколько существует способов покраски объектов X различными цветами (набор Y ), чтобы цвета объектов y=f(x) удовлетворяли определенным ограничениям.

    Факториалом числа n (обозначается как n!) называется произведение всех натуральных чисел до n включительно: $$n!=1\cdot 2\cdot 3\cdot \dotsc \cdot (n-1)\cdot n $$ .

    Пример. Факториал $$3!= 1\cdot 2\cdot 3=6$$, $$4!= 1\cdot 2\cdot 3\cdot 4=3!\cdot 4=24$$.

    Из предыдущего примера можно сделать вывод, что справедлива следующая теорема.

    Теорема. Имеет место формула: $$n!=(n-1)!\cdot n$$.

    Доказательство. По определению факториала $$\smu (n-1)!=1\cdot 2\cdot 3\cdot \dotsc \cdot (n-1)$$. Подставляя в формулу $$n!=1\cdot 2\cdot 3\cdot \dotsc\cdot (n-1)\cdot n$$ вместо произведения первых n-1 сомножителей равное ему значение (n-1)!, получим доказываемое. Докажите эту теорему методом математической индукции самостоятельно.

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

    Пример. Факториал 10!=3628800! (последний восклицательный знак - восклицательный из-за его большого значения, а не знак факториала).

    При вычислении выражений с факториалами можно эффективно сокращать.

    Пример. Вычислим $$\frac {12!}{10!} = \frac {10!\cdot 11\cdot 12}{10!} =11\cdot 12 = 132$$.

    Размещение из n элементов по k элементов - всякое упорядоченное подмножество, состоящее из k элементов множества из n элементов. Два размещения отличны друг от друга, если они отличаются либо составом элементов, либо порядком элементов. Число различных размещений из n элементов по k элементов обозначается символом $$A^k_n$$.

    Пример. Размещение $$A^2_5= \frac {5!}{3!} =4\cdot 5=20$$.

    Теорема. Число различных размещений из n элементов по k равно$$A^k_n = \frac {n!}{(n-k)!} =(n-k+1)(n-k+2)\dotsc(n-1)n,$$ причем имеет место следующее соотношение:$$A^k_n = (n-k+1)A^{k-1}_n.$$

    Размещение n элементов по n элементов называется перестановкой .

    Теорема. Число различных перестановок равно Pn=n!.

    Подстановкой ( n -ой степени) из n элементов называется взаимно однозначное отображение множества из n символов на себя. Обычно элементы этого множества нумеруются и отождествляются с n числами натурального ряда чисел.

    Пример. Вместо подстановки - отображения элементов множества X={a, b, c, g}, - говорят об отображении множества {1, 2, 3, 4} и обозначают эту подстановку как$$\begin{pmatrix} 1 2 3 4 \cr 2 4 1 3 \end{pmatrix}$$

    Умножение подстановок - операция, которая ставит в соответствие упорядоченной паре подстановок n -ой степени A и B третью подстановку C той же степени по правилу:$$A= \begin{pmatrix} 1 2 3 \dotsc n\cr i_1 i_2 i_3 \dotsc i_n\cr \end{pmatrix},$$ $$B= \begin{pmatrix} i_1 i_2 i_3 \dotsc i_n\cr j_1 j_2 j_3 \dotsc j_n\cr \end{pmatrix},$$ $$C= \begin{pmatrix} 1 2 3 \dotsc n \cr j_1 j_2 j_3 \dotsc j_n \end{pmatrix} .$$

    Часто бывает необходимо найти число всех подмножеств, состоящих из m элементов, каждое из которых можно составить из n элементов данного множества. Это число равно $$C^m_n$$ и называется сочетанием из n элементов по m элементов.

    Теорема. Верны равенства $$C^k_n = \frac {n!}{k!(n-k)!}$$, $$C^k_n = \frac {A^k_n}{P_k}$$.

    Пример. Найдем число $$C^2_4 = \frac {4!}{2!(4-2)!} = \frac {4!}{2!2!} = \frac {1\cdot 2\cdot 3\cdot 4}{1\cdot 2\cdot 1\cdot 2} =6$$.

    Рассмотрим известные формулы

    (a+b)1 = a+b , 
 (a+b)2 = a2+2ab+b2, 
 (a+b)3 = a3+3a2b+3ab2+b3.

    Аналогично можно вычислять остальные степени, но мы вместо продолжения такой последовательности формул сформулируем общую теорему о них.

    Теорема. Справедлива формула (бинома Ньютона):$$(a+b)^n = a^n + \frac {n}{1!}a^{n-1} b + \frac {n(n-1)}{2!}a^{n-2} b^2 + \dotsc \\ \dotsc + \frac {n(n-1)(n-2)\dotsc (n-k+1)}{k!} a^{n-k}b^k + \dotsc + b^n, \\ k! =1\cdot 2\cdot 3 \cdot \dotsc\cdot (k-1)k , \quad k!=(k-1)! k, \quad 0!=1.$$

    Эту теорему можно доказать методом математической индукции. Это Ваша непростая и самостоятельная работа.

    Используя эти числа $$C^m_n$$, можно записать бином Ньютона: $$(a+b)^n = C^0_n a^n + C^1_n a^{n-1}b + \dotsc + C^k_na^{n-k}b^k + \dotsc + C^n_n b^n$$.

    Коэффициент называется биномиальным коэффициентом.

    Теорема. Справедливы формулы для биномиальных коэффициентов:

  • $$2^n=C^0_n+C^1_ n +\dotsc+ C^n_n$$ - свойство суммы биномиальных коэффициентов;
  • $$C^m_n=C^{n-m}_n$$ - свойство симметрии;
  • $$C^m_n+C^{m+1}_n = C^{m+1}_{n+1}$$ - свойство сложения.
    •

    Доказательство. Докажем первое равенство. Если в формуле бинома Ньютона положить a=b=1, то непосредственно получаем это равенство. Докажем второе равенство. Так как$$C^m_n = \frac {n!}{m!(n-m)!}, \\ C^{n-m}_n = \frac {n!}{(n-m)!m!},$$ то равенство - очевидное. Равенство 3 можно доказать как прямой подстановкой формул с факториалами для всех участников этого равенства и последующего приведения к общему знаменателю, так и с помощью следующих рассуждений: $$C^{m+1}_{n+1}$$ - число всевозможных (m+1) -элементных подмножеств из (n+1) -элементного множества. Если ограничиться выбором m элементов, то таких случаев будет ровно $$C^m_n$$, а если рассмотреть остальные (исключая выбранные) возможности, то их будет ровно $$C^m_n$$. Складывая их, получаем доказываемое равенство.

    Выше мы уже использовали обозначение $$\sum^n_{k=1} x_k$$ для суммы чисел x1+x2+...+xn.

    Иногда нижний предел суммирования снабжают условием - "ограничителем" суммируемых членов этой последовательности.

    Пример. Если нужно суммировать только числа на четных местах до n, то можно использовать одно из следующих обозначений (лучшее - первое):$$\sum\limits_{k=1}^{[n/2]} x_{2k}, \qquad \sum\limits^n_{\substack {k=2\\k=2m, \ m\in N}} x_k, \qquad \sum\limits^n_{\substack {k=2\\k \mod 2 =0}} x_k, \qquad \sum\limits^n_{k\ \text{--- четное}} x_k.$$

    Здесь [n/2] - целая часть от числа половины числа n.

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

    Пример. Когда Гаусса в десятилетнем возрасте учитель решил, как он предполагал, занять надолго подсчетом суммы Sn=1+2+3+...+n, то будущий математик додумался до уловки, на которой базируется теперь вычисление суммы арифметической прогрессии: Sn + Sn = (1 + 2 + 3 + ... + n-1 + n) + (n + n-1 + n-2 + ... + 2 + 1) = = (1 + n) + (2 + n-1) + (3 + n-2) + ... + (n-1 + 2) + (n + 1) = = (1 + n) + (1 + n) + (1 + n) + ... + (1 + n) + (1 + n) = (1 + n)n. Отсюда получаем известную формулу суммы членов арифметической прогрессии: Sn=(n+1)n/2.

    Рассмотрим некоторые общие методы вычисления конечных сумм.

    Самым простым прагматическим методом является поиск нужной суммы в справочниках "Сумм и интегралов" (человеческим опытом и знаниями нельзя пренебрегать!). Многие часто используемые суммы кем-то наверняка уже давно вычислены и предлагаются в этих справочниках.

    Пример. Важные суммы из, например, известного справочника Двайта "Таблица сумм и интегралов":$$\sum\limits^n_{k=1} k^2 = \frac {n(n+1)(2n+1)}{6}, \\ \sum\limits^n_{k=1} k^3 = \frac {n^2(n+1)^2} 4, \\ \sum\limits^n_{k=0} (-1)^k \frac {1}{2k+1} = \frac {\pi}{4}, \\ \sum\limits^n_{k=1} \frac {1}{k^2} = \frac {\pi^2}{6}.$$

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

    Третий метод можно назвать методом подбора подходящей рекуррентной зависимости. Он базируется на следующей теореме.

    Теорема. Если для суммы вида$$S_n= \sum^n_{k=1}x_k$$ можно найти функцию F(k), для которой при любом k выполнено рекуррентное равенство xk=F(k+1)-F(k), то данную сумму можно вычислить по формуле: Sn=F(n+1)-F(1).

    Пример. Вычислим сумму вида$$\sum^n_{k=1} \frac {1}{k(k+1)}.$$ Здесь $$x_k=\frac {1}{k(k+1)}$$ и, как легко это проверить, справедливо равенство$$x_k = \frac 1k - \frac {1}{k+1}.$$ Поэтому имеем равенство $$F(k)=-\frac {1}{k}$$ для всех натуральных значений k. Тогда можно записать равенство вида$$\sum^n_{k=1} \frac {1}{k(k+1)} = \frac {n}{n+1}.$$

    Сумма$$S_n= \sum^n_{k=1} x_k$$ эквивалентна рекуррентности$$S_0=x_0, \ \ S_n=S_{n-1}+x_n,\quad n>0,$$ а эта связь помогает эффективно вычислять суммы.

    Есть и другие, достаточно сложные методы суммирования.

    Аналогично знаку суммы вводится и знак произведения:$$P_n=\prod\limits^n_{k=1}x_k =x_{1x2} \cdots x_n .$$

    Пример. Факториал числа n>0 можно записать в виде$$n!=\prod^n_{k=1} k.$$ Для n=0 условно полагают 0!=1. Он совпадает с 1!.

    В математике часто используют ряд чисел, имеющих собственные имена в силу их исключительной важности. Примером такого числа является рассмотренное выше натуральное число (число Непера) e. Число $$\pi$$ можно также отнести к таким числам. Рассмотрим некоторые другие важные числа.

    Числа Мерсенна - числа вида Mn=2n-1. Если n - не простое (например, кратно m, то есть n=km ), то эти числа - всегда не простые, так как в этом случае имеет место разложение (2km-1)=(2m-1)(2m(k-1)+2m(k-1)+ ...+1). Эти числа не всегда простые и в том случае, когда n - простое число.

    Числа Ферма имеют вид: $$F_n=2^{2^n}+1$$ и предполагались самим Ферма (кстати, в письме к Мерсенну) простыми $$(n\ge 0)$$, но затем было доказано, что F5=4294967297 - не простое и делится, например, на 641.

    Числа Паскаля или треугольник Паскаля (проявление красоты и симметрии математических объектов):$$\begin{matrix} n C_n^0C_n^1C_n^2C_n^3C_n^4C_n^5C_n^6C_n^7C_n^8C_n^9C_n^{10} \cr 0 1 \cr 1 1 1 \cr 2 1 2 1 \cr 3 1 3 3 1 \cr 4 1 4 6 4 1 \cr 5 1 5 10 10 5 1 \cr 6 1 6 15 20 15 6 1 \cr 7 1 7 21 35 35 21 7 1 \cr 8 1 8 28 56 70 56 28 8 1 \cr 9 1 9 36 84 126 126 84 36 9 1 \cr 10 1 10 45 120 210 252210120 45 10 1 \cr \end{matrix}$$

    Числа Эйлера $$\langle C^m_n\rangle$$ (треугольник Эйлера), связывают обычные степени с биномиальными коэффициентами и удовлетворяют соотношениям:$$x^n =\sum\limits^n_{k=0} \langle C^k_n\rangle C^n_{x+k} , \quad n\ge 0, \\[3pt] \langle C^k_n\rangle =(k+1) \langle C^k_{n-1}\rangle + (n-k) C^{k-1}_{n-1}, \quad \langle C^0_0\rangle =1.$$ Эти числа можно записать в виде, аналогичном треугольнику Паскаля:$$\begin{matrix} n \kern-1pt\langle C_n^0\rangle\kern-1pt \langle C_n^1\rangle \langle C_n^2\rangle \langle C_n^3\rangle \langle C_n^4\rangle \langle C_n^5\rangle \langle C_n^6\rangle \langle C_n^7\rangle \kern-1pt\langle C_n^8\rangle\kern-1pt \kern-1pt\langle C_n^9\rangle\kern-1pt \cr 0 1 \cr 1 1 0 \cr 2 1 1 0 \cr 3 1 4 1 0 \cr 4 1 11 11 1 0 \cr 5 1 26 66 26 1 0 \cr 6 1 57 302 302 57 1 0 \cr 7 1 120 1191 2416 1191 120 1 0 \cr 8 1 247 4293 15619 15619 4293 247 1 0 \cr 9 1 502 14608 88234 156190 88234 14608 502 1 0 \cr \end{matrix}$$

    Пример. Из треугольника Эйлера и приведенного выше рекуррентного соотношения получаем, в частности,$$x^2=C^2_x =C^2_{x+1}, \\[2pt] x^3=C^3_x +4C^3_{x+1} + C^3_{x+2}, \\[2pt] x^4 = C^4_x + 11 C^4_{x+1} +11C^4_x + C^4_{x+1} \ \ \text{и т.д.}$$

    В математике (особенно, в ее разделе - "теория чисел") рассматриваются и другие замечательные числа.

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

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^