ТГиК-2019-Лекция-14.10.2019

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Формула включений-исключений

Пусть есть n множеств \(A_1, A_2, ... , A_n \), которые взаимно пересекаются. Как найти \(\left | A_1 \cup ... \cup A_n \right | \) ?

Формула, которую нам предстоит доказать\[ \left | \bigcup^n_{i=1} {A_{i}} \right | = \sum^n_{k=1} {(-1)^{k+1} \mbox{ }\sum_{1 \le i_1 < ... < i_k \le n} {\left | A_{i1} \cap ... \cap A_{ik} \right |}} \mbox{ }(1)\]

Доказательство

Доказательство проведем по индукции.

1) База индукции

Рассмотрим пустое множество.

В формуле слева будет 0 и справа будет 0. Следовательно, формула верна.

2) Предположение

Пусть формула верна, если \( \left | \bigcup^n_{i=1} {A_{i}} \right | = m \) \((2)\)

3) Шаг

Введем новый элемент \(a\). Добавим его в множества \(A_{j_1}, ..., A_{j_l}\)

Введём новое обозначение по такому правилу\[A'_i = \begin{cases} A_i, & \mbox{если } i \not\in \left \{j_1, j_2, ..., j_l \right \} \\ A_i \cup a, & \mbox{если } i \in \left \{j_1, j_2, ..., j_l \right \} \end{cases}\]

Следовательно, \( \left | \bigcup^n_{i=1} {A'_{i}} \right | = m+1 \) \((3)\)

4) Вычтем "левые части" в формуле (1), то есть (2)-(3)\[\left | \bigcup^n_{i=1} {A'_{i}} \right | - \left | \bigcup^n_{i=1} {A_{i}} \right | = 1 \]

5) Вычтем аналогично "правые части" в формуле (1)\[\sum^n_{k=1} {(-1)^{k+1} \mbox{ }\sum_{1 \le i_1 < ... < i_k \le l} {(\left | A'_{i1} \cap ... \cap A'_{ik} \right |-\left | A_{i1} \cap ... \cap A_{ik} \right |)}} = \]

Разность \(\left | A'_{i1} \cap ... \cap A'_{ik} \right |-\left | A_{i1} \cap ... \cap A_{ik} \right |\) будет либо 0, либо 1, причём единице она равна тогда и только тогда, когда элемент \(a\) есть во всех \(A'_{i1}, ..., A'_{ik}\) Кроме того, если \(k>l\) то существует такое множество, где нет элемента \(a\). Следовательно, разность будет равна 0.

6) С учётом преобразований, получим\[ = \sum^{l}_{k=1}{(-1)^{k+1} \mbox{ } \sum_{1 \le i_1 < ... < i_k \le n} {1} = \sum^{l}_{k=1}{(-1)^{k+1} C^k_l}} = \]

Из бинома Ньютона\[(1-1)^n = \sum^l_{k=0}{C^k_n (-1)^k}\] У нас есть два существенных различия: во-первых, суммирование в биноме Ньютона идёт с 0; во-вторых, в нашем выражении степень \(\left \{ k+1 \right \}\)

Второе различие можно разрешить, если вынести (-1) за знак суммирования, а первое - если прибавить и вычесть элемент суммирования при \(k = 0 \)

7) Тогда\[ = - \sum^{l}_{k=1}{(-1)^{k} C^k_l} + C^0_l = 0 + 1 = 1\]

Первое слагаемое было приведено к случаю из бинома Ньютона и потому оно 0.

Разность левых частей и разность правых частей совпадают, следовательно, формула доказана.

Асимптотические оценки для комбинаторных величин

Как определить асимптотику?

1 способ:

\(\lim_{x \to A} \frac{f(x)}{g(x)} = 1 \Longleftrightarrow f(x) \sim g(x) \mbox{ при } x \to A \)

Что делать, если \(g(x)=0\)?

2 способ.

\( f(x) = g(x)(1+\overline {o}(1)) \Longleftrightarrow f(x) \sim g(x) \mbox{ при } x \to A \)

Примеры.

  • \(x \not\sim 2x\), так как\[\lim_{x \to 0} \frac{x}{2x} = \frac{1}{2} \neq 1 \]

С другой стороны, \( 2x=x(1+1) \mbox{, } 1\neq \overline {o}(1) \mbox{, следовательно, }x \not\sim 2x\)

  • \(sin(x)\sim x\), так как\[\lim_{x \to 0} \frac{sin(x)}{x} = 1\]
  • \(e^x \sim e^x + x^{100} \mbox{, так как } e^x + x^{100} = e^x (1+ \frac{x^{100}}{e^x} ) = e^x(1 +\overline {o}(x))\)

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

Асимптотика числа сочетаний из n по k

1) Известно, что число \(C^k_n\) связано с треугольником Паскаля (см. ТГиК-2019-Лекция-16.09.2019). В треугольнике Паскаля можно заметить, что коэффициенты сначала возрастают, а затем - убывают. Это свойство можно записать следующим образом\[ \mbox{Для нечётных: } C^{0}_{2n+1} < C^{1}_{2n+1} < ... C^{n}_{2n+1} = C^{n+1}_{2n+1} > C^{n+2}_{2n+1} > ... >C^{2n+1}_{2n+1} \\ \mbox{Для чётных: } C^{0}_{2n} < C^{1}_{2n} < ... C^{n}_{2n}> C^{n+1}_{2n} > ... >C^{2n}_{2n} \]

