СВ в 13:51, 24 октября 2026

2026-10-24T13:51:32Z

← Предыдущая		Версия 13:51, 24 октября 2026
Строка 18:		Строка 18:
	Беспорядком на множестве $\{1,...,n\}$ называется перестановка, которая не сохраняет ни одного элемента: $\pi(i)\neq i, i=\overline{1,n}$.		Беспорядком на множестве $\{1,...,n\}$ называется перестановка, которая не сохраняет ни одного элемента: $\pi(i)\neq i, i=\overline{1,n}$.
	}}		}}

			[[Файл:p30-01-derangement-examples.svg\|frame\|none\|900px\|alt=Две перестановки четырёх элементов: слева две неподвижные точки перечёркнуты, справа все элементы сдвинуты\|Рис. 1. Беспорядок — перестановка без неподвижных точек. Слева перестановка оставляет элементы 1 и 4 на месте (стрелки перечёркнуты), справа все четыре элемента сдвинуты. Для <math>n=4</math> беспорядков 9 из 24 перестановок.]]


	'''Задача.''' Найти число беспорядков на множестве $\{1,...,n\}$:		'''Задача.''' Найти число беспорядков на множестве $\{1,...,n\}$:
Строка 40:		Строка 43:

	Нетрудно видеть, что $f_\geq(T) = \|S\setminus T\|!$ {{---}} число перестановок на множестве $S\setminus T$.		Нетрудно видеть, что $f_\geq(T) = \|S\setminus T\|!$ {{---}} число перестановок на множестве $S\setminus T$.

			[[Файл:p30-02-fix-set-factorial.svg\|frame\|none\|900px\|alt=Две перестановки с закреплёнными элементами 1 и 3: свободные 2 и 4 либо неподвижны, либо меняются местами\|Рис. 2. Если закрепить <math>T=\{1,3\}</math>, свободными остаются <math>n-\|T\|=2</math> элемента; их можно переставить <math>2!=2</math> способами. Поэтому <math>f_\geq(T)=(n-\|T\|)!</math>; только второй вариант входит в <math>f_=(T)</math>.]]


	Очевидно, $D(n) = f_=(\varnothing)$. Следующее утверждение решает задачу.		Очевидно, $D(n) = f_=(\varnothing)$. Следующее утверждение решает задачу.
Строка 55:		Строка 61:
	</math>		</math>
	}}		}}

			[[Файл:p30-03-inclusion-exclusion-d4.svg\|frame\|none\|900px\|alt=Таблица слагаемых для D(4): 24 − 24 + 12 − 4 + 1 = 9\|Рис. 3. Слагаемые <math>D(4)</math>, сгруппированные по числу <math>i</math> закреплённых свойств: <math>C(4,i)</math> наборов по <math>(4-i)!</math> перестановок. Сумма <math>24-24+12-4+1=9</math>; то же даёт <math>4!(1-1+1/2-1/6+1/24)</math>.]]

	Конспект: [[Дискретная математика]]		Конспект: [[Дискретная математика]]

	[[Категория:Дискретная математика]]		[[Категория:Дискретная математика]]

СВ: Новая страница: «== Интуитивная постановка задачи == {{Пример |content=Пусть в рамках чемпионата в $n$ городах до...»

2026-10-11T10:08:30Z

Новая страница: «== Интуитивная постановка задачи == {{Пример |content=Пусть в рамках чемпионата в $n$ городах до...»

Новая страница

== Интуитивная постановка задачи ==

{{Пример
|content=Пусть в рамках чемпионата в $n$ городах должно пройти ровно по одному матчу.
Матчи судят $n$ судей, каждый из которых из одного из городов, все из разных.
Сколькими способами можно распределить судей по матчам, чтобы ни один судья не судил в своем городе?
}}
{{Пример
|content=Пусть $n$ человек пришли в театр и сдали шляпы в гардероб.
Когда спектакль закончился и зрители получили шляпы назад, оказалось, что каждый из $n$ получил чужую шляпу.
Сколько существует вариантов такого события?
}}

== Формальная постановка задачи ==

{{Определение
|definition=
Беспорядком на множестве $\{1,...,n\}$ называется перестановка, которая не сохраняет ни одного элемента: $\pi(i)\neq i, i=\overline{1,n}$.
}}

'''Задача.''' Найти число беспорядков на множестве $\{1,...,n\}$:
$D(n) = |\{\pi | \pi\in\sigma_n, \pi(i)\neq i, i=\overline{1,n}\}|$.

Решим эту задачу с помощью принципа включения-исключения.

Будем говорить, что $\pi\in\sigma_n$ обладает свойством $i$, если $\pi(i)=i$.
Тогда $S=\{1,...,n\}$ {{---}} множество всех свойств, которыми может обладать перестановка.

Пусть $T\subseteq S$, $f_=(T)$ {{---}} число перестановок, каждая из которых обладает всеми
свойствами из $T$ и не обладает свойствами из $S\setminus T$:
<math>
f_=(T) = |\{\pi | \pi\in\sigma_n, \pi(i)=i, i\in T; \pi(j)\neq j, j\in S\setminus T\}|.
</math>

$f_\geq(T)$ {{---}} число перестановок, каждая из которых обладает всеми свойствами из $T$ и, возможно, какими-то еще:
<math>
f_\geq(T) = |\{\pi | \pi\in\sigma_n, \pi(i)=i, i\in T\}|.
</math>
Следовательно, верна формула: $f_\geq (T) = \sum_{T\subseteq Y\subseteq S} f_=(Y)$.

Нетрудно видеть, что $f_\geq(T) = |S\setminus T|!$ {{---}} число перестановок на множестве $S\setminus T$.

Очевидно, $D(n) = f_=(\varnothing)$. Следующее утверждение решает задачу.
{{Утверждение
|statement=$D(n) = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!}.$
|proof=Так как <math>f_\geq(T) = |S\setminus T|!</math>, то по формуле включения-исключения

<math>
D(n) = f_=(\varnothing)= \sum_{Y\subseteq S} (-1)^{|Y|} f_\geq(Y) = \sum_{Y\subseteq S} (-1)^{|Y|} |S\setminus Y|!=
</math>
<math>= \sum_{i=0}^{n} \sum_{\substack{Y\subseteq S,\\ |Y|=i}} (-1)^{i} (n-i)! =
\sum_{i=0}^{n} (-1)^i(n-i)!\binom{n}{i} =
</math>
<math>= \sum_{i=0}^{n} (-1)^i \frac{(n-i)! n!}{i! (n-i)!} = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!}.
</math>
}}

Конспект: [[Дискретная математика]]

[[Категория:Дискретная математика]]

Задача о беспорядках - История изменений

СВ в 13:51, 24 октября 2026

СВ: Новая страница: «== Интуитивная постановка задачи == {{Пример |content=Пусть в рамках чемпионата в $n$ городах до...»