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

2026-10-24T13:48:27Z

← Предыдущая		Версия 13:48, 24 октября 2026
Строка 17:		Строка 17:
	f_\geq (T) = \sum_{T\subseteq Y\subseteq S} f_=(Y).		f_\geq (T) = \sum_{T\subseteq Y\subseteq S} f_=(Y).
	</math>		</math>

			[[Файл:p29-01-exact-vs-atleast.svg\|frame\|none\|900px\|alt=Диаграмма Венна с точными классами и четыре суммы f≥, собранные из этих классов\|Рис. 1. <math>f_=(Y)</math> — элементы ровно с набором свойств <math>Y</math>, а <math>f_\geq(T)</math> — все элементы, у которых есть все свойства <math>T</math>. Для двух свойств суммы получаются сложением точных классов: <math>f_\geq(\varnothing)=1+2+1+2=6</math>, <math>f_\geq(\{1\})=2+2=4</math> и так далее.]]

	Далее нам бы хотелось найти обратное соотношение. То есть способ находить		Далее нам бы хотелось найти обратное соотношение. То есть способ находить
Строка 59:		Строка 61:
	</math>		</math>
	}}		}}

			[[Файл:p29-02-inclusion-exclusion-signs.svg\|frame\|none\|900px\|alt=Знакопеременные суммы f≥ для T = ∅ и T = {1}, дающие 1 и 2\|Рис. 2. Обратная формула: <math>f_=(T)</math> — знакопеременная сумма <math>f_\geq(Y)</math> по всем <math>Y\supseteq T</math>. Слева <math>T=\varnothing</math>: <math>6-4-3+2=1</math>; справа <math>T=\{1\}</math>: в сумму входят только <math>\{1\}</math> и <math>\{1,2\}</math>, поэтому <math>4-2=2</math>.]]

			[[Файл:p29-03-cancellation-table.svg\|frame\|none\|900px\|alt=Таблица вкладов шести элементов в знакопеременную сумму: у элемента без свойств вклад 1, у остальных 0\|Рис. 3. Почему знаки сокращаются: элемент входит в те <math>f_\geq(Y)</math>, для которых <math>Y\subseteq g(a)</math>. У <math>a_1</math> без свойств остаётся только <math>+1</math>, у остальных элементы со знаками <math>+1</math> и <math>-1</math> взаимно уничтожаются, поэтому итог равен 1.]]

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

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

СВ: Новая страница: «Пусть $A$ {{---}} заданное множество и $S$ {{---}} множество свойств (множество, элементы которого...»

2026-10-11T10:03:49Z

Новая страница: «Пусть $A$ {{---}} заданное множество и $S$ {{---}} множество свойств (множество, элементы которого...»

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

Пусть $A$ {{---}} заданное множество и $S$ {{---}} множество свойств (множество, элементы которого будут называться свойствами).
Каждый элемент из $A$ может обладать некоторыми свойствами из $S$.
Другими словами, задана функция, сопоставляющая каждому элементу из $A$ некоторое подмножество множества $S$: $g: A \rightarrow 2^S$.
Будем говорить, что элемент $a$ обладает свойствами $g(a)$.

Пусть $T\subseteq S$.
Обозначим $f_=(T)$ {{---}} число элементов из множества $A$, которые обладают всеми
свойствами из $T$ и не обладают свойствами из множества $S\setminus T$;
$f_=(T) = \left|\{a: a\in A\textrm, T = g(a)\}\right|$.

$f_\geq(T)$ {{---}} число элементов из $A$, которые обладают всеми свойствами из $T$ и, возможно, какими-то еще.

$f_\geq(T) = \left|\{a: a\in A\textrm, T\subseteq g(a)\}\right|$.

Тогда очевидно, что
<math>
f_\geq (T) = \sum_{T\subseteq Y\subseteq S} f_=(Y).
</math>

Далее нам бы хотелось найти обратное соотношение. То есть способ находить
значение функции $f_=$, зная значения функции $f_\geq$.

Пусть $\varphi: 2^S\rightarrow \mathbb{R}$ {{---}} произвольная функция, сопоставляющая каждому подмножеству конечного множества $S$ некоторое вещественное число.
Пусть $\psi$ {{---}} такая функция из $2^S$ в $\mathbb{R}$, что
<math>
\psi(T) = \sum_{T\subseteq Y\subseteq S} \varphi(Y),\quad \forall T\subseteq S.
</math>

Тогда
<math>
\varphi(T) = \sum_{T\subseteq Y\subseteq S} (-1)^{|Y\setminus T|} \psi(Y),\quad \forall T\subseteq S.
</math>

'''Доказательство.'''
Пусть $T\subseteq S$.

Тогда
<math>\sum_{T\subseteq Y\subseteq S} (-1)^{|Y\setminus T|} \psi(Y)=
\sum_{T\subseteq Y\subseteq S} (-1)^{|Y\setminus T|} \sum_{Y\subseteq Z\subseteq S} \varphi(Z)=
</math>
<math>= \sum_{T\subseteq Y\subseteq Z\subseteq S} (-1)^{|Y\setminus T|} \varphi(Z)=
\sum_{T\subseteq Z\subseteq S} \varphi(Z) \sum_{T\subseteq Y\subseteq Z} (-1)^{|Y\setminus T|} =
</math>
<math>= \sum_{T\subseteq Z\subseteq S} \varphi(Z) \sum_{i=0}^{|Z\setminus T|}\sum_{\substack{T\subseteq Y\subseteq Z,\\ |Y|=|T|+i}} (-1)^{|Y\setminus T|} =
\sum_{T\subseteq Z\subseteq S} \varphi(Z) \sum_{i=0}^{|Z\setminus T|} (-1)^{i} \binom{|Z\setminus T|}{i}= \sum_{T\subseteq Z\subseteq S}\varphi(Z)\delta_o(|Z\setminus T|) = \varphi(T).
</math>

Здесь $\delta_o(n)$ {{---}} дельта-функция.

{{Следствие
|statement=Поскольку $f_\geq (T) = \sum_{T\subseteq Y\subseteq S} f_=(Y)$, то для любого $T\subseteq S$
<math> \label{equation:include-exclude}
f_=(T) = \sum_{T\subseteq Y\subseteq S} (-1)^{|Y\setminus T|} f_\geq(Y).
</math>

В частности,
<math> \label{equation:include-exclude_varnothing}
f_=(\varnothing) = \sum_{Y\subseteq S} (-1)^{|Y|} f_\geq(Y).
</math>
}}

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

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

Принцип включения-исключения - История изменений

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

СВ: Новая страница: «Пусть $A$ {{---}} заданное множество и $S$ {{---}} множество свойств (множество, элементы которого...»