Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Як обчислити кількість перестановок n елементів?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)**Кількість перестановок** n різних елементів дорівнює n! (факторіал n). За визначенням n! = 1 · 2 · 3 · … · n, а 0! = 1. **Ключове:** факторіал зростає дуже швидко - вже 20! ≈ 2.43e18, тому для точних обчислень потрібні типи великих чисел (BigInt, arbitrary precision).Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення## Коротка відповідь Кількість перестановок n різних елементів дорівнює n! (факторіал n). За визначенням n! = 1 · 2 · 3 · … · n, а 0! = 1. ## Докладне пояснення ### Що таке факторіал - Визначення: n! = 1 · 2 · 3 · … · n для n ≥ 1; за домовленістю 0! = 1. - Рекурентно: n! = n · (n − 1)!, де 0! = 1. - Приклад: 5! = 1 · 2 · 3 · 4 · 5 = 120. ### Звідки береться формула Перестановка - це впорядкування всіх n різних елементів. На перше місце можна поставити будь-який з n елементів, на друге - будь-який із залишку (n − 1), на третє - (n − 2) і так далі, поки не вичерпаємо елементи. Перемножуючи кількість варіантів на кожному кроці, отримуємо n · (n − 1) · (n − 2) · … · 2 · 1 = n!. ### Приклади перестановок - n = 3: 3! = 6. Перестановки елементів {A, B, C}: ABC, ACB, BAC, BCA, CAB, CBA. - n = 5: 5! = 120. - n = 0: 0! = 1 (одна «порожня» перестановка). ### Часті варіації на співбесідах - Розміщення без повторень (впорядковані вибірки з n по k): A(n, k) = n! / (n − k)!. Приклад: A(5, 2) = 5 · 4 = 20. - Перестановки з повтореннями: якщо серед n елементів є групи, що повторюються, розмірів m1, m2, …, mr (m1 + … + mr = n), то кількість різних перестановок дорівнює n! / (m1! · m2! · … · mr!). Приклад: перестановки слова «ANNA» (літери: A×2, N×2) - 4! / (2! · 2!) = 6. - Кругові перестановки (розташування по колу, де повороти вважаються однаковими): (n − 1)!. - Впорядковані послідовності довжини k з поверненням (вибір із повтореннями): n^k. ### Практичні зауваження - Факторіал зростає дуже швидко: вже 20! ≈ 2.43e18, тому використовуйте типи великих чисел (BigInt, arbitrary precision). - Остерігайтеся переповнення стандартних цілочисельних типів. - У багатьох задачах факторіал не обчислюють напряму - використовують скорочення в дробах (наприклад, в A(n, k) скорочують добуток). ### Код: як порахувати n! на практиці JavaScript (BigInt): ``` function factorial(n) { if (!Number.isInteger(n)) throw new TypeError('n must be an integer'); if (n < 0) throw new RangeError('n must be >= 0'); let result = 1n; const N = BigInt(n); for (let i = 2n; i <= N; i++) { result *= i; } return result; // BigInt } // Приклади console.log(factorial(0).toString()); // "1" console.log(factorial(5).toString()); // "120" console.log(factorial(25).toString()); // "15511210043330985984000000" ``` Python: ``` def factorial(n: int) -> int: if not isinstance(n, int): raise TypeError("n must be an integer") if n < 0: raise ValueError("n must be >= 0") result = 1 for i in range(2, n + 1): result *= i return result # Приклади виклику print(factorial(0)) # 1 print(factorial(5)) # 120 print(factorial(25)) # 15511210043330985984000000 # Примітка: у стандартній бібліотеці є готова функція math.factorial(n). ```Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.