chapter08.qq

\chapter Теорема Вейерштрасса, немного комбинаторики и число e \label chap:08:weierstrass

До сих пор у нас был единственный способ доказать, что некоторая
последовательность имеет предел: угадать, чему этот предел равен, а затем
использовать определение, чтобы доказать, что он действительно этому равен. В
этой лекции мы познакомимся с утверждением, которое позволит доказать
существование предела в ситуации, когда его значение неизвестно. Но начнём мы
слегка издалека.

\section Ограниченные множества
\subsection Максимум и минимум
\definition \label def:08:bound
    Пусть $X$ — некоторое числовое множество, $X\subset \mathbb R$. Пусть
    существует такое число $C$, что все элементы множества $X$ не превосходят
    $C$:
    \eq
        \forall x \in X\colon x \le C.
    Тогда множество $X$ называется \emph{ограниченным сверху}.
    
Аналогично, с заменой неравенства $\le$ на $\ge$, определяется множество,
ограниченное снизу.

\remark
    Для дальнейшего полезно ввести новые обозначения, позволяющие описывать
    множества, получаемые из других множеств по некоторым правилам. Проще всего
    объяснить их на примере.
    \itemize
        \item 
            $\seq{n^2 \mid n \in \mathbb N}$ — множество всех квадратов всех
            натуральных чисел. Фигурные скобки подсказывают, что мы создаём
            новое множество, после вертикальной черты написано, какие значения
            пробегает переменная $n$, а до черты — как из переменной $n$
            изготовить элементы множества.
        \item
            $\seq{n \in \mathbb N \mid \exists k \in \mathbb N \colon k^2=n}$ —
            это тоже множество квадратов всех натуральных чисел, только
            записанное иначе.  Здесь до вертикальной черты написано, из какого
            множества выбирается $n$, а после — какому условию $n$ должно
            удовлетворять, чтобы быть включённым в наше новое множество.
\remark
    Пусть есть последовательность $\seq{a_n}$. Рассмотрим множество всех её
    элементов: $\set{a_n \mid n \in \mathbb N}$. (В отличие от последовательности,
    это просто множество: в нём нет никакого порядка, и каждый элемент в него
    может входить только один раз. Например, для последовательности
    $\seq{(-1)^n}$ получится конечное множество $\set{1, -1}$; такое же
    множество получится для последовательности $\seq{(-1)^{n+1}}$.) Это
    множество ограничено тогда и только тогда, когда последовательность
    ограничена. (Докажите!)


\definition \label def:08:max-min
    Рассмотрим произвольное числовое множество $X\subset \mathbb R$. Его
    \emph{максимумом} (соответственно, \emph{минимумом}) называется такой
    элемент $X$, который не меньше (соответственно, не больше) всех элементов
    $X$:
    \align
        \item 
            & \max  X =  m  \quad \Leftrightarrow 
        \splitem \splonly{&\Leftrightarrow} \quad (m \in X) \wedge (\forall y
            \in X\colon m \ge y).
        \item
            & \min  X = M  \quad \Leftrightarrow 
        \splitem \splonly{&\Leftrightarrow} \quad (M \in X) \wedge (\forall y
            \in X\colon M \le y).

\question
    Что будет, если заменить нестрогое неравенство на строгое?
    \quiz
        \choice
            Ничего не изменится, мы такое уже проходили.
            \comment
                В этот раз всё не так.
        \choice \correct
            Определение потеряет свой смысл.
            \comment
                Действительно, если потребовать строгое неравенство, условие
                будет всегда нарушаться: элемент не может быть строго больше или
                строго меньше самого себя.
\exercise
    Докажите, что если максимум (минимум) определён, он задан единственным
    образом.
Если множество конечное, у него всегда определён максимум и минимум, мы уже
пользовались этим свойством. (Доказать это аккуратно с помощью индукции —
полезное упражнение.) Если множество бесконечно, становится интереснее.

Если максимум множества $X$ существует, это множество обязательно ограничено
сверху: действительно, сам этот максимум можно подставить в
\ref[определение][def:08:bound] в качестве $C$. Аналогично, если существует
минимум, множество ограничено снизу.

В обратную сторону, однако, это не работает: например, если множество ограничено
сверху, ещё не факт, что у него есть максимум.

