1.4: Комбінаторні докази

Template:MathJaxLevin

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

1. Кубок Стенлі вирішується в кращому турнірі 7 між двома командами. Скільки способів може перемогти ваша команда? Відповімо на це питання двома способами:
   1. Скільки з 7 ігор потрібно вашій команді, щоб виграти? Скільки способів це може статися?
   2. Що робити, якщо на турнір пройдуть всі 7 ігор? Так ви виграєте останню гру. Скільки способів можуть спуститися перші 6 ігор?
   3. Що робити, якщо турнір пройде всього 6 ігор? Скільки способів це може статися? А як щодо 5 ігор? 4 гри?
   4. Які два різні способи обчислити кількість способів, які ваша команда може виграти? Запишіть рівняння за участю біноміальних коефіцієнтів (тобто\({n \choose k}\)). Який візерунок у трикутнику Паскаля це приклад?
2. Узагальнити. Що робити, якщо правила змінилися і ви зіграли кращий\(9\) турнір (потрібно 5 перемог)? Що робити, якщо ви грали в\(n\) ігровий турнір з\(k\) перемогами, які повинні бути названі чемпіоном?

Візерунки в трикутнику Паскаля

Погляньте ще раз на трикутник Паскаля. Забудьте на мить, звідки воно походить. Просто подивіться на нього як на математичний об'єкт. Що ви помічаєте?

У трикутнику приховано безліч візерунків, достатньо, щоб заповнити книгу розумних розмірів. Ось лише деякі з найбільш очевидних з них:

1. Записи на кордоні трикутника - це все 1.
2. Будь-який запис, який не знаходиться на кордоні, є сумою двох записів над ним.
3. Трикутник симетричний. У будь-якому рядку записи з лівого боку дзеркальні з правого боку.
4. Сума всіх записів у заданому рядку дорівнює 2. (Ви повинні перевірити це!)

Ми хотіли б висловити ці спостереження більш точно, а потім довести, що вони правильні. Тепер кожен запис у трикутнику Паскаля насправді є біноміальним коефіцієнтом. 1 на самій вершині трикутника є\({0 \choose 0}\). Наступний ряд (який ми будемо називати рядком 1, хоча він і не самий верхній ряд) складається з\({1 \choose 0}\) і\({1 \choose 1}\). Ряд 4 (ряд 1, 4, 6, 4, 1) складається з біноміальних коефіцієнтів

\ begin {рівняння*} {4\ вибрати 0} ~~ {4\ вибрати 1} ~~ {4\ вибрати 2} ~~ {4\ вибрати 3} ~~ {4\ вибрати 4}. \ end {рівняння*}

З огляду на цей опис елементів у трикутнику Паскаля, ми можемо переписати наведені вище спостереження наступним чином:

