1.2: Біноміальні коефіцієнти

Template:MathJaxLevin

Досліджуйте!

У шахах тура може пересуватися тільки прямими (не по діагоналі). Заповніть кожен квадрат шахової дошки нижче кількістю різних найкоротших шляхів, які тура, у верхньому лівому куті, може пройти, щоб дістатися до цього квадрата. Наприклад, один квадрат вже заповнений. Є шість різних шляхів від тури до квадрата: DDRR (вниз праворуч), DRDR, DRRD, RDDR, RDRD, RDRD і RRDD.

Ось деякі очевидно різні дискретні об'єкти, які ми можемо порахувати: підмножини, бітові рядки, шляхи решітки та біноміальні коефіцієнти. Ми наведемо приклад кожного типу проблеми підрахунку (і скажемо, що ці речі навіть є). Як ми побачимо, ці проблеми підрахунку напрочуд схожі.

Підмножини

Підмножини повинні бути знайомими, інакше прочитайте розділ 0.3 ще раз. Припустимо, ми дивимося на набір$A = \{1,2,3,4,5\}$. Скільки підмножин$A$ містять рівно 3 елементи?

По-перше, більш просте питання: Скільки підмножин$A$ є загальним? Іншими словами, що таке$|\pow(A)|$ (кардинальність силового набору$A$)? Подумайте про те, як ми б побудувати підмножину. Нам потрібно вирішити, для кожного з елементів, включати$A\text{,}$ чи ні елемент в нашу підмножину. Тому нам потрібно вирішити «так» або «ні» для елемента 1. І для кожного вибору, який ми робимо, нам потрібно вирішити «так» або «ні» для елемента 2. І так далі. Для кожного з 5 елементів у нас є 2 варіанти. Тому кількість підмножин просто$2\cdot 2\cdot 2 \cdot 2\cdot 2 = 2^5$ (за мультиплікативним принципом).

З цих 32 підмножин, скільки мають 3 елементи? Це не очевидно. Зауважте, що ми не можемо просто використовувати мультиплікативний принцип. Можливо, ми хочемо сказати, що у нас є 2 варіанти (так/ні) для першого елемента, 2 варіанти для другого, 2 варіанти для третього, а потім лише 1 вибір для інших двох. Але що робити, якщо ми скажемо «ні» одному з перших трьох елементів? Тоді у нас буде два варіанти для 4-го елемента. Який безлад!

Ще одна (погана) ідея: нам потрібно вибрати три елементи, які будуть в нашій підмножині. Є 5 елементів на вибір. Таким чином, є 5 варіантів для першого елемента, і для кожного з цих 4 варіантів для другого, а потім 3 для третього (останнього) елемента. Мультиплікативний принцип сказав би тоді, що існує загальна кількість$5 \cdot 4 \cdot 3 = 60$ способів вибору підмножини елементів 3. Але це не може бути правильним ($60 > 32$з одного боку). Одним з результатів, які ми отримали б від цих варіантів, буде набір,$\{3,2,5\}\text{,}$ вибравши спочатку елемент 3, потім елемент 2, потім елемент 5. Іншим результатом буде$\{5,2,3\}$ вибір спочатку елемента 5, потім елемента 2, потім елемента 3. Але це один і той же набір! Ми можемо виправити це, розділивши: для кожного набору з трьох елементів, є 6 результатів підраховується кількість наших 60 (оскільки є 3 варіанти, для якого ми перераховуємо перший елемент, 2 для якого ми перераховуємо другий, і 1, для якого ми перераховуємо останній). Таким чином, ми очікуємо, що там буде 10 3-елементні підмножини$A$.

Чи правильно це? Ну, ми могли б перерахувати всі 10 з них, будучи дуже систематичними в цьому, щоб переконатися, що ми не пропускаємо жодного або перерахуємо жодного двічі. Або ми могли б спробувати підрахувати, скільки підмножин$A$ не мають 3 елементи в них. Скільки не мають елементів? Всього 1 (порожній набір). Скільки мають 5? Знову ж таки, просто 1. Це випадки, коли ми говоримо «ні» всім елементам, або «так» всім елементам. Гаразд, як щодо підмножин, які містять один елемент? Їх 5. Треба сказати «так» рівно одному елементу, і є 5 на вибір. Це також кількість підмножин, що містять 4 елементи. Це ті, для яких ми повинні сказати «ні» рівно одному елементу.