\example 
    Пусть $X=[0, 1) = \set{x \in \mathbb R\mid 0 \le x < 1}$ — полуоткрытый
    интервал, включащий в себя $0$, но не включающий единицу. Это множество
    ограничено и сверху, и снизу.  У него есть минимум — это число $0$, но нет
    максимума. Действительно, любое число $x \in [0, 1)$ меньше 1 (см.
    \ref[рис.][fig:08:nomax]). Рассмотрим число $y=\frac{x+1}{2}$ — середину
    отрезка $[x, 1]$. Оно больше $x$, но меньше $1$ (проверьте аккуратно с
    помощью неравенств). Значит, $x$ не является максимумом.

    \figure
        \img
            \src
                weierstrass-1.svg
            \style
                padding: 2em;
                max-width: 500px;
            \alt
                Иллюстрация к доказательству утверждения о том, что у
                полуинтервала $[0, 1)$ нет максимума, описание см. в тексте.
        \caption
            У множества $[0, 1)$ нет максимума.
        \label fig:08:nomax

Это неудачно: мы бы хотели как-то обобщить понятие максимума и минимума, чтобы
они существовали для любого ограниченного с соответствующей стороны множества.
Если ещё раз посмотреть на пример с полуоткрытым интервалом $[0, 1)$, и задать
вопрос, какое число подходит на роль его «обобщённого максимума», напрашивается
ответ, что это число $1$. Единственная причина, по которой $1$ не является
максимумом на самом деле — то, что $1$ не принадлежит нашему множеству. Если бы
мы могли снять это ограничение…

\subsection Точная верхняя и нижняя грани

Что будет, если мы уберём в \ref[определении максимума\nonumber][def:08:max-min]
требование, чтобы $M$ принадлежал $X$. Для полуинтервала $[0, 1)$, число $1$
будет удовлетворять новому определению. Однако, не только оно: любое число,
большее 1, тоже ему будет удовлетворять. Мы лишились единственности. Однако,
сделали важный шаг на пути к построению нужного нам понятия. Штука, которую мы
определили, называется \emph{верхней гранью} множества.

\definition \label def:08:bound-C
    \emph{Верхней гранью} множества $X$ называется такое число $C$, которое не
    меньше всех элементов $X$:
    \eq
        \forall x \in X\colon x \le C.

    Аналогично (заменой неравенства $\le$ на $\ge$) определяетcя \emph{нижняя грань}
    множества.

    Множество всех верхних граней $X$ будем обозначать через $\UB(X)$ (от англ.
    \emph{upper bound}), а нижних — через $\LB(X)$ (от \emph{lower bound}).



Сравнивая определения \ref{def:08:bound-C} и \ref{def:08:bound}, мы видим, что
множество является ограниченным сверху (снизу) тогда и только тогда, когда у
него есть верхняя (нижняя) грань, то есть $\UB(X)$ непусто (соответственно,
$\LB(X)$ непусто). Собственно, верхняя грань (нижняя грань) — это ровно та самая
константа $C$, которая участвует в \ref[определении][def:08:bound]. Слово
«грань» здесь следует понимать как «то, что ограничивает».

Вернёмся к задаче определения «обобщённого максимума» и примеру с полуинтервалом
$[0, 1)$. Множеством верхих граней этого интервала оказывается весь луч $[1,
+\infty)$, см. \ref[рис.][fig:08:bounds]. Какое число из этого луча в наибольшей
степени достойно того, чтобы назваться «обобщённым максимумом» множества $[0,
1)$? Очевидно, самое маленькое: число $1$.

\figure
    \img
        \src
            weierstrass-2.svg
        \style
            padding:1em;
        \alt
            Нарисован полуинтервал X=[0, 1). Его множеством нижних граней LB(X)
            является луч (-∞, 0], а множеством верхних граней UB(X) является луч
            [1, +∞).
    \caption
        Множества верхних и нижних граней для $[0, 1)$.
    \label
        fig:08:bounds
\definition \label def:08:sup-inf
    Пусть $X \subset \mathbb R$ — некоторое числовое множество. Его \emph{точной
    верхней гранью} называется самая маленькая верхняя грань, то есть минимум
    множества $\UB(X)$. Аналогично, \emph{точной нижней гранью} называется самая
    большая из нижних граней, то есть максимум множества $\LB(X)$.

    Точная верхняя грань также называется \emph{супремумом}, а точная нижняя
    грань — \emph{инфимумом}. В обозначениях:

    \eq
        \sup X := \min \UB(X),\quad \inf X := \max \LB(X).

Позвольте! — скажет тут читатель, — вы водите нас кругами! Обещали построить
обобщение максимума и минимума, но вернулись в итоге к ним же самим: супремум
определяется через минимум, а инфимум — через максимум. Казалось бы, мы должны
столкнуться с теми же самыми трудностями, от которых стремились уйти: максимум и
минимум могут быть не определены. Стоило ли тогда так мучаться?

Оказывается, да, стоило. Дело в том, что каким бы ни было множество $X$, если
множество его верхних граней $\UB(X)$ не пусто, у него обязательно есть
минимальный элемент $\min \UB(X)$, и аналогично если непусто множество нижних
граний, определён его максимум.

