Калькулятор треугольника Паскаля

C(n, k) = C(n-1, k-1) + C(n-1, k); C(n, 0) = C(n, n) = 1; сумма строки = 2^n

n

Число строк для печати, причём единственная единица наверху считается строкой 0. То есть n строк — это строки с 0 по n - 1, и в последней напечатанной строке n чисел. Ввод принимается от 1 до 53, и потолок здесь не про размер экрана — см. ниже пункт про сумму строки, именно она кончается первой

k

Позиция внутри строки, отсчитываемая от 0 у левого края. В строке n есть числа на позициях от k = 0 до k = n, то есть n + 1 число. Две крайние позиции особые: C(n, 0) и C(n, n) равны 1, и это та пара единиц, что идёт по бокам треугольника. Всё строго между ними — сумма двух чисел из строки выше

C(n-1, k-1) + C(n-1, k)

Правило, по которому строится всё остальное, и то, которому следует страница. Число на позиции k в строке n — сумма двух чисел над ним: того, что прямо над ним слева, и того, что прямо над ним справа; поэтому края всегда видят только одно число и остаются единицами. Это делается сложением, а не по формуле с факториалами, поэтому каждое промежуточное значение точно, и треугольник на экране буквально представляет собой последовательность выполненных сложений

C(n, k) = n! / (k! (n-k)!)

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

2^n

Сумма строки n и причина, по которой ввод кончается там, где кончается. Сложите строку — и всегда получите степень двойки: строка 0 даёт 1, строка 1 даёт 2, строка 2 даёт 4, а строка 6 даёт 64. Удвоение на каждой строке и приводит к тому, что сумма выходит из точно представимого диапазона раньше, чем любой отдельный коэффициент: строка 52 даёт в сумме 4 503 599 627 370 496, строка 53 — 9 007 199 254 740 992, а это на единицу больше наибольшего целого, которое число с плавающей точкой двойной точности хранит точно

1, 6, 15, 20, 15, 6, 1

Строка 6, напечатанная целиком, — последняя строка в семи по умолчанию. Сверьте её со строкой выше, и каждое число окажется суммой двух соседей: 6 это 1 + 5, 15 это 5 + 10, 20 это 10 + 10, а дальше строка зеркалится. Строка всегда симметрична относительно середины, потому что выбрать k предметов, чтобы оставить, и выбрать n - k предметов, чтобы отбросить, — это один и тот же выбор, посчитанный дважды

Треугольник — самый быстрый способ раскрыть бином вручную. Чтобы перемножить (x + y) в шестой степени, вы читаете строку 6 прямо со страницы и пишете 1x⁶ + 6x⁵y + 15x⁴y² + 20x³y³ + 15x²y⁴ + 6xy⁵ + 1y⁶, вообще не перемножая многочлены. Биномиальное разложение проще всего читать именно так: строка сразу даёт все коэффициенты, а показатель степени при x убывает слева направо. Отдельный коэффициент нужен, когда требуется всего один член, и страница сочетаний считает его прямо по n и k, не выстраивая промежуточные строки. Задачи теории вероятностей с двумя исходами пользуются теми же числами: вероятность ровно 4 орлов при 10 бросках равна C(10, 4), делённому на 2¹⁰, и это 1 024 в знаменателе — сумма строки 10. Треугольник отвечает и на вопросы подсчёта, выглядящие никак не связанными: число путей по сетке из одного угла в противоположный, число способов добраться до конкретной клетки, если можно двигаться только вправо и вниз, и количество подмножеств заданного размера. Сочетания C(n, k) — это и есть числа треугольника, только посчитанные по формуле. Когда вопрос в том, что это за числа, а не что они означают, их печатает эта страница; когда нужно знать, сколькими способами что-то может произойти, короткий путь — страница сочетаний; а когда вопрос о числах Фибоначчи, спрятанных в диагоналях, эту последовательность разбирает страница чисел Фибоначчи.

