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

Last updated
Save as PDF

Page ID: 64394

$ \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}}$

Згадайте появу трикутника Паскаля в прикладі 1.3.4. Якщо ви стикалися з трикутником раніше, ви можете знати, що він має багато цікавих властивостей. Ми розглянемо деякі з них тут.

Ви можете знати, наприклад, що записи в трикутнику Паскаля - це коефіцієнти полінома, отриманого шляхом підвищення біноміального до цілого степеня. Наприклад,

\[(x+y)^3=1\cdot x^3+3\cdot x^2y+ 3\cdot xy^2+1\cdot y^3\nonumber \]

і коефіцієнти 1, 3, 3, 1 утворюють три рядки трикутника Паскаля. З цієї причини числа$n\choose k$ зазвичай називають біноміальними коефіцієнтами.

Теорема $\PageIndex{1}$: Binomial Theorem

\[ (x+y)^n={n\choose 0}x^n+{n\choose 1}x^{n-1}y+ {n\choose 2}x^{n-2}y^2+\cdots+{n\choose n}y^n= \sum_{i=0}^n {n\choose i}x^{n-i}y^i\nonumber \]

Доказ

Доводимо це шляхом індукції на$n$. Легко перевірити перші кілька, скажімо для того$n=0,1,2$, які формують базовий корпус. Тепер припустимо, теорема вірна для$n-1$, тобто\[(x+y)^{n-1} =\sum_{i=0}^{n-1} {n-1\choose i}x^{n-1-i}y^i.\nonumber \]

Тоді\[(x+y)^n=(x+y)(x+y)^{n-1}=(x+y)\sum_{i=0}^{n-1} {n-1\choose i}x^{n-1-i}y^i.\nonumber \]

Використовуючи розподільну властивість, це стає\[\eqalign{ x\sum_{i=0}^{n-1} {n-1\choose i}x^{n-1-i}y^i+ y&\sum_{i=0}^{n-1} {n-1\choose i}x^{n-1-i}y^i\cr &=\sum_{i=0}^{n-1}{n-1\choose i}x^{n-i}y^i+ \sum_{i=0}^{n-1} {n-1\choose i}x^{n-1-i}y^{i+1}.\cr}\nonumber \]

Ці дві суми мають багато спільного, але вона трохи замаскована «зміщенням»: перша сума починається з$x^ny^0$ терміну і закінчується$x^{1}y^{n-1}$ терміном, тоді як відповідні члени у другій сумі -$x^{n-1}y^{1}$ і$x^{0}y^{n}$. Перепишемо другу суму так, щоб вони збігалися:

\[\eqalign{ \sum_{i=0}^{n-1}{n-1\choose i}&x^{n-i}y^i+ \sum_{i=0}^{n-1} {n-1\choose i}x^{n-1-i}y^{i+1}\cr &=\sum_{i=0}^{n-1}{n-1\choose i}x^{n-i}y^i+ \sum_{i=1}^{n} {n-1\choose i-1}x^{n-i}y^{i}\cr &={n-1\choose 0}x^n+\sum_{i=1}^{n-1}{n-1\choose i}x^{n-i}y^i+ \sum_{i=1}^{n-1} {n-1\choose i-1}x^{n-i}y^{i}+{n-1\choose n-1}y^{n}\cr &={n-1\choose 0}x^n+ \sum_{i=1}^{n-1}({n-1\choose i}+{n-1\choose i-1})x^{n-i}y^{i}+ {n-1\choose n-1}y^{n}.\cr }\nonumber \]

Тепер ми можемо використовувати теорему 1.3.1, щоб отримати:

\[\eqalign{ {n-1\choose 0}x^n+ &\sum_{i=1}^{n-1}({n-1\choose i}+{n-1\choose i-1})x^{n-i}y^{i}+ {n-1\choose n-1}y^{n}.\cr &={n-1\choose 0}x^n+ \sum_{i=1}^{n-1}{n\choose i}x^{n-i}y^{i}+ {n-1\choose n-1}y^{n}.\cr &={n\choose 0}x^n+ \sum_{i=1}^{n-1}{n\choose i}x^{n-i}y^{i}+ {n\choose n}y^{n}\cr &=\sum_{i=0}^{n}{n\choose i}x^{n-i}y^{i}.\cr }\nonumber \]

На наступному, останньому кроці ми використовували факти, які${n-1\choose 0}={n\choose 0}$ і${n-1\choose n-1}={n\choose n}$.

Ось цікавий наслідок цієї теореми: Розглянемо

\[(x+y)^n=(x+y)(x+y)\cdots(x+y).\nonumber \]

Один із способів ми можемо подумати про спробу примножити це: Пройдіть через$n$ фактори$(x+y)$ і в кожному факторі виберіть$x$ або або$y$; врешті-решт, помножте свій вибір разом, отримуючи якийсь термін$xxyxyy\cdots yx= x^iy^j$, як, звичайно,$i+j=n$. Якщо ми зробимо це всіма можливими способами і потім збираємо подібні терміни, то однозначно отримаємо

\[\sum_{i=0}^n a_ix^{n-i}y^i.\nonumber \]

