Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Що таке трикутник Паскаля?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

Трикутник Паскаля - це нескінченна таблиця біноміальних коефіцієнтів 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), через що цикл виконує вдвічі більше роботи.

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

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

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати604 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.