Поки що ми нарахували 12 з 32 підмножин. Ми ще не порахували підмножини з кардинальністю 2 і з кардинальністю 3. Всього залишилося 20 підмножин, щоб розділити між цими двома групами. Але кількість кожного має бути однаковим! Якщо ми скажемо «так» рівно двом елементам, що може бути досягнуто точно такою ж кількістю способів, як і кількість способів, ми можемо сказати «ні» рівно двом елементам. Таким чином, кількість 2-елементних підмножин дорівнює кількості 3-елементних підмножин. Разом є 20 з цих підмножин, тому 10 кожен.

Кількість елементів:	0	1	2	3	4	5
Кількість підмножин:	1	5	10	10	5	1

Бітові рядки

«Біт» є коротким для «двійкової цифри», тому бітовий рядок - це рядок двійкових цифр. Двійкові цифри - це просто числа 0 і 1. Усі наступні рядки є бітовими рядками:

\ begin {рівняння*} 1001\ квад 0\ квад 1111\ квад 1010101010\ кінець {рівняння*}

Кількість бітів (0 або 1) в рядку дорівнює довжині рядка; рядки вище мають довжину 4, 1, 4 і 10 відповідно. Ми також можемо запитати, скільки бітів є 1. Число 1 в бітовому рядку - це вага рядка; ваги вищевказаних рядків 2, 0, 4 і 5 відповідно.

Визначення: Бітові рядки

• Рядок$n$ -біт є бітовим рядком довжини$n$. Тобто це рядок, що містить$n$ символи, кожен з яких є бітом, або 0, або 1.
• Вага бітового рядка - це число 1 в ньому.
• $\B^n$це набір всіх$n$ -бітових рядків.
• $\B^n_k$це набір всіх$n$ -бітових рядків ваги$k$.

Наприклад, елементами множини$\B^3_2$ є бітові рядки 011, 101 і 110. Це єдині рядки, що містять три біти рівно два з яких є 1.

Питання підрахунку: Скільки бітових рядків мають довжину 5? Скільки з них мають вагу 3? Іншими словами, ми просимо кардинальності$|\B^5|$ і$|\B^5_3|$.

Знайти кількість 5-бітних рядків варто прямо вперед. У нас є 5 біт, і кожен може бути або 0 або 1. Таким чином, є 2 варіанти для першого біта, 2 варіанти для другого, і так далі. За мультиплікативним принципом існують$2 \cdot 2 \cdot 2\cdot 2 \cdot 2 = 2^5 = 32$ такі рядки.

Знайти кількість 5-бітних рядків вагою 3 складніше. Подумайте, як могла б запуститися така струна. Перший біт повинен бути або 0, або 1. У першому випадку (рядок починається з 0), ми повинні вирішити ще чотири біти. Щоб мати в цілому три 1, серед цих чотирьох бітів, що залишилися, повинні бути три 1, Щоб підрахувати всі ці рядки, ми повинні включити всі 4-бітові рядки вагою 3. У другому випадку (рядок починається з 1), у нас ще є чотири біти, щоб вибрати, але тепер тільки два з них можуть бути 1, тому ми повинні дивитися на всі 4-бітні рядки ваги 2. Таким чином, рядки у$\B^5_3$ всіх мають форму$1\B^4_2$ (тобто 1 після рядка з$\B^4_2$) або$0\B^4_3$. Ці два набори є неспільними, тому ми можемо використовувати принцип адитиви:

\ begin {рівняння*} |\ B^5_3| = |\ B^4_2| + |\ B^4_3|. \ end {рівняння*}

Це приклад рецидивного відношення. Ми представили один екземпляр нашої проблеми підрахунку з точки зору двох простіших екземплярів проблеми. Якби ми знали кардинальності$\B^4_2$ і$\B^4_3$. Повторюючи ті ж міркування,

\ begin {рівняння*} |\ B^4_2| = |\ B^3_1| + |\ B^3_2|\ квадратний\ mbox {і}\ квад |\ B^4_3| = |\ B^3_2| + |\ B^3_3|. \ end {рівняння*}

Ми можемо продовжувати йти вниз, але це повинно бути досить добре. Обидва$\B^3_1$ і$\B^3_2$ містять 3 бітові рядки: ми повинні вибрати один з трьох бітів, щоб бути 1 (три способи зробити це) або один з трьох бітів, щоб бути 0 (три способи зробити це). Крім того,$\B^3_3$ містить лише один рядок: 111. Таким чином$|\B^4_2| = 6$ і$|\B^4_3| = 4\text{,}$ який ставить$\B^5_3$ в цілому 10 рядків.

