Вопрос из вступления звучит так: сколькими способами можно выбрать три предмета из шести? Такие вопросы задают по-разному. Говорят о числе способов выбрать $k$ предметов из $n$, о числе сочетаний из $n$ по $k$, о количестве вариантов. Во всех случаях речь об одном и том же числе. Посчитаем его, когда предметов немного, честно выписывая все варианты.

Возьмём четыре предмета и обозначим их числами 1, 2, 3, 4. Два предмета из них можно выбрать шестью способами: $$\{1,2\},\ \{1,3\},\ \{1,4\},\ \{2,3\},\ \{2,4\},\ \{3,4\}.$$ Порядок внутри набора не важен: $\{1,2\}$ и $\{2,1\}$ — один и тот же выбор. Так же выпишем и другие случаи.

Другие случаи можно посмотреть в виджете: задайте, сколько всего предметов и сколько из них нужно выбрать, и он выпишет все варианты.

Теперь попробуем так же выписать тройки из шести вкусов. Занумеруем вкусы по порядку, от сладкого (1) до вяжущего (6), и начнём: $\{1,2,3\}$, $\{1,2,4\}$, $\{1,3,5\}$, $\{2,4,6\}$… Сразу видны три трудности. Записей много. Непонятно, в каком порядке их перебирать. И когда список кончится, трудно проверить, что ни одна тройка не пропущена.

Все три трудности снимает простой код. Пройдём по номерам от 1 до 6 и напишем 1, если вкус выбран, и 0, если нет. Получится последовательность из шести нулей и единиц; для краткости будем называть такие последовательности словами. Тройка «сладкий, солёный, горький», то есть $\{1,3,5\}$, станет словом 101010, тройка «кислый, солёный, острый», то есть $\{2,3,4\}$, — словом 011100. Каждой тройке отвечает слово длины 6 ровно с тремя единицами.

Слово из нулей и единиц — это ещё и число, записанное в двоичной системе. В привычной записи места цифр справа налево означают единицы, десятки, сотни. В двоичной записи цифр только две, 0 и 1, а места справа налево означают 1, 2, 4, 8, 16, 32: каждое следующее вдвое больше. Слово 011100 — это число $16+8+4=28$.

Выпишем все слова длины 3 по возрастанию: 000, 001, 010, 011, 100, 101, 110, 111. Каждое слово оказалось двоичной записью своего номера в списке, если считать с нуля: 000 записывает 0, 101 записывает 5, а 111 записывает 7.

В виджете можно нажимать и на предметы, и на цифры слова: меняется одно — меняется и другое. Под каждой цифрой подписано, что означает её место в двоичной записи. Кнопка «+1» прибавляет к числу единицу, и, нажимая её, можно пройти по очереди все наборы.

Нули впереди числа не меняют, но в слове они нужны: первый ноль в 011100 означает, что первый вкус не выбран. Поэтому длина слова всегда равна числу предметов. А главное, тройки теперь можно перебирать по порядку чисел, например по убыванию: 111000, 110100, 110010, 110001, 101100 и так далее. Ничего не пропустишь и ничего не повторишь. В первом виджете при шести предметах и трёх выбранных видны все такие слова.

Вот тот же код для выбора двух предметов из четырёх:

Эта таблица работает как словарь в обе стороны: каждому набору отвечает ровно одно слово, и каждое слово с двумя единицами — перевод ровно одного набора. Набор восстанавливается по слову: это номера мест, где стоят единицы.

Соответствие, которое работает в обе стороны, называют взаимно однозначным (по-учёному — биекцией). Если между двумя совокупностями есть взаимно однозначное соответствие, предметов в них поровну. Так учитель, не пересчитывая детей, видит, что их столько же, сколько стульев: каждый сидит на своём стуле, ни один стул не занят дважды, и свободных стульев нет. Поэтому тройки вкусов можно не выписывать, а считать слова: их столько же. Этим приёмом мы будем пользоваться постоянно.

Теперь можно сказать то же самое точно. Набор, выбранный из имеющихся предметов, математики называют подмножеством, а сами предметы — элементами.