Давайте ещё раз вернёмся к полуинтервалу $[0, 1)$. Его множество верхних граней
— замкнутый луч $[1, +\infty)$, содержащий единицу. Может показаться, что если
мы теперь возмём вместо полуинтервала замкнутый отрезок $[0, 1]$, множество
верхних граней станет открытым лучом и лишится своего минимального элемента. Но
нет! Из-за использования нестрого неравенства в
\ref[определении][def:08:bound-C], верхняя грань может принадлежать множеству
$X$ (это не запрещено). Множеством всех верхних граней отрезка $[0, 1]$
по-прежнему является замкнутый луч $[1, +\infty)$, и он по-прежнему содержит
минимальный элемент — число $1$. Здорово, правда?

\theorem \label thm:08:sup-inf
    Если множество $X \subset \mathbb R$ ограничено сверху, у него есть точная
    верхняя грань. Если оно ограничено снизу — точная нижняя.

Эта теорема доказывается не очень сложно, хотя и немножко занудно. (Как-то я
даже хотел рассказать доказательство на лекциях, но, прикинув масштабы бедствия,
понял, что все быстро уснут, и отказался от этой идеи.) Например, доказательство
можно найти \href[в
Википедии][https://ru.wikipedia.org/wiki/Точная_верхняя_и_нижняя_границы#Доказательство].
Выглядит жутковато, но если сесть и аккуратно в нём разобраться, вы увидите, что
оно не очень сложное. Тем не менее, мы не будем его подробнее обсуждать. Однако,
стоит обсудить, почему эта теорема не так очевидна, как может показаться из
рассмотрения примера с полуинтервалом.

Представьте себе, что мы переместились во времена Пифагора, когда про
вещественные числа ещё ничего не знали. Рассмотрим множество
\eq
    S := \set{x \in \mathbb Q \mid x^2 < 2}.
Древние греки вполне могли такое множество рассмотреть: оно состоит из
рациональных чисел, и в его определении никакие иррациональные числа не
участвуют. Однако, если бы древний грек попытался найти точную верхнюю грань
множества $S$, его бы постигла неудача. Действительно, он бы рассматривал только
рациональные верхние грани (других чисел он не знает). Поскольку $\sqrt{2}$, как
мы сейчас знаем, иррационален (см.  \ref[теорему][thm:01:sqrt2] из
\ref[лекции][chap:01:setsnumbers]), множество \emph{рациональных} верхних граней
для $S$ не содержит минимального элемента: какое бы рациональное число, большее
$\sqrt{2}$ мы бы ни взяли, можно найти рациональное число поменьше, по-прежнему
являющееся верхней гранью для $S$. (Это следует из плотности множества
рациональных чисел, которую мы доказывали на семинарах.) Неудача!

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

\section Теорема Вейерштрасса
Вернёмся к последовательностям.
\theorem  \label thm:08:weierstrass
    (Вейерштрасс)
    Пусть последовательность $\seq{a_n}$ ограничена сверху и неубывает. Тогда
    она имеет предел.

    \figure
        \img
            \src
                weierstrass-3.svg
            \alt
                Нарисован график неубывающей последовательности, ограниченной
                сверху числом C. Между C и максимальным изображенным элементом
                последовательности есть заметный зазор.
            \style
                padding:1em;
        \caption
            Иллюстрация к \ref[теореме][thm:08:weierstrass]. Неубывающая
            ограниченная последовательность. Здесь число $C$ является какой-то
            из верхних граней (не обязательно точной) для множества всех членов
            последовательности.
    
        
\proof
    Рассмотрим множество элементов последовательности $\set{a_n \mid n \in
    \mathbb N}$. Поскольку последовательность ограничена сверху, это множество
    тоже ограничено сверху. Возьмём его точную верхнюю грань (она существует по
    \ref[теореме][thm:08:sup-inf]) и обозначим её за $A$. Докажем, что $A$
    является пределом нашей последовательности.


    \paragraph{Близкие элементы существуют} Сперва докажем более слабое
    утверждение: докажем, что элементы последовательности подходят к $A$ сколь
    угодно близко, см. \ref[рис.][fig:08:weierstrass-proof]. Формально:
    \equation \label eq:08:A
        \forall \eps>0\\ \exists N \in \mathbb N \colon |a_N - A| < \eps.
    Это ещё не определение предела (мы ничего не говорим про бесконечный хвост
    последовательности, а говорим только про один элемент), но давайте начнём с
    этого.
    \figure
        \img
            \src
                weierstrass-4.svg
            \alt
                Нарисован график неубывающей последовательности, ограниченной
                сверху числом C и числом A < C. Между A и максимальным изображенным элементом
                последовательности нет заметного зазора. Нарисована также прямая
                y=A-ε и n=N. Все точки, начиная с n=N, лежат в коридоре между
                y=A и y=A-ε.
            \style
                padding:1em;
        \caption
            Иллюстрация к доказательству теоремы Вейерштрасса, $A=\sup
            \set{a_n\mid n \in \mathbb N}$.
        \label
            fig:08:weierstrass-proof
    От противного, пусть это неверно. Запишем отрицание:
    \eq
        \exists \eps > 0 \\ \forall N \in \mathbb N\colon |a_N - A| \ge \eps
    Заметим, что раз $A$ — верхняя грань множества всех элементов
    последовательности, каждый из элементов не больше $A$ и значит модуль
    раскрывается как $A-a_N$. Тогда нашлось такое $\eps$, что все элементы
    последовательности удовлетворяют неравенству
    \eq
        A - a_N \ge \eps,
    или, иными словами, $a_n \le A-\eps$. Таким образом, все элементы
    $\seq{a_n}$ не превосходят $(A-\eps)$, то есть $(A-\eps)$ — верхняя грань.
    (На \ref[рис.][fig:08:weierstrass-proof] в этом случае не было бы никаких
    точек последовательности выше $y=A-\eps$.) Но $A-\eps < A$, а мы
    предположили, что $A$ точная верхняя грань, то есть
    минимум из всех верхних граней. Противоречие!

    Иными словами, если элементы последовательности не подходят к $A$ сколь
    угодно близко, то между $A$ и этими элементами есть «зазор», и $A$ можно
    было бы уменьшить, сохранив его свойство быть верхней гранью. Это
    противоречит тому, что $A$ точная (самая маленькая) верхняя грань.

    \paragraph{Монотонность} Заметим, что в силу монотонности, если $a_N > A -
    \eps$, то для всякого $n>N$, $a_n \ge a_N > A - \eps$. Поскольку для всех
    элементов выполняется, что $a_N \le A$, отсюда следует, что для $|a_n -
    A|=A-a_n < \eps$.

    Таким образом, утверждение доказано по определению предела: мы показали, что
    для всякого $\eps$ найдётся такое $N$ (определяемое из формулы
    \ref{eq:08:A}), что для всех $n>N$, $|a_n - A| < \eps$.

\remark 
    Конечно, легко сформулировать и доказать теорему Вейерштрасса для
    ограниченных снизу невозрастающих последовательностей.

\remark \label rem:08:limbound
    В ходе доказательства получили, что предел неубывающей последовательности
    является точной верхней гранью всех её членов. Отсюда в частности следует,
    что все члены не превосходят предела: если $\seq{a_n}$ неубывает и имеет
    предел $A$, то для всех натуральных $k$, $a_k \le A$. Конечно, мы могли бы
    получить этот результат и непосредственно: в силу неубывания, для всех
    $n>k$, $a_k \le a_n$. Зафиксируем $k$ и перейдём в этом неравенстве к
    пределу при $n\to \infty$. (Поскольку предел зависит только от «хвоста»
    последовательности, тот факт, что неравенство выполняется не для всех $n$, а
    только для тех, которые больше $k$, не является препятствием — можно просто
    выкинуть первые $k$ элементов обеих последовательностей.) Получим $a_k \le
    \lim_{n \to \infty} a_n = A$. 

\section Биномиальные коэффициенты
\subsection Упорядоченные наборы
\definition
    Пусть есть множества $X$ и $Y$. \emph{Декартовым произведением} этих
    множеств называется множество упорядоченных пар $(x, y)$, где $x \in X$ и
    $y\in Y$. Пишут:
    \eq
        X \times Y = \set{(x, y)\mid x\in X,\\ y\in Y}.

\example
    Рассмотрим множество $\mathbb R^2=\mathbb R \times \mathbb R$ — декартов
    квадрат множества вещественных чисел. Оно состоит из упорядоченных пар $(x,
    y)$, где $x$ и $y$ — вещественные числа. С этим объектом мы хорошо знакомы
    из школы: это обыкновенная декартова плоскость.

\question
    Пусть множества $X$ и $Y$ конечны: в $X$ 3 элемента, а в $Y$ два. Сколько
    элементов в множестве $X\times Y$?
    \quiz
        \choice \correct
            6
            \comment
                Конечно: к каждому из трёх элементов $X$ можно приписать два
                элемента из $Y$, значит всего шесть элементов.
        \choice
            5
            \comment
                Интересно, как это получилось?
        \choice
            3
            \comment
                Ой?
        \choice
            12
            \comment
                Откуда это могло взяться?

Можно рассматривать декартово произведение больше, чем двух множеств: оно
состоит из упорядоченных наборов элементов, каждый из которых взят из
соответствующего сомножителя. Например:
\align \nonumber
    \item X \times Y \times Z = \set{(x, y, z)\mid  x \in X, \\ y \in Y, \\ 
    \splitem z \in Z}.
Можно было бы расставить скобки в выражении $X \times  Y \times Z$ и, например,
получить множество $(X \times Y) \times Z$, элементами которого были бы
упорядоченные пары $(w, z)$, где $z \in Z$ и $w\in X\times Y$, то есть $w=(x,
y)$ — тоже упорядоченная пара. Но с практической точки зрения обычно нет никакой
разницы между выражениями вида $((x, y), z)$ и $(x, y, z)$.

\definition
    Результат $k$-кратного декартова умножения множества $X$ на себя называется
    \emph{$k$-й декартовой степенью} множества $X$ и обозначается $X^k$. Оно
    состоит из упорядоченных $k$-элементных наборов элементов множества $X$:
    \align \nonumber
        \item X^k=\set{(x_1, x_2, \ldots, x_k)\mid 
                 x_1\in X, 
        \splitem x_2 \in X, \ldots, x_k \in X}.

Про упорядоченные наборы важно понимать следующее: элементы в них могут
повторяться (никто не мешает вам рассмотреть точку $(1, 1) \in \mathbb R^2$) и
порядок следования элементов важен (точка $(1, 2)$ — это совсем не то же самое,
что точка $(2, 1)$).

\proposition  \label prop:08:tuples
    Пусть $X$ — конечное множество, состоящее из $n$ элементов. Тогда $X^k$ состоит
    из $n^k$ элементов. Иными словами, количество $k$-элементных упорядоченных
    наборов из $n$-элементного множества равно $n^k$.
\proof
    Совсем аккуратное доказательство проводится по индукции, но и без неё всё
    довольно наглядно. Пусть нам нужно выбрать $k$-элементный упорядоченный
    набор. Будем выписывать его по очереди. У нас есть $n$ различных способов
    выбрать первый элемент, см. \ref[рис.][fig:08:tuples]. После того, как
    первый элемент выбран, к нему нужно приписать второй элемент, и это можно
    сделать $n$ разными способами. Всего получается $n\times n$ способов
    выписать первые два элемента. Когда первые два элемента зафиксированы, есть
    $n$ способов выписать третий элемент, значит количество вариантов умножается
    на $n$ и становится равно $n^2\times n = n^3$. И так далее до $k$-го
    элемента.

    \figure
        \img
            \src
                weierstrass-5.svg
            \style
                padding: 1em;
                max-width: 400px;
            \alt
                Иллюстрация к построению всех возможных упорядоченных наборов из
                элементов 1 и 2. Из левой точки выходят две стрелочки, на одной
                написано 1, на другой 2, они указывают в две новые точки. Из
                каждой из этих точек выходят по две стрелочки (опять на одной
                написано 1, на другой 2), которые ведут в четыре новые точки. Из
                каждой из этих точек выходит по две стрелочки, получается 8
                точек. Каждой из этих точек соответствует упорядоченный набор,
                который считывается из цифр, написанных на стрелочках.
        \caption
            Построение всевозможных трёхэлементных упорядоченных наборов из
            чисел $1$ и $2$. Выбор каждого следующего элемента удваивает
            количество наборов.
        \label fig:08:tuples

\subsection Наборы без повторений

Рассмотрим теперь упорядоченные наборы без повторяющихся элементов.
\proposition \label prop:08:tuples-without-replacements
    Количество $k$-элементных упорядоченных наборов из $n$-элементного множества
    равно 
    \eq
        n(n-1)\ldots (n-k+1)=\frac{n!}{(n-k)!},
    где $n!=1\times 2\times 3\times \cdots \times n$ — $n$-факториал. (По
    определению полагают, что $0!=1$.)
\proof
    Доказательство очень похоже на доказательство
    \ref[утверждения][prop:08:tuples], см.
    \ref[рис.][fig:08:tuples-without-replacements] Будем выписывать набор
    последовательно.  Есть $n$ способов выбрать первый элемент. После того, как
    первый элемент выбран, остаётся $(n-1)$ способ выбрать второй элемент
    (потому что повторяться нельзя, и значит множество допустимых элементов
    сокращается на $1$). Значит, есть $n\cdot(n-1)$ способов выбрать первые два
    элемента. И так далее. Получится $k$ сомножителей, начиная с $n=(n-0)$.
    Значит, последний сомножитель будет $(n-(k-1))=(n-k+1)$. (Чтобы не
    запутаться, всегда полезно подставить какое-нибудь конкретное значение
    — например, $k=2$ — и посмотреть, что получится.)


    \figure
        \img
            \src
                weierstrass-6.svg
            \style
                padding: 1em;
                max-width: 400px;
            \alt
                Иллюстрация к построению всех возможных упорядоченных наборов из
                элементов 1, 2, 3, 4 без повторений длины 3. Из левой точки
                выходят четыре стрелочки, на них написано 1, 2, 3, 4, они
                указывают в четыре новые точки. Из каждой из этих точек выходят по
                три стрелочки, на каждой из которых написана цифра, которая не
                написана на входящей стрелочке. Получается 12 новых точек. Из
                каждой из них выходит по две стрелочки с двумя оставшимися
                цифрами, получается 24 точки.  Каждой из этих точек
                соответствует упорядоченный набор, который считывается из цифр,
                написанных на стрелочках.
        \caption
            Построение всевозможных трёхэлементных упорядоченных наборов без
            повторений из чисел $1$, $2$, $3$ и $4$. На каждом следующем шаге
            число возможных элементов уменьшается на 1.
        \label fig:08:tuples-without-replacements

\subsection Неупорядоченные наборы без повторений 

Сколько существует $k$-элементных подмножеств данного $n$-элементного множества?
Если выписать элементы подмножества в строчку, получится $k$-элементный набор
без повторений. Однако, между упорядоченными наборами и подмножествами есть
важное различие: множество не упорядочено. Наборы $(1, 2)$ и $(2, 1)$ — разные
наборы, множества $\set{1, 2}$ и $\set{2, 1}$ — одно и то же множество. Поэтому
количество упорядоченных наборов больше количества подмножеств. Во сколько раз?

\question
    Пусть есть $k$-элементное множество. Сколькими способами его элементы можно
    упорядочить (выстроить в ряд)? Иными словами, сколько есть различных
    $k$-элементных наборов без повторяющихся элементов из элементов данного
    $k$-элементного множества?

Ответ на этот вопрос содержится в
\ref[утверждении][prop:08:tuples-without-replacements]: нужно просто подставить
$n=k$. Видно, что в этом случае $(n-k)=0$, а по определению $0!=1$. Значит,
искомое число способов равно $k!$.

\proposition \label prop:08:Cnk
    Обозначим количество $k$-элементных подмножеств $n$-элементного множества
    через $C_n^k$. Тогда
    \align 
        \item \label eq:08:Cnk
            C_n^k = \frac{n(n-1)\cdots (n-k+1)}{k!} =
        \splitem \splonly{=} \frac{n!}{k!(n-k)!}.
\proof
    Пусть мы выписали все $\frac{n!}{(n-k)!}$ упорядоченных $k$-элементных
    наборов наборов из элементов нашего $n$-элементного множества (см.
    \ref[утверждение][prop:08:tuples-without-replacements] ). Рассмотрим
    какой-нибудь из этих наборов. Его элементы можно переставлять $k!$ разными
    способами, получая новые наборы из нашего списка (включая его самого). Все
    они задают одно и то же подмножество. Значит, если мы хотим посчитать
    подмножества, нужно все эти $k!$ наборов посчитать один раз. Таким образом,
    чтобы получить количество подмножеств из количества наборов, надо количество
    наборов разделить на $k!$. (Поскольку каждому подмножеству соответствует
    ровно $k!$ упорядоченных наборов.) Отсюда и следует формула \ref{eq:08:Cnk}.

    \figure
        \img
            \src
                weierstrass-7.svg
            \alt
                Упорядоченные наборы с предыдущей картинки, которые задают одно
                и то же множество, объединены. Например, множеству {1, 2, 3}
                соответствует шесть наборов: (1, 2, 3), (1, 3, 2), (2, 1, 3),
                (2, 3, 1), (3, 1, 2), (3, 2, 1).
            \style
                padding: 1em;
                max-width: 600px;
            \alt
        \caption
            Построение всевозможных трёхэлементных подмножеств множества
            $\set{1, 2, 3, 4}$. Мы сначала построили всевозможные упорядоченные
            3-элементные наборы без повторений, а потом объединили те из них,
            которые отличаются только порядком и следовательно задают одно и то
            же множество. На рисунке отмечены два таких объединения, в каждом по
            6 наборов (здесь $6=3!$ — число способов переставить три элемента).
            Напишите, какие два множества мы не указали, и отметьте все наборы,
            которые задают эти множества.
        \label fig:08:subsets
\exercise
    Самый лучший способ понять все утверждения, сформулированные выше, такой:
    взять какое-нибудь небольшое $n$ и $k$ и пройти все шаги. Например, $n=4$,
    $k=2$. Выпишите все двухэлементные упорядоченные наборы без повторений с
    элементами из множества $X=\set{1, 2, 3, 4}$, руководствуясь алгоритмом из
    \ref[утверждения][prop:08:tuples-without-replacements]. Посчитайте, сколько их
    получилось. Затем объедините их в группы, так, чтобы в каждой группе наборы
    отличались только порядком (и следовательно задавали одно и то же
    множество). Сколько элементов в каждой группе? Сколько всего групп?
    Повторите эти действия, например, с $n=5$, $k=3$.

\remark
    Числа $C_n^k$ называются \emph{биномиальными коэффициентами} (почему так —
    будет ясно в следующем разделе) или \emph{числом сочетаний из $n$ элементов
    по $k$}. Другое обозначение: $\binom{n}{k}$ — обратите внимание, что в этом
    случае $n$ ставится сверху.

\subsection Бином Ньютона

Рассмотрим выражение $(a+b)^n$. Что получится, если раскрыть в нём скобки и
привести подобные слагаемые?

\example Посмотрим, что происходит при небольших значениях $n$:
    \align \nonumber
        \item (a+b)^2=(a+b)(a+b)=
        \splitem \splonly{=} aa + a b + b a + b b = 
        \splitem \splonly{=} a^2 + 2ab + b^2;
    \align \nonumber
        \item
            (a+b)^3 & =  (a+b)(a+b)(a+b) =
        \splitem \splonly{&=}(a+b)(aa+ab+ba+bb)=
        \item
            &=aaa+aab+aba+abb
        \splitem \splonly{&+\,} baa+bab+bba+bbb=
        \item    
            & =a^3+3a^2b+3ab^2+b^3.

Мы видим, что если не приводить подобные слагаемые, каждый раз получается сумма
всевозможных мономов, состоящих из $n$ сомножителей, каждый сомножитель — $a$
или $b$ — они выглядят как «слова» типа $aaba$. Так будет и дальше: каждый раз
нужно умножить $(a+b)$ на $(a+b)^{n-1}$, то есть приписать слева к каждому
«слову», получающемуся в $(a+b)^{n-1}$, букву $a$ (получили $(n-1)$ новых
«слов» длины $n$), а затем букву $b$ (получили ещё $(n-1)$ новых «слов» длины
$n$), и всё сложить. Если в разложении $(a+b)^{n-1}$ были все $(n-1)$-буквенные
«слова» из букв $a$ и $b$, то в разложении $(a+b)^n$ будут все $n$-буквенные
слова из букв $a$ и $b$.

Теперь нужно привести подобные слагаемые. Например, для $(a+b)^2$ мы замечаем,
что $ab=ba$ и значит коэффициент при $ab$ равен двум. Для $(a+b)^3$, чтобы
посчитать коэффициент при $a^2b$, нужно найти количество «слов», в которых две
буквы $a$ и одна буква $b$. Таких слов 3: $aab$, $aba$ и $baa$. Значит,
коэффициент при $a^2b$ равен трём.

\theorem
    Если раскрыть собки и привести подобные слагаемые в выражении $(a+b)^n$,
    получится сумма мономов вида $a^k b^{n-k}$, коэффициент перед каждым таким
    мономом равен $C_n^k$:
    \eq
        (a+b)^n = \sum_{k=0}^n C_n^k a^k b^{n-k}.
\proof
    Коэффициент при выражении $a^k b^{n-k}$ — это количество различных «слов»
    длины $n$, в которых входит ровно $k$ раз буква $a$ и оставшиеся $(n-k)$ раз
    буква $b$.  Сколько таких слов существует? Поскольку мы знаем длину слова
    (она равна $n$), и знаем, что в слове бывают только буквы $a$ и $b$, чтобы
    задать такое слово, нужно просто задать, на каких позициях стоят буквы $a$.
    Всего возможных позиций $n$, из них $k$ позиций нужно заполнить буквами $a$.
    Чтобы выбрать эти позиции, нужно из $n$-элементного множества (всех позиций)
    выбрать $k$-элементное подмножество (тех позиций, на которых мы напишем
    $a$). Это можно сделать $C_n^k$ различными способами.
\remark
    Разумеется, у этой теоремы есть строгое формальное доказательство через
    индукцию. Провести его — полезное упражнение. Однако, на мой взгляд, понять
    смысл из этого доказательство — довольно трудно. Поэтому я его здесь не
    привожу.

\section Число $e$

Рассмотрим следующий предел
\eq
    \lim_{n\to \infty} \left(1+\frac{1}{n}\right)^n.
Чему он равен? Если вы попробуете применить арифметику пределов, то заметите,
что основание степени стремится к $1$, а показатель — к бесконечности. Чему
«равняется» $1^\infty$? Увы, это неопределенность. Лобовой метод тут не
работает. Мы пока даже не знаем, существует этот предел, или нет. Однако, скоро
узнаем.


\proposition
    При всех $n$,
    \eq
        \left(1+\frac{1}{n}\right)^n < 3.
\proof
    Случай $n=1$ разбирается явно. Пусть $n>1$. Раскроем скобки по биному
    Ньютона (ага! пригодился!).
    Имеем:
    \align 
        \item \label eq:08:eee
            & \left(1+\frac{1}{n}\right)^n  =  1^n + \frac{n}{1!} \frac{1}{n} +
        \splitem \splonly{&+} \frac{n(n-1)}{2!} \frac{1}{n^2} + 
        \splitem \splonly{&+} \frac{n(n-1)(n-2)}{3!} \frac{1}{n^3} + \ldots +
        \splitem \splonly{&+} \frac{n(n-1)(n-2)\ldots 1}{n!}\frac{1}{n^n}.
    Первые два слагаемые равны $1$. Рассмотрим $(k+1)$-е слагаемое, $k>2$. Оно
    имеет вид:
    \align 
        \item \nonumber
            \frac{n(n-1)\ldots(n-k+1)}{k!}\frac{1}{n^k} =
        \splitem \splonly{=} \frac{n}{n}\frac{n-1}{n}\cdots\frac{n-k+1}{n}\frac{1}{k!}=
        \item \label eq:08:term 
            = \left(1 - \frac{1}{n}\right) \cdots\left(1-\frac{k-1}{n}\right)\frac{1}{k!}

    Иными словами, оно состоит из $(k-1)$ сомножителя вида $1-\frac{m}{n}$, где 
    $m$ меняется от $1$ до $(k-1)$, и последнего сомножителя $\frac{1}{k!}$.

    Заметим, что каждый из сомножителей вида $1-\frac{m}{n}$ меньше 1.
    Значит, всё слагаемое меньше $\frac{1}{k!}$. Но с другой стороны
    $2^{k-1} \le k!$ для всех натуральных $k$ (проверьте, а ещё лучше — докажите
    по индукции, что это так) и значит
    $\frac{1}{k!} \le \frac{1}{2^{k-1}}$. Имеем:
    \eq
        \left(1+\frac{1}{n}\right)^n  < 1 + 1 + \frac{1}{2^1} + \frac{1}{2^2} +
        \ldots \frac{1}{2^n}.
    Слагаемые, начиная с третьего, образуют геометрическую прогрессию с
    положительным знаменателем, меньшим $1$. Её сумма меньше суммы
    соответствующей бесконечной геометрической прогрессии, которая в свою
    очередь равна 1. (Не нужно знать формулу суммы бесконечной геометрической
    прогрессии, чтобы это увидеть: если у вас была одна шоколадка, вы её
    разломали пополам, съели половину (то есть $1/2$), остаток разломали снова пополам,
    съели половину от половину (то есть $1/2^2$) и т.д., в каждый момент времени вы
    съедите меньше, чем целую шоколадку, а в пределе съедите её всю.) Значит,
    вся сумма меньше трёх.
        
\proposition
    Последовательность
    \eq
        \largeseq{\left(1+\frac{1}{n}\right)^n}
    монотонно возрастает.
\proof
    Рассмотрим представление \ref{eq:08:eee}. Что произойдёт при увеличении $n$
    на единицу? Первые два слагаемые не изменятся. Добавится ещё одно
    неотрицательное слагаемое. Что произойдёт с остальными?

    Первые два слагаемые равны 1, они не изменятся. Слагаемые, начиная с
    третьего, задаются формулой \ref{eq:08:term}. Возьмём какое-то конкретное
    слагаемое, то есть зафиксируем какое-то $k>2$. Посмотрим на правую часть
    \ref{eq:08:term}. Что произойдёт с ней, когда $n$ увеличится, а $k$
    останется прежним?  Во-первых, сомножитель $\frac{1}{k!}$, стоящий в конце,
    не изменится. Во-вторых, количество сомножителей вида $1-\frac{m}{n}$ тоже
    не изменится, их $(k-1)$ штука. Наконец, каждый из сомножителей такого вида
    при увеличении $n$ увеличивается, поскольку дробь $\frac{m}{n}$
    уменьшается, но перед ней стоит минус.
        
    Итак, в результате увеличения $n$ на единицу к сумме \ref{eq:08:term}
    добавится положительное слагаемое, а остальные слагаемые не уменьшатся.
    Значит, сумма возрастёт.

\corollary \nonumber
    Таким образом, наша последовательность возрастает и ограничена сверху.
    Значит, по \ref[теореме Вейерштрасса\nonumber][thm:08:weierstrass], у неё
    есть предел.

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

\section Заключение

Мы доказали теорему Вейерштрасса, позволяющую исследовать на сходимость
монотонные ограниченные последовательности. С её помощью, а также с помощью
бинома Ньютона, мы определили число $e$ как предел некоторой последовательности.
Оно нам ещё пригодится.