Але почекайте —32 і 10 були відповідями на підрахункові питання про підмножини. Збіг? Зовсім немає. Кожен бітовий рядок можна розглядати як код для підмножини. Для набору$A = \{1,2,3,4,5\}\text{,}$ ми б використовували 5-бітові рядки, по одному біту для кожного елемента$A$. Кожен біт у рядку дорівнює 0, якщо відповідний елемент не$A$ знаходиться в підмножині, і 1, якщо елемент$A$ знаходиться в підмножині. Пам'ятайте, що визначення підмножини склало послідовність з п'яти так/ні голосів за елементи$A$. Замість так, ми ставимо 1; замість ні ставимо 0.

Наприклад, бітовий рядок$11001$ представляє підмножину,$\{1,2,5\}$ оскільки перший, другий і п'ятий біти є 1.$\{3,5\}$ Підмножина буде закодована рядком$00101$. Те, що ми насправді маємо тут, - це біекція від$\pow(A)$ до$\B^5$.

Тепер, щоб підмножина містила рівно три елементи, відповідний бітовий рядок повинен містити рівно три одиниці. Іншими словами, вага повинна бути 3. Таким чином, підрахунок кількості 3-х елементних підмножин збігається з$A$ підрахунком кількості 5-бітних рядків вагою 3.

Решіткові шляхи

Цілочисельна решітка - це множина всіх точок декартової площини, для яких$x$ і$y$ координати є цілими числами. Якщо ви любите малювати графіки на графічному папері, то решітка - це сукупність всіх перетинів ліній сітки.

Гратчастий шлях - один з найкоротших шляхів, що з'єднує дві точки на решітці, що рухаються тільки по горизонталі і вертикалі. Наприклад, ось три можливі шляхи решітки від точок$(0,0)$ до$(3,2)\text{:}$

Зверніть увагу, щоб шлях був найкоротшим, кожен рух повинен бути або вправо, або вгору. Крім того, у цьому випадку зауважте, що незалежно від того, яким шляхом ми йдемо, ми повинні зробити три кроки правильно і два кроки вгору. Незалежно від того, в якому порядку ми робимо ці кроки, завжди буде 5 кроків. Таким чином, кожен шлях має довжину 5.

Питання підрахунку: скільки ґратчастих шляхів є між$(0,0)$ і$(3,2)\text{?}$ Ми могли б спробувати намалювати всі ці, або замість того, щоб малювати їх, може бути просто перерахувати, в якому напрямку ми рухаємося на кожному з 5 кроків. Один шлях може бути RRUUR, або може бути UURRR, або, можливо, RURRU (вони відповідають трьом шляхах, намальованим вище). Так скільки таких рядків R і U є?

Зверніть увагу, що кожен з цих рядків повинен містити 5 символів. Рівно 3 з них повинні бути R (так як наше призначення 3 одиниці праворуч). Це здається жахливо знайомим. Насправді, що, якщо ми використовували$1$ замість R і 0 замість U? Тоді ми б просто мати 5-бітові рядки вагою 3. Їх 10, тому існує 10 ґратчастих шляхів від (0,0) до (3,2).

Відповідність між бітовими рядками і шляхами решітки на цьому не припиняється. Ось ще один спосіб підрахунку ґратчастих шляхів. Розглянемо решітку, показану нижче:

Будь-який шлях решітки від (0,0) до (3,2) повинен проходити рівно через одне з$A$ і$B$. Точка$A$ знаходиться на відстані 4 кроків від (0,0) і два з них знаходяться вправо. Кількість шляхів решітки до$A$ дорівнює числу 4-бітних рядків вагою 2, а саме 6. Точка$B$ знаходиться в 4 кроках від (0,0), але тепер 3 з них знаходяться вправо. Таким чином, кількість шляхів до точки$B$ таке ж, як кількість 4-бітових рядків вагою 3, а саме 4. Таким чином, загальна кількість шляхів до (3,2) просто$6+4$. Таким же чином ми розрахували кількість 5-бітних рядків вагою 3. Точно таке ж відношення повторення існує для бітових рядків і для шляхів решітки.

Біноміальні коефіцієнти

Біноміальні коефіцієнти - це коефіцієнти в розширеному варіанті біноміала, такі як$(x+y)^5$. Що відбувається, коли ми множимо такий біноміал? Ми будемо розширювати$(x+y)^n$ для різних значень$n$. Кожен з них робиться шляхом множення всього (тобто, Foil-ing), а потім збираючи подібні терміни.

