![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Задача о беспорядках ⇐ ПредыдущаяСтр 4 из 4
Как применение метода включений и исключений рассмотрим задачу о беспорядках или задачу о встречах, предложенную Монмором, которая представляет интерес для различных приложений. Сколькими способами можно разместить Перестановку без повторений можно представить как биекцию множества
Перестановку Задача о беспорядках состоит в том, чтобы подсчитать число Обозначим через
Множество
Подсчитаем число перестановок в каждом из множеств Множество По индукции находим, что По формуле включений и исключений В каждой из этих сумм слагаемые не зависят от индекса суммирования, поэтому для вычисления надо знать только их количество. В первой сумме
После подстановки в уравнение (8) и несложных преобразований находим
Выражение, стоящее в скобках, представляет собой частичную сумму ряда, сходящегося к
|