Доказательство данного свойства

1) \(C^{k}_{n} = C^{n-k}_{n}\), следовательно, рассматриваемая "полоса" в треугольнике Паскаля симметрична

2) \(C^{k+1}_{n+1} = C^{k+1}_{n} + C^{k}_{n}\)

3) Пусть \(C^{k}_{n} < C^{k+1}_{n} < C^{k+2}_{n}\)

Тогда \(C^{k}_{n} + C^{k+1}_{n} < C^{k+1}_{n} + C^{k+2}_{n}\)

В левой части - \(C^{k+1}_{n+1}\), в правой части - \(C^{k+2}_{n+1}\)

2) Так как сумма элементов очевидно больше максимального элемента суммы\[ \sum^{2n}_{k=0}{C^{k}_{2n}} = 2^{2n} \ge C^{n}_{2n}\]

3) Каждый элемент суммы заменим на максимальный. Тогда, очевидно, "новая" сумма будет больше изначальной\[ \sum^{2n}_{k=0}{C^{n}_{2n}} = (2n+1)C^{n}_{2n} \ge \sum^{2n}_{k=0}{C^{k}_{2n}} = 2^{2n} \]

4) Полученные неравенства можно записать в виде одного двойного:

\( \frac{2^{2n}}{2n+1} \le C^{n}_{2n} \le 2^{2n} \)

Значит, \(C^{n}_{2n}\) "не сильно отличается" от \(2^{2n}\)

5) Воспользуемся формулой Стирлинга\[ n! \sim \sqrt{2\pi n} \left(\frac{n}{e} \right )^n \]

Тогда\[ C^n_{2n} = \frac {(2n)!}{(n!)^2} \sim \frac {\sqrt{2 \pi 2n} \left(\frac{2n}{e} \right )^{2n}}{(\sqrt{2 \pi 2n}\left(\frac{n}{e} \right )^n)^2} = \frac {2^{2n}}{\sqrt{\pi n}} \]

Таким образом, выведена следующая асимптотика\[ C^n_{2n} \sim \frac {2^{2n}}{\sqrt{\pi n}} \]

Вернёмся к \(C^k_n\)

1) \[ C^k_n = \frac{n!}{k!(n-k)!} = \frac{n(n-1)(n-2)...(n-(n-1))}{k!(n-k)!} = \frac{n^n (1-\frac{1}{n})(1-\frac{2}{n})...(1-\frac{n-1}{n})}{k!(n-k)!} = \frac{n^k}{k!} (1-\frac{1}{n})(1-\frac{2}{n})...(1-\frac{k-1}{n}) = \]

Уже можно сделать следующий вывод: если \(k = \overline {o}(n)\), то \(C^k_n \sim \frac{n^k}{k!}\)

2) Можно продолжить рассуждения следующим образом\[ \frac{n^k}{k!} exp \left \{ ln(1-\frac{1}{n}) + ln(1-\frac{2}{n})+...+ln(1-\frac{n-1}{n}) \right \} = \left | Замечание: ln(1-x)=x+\overline {o}(x) \right |= \\ = \frac{n^k}{k!} exp \left \{ \frac{1}{n} +\frac{2}{n}+...+\frac{n-1}{n} + \overline {o}(\frac{1}{n}) + \overline {o}(\frac{2}{n}) +...+ \overline {o}(\frac{n-1}{n}) \right \} = \frac{n^k}{k!} exp \left \{ \frac{k(k-1)}{2n} + \overline {o}(\frac{k(k-1)}{2n}) \right \} \]

Вывод: если \(k^2 = \overline {o}(n) \), то \(C^k_n \sim \frac{n^k}{k!} exp\left \{ \frac{k(k-1)}{2n} \right \} \)