\ почати {рівняння*} (x+y) ^1 = x + y\ кінець {рівняння*}\ почати {рівняння*} (x+y) ^2 = x^2 + 2xy+ y^2\ end {рівняння*}\ початок {рівняння*} (x+y) ^3 = x^3 + 3x^2y + 3xy^2 + y^3\ кінець {рівняння*} *}\ почати {рівняння*} (x+y) ^4 = x^4 + 4x^3y + 6x^2y^2y^2+ 4xy^3+ y^4. \ end {рівняння*}

Насправді існує більш швидкий спосіб розширити вищевказані біноми. Наприклад, розглянемо наступний,$(x+y)^5$. Те, що ми насправді робимо, примножується,

\ begin {рівняння*} (x+y) (x+y) (x+y) (x+y) (x+y). \ end {рівняння*}

Якщо це виглядає складним, поверніться до справи$(x+y)^3 = (x+y)(x+y)(x+y)$. Чому у нас тільки один$x^3$,$y^3$ але три$x^2y$ і$xy^2$ терміни? Кожен раз, коли ми розподіляємо над a,$(x+y)$ ми створюємо дві копії того, що залишилося, одну помножену$x\text{,}$ на іншу, помножену на$y$. Щоб отримати,$x^3\text{,}$ нам потрібно вибрати «помножений на$x$» сторону кожного разу (у нас немає$y$ жодної в терміні). Це станеться лише один раз. З іншого боку, щоб отримати,$x^2y$ нам потрібно виділити$x$ сторону двічі, а$y$ сторону один раз. Іншими словами, нам потрібно вибрати один з трьох$(x+y)$ термінів, щоб «внести» їх$y$.

Аналогічно, в$(x+y)^5\text{,}$ розширенні буде тільки один$x^5$ термін і один$y^5$ термін. Це тому, що для отримання a$x^5\text{,}$ нам потрібно використовувати$x$ термін у кожній з копій біноміального$(x+y)\text{,}$ і аналогічно для$y^5$. Що про$x^4y\text{?}$ Щоб отримати такі терміни, ми повинні використовувати чотири$x$ і один,$y\text{,}$ так що нам потрібно рівно один з п'яти біноміалів, щоб внести свій внесок$y$. Є 5 варіантів для цього, тому є 5 способів отримати$x^4y\text{,}$ так$x^4y$ коефіцієнт 5. Це також коефіцієнт з$xy^4$ тієї ж (але протилежної) причини: існує 5 способів вибрати, який з 5 біноміалів сприяє єдиному$x$. Поки що у нас є

\ begin {рівняння*} (x+y) ^5 = x^5 + 5x^4y +\ підкреслення {~? ~} ~x^3y^2 +\ підкреслення {~? ~} ~x^2y^3+ 5 xy ^ 4 + y^5. \ end {рівняння*}

Нам ще знадобляться коефіцієнти$x^3y^2$ і$x^2y^3$. В обох випадках нам потрібно вибрати рівно 3 з 5 біноміалів, щоб внести одну змінну, інші два, щоб внести іншу. Зачекайте. Це звучить знайомо. У нас є 5 речей, кожна може бути однією з двох речей, і нам потрібно всього 3 з них. Це так само, як приймати 5 біт і переконавшись, що рівно 3 з них є 1, Таким чином, коефіцієнт$x^3y^2$ (а також$x^2y^3$) буде точно такий же, як кількість бітових рядків довжиною 5 і вагою 3, які ми знайшли раніше бути 10. Отже, ми маємо:

\ begin {рівняння*} (x+y) ^5 = x^5 + 5x^4y + 10x^3y^2 + 10x^2y^3y^3+ 5 xy ^ 4 + y^5. \ end {рівняння*}

Ці цифри ми продовжуємо бачити знову і знову. Вони являють собою кількість підмножин певного розміру, кількість бітових рядків певної ваги, кількість шляхів решітки та коефіцієнти цих біноміальних добуків. Назвемо їх біноміальними коефіцієнтами. У нас навіть є спеціальний символ для них:${n \choose k}$.

Визначення: Біноміальні коефіцієнти

Для кожного цілого$n \ge 0$ і цілого числа$k$ з$0 \le k \le n$ є число

\ begin {рівняння*} {n\ вибрати k}\ end {рівняння*}

