Теория комбинаторики

Центральное место в теории занимают правила суммы и произведения. Правило суммы гласит: если элемент A можно выбрать m способами, а элемент B — k способами, то выбор "A или B" можно сделать m + k способами (при условии, что выборы взаимоисключающие). Правило произведения утверждает, что пару "A и B" можно выбрать m * k способами.

Принцип Дирихле

В теории комбинаторики важное место занимает принцип Дирихле ("принцип ящиков"). Если n+1 кроликов рассадить в n клеток, то хотя бы в одной клетке окажется не менее двух кроликов. Этот простой принцип позволяет доказывать неочевидные утверждения.

Рекуррентные соотношения

Многие комбинаторные задачи решаются с помощью рекурсии. Классический пример — числа Фибоначчи, где каждое следующее число равно сумме двух предыдущих. Понимание рекурсии необходимо для программистов и математиков.

Академические источники

• МФТИ: Кафедра высшей математики
• Мехмат МГУ
• ВШЭ: Курсы по дискретной математике
• ArXiv.org: Mathematics
• zbMATH Open
• American Mathematical Society

Учебная литература

• Ландо С.К. "Лекции о производящих функциях"
• Спивак А.В. "Тысяча и одна задача по математике"
• Белоусов А.И. "Дискретная математика"
• Липский В. "Комбинаторика для программистов"

Теория служит базой для практических расчетов, описанных в статье Комбинаторика и вероятности.