Еще комба, обнаруженная в статье Уитни хрен знает какого бородатого года, где он по сути рассказывает о прелестях формулы включения-исключения, в том числе вводит хроматический многочлен графа. Но к графам задача отношения не имеет.
Даны две колоды из N карт - в каждой колоде все карты разные, но состав обоих колод одинаковый. Случайным образом выкладывают обе колоды в два ряда - одну колоду над другой. С какой вероятностью ни в одной позиции не будет совпадения карт? (порядки карт в обоих рядах равновероятны).
Методом включения-исключения и несложной комбинаторикой получаем ответ:
ОтветитьУдалить1 - 1/1! + 1/2! - 1/3! +... +(-1)^N/N!
Получается неплохое приближение для e^{-1}, что любопытно.