прочитайте «$n$вибрати»$k$. У нас є:

• ${n\choose k} = |\B^n_k|\text{,}$кількість$n$ -бітових рядків ваги$k$.
• ${n \choose k}$кількість підмножин набору розміру,$n$ кожна з яких має кардинальність$k$.
• ${n \choose k}$кількість ґратчастих шляхів довжини,$n$ що містять$k$ кроки праворуч.
• ${n \choose k}$це коефіцієнт$x^ky^{n-k}$ в розширенні$(x+y)^n$.
• ${n \choose k}$кількість способів вибору$k$ об'єктів із загальної кількості$n$ об'єктів.

Останній пункт кулі зазвичай приймається за визначення${n \choose k}$. З$n$ предметів ми повинні вибрати$k$ їх, тому є$n$ вибір$k$ способів зробити це. Кожну з наших проблем підрахунку вище можна переглянути таким чином:

• Скільки підмножин$\{1,2,3,4,5\}$ містять рівно 3 елементи? Ми повинні вибрати$3$ з 5 елементів, які будуть в нашій підмножині. Є${5 \choose 3}$ способи зробити це, тому є${5 \choose 3}$ такі підмножини.
• Скільки бітових рядків мають довжину 5 і вагу 3? Ми повинні вибрати$3$ з 5 бітів, щоб бути 1. Є${5 \choose 3}$ способи зробити це, тому є${5 \choose 3}$ такі бітові рядки.
• Скільки ґратчастих шляхів існує від (0,0) до (3,2)? Ми повинні вибрати 3 з 5 кроків, щоб бути назустріч правому. ${5 \choose 3}$Способи зробити це є, тому існують${5 \choose 3}$ такі ґратчасті доріжки.
• Який коефіцієнт розширення$(x+y)^5\text{?}$ Ми повинні вибрати 3 з 5 копій біноміалу, щоб внести свій внесок$x$.$x^3y^2$ Є${5 \choose 3}$ способи зробити це, тому коефіцієнт є${5 \choose 3}$.

Повинно бути зрозуміло, що в кожному випадку вище ми маємо правильну відповідь. Все, що нам потрібно було зробити, це правильно сформулювати питання, і стало очевидно, що${5 \choose 3}$ це правильно. Однак це не говорить нам про те, що відповідь насправді 10 у кожному конкретному випадку. Ми зрештою знайдемо формулу для,${n \choose k}\text{,}$ але поки що, озирніться назад на те, як ми прийшли до відповіді 10 у наших підрахункових проблемах вище. Все це дійшло до бітових рядків, і у нас є відношення повторення для бітових рядків:

\ begin {рівняння*} |\ b^n_k| = |\ B^ {n-1} _ {k-1} | + |\ B^ {n-1} _k|. \ end {рівняння*}

Пам'ятайте, це тому, що ми можемо почати бітовий рядок з 1 або 0. В обох випадках у нас є$n-1$ більше бітів, щоб вибрати. Рядки, що починаються з 1, повинні містити$k-1$ більше 1, тоді як рядки, що починаються з 0, все ще потребують$k$ більше 1.

Оскільки$|\B^n_k| = {n \choose k}\text{,}$ однакове відношення повторення має для біноміальних коефіцієнтів:

Відношення повторення для${n \choose k}$

\ begin {рівняння*} {n\ вибрати k} = {n-1\ вибрати k-1} + {n-1\ вибрати k}\ end {рівняння*}

Трикутник Паскаля

Давайте організуємо біноміальні коефіцієнти${n \choose k}$ в трикутник наступним чином:

Це може тривати так далеко вниз, як нам подобається. Відношення повторення для${n \choose k}$ говорить нам, що кожен запис у трикутнику є сумою двох записів над ним. Записи по сторонам трикутника завжди дорівнюють 1. Це тому, що${n \choose 0} = 1$ для всіх,$n$ оскільки існує лише один спосіб вибрати 0$n$ об'єктів, і${n \choose n} = 1$ оскільки існує один спосіб$n$ виділити всі з$n$ об'єктів. Використовуючи відношення повторення, і той факт, що сторони трикутника є 1, ми можемо легко замінити всі записи вище правильними значеннями${n \choose k}$. Це дає нам трикутник Паскаля.

Ми можемо використовувати трикутник Паскаля для обчислення біноміальних коефіцієнтів. Наприклад, використовуючи трикутник нижче, ми можемо знайти${12 \choose 6} = 924$.