Комбинаторика: Сочетания, Перестановки и Включения-Исключения

Формулы размещений и сочетаний C(n, k), модульный обратный элемент, формула включений-исключений (PIE) и числа Каталана.

Исходная заготовка: полнота объяснения и примеров ожидает редакторской проверки.

Формула числа сочетаний

C_n^k = \binom{n}{k} = \frac{n!}{k!(n-k)!}

C_n = \frac{1}{n+1} \binom{2n}{n}

Описывают число правильных скобочных последовательностей длины

2n

и число различных триангуляций

n+2

-угольника.

Вернитесь к обучению и выберите следующий материал.

Отметка сохранится в этом браузере. Её можно отменить или снять кнопкой «Изучено».