1. Семь строк, последняя — 1, 6, 15, 20, 15, 6, 1

   1. Строка 0 — это 1, а строка 1 — 1, 1: оба края каждой строки всегда равны 1
   2. Строка 2: 1 + 1 = 2 в середине, получается 1, 2, 1
   3. Строка 3: 1 + 2 = 3 дважды, получается 1, 3, 3, 1; строка 4: 1 + 3 = 4 и 3 + 3 = 6, получается 1, 4, 6, 4, 1
   4. Строки 5 и 6 продолжают так же и заканчиваются на 1, 6, 15, 20, 15, 6, 1
   5. Складываем строку 6 целиком: 1 + 6 + 15 + 20 + 15 + 6 + 1 = 64, а это 2 в шестой степени

   Значение по умолчанию. Два обстоятельства стоит проверить по экрану. Во-первых, каждое число — сумма двух над ним: 15 это 5 + 10, 20 это 10 + 10, и строка симметрична, потому что 20 стоит в середине семи чисел и пары расходятся от него в обе стороны. Во-вторых, сумма строки каждый раз удваивается — 1, 2, 4, 8, 16, 32, 64, — так что читатель, знающий, что предыдущая строка даёт 32, предскажет эту ещё до сложения. Это удвоение — тот же факт, что и две единицы по краям: каждая строка выше отдаёт свой итог дважды, один раз в левую половину и один раз в правую.

2. Четыре строки, самый короткий полезный треугольник

   1. Строка 0 — это 1; строка 1 — 1, 1
   2. Строка 2 — 1, 2, 1, где 2 получается из 1 + 1
   3. Строка 3 — 1, 3, 3, 1, где каждая 3 получается из 1 + 2
   4. Складываем последнюю строку: 1 + 3 + 3 + 1 = 8, а это 2 в третьей степени

   Строка 3 здесь последняя, и именно на ней треугольник становится интересным: 1, 3, 3, 1 — коэффициенты (x + y)³, поэтому x³ + 3x²y + 3xy² + y³ можно выписать прямо по этой строке, ничего не перемножая. Это ещё и последняя строка, которую можно проверить руками за несколько секунд, поэтому на неё стоит посмотреть прежде, чем на длинные. Обратите внимание: 4 строки означают строки с 0 по 3 — введённое число это количество строк, а не индекс самой большой.

3. Одна строка, тривиальный случай

   1. Строка 0 — это одна единица, и складывать над ней нечего
   2. Запрошена одна строка — одна строка и напечатана
   3. Сумма строки равна 1, а это 2 в нулевой степени

   Наименьший ввод, который принимает страница, и он принимается, а не считается пустым. Треугольник из одной строки не вырожден — это базовый случай, из которого строится каждая следующая строка. Чтение его подтверждает и нумерацию: запрос на 1 строку даёт строку 0, а не строку 1, и это важно, как только вы начнёте сверять треугольник с биномиальным разложением. То, что сумма равна 1, а не 0, — это тот же факт в арифметике, что и одна единица на вершине треугольника.

Число строк должно быть целым от 1 до 53. Потолок стоит потому, что каждое напечатанное число должно быть таким, которое компьютер ещё представляет точно, а за этой границей два соседних целых сливаются в одно значение — напечатанные цифры выглядят совершенно обычно, но больше не обозначают то число, которым называются. Раньше всех сдаётся сумма строки: строка 52 даёт в сумме 4 503 599 627 370 496, а строка 53 — 9 007 199 254 740 992, что на единицу больше наибольшего целого, которое число с плавающей точкой двойной точности хранит точно. Отдельные коэффициенты продержались бы до строки 56 — первый вышедший за границу это C(57, 28), в строке 57, — но треугольник печатается строка за строкой, поэтому решает сумма. Ноль строк отклоняется: пустой треугольник ничего не печатает, значит и ответа дать нельзя. Доли строки отклоняются, а не округляются: двух с половиной строк не бывает. Строки возвращаются одной плоской строкой чисел, разделённых запятыми, а друг от друга строки отделены точкой с запятой, и разделителей разрядов внутри чисел нет вообще, поэтому большой коэффициент печатается как 184756, тогда как в обычном тексте то же число пишется 184 756. На широком треугольнике это означает длинную строку с прокруткой. Справочная таблица ниже показывает первые семь строк, а не следует за вашим вводом, и ни одну строку нельзя запросить напрямую — страница всегда печатает сверху вниз.