Это и есть число способов выбрать $k$ предметов из $n$: по таблице $\binom32=3$, $\binom42=6$, $\binom43=4$. Вместо чисел можно брать любые предметы — людей, вершины, вкусы: важно только, сколько их. В вопросе о вкусах нужно найти $\binom63$. В русской школе пишут $C_n^k$, а запись в скобках ввёл в 1826 году австрийский математик Андреас фон Эттингсгаузен.

В определении $k$ может быть и больше $n$. Чему равно $\binom3{10}$? У множества из трёх элементов нет подмножеств из десяти элементов, поэтому $\binom3{10}=0$. Так же при любом $k\gt n$ получается $\binom nk=0$. Отдельно договариваться об этом не нужно: это следует из определения.

В виджетах ниже слово изображено рядом клеток: единица — закрашенная клетка, ноль — пустая. Этот язык старше, чем кажется. Больше двух тысяч лет назад индийский учёный Пингала разбирал стихотворные размеры санскрита. Каждый размер задаётся последовательностью лёгких и тяжёлых слогов, то есть снова словом из двух знаков: «тяжёлый, лёгкий, лёгкий, тяжёлый» записывается как 1001. Пингала считал, сколько размеров данной длины содержат данное число тяжёлых слогов.

По таблице из трёх предметов получаются три пары, из четырёх — шесть. Найдём ответ для любого $n$. Разберём три способа; в каждом сначала посчитаем пары из пяти предметов (должно получиться 10), а потом то же самое в общем виде. Нам понадобится правило произведения: если первый выбор можно сделать $a$ способами, а второй при любом первом — $b$ способами, то оба выбора вместе можно сделать $a\cdot b$ способами.

Способ 1 — по наименьшему элементу. Пара $\{i,j\}$ с $i\lt j$ задаётся меньшим числом $i$ и бо́льшим $j$. Если меньшее число равно $i$, бо́льшее можно выбрать $n-i$ способами: это любое из чисел $i+1,\dots,n$. Для пяти предметов при $i=1$ получаются четыре пары, при $i=2$ три, при $i=3$ две, при $i=4$ одна, всего $4+3+2+1=10$. В общем случае $$\binom n2=(n-1)+(n-2)+\dots+2+1.$$ Чтобы сосчитать такую сумму, запишем её в обратном порядке под исходной и сложим столбиками. Для пяти предметов: $$\begin{array}{ccccccc}4&+&3&+&2&+&1\\1&+&2&+&3&+&4\end{array}$$ Каждый столбик даёт 5, столбиков 4, поэтому удвоенная сумма равна $5\cdot4=20$, то есть $2\cdot10=20$. В общем случае каждый столбик даёт $n$, столбиков $n-1$, поэтому $2\binom n2=n(n-1)$.

Способ 2 — клетки таблицы. Нарисуем таблицу $n\times n$. Клетка в строке $i$ и столбце $j$ — это упорядоченная пара $(i,j)$: пары $(2,5)$ и $(5,2)$ разные, хотя множество $\{2,5\}$ одно. Клеток вне диагонали, где $i\ne j$, по правилу произведения $n(n-1)$: строку можно выбрать $n$ способами, а столбец — $n-1$ способом. С другой стороны, каждое множество $\{i,j\}$ занимает ровно две такие клетки, $(i,j)$ и $(j,i)$, одну выше диагонали и одну ниже. Значит, $n(n-1)=2\binom n2$. Для пяти предметов получается $5\cdot4=20$ клеток и 10 пар.

Клетки выше диагонали образуют лесенку; в виджете она отражается под диагональ, а после сдвига на клетку вверх две лесенки складываются в прямоугольник из $n-1$ ряда по $n$ клеток.

Способ 3 — стрелки и отрезки. Отметим $n$ точек и соединим каждые две отрезком; отрезков столько же, сколько пар. Проведём стрелки от каждой точки к каждой другой и посчитаем их. Начало стрелки можно выбрать $n$ способами, конец — $n-1$ способом, всего $n(n-1)$ стрелок. С другой стороны, каждый отрезок несёт ровно две стрелки, по одной в каждую сторону. Значит, снова $n(n-1)=2\binom n2$. У пяти точек $5\cdot4=20$ стрелок и 10 отрезков. Если точки — вершины пятиугольника, это пять сторон и пять диагоналей. Так же решается задача о рукопожатиях: если каждый из $n$ человек пожал руку каждому, рукопожатий столько же, сколько пар, $\binom n2$.

