Бином Ньютона и треугольник Паскаля

Соединяем алгебру и комбинаторику: формула бинома Ньютона и треугольник Паскаля, где живут все сочетания.

Бином Ньютона — формула разложения степени суммы (a + b)^n через биномиальные коэффициенты (сочетания).

Зачем это нужно

Биномиальные коэффициенты C(n, k) возникают не только при подсчёте сочетаний — они появляются в разложении степеней, в теории вероятностей (биномиальное распределение — это про k успехов из n испытаний), в анализе алгоритмов. Треугольник Паскаля — это компактный способ вычислить их все сразу, без факториалов и без переполнения. А связь «алгебраическое разложение ↔ комбинаторный подсчёт» — красивый пример того, как одна и та же математика смотрит на задачу с двух сторон.

Формула бинома Ньютона

Все знают (a + b)² = a² + 2ab + b². А что с произвольной степенью? Бином Ньютона даёт ответ:

(a + b)^n = C(n,0)·a^n + C(n,1)·a^(n-1)·b + ... + C(n,n)·b^n

Словами: раскрывая (a + b)^n, мы получаем сумму слагаемых вида C(n,k)·a^(n−k)·b^k, где k пробегает от 0 до n. Коэффициент перед каждым слагаемым — это биномиальный коэффициент C(n, k), то самое число сочетаний.

Почему именно сочетания — комбинаторное объяснение

Откуда берётся C(n, k)? Раскрытие (a + b)^n = (a+b)·(a+b)·...·(a+b) — это выбор из каждой из n скобок либо a, либо b, а потом перемножение. Слагаемое a^(n−k)·b^k получается, когда мы выбрали b ровно из k скобок (и a из остальных). А сколькими способами выбрать k скобок из n? Ровно C(n, k)! Вот почему коэффициент — это сочетание. Алгебра и комбинаторика оказались одним и тем же.

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

Треугольник Паскаля — это таблица биномиальных коэффициентов. В строке n стоят числа C(n,0), C(n,1), ..., C(n,n). Вот его начало:

           1
          1 1
         1 2 1
        1 3 3 1
       1 4 6 4 1
      1 5 10 10 5 1

Главное свойство — правило сложения: каждое число равно сумме двух чисел над ним. Формально: C(n, k) = C(n−1, k−1) + C(n−1, k). Это не магия, а комбинаторика: выбирая k элементов из n, мы либо берём последний элемент (тогда осталось выбрать k−1 из n−1), либо не берём (выбираем k из n−1). Два непересекающихся случая — складываем (правило суммы). Это же правило даёт удобный способ вычислять коэффициенты без факториалов.

Строим треугольник Паскаля на Python

import math

# Способ 1: напрямую через сочетания
print("Через C(n,k):")
for n in range(6):
    print([math.comb(n, k) for k in range(n + 1)])

# Способ 2: по правилу сложения (без факториалов)
print("По правилу сложения:")
triangle = [[1]]
for n in range(1, 6):
    prev = triangle[-1]
    row = [1] + [prev[i] + prev[i + 1] for i in range(len(prev) - 1)] + [1]
    triangle.append(row)
for row in triangle:
    print(row)

Вывод:

Через C(n,k):
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]
По правилу сложения:
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]

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

Проверяем бином Ньютона численно

Убедимся, что формула действительно даёт правильное значение: сравним прямое возведение в степень с суммой по биному.

import math

a, b, n = 2, 3, 4
direct = (a + b) ** n
expansion = sum(math.comb(n, k) * a ** (n - k) * b ** k
                for k in range(n + 1))
print(f"(2 + 3)^4 напрямую    = {direct}")
print(f"(2 + 3)^4 по биному   = {expansion}")
print("Совпадают:", direct == expansion)

Вывод:

(2 + 3)^4 напрямую    = 625
(2 + 3)^4 по биному   = 625
Совпадают: True

Формула бинома Ньютона дала точно 625 = 5^4 — как и прямое вычисление. Полезный частный случай: подставим a = b = 1, получим 2^n = C(n,0)+C(n,1)+...+C(n,n) — сумма всей строки треугольника Паскаля равна степени двойки. Это и есть «число всех подмножеств», к которому мы уже подходили с трёх разных сторон.

Скрытые узоры треугольника

Сумма n-й строки равна 2^n.
Вторая диагональ — натуральные числа (1, 2, 3, ...), третья — «треугольные» числа (1, 3, 6, 10, ...).
Знакочередующаяся сумма строки равна нулю (при n ≥ 1): C(n,0) − C(n,1) + C(n,2) − ... = 0.

Сочетания с повторениями: метод «шаров и перегородок»

До сих пор мы выбирали различные элементы. А если можно брать повторы? Например: сколькими способами купить 5 пирожных, если в кофейне 3 сорта (и сорта можно повторять)? Это сочетания с повторениями, и для них есть изящный приём — метод шаров и перегородок (stars and bars).

Представим 5 покупок как 5 «шаров», которые нужно распределить по 3 сортам. Поставим 2 «перегородки», разделяющие шары на 3 группы: например, ●●|●|●● означает «2 первого сорта, 1 второго, 2 третьего». Любой выбор — это расстановка 5 шаров и 2 перегородок в ряд из 7 позиций, а количество таких расстановок — это C(7, 2) = 21: выбираем, на каких 2 из 7 мест стоят перегородки. Проверим перебором:

from itertools import product
import math
# x1 + x2 + x3 = 5, все x >= 0 (сколько каждого из 3 сортов)
count = sum(1 for combo in product(range(6), repeat=3) if sum(combo) == 5)
print("Перебором:", count, "| формула C(5+3-1, 3-1) = C(7,2) =", math.comb(7, 2))

Вывод:

Перебором: 21 | формула C(5+3-1, 3-1) = C(7,2) = 21

Общая формула: число способов выбрать k элементов из n сортов с повторениями равно C(n+k−1, k). Метод шаров и перегородок — один из самых элегантных приёмов комбинаторики: он сводит хитрый подсчёт к обычным сочетаниям.

Типичные ошибки

Забывать степени в слагаемых. В (a+b)^n каждое слагаемое — это C(n,k)·a^(n−k)·b^k, а не просто C(n,k). Коэффициенты из Паскаля — только множители.
Считать факториалы для больших коэффициентов. Это медленно и переполняется. Правило сложения (треугольник) — точнее и устойчивее.
Путать индексацию. Строки и позиции в треугольнике нумеруются с нуля: вершина — это C(0,0).

Итог

Бином Ньютона: (a+b)^n = Σ C(n,k)·a^(n−k)·b^k; коэффициенты — это сочетания.
Сочетания появляются потому, что мы выбираем, из каких k скобок взять b.
Треугольник Паскаля строится правилом C(n,k) = C(n−1,k−1) + C(n−1,k) — без факториалов.
Сумма строки = 2^n; в треугольнике спрятаны натуральные и треугольные числа.