Что делает этот калькулятор
Инструмент строит таблицу сочетаний с повторениями — их также называют коэффициентами мультимножеств. Если есть n различных типов элементов, калькулятор показывает, сколькими способами можно составить неупорядоченную выборку размера r, когда каждый элемент разрешено брать сколько угодно раз — и так для каждого целого r от начального до конечного значения. Эта величина обозначается \(H(n, r)\) и равна биномиальному коэффициенту \(C(n + r - 1, r)\).
Как пользоваться
Укажите количество различных элементов n (не меньше 1), затем начальное и конечное значения r. Калькулятор выдаёт по одной строке на каждое r, и в каждой — точное значение \(H(n, r)\). Поскольку эти числа растут невероятно быстро, расчёты ведутся в режиме длинной арифметики (big-integer), поэтому даже большие таблицы остаются абсолютно точными.
Разбор формулы
Классический приём «звёзды и палочки» показывает, что выбрать r элементов из n типов с повторениями — то же самое, что разложить r одинаковых звёздочек по n ячейкам, разделённым n − 1 палочкой. Число способов расставить эти n + r − 1 символов равно \(C(n + r - 1, r)\). Стоит запомнить два частных случая: \(H(n, 0) = 1\) (пустая выборка) и \(H(1, r) = 1\) (существует лишь одно мультимножество из r копий единственного элемента).
Пример с расчётом
Возьмём \(n = 5\) и r от 0 до 4.
$$H(5,0) = C(4,0) = 1$$$$H(5,1) = C(5,1) = 5$$$$H(5,2) = C(6,2) = 15$$$$H(5,3) = C(7,3) = 35$$$$H(5,4) = C(8,4) = 70$$Получается таблица: 1, 5, 15, 35, 70. Для второй проверки:
$$H(30,4) = C(33,4) = \frac{33 \cdot 32 \cdot 31 \cdot 30}{24} = 40920$$Частые вопросы
Чем это отличается от обычных сочетаний? В обычных сочетаниях \(C(n, r)\) повторения запрещены, а здесь каждый тип элемента можно брать несколько раз — именно поэтому индекс становится равным \(n + r - 1\).
Важен ли порядок? Нет. Выборка {A, A, B} — это то же самое, что {B, A, A}. Если бы порядок имел значение, нужно было бы использовать размещения с повторениями (\(n^r\)).
Почему числа получаются такими огромными? Коэффициент мультимножества растёт примерно как многочлен степени \(n - 1\) от r, поэтому при больших n или r значения становятся астрономически большими — здесь они вычисляются с абсолютной точностью.
