А если порядок важен?
К предыдущей задаче возник естественный вопрос: а что изменится, если порядок выбранных дней учитывать?
Тогда это уже не сочетания, а размещения. Например, (1; 4; 8; 13) и (1; 8; 13; 4) будут считаться разными вариантами.
Число размещений из 20 элементов по 4 равно A₂₀⁴ = 20·19·18·17.
Попробуем теперь найти 2026-е размещение в лексикографическом порядке.
Все размещения, начинающиеся с 1, образуют блок размером 19·18·17 = 5814.
Поэтому 2026-е размещение действительно начинается с 1.
После этого для каждого фиксированного второго элемента остаётся 18·17 = 306 вариантов.
Удобно считать от нуля:
2026−1 = 2025,
2025 = 6·306 + 189.
Значит, второй элемент — 7-й среди оставшихся: 8.
Далее
189 = 11·17 + 2.
После 1 и 8 третий элемент — 12-й среди оставшихся: 14.
Наконец, остаётся выбрать 3-й из ещё не использованных чисел: 4.
Получаем (1; 8; 14; 4).
Комментарий к предыдущей задаче подсвечивает важное различие.
Для сочетаний порядок не учитывается, и размеры блоков задаются биномиальными коэффициентами:
C₁₉³, C₁₈³, …
Для размещений порядок важен, и вместо них появляются произведения
19·18·17, 18·17, 17, …
Стоит разрешить перестановку выбранных элементов — и у того же лексикографического списка меняется вся арифметика блоков.
Post #1312
693
- 🔥 5
- 👍 2