Все три способа привели к одному ответу.

Во всех трёх способах работает одна мысль: двойной подсчёт. Одно и то же количество (две суммы столбиками, клетки, стрелки) считаем двумя способами. Один раз получаем произведение, которое легко найти, а другой раз — неизвестное число пар, умноженное на 2. Приравниваем два ответа: $n(n-1)=2\binom n2$. Деления здесь нет: мы только умножаем, а каждое умножение опирается на правило произведения. К этой мысли мы ещё будем возвращаться.

Со сложением задом наперёд связан анекдот: учитель задал классу сложить числа от 1 до 100, а маленький Гаусс сразу написал ответ, 5050. Это именно анекдот. В первой биографии Гаусса, вышедшей в 1856 году, история о школьной задаче есть, но чисел от 1 до 100 в ней нет; по данным Брайана Хейса, собравшего больше сотни пересказов, эти числа появляются только в книге 1938 года.

Ответ: одним. Ничего не выбрать — тоже вариант выбора; в вопросе из вступления его специально исключили словами «хотя бы один вкус». На языке слов это видно сразу: слово 0000 можно написать, как и любое другое, и такое слово одно.

На языке множеств ничего не выбрать — значит взять пустое подмножество, в котором нет ни одного элемента. Множества считаются равными, если у них одни и те же элементы, поэтому пустое подмножество одно: у двух пустых множеств элементы одни и те же — никаких. Итак, $\binom40=1$.

Соберём теперь все случаи для четырёх предметов вместе. Ниже выписаны все слова длины 4 — их 16 — и разложены по числу единиц.

В столбцах соответственно 1, 4, 6, 4 и 1 слово: $$\begin{gathered}\binom40=1,\quad\binom41=4,\quad\binom42=6,\\\binom43=4,\quad\binom44=1.\end{gathered}$$ Числа ряда — высоты столбцов: мы выписали все слова длины 4 и разложили их по числу единиц, каждое слово попало ровно в один столбец. Крайние столбцы устроены просто при любом числе предметов.

Ряд 1, 4, 6, 4, 1 одинаково читается с обоих концов. Так же и для шести предметов $\binom62=\binom64=15$: выбрать два предмета из шести — то же самое, что выбрать четыре, которые останутся. На языке слов это ещё нагляднее. Поменяем в слове нули на единицы и наоборот: 1000 станет 0111, а 1100 станет 0011.

В частности, при $n\ge1$ выполняется $\binom n{n-1}=\binom n1=n$: слово с одним нулём задаётся местом этого нуля. В трактате Чараки сочетания из пяти вкусов описаны именно так: их шесть, потому что из смеси каждый раз исключается ровно один вкус. Набор из пяти вкусов задаётся тем единственным, которого в нём нет.

Строки нумеруются с нуля, и ряд для четырёх предметов оказывается строкой номер 4. Заполним строки с номерами от 0 до 6 тем, что уже доказано: края по утверждению 6, числа $\binom n2$ по утверждению 4, остальное отражением по утверждению 7. Наверху стоит $\binom00=1$: из пустого множества можно выбрать ровно одно подмножество — его самого. $$\begin{array}{c}1\\1\quad1\\1\quad2\quad1\\1\quad3\quad3\quad1\\1\quad4\quad6\quad4\quad1\\1\quad5\quad10\quad10\quad5\quad1\\1\quad6\quad15\quad\boxed{\,?\,}\quad15\quad6\quad1\end{array}$$

Заполнились все клетки, кроме одной. Утверждения 4, 6 и 7 дают $\binom nk$, когда $k$ или $n-k$ не больше двух, а в строках с номерами от 0 до 6 только у одной клетки и $k$, и $n-k$ не меньше трёх — у $\binom63$. Это и есть вопрос о трёх вкусах из шести. Чтобы ответить на него, нужен новый инструмент.

