N1. 80c21
Задача N1: 80c21.
Что значит 80c21
- Это биномиальный коэффициент C(80,21) — число сочетаний из 80 элементов по 21.
Способ решения (пошагово, подробно)
Запись через множители C(80,21) можно записать как отношение произведения 21 множителя сверху к 21! снизу: C(80,21) = (80 × 79 × 78 × … × 60) / (21 × 20 × 19 × … × 1).
Разложение на простые множители Разложим каждый множитель в числителе и знаменателе на простые:
Числитель (80 … 60): 60 = 2^2 · 3 · 5 61 = 61 62 = 2 · 31 63 = 3^2 · 7 64 = 2^6 65 = 5 · 13 66 = 2 · 3 · 11 67 = 67 68 = 2^2 · 17 69 = 3 · 23 70 = 2 · 5 · 7 71 = 71 72 = 2^3 · 3^2 73 = 73 74 = 2 · 37 75 = 3 · 5^2 76 = 2^2 · 19 77 = 7 · 11 78 = 2 · 3 · 13 79 = 79 80 = 2^4 · 5
Знаменатель 21! разложим на простые: 21! содержит 2^18 · 3^9 · 5^4 · 7^3 · 11 · 13 · 17 · 19 (остальные простые в 21! встречаются в меньших степенях или отсутствуют).
- Вычитание степеней простых (сокращение) Из разложения числителя и знаменателя по простым получаем остатки простых в числителе:
- 2: 24 (числитель) − 18 (знаменатель) = 2^6
- 3: 9 − 9 = 0 (3 исчезает)
- 5: 6 − 4 = 2 → 5^2 остается
- 7: 3 − 3 = 0 (7 исчезает)
- 11: 2 − 1 = 1 → 11 остаётся
- 13: 2 − 1 = 1 → 13 остаётся
- 17: 1 − 1 = 0 (исчезает)
- 19: 1 − 1 = 0 (исчезает) Оставшиеся над числителем простые: 23, 31, 37, 61, 67, 71, 73, 79
Итого после сокращения остаются множители: 2^6 · 5^2 · 11 · 13 · 23 · 31 · 37 · 61 · 67 · 71 · 73 · 79
- Вычисление итогового произведения Сначала умножим поэтапно:
- 2^6 · 5^2 = 64 · 25 = 1600
- 1600 · 11 = 17600
- 17600 · 13 = 228800
- 228800 · 23 = 5262400
- 5262400 · 31 = 163134400
- 163134400 · 37 = 6035972800
- 6035972800 · 61 = 368194340800
- 368194340800 · 67 = 24669020833600
- 24669020833600 · 71 = 1751500479185600
- 1751500479185600 · 73 = 127859534980548800
- 127859534980548800 · 79 = 10100903263463355200
Ответ C(80,21) = 10 100 903 263 463 355 200
Пояснение и полезные примеры
- 80c21 можно also использовать симметрию: C(80,21) = C(80,59). Это иногда может быть удобнее для вычислений.
- В этом решении мы предпочли факторизацию и вычитание степеней простых, чтобы получить точное целое число без ошибок при последовательном делении.
Если хочешь, могу показать ещё один вариант вычисления (через последовательное умножение с сокращениями на каждом шаге) или проверить результат другим способом.