Для чего нужен треугольник Паскаля?

В основном для раскрытия биномов. Числа в строке n — это коэффициенты, которые получаются при раскрытии (x + y) в n-й степени, поэтому строка 6 позволяет сразу выписать семь членов (x + y)⁶, ничего не перемножая. Те же числа считают сочетания: C(n, k) — это число на позиции k в строке n, поэтому они отвечают на вопросы вроде того, сколькими способами можно выбрать 4 человека из 10. Встречаются они и в теории вероятностей, где вероятность ровно 4 орлов при 10 бросках монеты равна C(10, 4) из 2¹⁰ — а это 1 024, сумма строки 10. Подсчёт путей по сетке тоже обходится ими: число маршрутов из одного угла сетки в противоположный, если двигаться только вправо и вниз, — это число из треугольника.

Почему ввод останавливается на 53 строках?

Потому что сумма строки перестаёт быть целым, которое компьютер может представить точно. Строка 52 даёт в сумме 4 503 599 627 370 496, а строка 53 — 9 007 199 254 740 992, и это второе число на единицу больше наибольшего значения, которое число с плавающей точкой двойной точности хранит точно. За этой границей два соседних целых становятся одним значением, поэтому напечатанные цифры выглядят обычно, но больше не обозначают число, которым называются. Отдельные коэффициенты продержались бы дольше — первый вышедший за границу это C(57, 28), в строке 57, — но треугольник печатается строка за строкой, поэтому решает сумма. Напечатать строку, у которой итог неверен, а отдельные числа верны, было бы очень сбивающим с толку.

Почему последняя строка печатается дважды?

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

Строки начинаются с 0 или с 1?

С 0 — это соглашение, которым обычно нумеруют коэффициенты. C(n, k) означает число на позиции k в строке n, поэтому верхняя единица — это строка 0, и запрос на 7 строк даёт строки с 0 по 6, заканчиваясь на 1, 6, 15, 20, 15, 6, 1: семь чисел, потому что в строке n всегда n + 1 чисел. Это важно при сверке треугольника с биномиальным разложением: строка коэффициентов для (x + y)⁶ — это строка 6, а не строка 7. Введённое число — количество строк, а не индекс самой большой.

Что такое сумма строки и почему она всегда степень двойки?

Сложите любую строку и получите 2 в степени её индекса: строка 0 даёт 1, строка 6 даёт 64, строка 10 даёт 1 024. Причина — правило, по которому треугольник строится. Каждая строка делается из строки выше, прибавленной к себе со сдвигом на одну позицию, поэтому каждое число из строки выше посчитано в строке ниже дважды: один раз слева, один раз справа. Удвоение итога каждый раз и даёт степени двойки. Тот же факт, прочитанный иначе: сумма строки n считает все подмножества множества из n элементов, а у множества из n элементов их 2ⁿ. Поэтому 1 024 в основании вероятности с десятью бросками монеты берётся прямо из строки 10.

Откуда в этом треугольнике числа Фибоначчи?

Из пологих диагоналей. Сложите числа вдоль линии, идущей вверх и влево, — например 1, затем 4, затем 3, — и промежуточные суммы дадут 1, 1, 2, 3, 5, 8, 13. Это числа Фибоначчи, где каждое следующее равно сумме двух предыдущих. Причина в том, что каждое число на диагонали само построено из двух чисел над ним, одно из которых лежит на той же диагонали, а другое — на следующей, поэтому диагонали напрямую наследуют рекуррентное соотношение Фибоначчи. Калькулятор чисел Фибоначчи разбирает эту последовательность отдельно, если захочется пойти дальше.

• Pascal's Triangle — the array of binomial coefficients, its additive rule, and the identities that fall out of it — Wolfram MathWorld (United States)
• Binomial Coefficient — what C(n, k) counts, the factorial formula, and why the additive rule gives the same values — Wolfram MathWorld (United States)
• Binomial Theorem — the expansion of (x + y)^n, whose coefficients are the rows of the triangle — Wolfram MathWorld (United States)