Присмотримся к треугольнику: каждое число в нём, кроме крайних, равно сумме двух чисел над ним, например $6=3+3$ и $10=4+6$. Это не совпадение.

Разберём сначала один случай: почему $\binom52=\binom41+\binom42$? Выпишем все слова длины 5 с двумя единицами и разложим их на две кучки по первой цифре. С 1 начинаются слова 11000, 10100, 10010, 10001. Если стереть первую единицу, останутся все слова длины 4 с одной единицей, их $\binom41=4$. Остальные шесть слов начинаются с 0: 01100, 01010, 01001, 00110, 00101, 00011. Если стереть первый ноль, останутся все слова длины 4 с двумя единицами, их $\binom42=6$. Вместе $4+6=10=\binom52$.

Так же устроен край строки. Почему $\binom44=\binom33+\binom34$? Слово длины 4 с четырьмя единицами одно, 1111, и оно начинается с 1; без первой цифры остаётся 111, то есть $\binom33=1$. Слов, которые начинаются с 0, нет вовсе: тогда на остальных трёх местах пришлось бы поставить четыре единицы. И правая часть с этим согласна: $\binom34=0$.

Единица $\binom00=1$ наверху треугольника с правилом согласована: строка 1 получается из строки 0, $\binom11=\binom00+\binom01=1+0$.

Теперь можно заполнить последнюю клетку: $$\binom63=\binom52+\binom53=10+10=20.$$ Из шести вкусов можно составить 20 смесей ровно по три.

То же правило годится и для людей. Выберем из восьми человек троих дежурных и отметим одного из восьми, скажем Веру. Групп с Верой $\binom72$ — к ней нужно добавить двоих из оставшихся семи; групп без Веры $\binom73$. Строка номер 7 складывается из строки номер 6: $\binom72=6+15=21$, $\binom73=15+20=35$. Итого $\binom83=21+35=56$.

Правило Паскаля заполняет треугольник строку за строкой, но чтобы дойти до $\binom{16}4$ Варахамихиры, понадобилось бы шестнадцать строк. Нужна формула, которая даёт число сразу.

Формулу можно было бы искать, сравнивая соседние числа одной строки. Но у биномиальных коэффициентов закономерность там не видна: в строке номер 6 стоят 1, 6, 15, 20, и от 6 к 15 целым множителем не перейти. Чтобы понять, как сравнивать соседей, отвлечёмся на похожую задачу, в которой важен порядок.

Выберем из трёх человек, Веры, Пети и Оли, капитана и заместителя. Запишем выбор парой: сначала капитан, потом заместитель. Получится шесть вариантов: ВП, ВО, ПВ, ПО, ОВ, ОП. Пар без ролей было бы три, а здесь каждая пара встречается дважды: капитан Вера и заместитель Петя — не тот же выбор, что капитан Петя и заместитель Вера.

Обозначение взято из книги Грэхема, Кнута и Паташника «Конкретная математика», а само число называют ещё убывающим факториалом. Мы только что нашли $3^{\underline 2}=6$. Ничего не выбрать можно одним способом, поэтому $n^{\underline 0}=1$. Если $k\gt n$, разных предметов не хватит, и $n^{\underline k}=0$.

Есть ли у размещений своё правило Паскаля? Возьмём $4^{\underline 2}$ — число способов выбрать капитана и заместителя из четырёх человек: к Вере, Пете и Оле добавим Гошу. Отметим Веру. Если Вера не выбрана, капитана и заместителя выбирают из трёх остальных: $3^{\underline 2}=6$ способов. Если выбрана, она капитан или заместитель — 2 способа, а на оставшееся место годится любой из трёх остальных: $2\cdot3^{\underline 1}=6$ способов. Всего $4^{\underline 2}=6+6=12$.

Заполним этим правилом первые строки треугольника: в строке $n$ стоят числа $n^{\underline 0},n^{\underline 1},\dots,n^{\underline n}$. $$\begin{array}{c}1\\1\quad1\\1\quad2\quad2\\1\quad3\quad6\quad6\\1\quad4\quad12\quad24\quad24\\1\quad5\quad20\quad60\quad120\quad120\end{array}$$

