Що таке трикутник Паскаля?

АлгоритмиJunior~3 хв читання

Коротка відповідь

Трикутник Паскаля - це нескінченна таблиця біноміальних коефіцієнтів C(n, k), де кожен рядок n починається і закінчується одиницею, а кожне внутрішнє число дорівнює сумі двох чисел над ним: C(n, k) = C(n−1, k−1) + C(n−1, k). Він використовується для обчислення сполучень і коефіцієнтів у розкладі (a + b)^n.

Докладне пояснення

Визначення

Трикутник Паскаля - це спосіб організувати числа C(n, k) (сполучення «n по k»). Межі трикутника заповнені одиницями: C(n, 0) = C(n, n) = 1. Внутрішні елементи обчислюються за рекурентною формулою: C(n, k) = C(n−1, k−1) + C(n−1, k). Індексація зазвичай починається з n = 0 у верхньому рядку (де єдиний елемент дорівнює 1).

Перші рядки

n	Значення C(n, k) зліва направо
0	1
1	1 1
2	1 2 1
3	1 3 3 1
4	1 4 6 4 1
5	1 5 10 10 5 1

Ключові властивості

Рекурентне співвідношення: C(n, k) = C(n−1, k−1) + C(n−1, k); базові випадки: C(n, 0) = C(n, n) = 1.
Біноміальна теорема: (a + b)^n = Σ C(n, k) a^(n−k) b^k.
Симетрія: C(n, k) = C(n, n − k).
Сума рядка: Σ_{k=0..n} C(n, k) = 2^n.
Діагоналі: край - усі одиниці; наступна діагональ - натуральні числа; далі - трикутні числа і т. д. Неглибокі діагоналі дають послідовність Фібоначчі.
Комбінаторний сенс: C(n, k) - кількість способів вибрати k елементів із n без урахування порядку.
Парність: за модулем 2 малюнок трикутника утворює фрактал Серпінського.

Алгоритми і код (JavaScript)

Нижче - практична реалізація для отримання n-го рядка і перших R рядків. Використовується BigInt, щоб уникнути переповнення для великих n. Формула для сусідніх коефіцієнтів: C(n, k+1) = C(n, k) × (n − k) / (k + 1).

javascript

function pascalRow(n) {
  const row = Array(n + 1);
  row[0] = 1n;
  for (let k = 1; k <= n; k++) {
    row[k] = (row[k - 1] * BigInt(n - (k - 1))) / BigInt(k);
  }
  return row;
}

function pascalTriangle(rows) {
  const tri = [];
  for (let n = 0; n < rows; n++) {
    tri.push(pascalRow(n));
  }
  return tri;
}

// Приклади використання
console.log(pascalRow(5).map(Number));       // [1, 5, 10, 10, 5, 1]
console.log(pascalTriangle(6).map(r => r.map(Number)));
// [
//   [1],
//   [1, 1],
//   [1, 2, 1],
//   [1, 3, 3, 1],
//   [1, 4, 6, 4, 1],
//   [1, 5, 10, 10, 5, 1]
// ]

Ця реалізація не використовує факторіали, працює за O(n) для одного рядка і стійка до переповнення завдяки BigInt.

Типові задачі на співбесіді

Вивести перші R рядків трикутника Паскаля (ітеративно, без рекурсії).
Отримати n-й рядок за O(n) пам'яті (інкрементально або in-place справа наліво).
Обчислити C(n, k) без факторіалів (множачи і ділячи по ходу; використовувати симетрію k = min(k, n − k)).

Складність

Побудова до рядка n повністю: O(n^2) за часом і пам'яттю.
Один рядок n: O(n) за часом і O(n) за пам'яттю (або O(1) додаткової пам'яті при виведенні по одному числу).

Часті помилки

Використання факторіалів (переповнення і зайва складність).
Ділення в числах із плаваючою комою замість цілочисельної арифметики (втрачається точність).
Ігнорування симетрії C(n, k) = C(n, n − k), через що цикл виконує вдвічі більше роботи.

Короткі формули

Замкнена форма (факторіальна): C(n, k) = n! / (k! (n − k)!).
Рекурентна формула: C(n, k) = C(n − 1, k − 1) + C(n − 1, k).
Сусідні коефіцієнти: C(n, k + 1) = C(n, k) × (n − k) / (k + 1).

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.