Ми знаємо, що правильне розширення має${n\choose i}=a_i$; це насправді те, що ми отримаємо цим методом? Так: врахуйте$x^{n-i}y^i$. Скільки разів ми отримаємо цей термін за допомогою даного методу? Це буде кількість разів, коли ми закінчимо з$i$$y$ -факторами. Оскільки є$n$ фактори$(x+y)$, кількість разів ми отримуємо$i$$y$ -фактори повинні бути кількістю способів вибору$i$$(x+y)$ факторів, щоб сприяти а$y$, а саме$n\choose i$. Це, мабуть, не корисний метод на практиці, але він цікавий і зрідка корисний.

Приклад$\PageIndex{1}$:

Використовуючи цей метод, ми можемо отримати\[(x+y)^3 = xxx + xxy + xyx + xyy + yxx + yxy + yyx + yyy\nonumber \], який дійсно стає$\displaystyle x^3+3x^2y+3xy^2 + y^3$ після збору подібних термінів.

Біноміальна теорема може бути використана для отримання багатьох цікавих ідентичностей. $\PageIndex{1}$ Поширений спосіб переписати його - підставити$y=1$, щоб отримати\[(x+1)^n=\sum_{i=0}^n {n\choose i} x^{n-i}.\nonumber \]

Якщо ми потім підставити$x=1$ ми отримуємо,\[2^n=\sum_{i=0}^n{n\choose i},\nonumber \] що є,$n$ Рядок Трикутник Паскаля суми до$2^n$. Це також легко зрозуміти комбінаторно: сума представляє загальну кількість підмножин $n$-множини, оскільки вона додає разом номери підмножин будь-якого можливого розміру. Безпосередньо легко побачити, що кількість підмножин$n$ -set дорівнює$2^n$: для кожного елемента множини ми робимо вибір, включити або виключити елемент. Загальна кількість способів зробити цей вибір$2\cdot2\cdots2=2^n$, за принципом множення.

Припустимо тепер, що$n\ge 1$ і ми$-1$ підставляємо$x$; ми отримуємо\[\label{eq:1} \eqalignno{ (-1+1)^n&=\sum_{i=0}^n{n\choose i}(-1)^{n-i}.}\]

Сума тепер є змінною сумою: кожен інший член множиться на$-1$. Оскільки ліва сторона є$0$, ми можемо переписати це, щоб отримати\[\label{eq:2} \eqalignno{ {n\choose 0}+{n\choose 2}+\cdots&={n\choose 1}+{n\choose 3}+\cdots. }\]

Так що кожна з цих сум є$2^{n-1}$.

Ще однією очевидною особливістю трикутника Паскаля є симетрія: кожен рядок читає однаково вперед і назад. Тобто у нас є:

Теорема $\PageIndex{2}$

$\displaystyle {n\choose i}={n\choose n-i}.$

Доказ: Це досить легко побачити комбінаторно: кожен$i$ -subset$n$ -subset асоціюється з$(n-i)$ -subset. Тобто, якщо$n$ -set є$A$, а якщо$B\subseteq A$ має розмір$i$, то доповнення$B$ має розмір$n-i$. Це встановлює$1–1$ відповідність між наборами розміру$i$ та наборами розміру$n-i$, тому номери кожного однакові. (Звичайно, якщо$i=n-i$, ніяких доказів не потрібно.)

Зверніть увагу, що це означає, що Біноміальна теорема $\PageIndex{1}$, також може бути записана як\[(x+y)^n=\sum_{i=0}^n {n\choose n-i}x^{n-i}y^{i}.\nonumber\] або\[(x+y)^n=\sum_{i=0}^n {n\choose i}x^{i}y^{n-i}.\nonumber\]

Ще однією яскравою особливістю трикутника Паскаля є те, що записи по ряду строго збільшуються до середини ряду, а потім строго зменшуються. Так як ми вже знаємо, що ряди симетричні, то перша частина цього має на увазі другу.

Теорема $\PageIndex{3}$

Для$1\le i\le \lfloor{n\over 2}\rfloor$,$\displaystyle {n\choose i}>{n\choose i-1}.$

Доказ

Це шляхом індукції; базовий випадок видно з перших кількох рядів. Напишіть

\[\eqalign{ {n\choose i}&={n-1\choose i-1}+{n-1\choose i}\cr {n\choose i-1}&={n-1\choose i-2}+{n-1\choose i-1}\cr }\nonumber \]

За умови$1\le i\le \lfloor{n-1\over 2}\rfloor$, що, ми знаємо за індукційною гіпотезою, що\[{n-1\choose i}>{n-1\choose i-1}.\nonumber\]

За умови$1\le i-1\le \lfloor{n-1\over 2}\rfloor$, що ми знаємо, що\[{n-1\choose i-1}>{n-1\choose i-2}.\nonumber \]

Отже$2\le i\le \lfloor{n-1\over 2}\rfloor$, якщо,\[{n\choose i}>{n\choose i-1}.\nonumber\]

Це залишає два особливих випадки для перевірки:$i=1$ і$i\ge \lfloor{n-1\over 2}\rfloor+1$. Їх залишають як вправу.

Автори та атрибуція

Template:ContribGuichard