Правило понятное, но считать по нему тяжело. Число складывается из двух чисел над ним, причём левое из них ещё умножается на $k$, номер места нового числа (места считаем с нуля). Числа растут быстро: в строке 5 уже стоит 120. А чтобы дойти до строки 8, пришлось бы заполнить все строки до неё.

Посмотрим вместо этого на соседей в одной строке. В строке 4 стоят 1, 4, 12, 24, 24: каждое следующее число получается из предыдущего умножением на 4, 3, 2 и 1.

Первое равенство связывает соседей в строке, второе — соседей по диагонали. Теперь до любого числа можно дойти от единицы на краю, не заполняя строк выше.

Пройдём по строке 8 от края по первому равенству утверждения 12: $8^{\underline 1}=1\cdot8=8$, $8^{\underline 2}=8\cdot7=56$, $8^{\underline 3}=56\cdot6=336$. Тот же ответ даёт и прямой подсчёт: капитана можно выбрать 8 способами, заместителя из оставшихся — 7, третьего — 6.

Каждый шаг вдоль строки добавляет один множитель, и после $k$ шагов получается произведение.

Последнее число строки, $n^{\underline n}$, — это число способов расставить по порядку все $n$ предметов. Для него есть своё обозначение.

По утверждению 14 $n!=n^{\underline n}$. Например, $3!=6$ и $10!=3\,628\,800$. Договорённость $0!=1$ согласуется с тем, что $n^{\underline 0}=1$: расставить ноль предметов можно одним способом. Второе равенство утверждения 12 при $k=n$ даёт $n!=n\cdot(n-1)!$, например $6!=6\cdot5!$: чтобы расставить шестерых, выберем первого, а остальных пятерых расставим за ним.

С размещениями всё обстоит наоборот, чем с биномиальными коэффициентами: правило Паскаля сложное, а соседей сравнивать просто, каждое число получается из соседа одним умножением.

Вернёмся к треугольнику Паскаля и сравним соседей тем же приёмом, что в утверждении 12: одно и то же количество будем выбирать в разном порядке.

Посчитаем тремя способами.

Сначала капитан. Капитана можно выбрать 25 способами, потом остальных 10 игроков из 24 человек — $\binom{24}{10}$ способами. Всего $25\cdot\binom{24}{10}$.

Сначала рядовые. Десять игроков без капитана можно выбрать $\binom{25}{10}$ способами, потом капитана из 15 оставшихся — 15 способами. Всего $\binom{25}{10}\cdot15$.

Сначала вся команда. Команду из 11 человек можно выбрать $\binom{25}{11}$ способами, потом капитана из её 11 игроков. Всего $\binom{25}{11}\cdot11$.

Во всех трёх случаях посчитано одно и то же, поэтому $$25\binom{24}{10}=15\binom{25}{10}=11\binom{25}{11}.$$ Самих чисел мы пока не знаем, но связь между ними уже есть. Теперь заменим 25 человек на $n$, а 11 игроков — на $k+1$: тогда рядовых будет $k$, и в равенстве встретятся соседние числа строки, $\binom nk$ и $\binom n{k+1}$.

В равенстве $(n-k)\binom nk=(k+1)\binom n{k+1}$ перенесём множитель $k+1$ в другую часть и получим связь между соседними числами строки.

Пройдём так по шестой строке от левого края. При $n=6$ множитель $\frac{n-k}{k+1}$ равен $\frac61$ при $k=0$, $\frac52$ при $k=1$ и $\frac43$ при $k=2$: $\binom61=\frac61\cdot1=6$, $\binom62=\frac52\cdot6=15$, $\binom63=\frac43\cdot15=20$. Двадцать смесей мы нашли без таблицы. На рисунке каждая стрелка несёт свой множитель. Дойти до клетки от единицы на краю можно четырьмя путями: по строке слева или справа и по одной из двух диагоналей.

