7: Доказові методи III - Комбінаторика
- Page ID
- 64794
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Трагедія - це коли я порізав палець. Комедія - це коли потрапляєш у відкриту каналізацію і вмираєш.
—Мел Брукс
- 7.1: Підрахунок
- Назва цього розділу, «Підрахунок», не призначена для того, щоб викликати звичний процес підрахунку овець, або підрахунку змін. Ми хочемо мати можливість підрахувати якусь колекцію в принципі, щоб ми змогли виявити формулу її розміру. Є два принципи, які будуть незамінними при підрахунку речей: «правило множення», яке говорить нам, коли ми повинні множити, і «правило додавання», яке говорить нам, коли ми повинні додати.
- 7.2: Парність і підрахунок аргументів
- Цей розділ стосується двох дуже потужних елементів арсеналу перевірки: «Парність» - це спосіб посилання на результат парного/непарного обчислення; Підрахувальні аргументи найчастіше приймають форму підрахунку деякої колекції двома різними способами - а потім порівняння цих результатів. Ці методи мають мало спільного один з одним, але коли вони застосовні, вони, як правило, виробляють дійсно елегантні маленькі аргументи.
- 7.3: Принцип «голубиного отвору»
- Слово «голуб» може стосуватися отвору, в якому сідає голуб (тобто в значній мірі, як це звучить) або ряд приблизно квадратних поглиблень у столі, в якому можна було б сортувати відповідність. Незалежно від того, чи вважаєте ви за краще думати про вкорінення птахів або літери, які сортуються, перша і найпростіша версія принципу pigeonhole полягає в тому, що якщо у вас більше «речей», ніж у вас є «контейнери», повинен бути контейнер, що містить принаймні дві речі.
- 7.4: Алгебра комбінацій
- Біноміал - це многочлен з двома долями. Здається, що ви вже бачили розташування цих біноміальних коефіцієнтів у трикутний масив - відомий як трикутник Паскаля. Річ, що робить цей трикутник таким приємним і що призводить до дивної назви «біноміальні коефіцієнти» для кількості k-комбінацій n-множини полягає в тому, що ви можете використовувати трикутник для (дуже швидко) обчислення степеней біноміалів.