1. \({n \choose 0} = 1\)і\({n \choose n} = 1\).
2. \({n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\).
3. \({n \choose k} = {n \choose n-k}\).
4. \({n\choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose n} = 2^n\).

Кожен з них є прикладом біноміальної ідентичності: тотожності (тобто рівняння), що включає біноміальні коефіцієнти.

Наша мета - встановити ці ідентичності. Ми хочемо довести, що вони дотримуються всіх цінностей\(n\) і\(k\). Ці докази можна зробити різними способами. Одним з варіантів було б дати алгебраїчні докази, використовуючи формулу для\({n \choose k}\text{:}\)

\ begin {рівняння*} {n\ вибрати k} =\ frac {n!} {(н-к)! \, k!}. \ end {рівняння*}

Ось як ви можете зробити це для другої ідентичності вище.

Приклад\(\PageIndex{1}\)

Дайте алгебраїчний доказ для біноміальної ідентичності

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

Рішення

Доказ

За визначенням\({n \choose k}\), we have

\ begin {рівняння*} {n-1\ вибрати k-1} =\ frac {(n-1)!} {(н-1- (к-1))! (к-1)!} =\ гідророзриву {(n-1)!} {(н-к)! (к-1)!} \ end {рівняння*}

і

\ begin {рівняння*} {n-1\ вибрати k} =\ frac {(n-1)!} {(н-1-к)! k!}. \ end {рівняння*}

Таким чином, починаючи з правого боку рівняння:

\ begin {align*} {n-1\ вибрати k-1} + {n-1\ вибрати k}\ amp =\ frac {(n-1)!} {(н-к)! (к-1)!} +\ гідророзриву {(n-1)!} {(н-1-к)! \, k!} \\\ амп =\ гідророзриву {(n-1)! k} {(н-к)! \, k!} +\ гідророзриву {(n-1)! (н-к)} {(н-к)! \, k!} \\\ амп =\ гідророзриву {(n-1)! (к+н-к)} {(н-к)! \, k!} \\\ амп =\ гідророзриву {n!} {(н-к)! \, k!} \\\ amp = {n\ вибрати k}. \ end {вирівнювати*}

Другий рядок (де знайдений спільний знаменник) працює тому, що\(k(k-1)! = k!\) and \((n-k)(n-k-1)! = (n-k)!\).

\(\square\)

Це, безумовно, є вагомим доказом, але також є абсолютно марним. Навіть якщо ви прекрасно розумієте доказ, це не говорить вам, чому особистість правдива. Кращим підходом було б пояснити, що\({n \choose k}\) означає, а потім сказати, чому це також\({n-1 \choose k-1} + {n-1 \choose k}\) означає. Давайте подивимося, як це працює для чотирьох ідентичностей, які ми спостерігали вище.

Приклад\(\PageIndex{2}\)

Поясніть, чому\({n \choose 0} = 1\) і\({n \choose n} = 1\).

Рішення

Про що говорять нам ці біноміальні коефіцієнти? Ну,\({n \choose 0}\) gives the number of ways to select 0 objects from a collection of \(n\) objects. There is only one way to do this, namely to not select any of the objects. Thus \({n \choose 0} = 1\). Similarly, \({n \choose n}\) gives the number of ways to select \(n\) objects from a collection of \(n\) objects. There is only one way to do this: select all \(n\) objects. Thus \({n \choose n} = 1\).

Крім того, ми знаємо, що\({n \choose 0}\) is the number of \(n\)-bit strings with weight 0. There is only one such string, the string of all 0's. So \({n \choose 0} = 1\). Similarly \({n \choose n}\) is the number of \(n\)-bit strings with weight \(n\). There is only one string with this property, the string of all 1's.

Інший спосіб:\({n \choose 0}\) gives the number of subsets of a set of size \(n\) containing 0 elements. There is only one such subset, the empty set. \({n \choose n}\) gives the number of subsets containing \(n\) elements. The only such subset is the original set (of all elements).

Приклад\(\PageIndex{3}\)

Поясніть чому\({n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\).

Рішення

Найпростіший спосіб побачити це - розглянути бітові рядки. \({n \choose k}\) is the number of bit strings of length \(n\) containing \(k\) 1's. Of all of these strings, some start with a 1 and the rest start with a 0. First consider all the bit strings which start with a 1. After the 1, there must be \(n-1\) more bits (to get the total length up to \(n\)) and exactly \(k-1\) of them must be 1's (as we already have one, and we need \(k\) total). How many strings are there like that? There are exactly \({n-1 \choose k-1}\) such bit strings, so of all the length \(n\) bit strings containing \(k\) 1's, \({n-1 \choose k-1}\) of them start with a 1. Similarly, there are \({n-1\choose k}\) which start with a 0 (we still need \(n-1\) bits and now \(k\) of them must be 1's). Since there are \({n-1 \choose k}\) bit strings containing \(n-1\) bits with \(k\) 1's, that is the number of length \(n\) bit strings with \(k\) 1's which start with a 0. Therefore \({n \choose k} = {n-1\choose k-1} + {n-1 \choose k}\).

Ще один спосіб: розглянемо питання, скільки способів можна вибрати\(k\) pizza toppings from a menu containing \(n\) choices? One way to do this is just \({n \choose k}\). Another way to answer the same question is to first decide whether or not you want anchovies. If you do want anchovies, you still need to pick \(k-1\) toppings, now from just \(n-1\) choices. That can be done in \({n-1 \choose k-1}\) ways. If you do not want anchovies, then you still need to select \(k\) toppings from \(n-1\) choices (the anchovies are out). You can do that in \({n-1 \choose k}\) ways. Since the choices with anchovies are disjoint from the choices without anchovies, the total choices are \({n-1 \choose k-1}+{n-1 \choose k}\). But wait. We answered the same question in two different ways, so the two answers must be the same. Thus \({n \choose k} = {n-1\choose k-1} + {n-1 \choose k}\).

Ви також можете пояснити (довести) цю особистість, підрахувавши підмножини або навіть ґратчасті шляхи.

Приклад\(\PageIndex{4}\)

Доведіть біноміальну ідентичність\[{n \choose k} = {n \choose n-k}. \nonumber\]

Рішення

Чому це правда? \({n \choose k}\) counts the number of ways to select \(k\) things from \(n\) choices. On the other hand, \({n \choose n-k}\) counts the number of ways to select \(n-k\) things from \(n\) choices. Are these really the same? Well, what if instead of selecting the \(n-k\) things you choose to exclude them. How many ways are there to choose \(n-k\) things to exclude from \(n\) choices. Clearly this is \({n \choose n-k}\) as well (it doesn't matter whether you include or exclude the things once you have chosen them). And if you exclude \(n-k\) things, then you are including the other \(k\) things. So the set of outcomes should be the same.

Давайте спробуємо приклад підрахунку піци, як ми робили вище. Скільки існує способів підібрати\(k\) toppings from a list of \(n\) choices? On the one hand, the answer is simply \({n \choose k}\). Alternatively, you could make a list of all the toppings you don't want. To end up with a pizza containing exactly \(k\) toppings, you need to pick \(n-k\) toppings to not put on the pizza. You have \({n \choose n-k}\) choices for the toppings you don't want. Both of these ways give you a pizza with \(k\) toppings, in fact all the ways to get a pizza with \(k\) toppings. Thus these two answers must be the same: \({n \choose k} = {n \choose n-k}\).

Ви також можете довести (пояснити) цю особистість за допомогою бітових рядків, підмножин або шляхів решітки. Аргумент bit string є приємним:\({n \choose k}\) counts the number of bit strings of length \(n\) with \(k\) 1's. This is also the number of bit string of length \(n\) with \(k\) 0's (just replace each 1 with a 0 and each 0 with a 1). But if a string of length \(n\) has \(k\) 0's, it must have \(n-k\) 1's. And there are exactly \({n\choose n-k}\) strings of length \(n\) with \(n-k\) 1's.

Приклад\(\PageIndex{5}\)

Доведіть біноміальну ідентичність\[{n\choose 0} + {n \choose 1} + {n\choose 2} + \cdots + {n \choose n} = 2^n. \nonumber\]

Рішення

Доказ

Давайте знову зробимо «доказ піци». Нам потрібно знайти питання про начинку для піци, яка має\(2^n\) as the answer. How about this: If a pizza joint offers \(n\) toppings, how many pizzas can you build using any number of toppings from no toppings to all toppings, using each topping at most once?

З одного боку, відповідь\(2^n\). For each topping you can say “yes” or “no,” so you have two choices for each topping.

З іншого боку, розділіть можливі піци на неспільні групи: піци без начинки, піци з однією начинкою, піци з двома начинками і т.д. якщо ми не хочемо начинки, є тільки одна піца така (порожня піца, якщо хочете), але було б краще думати про це число як \({n \choose 0}\) since we choose 0 of the \(n\) toppings. How many pizzas have 1 topping? We need to choose 1 of the \(n\) toppings, so \({n \choose 1}\). We have:

Піци з 0 начинками:\({n \choose 0}\) Піци з 1 начинкою:\({n \choose 1}\) Піци з 2 начинками:\({n \choose 2}\)

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

Знову ж таки, ми могли б довести ідентичність, використовуючи підмножини, бітові рядки або шляхи решітки (хоча аргумент шляху решітки трохи складний).

• \(\vdots\)
• Піца з\(n\) toppings: \({n \choose n}\).

\(\square\)

Сподіваємось, це дає деяке уявлення про те, як можуть йти пояснювальні докази біноміальних ідентичностей. Варто зазначити, що більш традиційні докази теж можуть бути красивими. ³ Більшість кожної біноміальної ідентичності можна довести за допомогою математичної індукції n, використовуючи рекурсивне визначення для\(n \choose k\). Ми обговоримо indu action в розділі 2.5. Наприклад, розглянемо наступне досить гладке підтвердження останньої особи.

Розгорнути біноміал\((x+y)^n\text{:}\)

\ begin {рівняння*} (x + y) ^n = {n\ вибрати 0} x^n + {n\ вибрати 1} x^ {n-1} y + {n\ вибрати 2} x^ {n-2} y^2 +\ cdots + {n\ вибрати n-1} x\ cdot y^n + {n\ вибрати n} y^n.\ кінець {рівняння*}

Нехай\(x = 1\) і\(y = 1\). Отримуємо:

\ begin {рівняння*} (1 + 1) ^n = {n\ вибрати 0} 1^n + {n\ вибрати 1} 1^ {n-1} 1 + {n\ вибрати 2} 1^ {n-2} 1^2 +\ cdots + {n\ вибрати n-1} 1\ cdot 1^n + {n\ вибрати n} 1^n.\ кінець {рівняння*}

Звичайно, це спрощує:

\ begin {рівняння*} (2) ^n = {n\ вибрати 0} + {n\ вибрати 1} + {n\ вибрати 2} +\ cdots + {n\ choose n-1} + {n\ choose n}. \ end {рівняння*}

Щось цікаве спробувати: Нехай\(x = 1\) і\(y = 2\). Акуратний так?

Більше доказів

Пояснювальні докази, наведені в наведених вище прикладах, зазвичай називаються комбінаторними доказами. Загалом, щоб дати комбінаторний доказ для біноміальної ідентичності, скажімо,\(A = B\) ви робите наступне:

1. Знайти проблему підрахунку ви зможете відповісти двома способами.
2. Поясніть, чому одна відповідь на проблему підрахунку є\(A\).
3. Поясніть, чому інша відповідь на проблему підрахунку\(B\).

Оскільки обидва\(A\) і\(B\) є відповідями на одне і те ж питання, ми повинні мати\(A = B\).

Хитра річ придумує питання. Це не завжди очевидно, але стає простіше, чим більше проблем підрахунку ви вирішуєте. Ви почнете розпізнавати типи відповідей як відповіді на типи питань. Найчастіше те, що станеться, ви будете вирішувати проблему підрахунку і випадково придумати два різні способи пошуку відповіді. Тепер у вас є біноміальне посвідчення, і доказ є прямо там. Доказом є проблема, яку ви щойно вирішили разом із двома вашими рішеннями.

Для прикладу розглянемо це підрахункове питання:

Скільки 10-літерних слів використовують рівно чотири A, три B, два C і один D?

Спробуємо вирішити цю проблему. У нас є 10 місць для листів, щоб піти. Чотири з них повинні бути A. Ми можемо вибрати чотири A-плями\({10 \choose 4}\) способами. Тепер, де ми можемо поставити B? Ну залишилося тільки 6 плям, нам потрібно їх підібрати\(3\). Це можна зробити\({6 \choose 3}\) способами. Два C потрібно йти в двох з 3 залишилися плями, так що у нас є\({3 \choose 2}\) способи зробити це. Це залишає тільки одне місце D, але ми могли б написати, що 1 вибір як\({1 \choose 1}\). Таким чином, відповідь:

\ begin {рівняння*} {10\ вибрати 4} {6\ вибрати 3} {3\ вибрати 2} {1\ вибрати 1}. \ end {рівняння*}

Але навіщо зупинятися на досягнутому? Ми можемо знайти відповідь і іншим способом. Для початку вирішимо, куди поставити той D: у нас 10 плям, нам потрібно вибрати 1 з них, так що це можна зробити\({10 \choose 1}\) способами. Далі виберіть один із\({9 \choose 2}\) способів розміщення двох С. Тепер у нас залишилися\(7\) плями, і три з них потрібно заповнити B. Для цього є\({7 \choose 3}\) способи. Нарешті, А можуть бути розміщені\({4 \choose 4}\) (тобто лише одним) способами. Так що ще одна відповідь на питання

\ begin {рівняння*} {10\ вибрати 1} {9\ вибрати 2} {7\ вибрати 3} {4\ вибрати 4}. \ end {рівняння*}

Цікаво. Це дає нам біноміальну ідентичність:

\ begin {рівняння*} {10\ вибрати 4} {6\ вибрати 3} {3\ вибрати 2} {1\ вибрати 1} = {10\ вибрати 1} {9\ вибрати 2} {7\ вибрати 3} {4\ вибрати 4}. \ end {рівняння*}

Ось кілька інших біноміальних тотожностей з комбінаторними доказами.

Приклад\(\PageIndex{6}\)

Доведіть особу

\ begin {рівняння*} 1 n + 2 (n-1) + 3 (n-2) +\ cdots + (n-1) 2 + n 1 = {n+2\ вибрати 3}. \ end {рівняння*}

Рішення

Щоб дати комбінаторний доказ, нам потрібно придумати питання, на яке ми можемо відповісти двома способами: один із способів повинен дати ліву сторону ідентичності, інший спосіб повинен бути правою стороною ідентичності. Наша підказка до того, яке питання поставити, приходить з правого боку:\({n+2 \choose 3}\) counts the number of ways to select 3 things from a group of \(n+2\) things. Let's name those things \(1, 2, 3, \ldots, n+2\). In other words, we want to find 3-element subsets of those numbers (since order should not matter, subsets are exactly the right thing to think about). We will have to be a bit clever to explain why the left-hand-side also gives the number of these subsets. Here's the proof.

Доказ

Розглянемо питання «Скільки 3-елементних підмножин є у множини?\(\{1,2,3,\ldots, n+2\}\text{?}\)” We answer this in two ways:

Відповідь 1: Ми повинні вибрати 3 елементи з колекції\(n+2\) elements. This can be done in \({n+2 \choose 3}\) ways.

Відповідь 2: Розбийте цю проблему на випадки, якими є середнє число у підмножині. Скажімо, кожна підмножина є\(\{a,b,c\}\) written in increasing order. We count the number of subsets for each distinct value of \(b\). The smallest possible value of \(b\) is \(2\), and the largest is \(n+1\).

Коли\(b = 2\), there are \(1 \cdot n\) subsets: 1 choice for \(a\) and \(n\) choices (3 through \(n+2\)) for \(c\).

Коли\(b = 3\), there are \(2 \cdot (n-1)\) subsets: 2 choices for \(a\) and \(n-1\) choices for \(c\).

Коли\(b = 4\), there are \(3 \cdot (n-2)\) subsets: 3 choices for \(a\) and \(n-2\) choices for \(c\).

І так далі. Коли\(b = n+1\), there are \(n\) choices for \(a\) and only 1 choice for \(c\), so \(n \cdot 1\) subsets.

Тому загальна кількість підмножин дорівнює

\ begin {рівняння*} 1 n + 2 (n-1) + 3 (n-2) +\ cdots + (n-1) 2 + n 1. \ end {рівняння*}

Оскільки Відповідь 1 і Відповідь 2 - це відповіді на одне і те ж питання, вони повинні бути рівними. Тому

\ begin {рівняння*} 1 n + 2 (n-1) + 3 (n-2) +\ cdots + (n-1) 2 + n 1 = {n+2\ вибрати 3}. \ end {рівняння*}

\(\square\)

Приклад\(\PageIndex{7}\)

Доведіть біноміальну ідентичність

\ begin {рівняння*} {n\ вибрати 0} ^2 + {n\ вибрати 1} ^2 + {n\ вибрати 2} ^2 +\ cdots + {n\ choose n} ^2 = {2n\ вибрати n}. \ end {рівняння*}

Рішення 1

Наведемо два різних докази цього факту. Перший буде дуже схожий на попередній приклад (підрахунок підмножин). Другим доказом є трохи гладкіше, використовуючи решітчасті доріжки.

Доказ

Розглянемо питання: «Скільки піц можна приготувати, використовуючи\(n\) toppings when there are \(2n\) toppings to choose from?”

Відповідь 1: Є\(2n\) toppings, from which you must choose \(n\). This can be done in \({2n \choose n}\) ways.

Відповідь 2: Розділіть начинку на дві групи\(n\) toppings (perhaps \(n\) meats and \(n\) veggies). Any choice of \(n\) toppings must include some number from the first group and some number from the second group. Consider each possible number of meat toppings separately:

0 м'яса:\({n \choose 0}{n \choose n}\), since you need to choose 0 of the \(n\) meats and \(n\) of the \(n\) veggies.

1 м'ясо:\({n \choose 1}{n \choose n-1}\), since you need 1 of \(n\) meats so \(n-1\) of \(n\) veggies.

2 види м'яса:\({n \choose 2}{n \choose n-2}\). Choose 2 meats and the remaining \(n-2\) toppings from the \(n\) veggies.

І так далі. Останній випадок - це\(n\) meats, which can be done in \({n \choose n}{n \choose 0}\) ways.

Таким чином, загальна кількість піци можлива

\ begin {рівняння*} {n\ вибрати 0} {n\ вибрати n} + {n\ вибрати 1} {n\ вибрати n-1} + {n\ вибрати 2} {n\ вибрати n-2} +\ cdots + {n\ choose n} {n\ choose 0}. \ end {рівняння*}

Це не зовсім ліва сторона... поки. Зауважте, що\({n \choose n} = {n \choose 0}\) and \({n \choose n-1} = {n \choose 1}\) and so on, by the identity in Example 1.4.4. Thus we do indeed get

\ begin {рівняння*} {n\ вибрати 0} ^2 + {n\ вибрати 1} ^2 + {n\ вибрати 2} ^2 +\ cdots + {n\ choose n} ^2. \ end {рівняння*}

Оскільки ці дві відповіді є відповідями на одне і те ж питання, вони повинні бути рівними, і таким чином

\ begin {рівняння*} {n\ вибрати 0} ^2 + {n\ вибрати 1} ^2 + {n\ вибрати 2} ^2 +\ cdots + {n\ choose n} ^2 = {2n\ вибрати n}. \ end {рівняння*}

\(\square\)

Для альтернативного доказу використовуємо решітчасті доріжки. Це розумно враховувати, оскільки права сторона ідентичності нагадує нам про кількість шляхів від\((0,0)\) to \((n,n)\).

Доказ

Розглянемо питання: скільки там решітчастих доріжок від\((0,0)\) to \((n,n)\text{?}\)

Відповідь 1: Ми повинні подорожувати\(2n\) steps, and \(n\) of them must be in the up direction. Thus there are \({2n \choose n}\) paths.

Відповідь 2: Зверніть увагу, що будь-який шлях від\((0,0)\) to \((n,n)\) must cross the line \(x + y = n\). That is, any path must pass through exactly one of the points: \((0,n)\), \((1,n-1)\), \((2,n-2)\), …, \((n, 0)\). For example, this is what happens in the case \(n = 4\text{:}\)

Скільки шляхів проходить\((0,n)\text{?}\) To get to that point, you must travel \(n\) units, and \(0\) of them are to the right, so there are \({n \choose 0}\) ways to get to \((0,n)\). From \((0,n)\) to \((n,n)\) takes \(n\) steps, and \(0\) of them are up. So there are \({n \choose 0}\) ways to get from \((0,n)\) to \((n,n)\). Therefore there are \({n \choose 0}{n \choose 0}\) paths from \((0,0)\) to \((n,n)\) through the point \((0,n)\).

What about through \((1,n-1)\). There are \({n \choose 1}\) paths to get there (\(n\) steps, 1 to the right) and \({n \choose 1}\) paths to complete the journey to \((n,n)\) (\(n\) steps, \(1\) up). So there are \({n \choose 1}{n \choose 1}\) paths from \((0,0)\) to \((n,n)\) through \((1,n-1)\).

In general, to get to \((n,n)\) through the point \((k,n-k)\) we have \({n \choose k}\) paths to the midpoint and then \({n \choose k}\) paths from the midpoint to \((n,n)\). So there are \({n \choose k}{n \choose k}\) paths from \((0,0)\) to \((n,n)\) through \((k, n-k)\).

All together then the total paths from \((0,0)\) to \((n,n)\) passing through exactly one of these midpoints is

\begin{equation*} {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2. \end{equation*}

Since these two answers are answers to the same question, they must be equal, and thus

\begin{equation*} {n \choose 0}^2 + {n \choose 1}^2 + {n \choose 2}^2 + \cdots + {n \choose n}^2 = {2n \choose n}. \end{equation*}

\(\square\)