Каждый шаг даёт новый множитель в числителе и новый в знаменателе: $\binom63=\frac{6\cdot5\cdot4}{1\cdot2\cdot3}$. В числителе стоит $6^{\underline 3}$, в знаменателе $3!$.

Шагать можно и по диагонали, как во втором равенстве утверждения 12. Первая и третья части равенства утверждения 17, записанные для команды из $k$ человек, дают $k\binom nk=n\binom{n-1}{k-1}$ при $1\le k\le n$. За $k$ шагов вверх по диагонали, до края $\binom{n-k}0=1$, получается та же формула; в виджете выше это путь «диагональ, слева».

Теперь можно найти число Варахамихиры: $\binom{16}4=\frac{16\cdot15\cdot14\cdot13}{1\cdot2\cdot3\cdot4}=1820$. А футбольную команду с капитаном из задачи 16 можно выбрать $11\binom{25}{11}=11\cdot4\,457\,400=49\,031\,400$ способами; проверьте по формуле, что два других ответа задачи дают то же число.

Формулу можно получить и сразу, без ходьбы по треугольнику, — тем же двойным подсчётом, что и число пар. Ходьба при этом не была лишней: она показала, как связаны соседние числа строки, и именно так рассуждал сам Паскаль.

Ответ мы знаем, это 56; получим его ещё раз. Капитана, заместителя и третьего игрока мы выбирали в задаче 13: это $8^{\underline 3}=8\cdot7\cdot6$ способов. Посчитаем их иначе: сначала выберем тройку ($\binom83$ способами), потом в ней капитана (3 способами), потом заместителя из двух оставшихся (2 способами); третий определится сам. Это одно и то же количество, поэтому $$\binom83\cdot3\cdot2=8\cdot7\cdot6,$$ то есть $6\binom83=336$ и $\binom83=56$, как и в примере с дежурными.

В общем случае размещение из $n$ по $k$ можно получить так: сначала выбрать множество из $k$ человек — $\binom nk$ способами, а потом расставить его по порядку — $k!$ способами. Каждое размещение получается ровно один раз: множество — это те, кто в нём выписан. Приравниваем: $$\binom nk\cdot k!=n^{\underline k}.$$ Остаётся перенести $k!$ в другую часть, и получится теорема 19. До этого последнего шага мы только умножали. Число пар получается при $k=2$: $\binom n2\cdot2=n(n-1)$.

Тот же ответ даёт задача, в условии которой числа 3 нет вовсе.

Ответ — $8!=40\,320$. Посчитаем иначе. Сначала выберем, кто займёт первые три места, — $\binom83$ способами; потом расставим этих троих на первых трёх местах — $3!$ способами; потом остальных пятерых на оставшихся пяти местах — $5!$ способами. Каждая расстановка получается ровно один раз: тройка — это те, кто стоит на первых трёх местах. Поэтому $$8!=\binom83\cdot3!\cdot5!,$$ то есть $40\,320=720\binom83$ и $\binom83=56$.

Тем же рассуждением для любых $0\le k\le n$ получается $n!=\binom nk\cdot k!\cdot(n-k)!$, вторая запись теоремы 19. Это рассуждение трудно придумать, не зная ответа: в задаче о расстановке восьми человек числа 3 нет, мы ввели его сами. Зато в равенстве $k$ и $n-k$ стоят на равных, и симметрия $\binom nk=\binom n{n-k}$ (утверждение 7) видна сразу.

Места можно разбивать не на две группы, а на несколько. Расставим девятерых по порядку и разобьём девять мест на группы из двух, трёх и четырёх мест подряд. Сначала решим, кто в какую группу попадёт, потом расставим людей внутри групп, $2!\cdot3!\cdot4!$ способами. Значит, число способов разбить людей на группы, умноженное на $2!\cdot3!\cdot4!$, равно $9!$. Само число способов разбить людей на группы равно 1260. Такие числа называют мультиномиальными коэффициентами, и мы, возможно, к ним ещё вернёмся.

У нас есть две формулы для одних и тех же чисел: правило Паскаля, которое вместе с единицами по краям вычисляет строку по предыдущей, и формула теоремы 19 с факториалами. Сначала проверим на примере, что они согласованы. По формуле $\binom52=\frac{5!}{2!\,3!}=10$, $\binom53=\frac{5!}{3!\,2!}=10$ и $\binom63=\frac{6!}{3!\,3!}=20$, и правило Паскаля выполняется: $20=10+10$.

Значит, теорему 19 можно доказать и по-другому. Треугольник однозначно задаётся единицами по краям и правилом Паскаля: каждая строка вычисляется по предыдущей. Формула даёт единицы по краям, $\frac{n!}{0!\,n!}=1$, и по утверждению 22 подчиняется тому же правилу. В строке 0 формула верна; если она верна в какой-то строке, то по правилу Паскаля верна и в следующей; значит, она верна во всех строках. Такое рассуждение называется доказательством по индукции.

И наоборот: зная формулу, правило Паскаля можно проверить вычислением, не раскладывая слова по кучкам. Подсчёт и вычисление — два взгляда на один и тот же факт.

Числа смесей из одного, двух, …, шести вкусов составляют всю шестую строку, кроме первого числа: единица в начале строки отвечает пустой смеси. Сложим: $$6+15+20+15+6+1=63.$$ Столько их и насчитано у Чараки. Вместе с пустой смесью получается 64.

Сложим так же числа в первых строках треугольника. Получится 1, 2, 4, 8, 16, 32, 64: каждая сумма вдвое больше предыдущей.

Похоже, что сумма строки $n$ равна $2^n$. Объясним это подсчётом.

То же видно и по двоичной записи. Слова длины 6, от 000000 до 111111, — это двоичные записи чисел от 0 до $32+16+8+4+2+1=63$, каждого ровно один раз. Чисел от 0 до 63 ровно 64. Пустой смеси отвечает 0, поэтому настоящих смесей 63 — по одной на каждое число от 1 до 63.

Удвоение, которое мы заметили в начале, видно и из правила Паскаля. Каждое число строки входит слагаемым ровно в два числа следующей строки — в то, что под ним слева, и в то, что под ним справа; крайние единицы следующей строки получают по одному такому вкладу. Поэтому в следующей строке каждое число предыдущей посчитано дважды: для строки 4 это $2\cdot16=32=1+5+10+10+5+1$. На языке слов это то же разложение по первой цифре, что в доказательстве правила Паскаля: слово длины $n+1$ — это слово длины $n$, перед которым приписан 0 или 1. Первая лампочка либо горит, либо нет.

Вот и ответы на вопросы из начала: из шести вкусов можно составить 20 смесей по три и 63 смеси всего, а 1820 смесей Варахамихиры получаются одной строчкой вычислений.

Ходьба вдоль строки, которая привела нас к формуле, — не наше изобретение. В 1654 году Блез Паскаль написал и отпечатал «Трактат об арифметическом треугольнике»; в свет он вышел посмертно, в 1665 году. Таблица у Паскаля повёрнута: его «основания» — это диагонали таблицы, и основание номер $m$ совпадает с нашей строкой $m-1$.

Двенадцатое следствие трактата утверждает: две соседние клетки одного основания относятся как число клеток от верхней до верха основания к числу клеток от нижней до низа, включительно. В наших обозначениях это утверждение 18; например, в строке 6 соседние числа 15 и 20 относятся как $3:4$. Доказывает его Паскаль по-другому: соотношение верно во втором основании, то есть в нашей строке из двух единиц, а если верно в каком-то основании, то верно и в следующем. Так устроено доказательство по индукции: проверить первый случай и показать, что из каждого случая следует следующий. Это одно из первых явных доказательств такого рода.

Седьмое следствие трактата совпадает с нашим наблюдением о суммах: сумма клеток каждого основания вдвое больше суммы предыдущего. В конце, после следствий, Паскаль ставит задачу — найти число в клетке, не строя треугольника, — и решает её так же, как мы: перемножает $3\cdot4\cdot5\cdot6$, делит на $1\cdot2\cdot3\cdot4$ и получает 15. У нас это $\binom64$ — соседка вопросительного знака в шестой строке.

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