СВ в 14:18, 24 октября 2026

2026-10-24T14:18:27Z

← Предыдущая		Версия 14:18, 24 октября 2026
Строка 177:		Строка 177:
	\|A_3\| = \binom{30+3-14}{3} = 969.		\|A_3\| = \binom{30+3-14}{3} = 969.
	\end{align*}		\end{align*}

			[[Файл:p32-01-bounded-solutions.svg\|мини\|600px\|alt=Таблица слагаемых: 2925 − 560 − 969 − 969 + 56 + 56 + 165 − 0 = 704\|Рис. 1. Из <math>2925</math> решений без верхних границ вычитаем <math>560</math>, <math>969</math> и <math>969</math> решений, нарушающих одну границу, прибавляем попарные пересечения <math>56</math>, <math>56</math>, <math>165</math> и вычитаем пустое тройное пересечение. Итого <math>704</math>.]]

	Также рассмотрим все возможные пересечения этих множеств и посчитаем их мощности.		Также рассмотрим все возможные пересечения этих множеств и посчитаем их мощности.
Строка 256:		Строка 258:
	&- 969 + 56 + 56 + 165 = 704.		&- 969 + 56 + 56 + 165 = 704.
	\end{align*}		\end{align*}


	Рассмотрим теперь систему с ограничением на сумму переменных снизу:		Рассмотрим теперь систему с ограничением на сумму переменных снизу:

СВ в 10:40, 11 октября 2026

2026-10-11T10:40:04Z

← Предыдущая		Версия 10:40, 11 октября 2026
Строка 282:		Строка 282:
	\end{align*}		\end{align*}
	которая может быть решена указанным выше способом.		которая может быть решена указанным выше способом.

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

СВ: Новая страница: «Число решений уравнения $x_1+x_2+\cdots + x_k = n$ в неотрицательн...»

2026-10-11T10:39:44Z

Новая страница: «Число решений уравнения $x_1+x_2+\cdots + x_k = n$ в неотрицательн...»

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

[[Композиция натурального числа|Число решений уравнения]] $x_1+x_2+\cdots + x_k = n$ в неотрицательных целых числах находится по формуле:
$N_=(n,k) = \binom{n+k-1}{k-1}$,
а число решений неравенства $x_1+x_2+\cdots + x_k \leq n$
в неотрицательных целых числах {{---}} по формуле: $N_\leq(n,k) = \binom{n+k}{k}$.

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

Для начала положим, что на значения переменных наложены ограничения снизу.
Пусть $a_i\in \mathbb{N}_0$, $i=\overline{1,k}$, и задана система
\begin{align*}
x_1&+x_2+\cdots + x_k = n, \\
&a_i\leq x_i,\quad i=\overline{1,k}.
\end{align*}
Чтобы найти число решений этой системы, достаточно сделать замену $y_i = x_i - a_i$.

Тогда $y_i\geq 0$ и
\begin{align*}
&(y_1 + a_1) + (y_2+a_2) + \cdots + (y_k+a_k) = n, \\
&y_1+ y_2+\cdots + y_k = n-a_1 -a_2 - \cdots - a_k.
\end{align*}

Согласно формуле, число целочисленных решений данной системы
<math> \label{equation:x_1+...x_k=n,a_i \leq x_i}
\binom{n +k - 1 -\sum_{i=1}^k a_i}{k-1}.
</math>

Аналогично, число решений системы
\begin{align*}
x_1&+x_2+\cdots + x_k \leq n, \\
&a_i\leq x_i,\quad i=\overline{1,k},
\end{align*}
равно
<math> \label{equation:x_1+...x_k \leq n,a_i \leq x_i}
\binom{n +k -\sum_{i=1}^k a_i}{k}.
</math>

Рассмотрим систему с ограничениями на переменные и сверху, и снизу.
Пусть $a_i, b_i\in \mathbb{N}_0$, $a_i\leq b_i$, $i=\overline{1,k}$.
Требуется найти число целочисленных решений системы
\begin{align}
x_1&+x_2+\cdots + x_k = n, \label{align:x_1+...x_k=n,a_i \leq x_i \leq b_i;1} \\
&a_i\leq x_i\leq b_i,\quad i=\overline{1,k}. \label{align:x_1+...x_k=n,a_i \leq x_i \leq b_i;2}
\end{align}

Пусть $A$ {{---}} множество решений системы
\begin{align*} \tag{*}
x_1&+x_2+\cdots + x_k = n,
\\
&a_i\leq x_i,\quad i=\overline{1,k}:
\end{align*}
<math>
A = \{(\alpha_1, \alpha_2,...,\alpha_k) | \alpha_1+\alpha_2 + \cdots \alpha_k = n,
a_i\leq \alpha_i, i=\overline{1,k}\}.
</math>
Согласно формулы для числа решений уравнения: <math>|A| = \binom{n +k - 1 -\sum_{i=1}^k a_i}{k-1}.</math>

Обозначим $A_s$, $s=\overline{1,k}$, {{---}} множество решений системы (*), для которых не выполняется
ограничение $x_s\leq b_s$:
\begin{align*}
A_s = \{(\alpha_1, \alpha_2,...,\alpha_k) | &\alpha_1+\alpha_2 + \cdots \alpha_k = n,
\\ & a_i\leq \alpha_i, i=\overline{1,k}, b_s+1\leq \alpha_s\}.
\end{align*}

Таким образом, все решения системы (*), которые не удовлетворяют
хотя бы одной верхней границе, лежат в множестве $A_1\cup A_2\cup ... \cup A_k$.
Следовательно, число решений системы равно
<math>|A\setminus(A_1\cup A_2\cup ... \cup A_k)| = |A|-|A_1\cup A_2\cup ... \cup A_k|.</math>
Использовав утверждение для пересечения множеств, получим
\begin{align*}
|A|-|A_1\cup A_2\cup ... \cup A_k| =
|A| - \sum_{\substack{Y\subseteq \{1,...,k\},\\ |Y|\geq 1}} (-1)^{|Y|-1} |\bigcap_{i\in Y} A_i|. \tag{**}
\end{align*}

Теперь, чтобы найти число решений системы, достаточно
научиться находить мощность пересечения произвольного набора множеств $A_j$.

Пусть $Y\subseteq \{1,...,k\}$. Тогда
\begin{align*}
\bigcap_{j\in Y} A_j = \{(\alpha_1, \alpha_2,...,\alpha_k) | &\alpha_1+\alpha_2 + \cdots \alpha_k = n,
\\ & a_i\leq \alpha_i, i=\overline{1,k}, b_s+1\leq \alpha_s, s\in Y\}.
\end{align*}
Другими словами, $\bigcap_{j\in Y} A_j$ есть множество решений системы
\begin{align*}
&x_1+x_2+\cdots + x_k = n, \\
&a_i\leq x_i, i\in\{1,...,k\}\setminus Y,\quad b_s+1\leq x_s, s\in Y.
\end{align*}

Тогда
<math>
|\bigcap_{i\in Y} A_i| =
\binom{n +k - 1 -\sum_{i=1}^k a_i - \sum_{j\in Y} (b_j+1-a_j)}{k-1}.
</math>
Подставив эти значения в формулу (**), получим число решений системы.

Рассуждения для системы
\begin{align*}
x_1&+x_2+\cdots + x_k \leq n,
\\
&a_i\leq x_i\leq b_i,\quad i=\overline{1,k}.
\end{align*}
аналогичны проведенным ранее рассуждениям равенства на неравенство.

'''Пример. '''
Пусть дана система неравенств
$x_1+x_2+x_3 \leq 30$,
$0 \leq x_1 \leq 10$,
$5 \leq x_2 \leq 12$,
$1 \leq x_3 \leq 8$.

Обозначим за $A$ множество целочисленных решений исходной системы без учета верхних границ на значение переменных:
\begin{equation*}
\begin{array}{c}
x_1+x_2+x_3 \leq 30,
\\
0 \leq x_1,
5 \leq x_2,
1 \leq x_3.
\end{array} \tag{*}
\end{equation*}
Число целочисленных решений системы $(*)$ вычисляем по известной формуле:
\begin{align*}
|A| &= \binom{n+k-\sum s_i}{k} = \binom{30+3-6}{3} = \binom{27}{3} =
\frac{27!}{3!\cdot 24!} = \\
&= \frac{27\cdot 26\cdot 25}{6} = 2925.
\end{align*}

Обозначим за $A_i$ множество целочисленных решений исходной системы $(*)$, которые не удовлетворяют верхней границе исходной системы на значение $x_i$, $i=\overline{1,3}$.
\begin{equation*}
A_1:\qquad
\begin{array}{c}
x_1+x_2+x_3 \leq 30,
\\
11 \leq x_1,
\qquad
5 \leq x_2,
\qquad
1 \leq x_3.
\end{array}
\end{equation*}
\begin{equation*}
A_2:\qquad
\begin{array}{c}
x_1+x_2+x_3 \leq 30,
\\
0 \leq x_1,
\qquad
13 \leq x_2,
\qquad
1 \leq x_3.
\end{array}
\end{equation*}
\begin{equation*}
A_3:\qquad
\begin{array}{c}
x_1+x_2+x_3 \leq 30,
\\
0 \leq x_1,
\qquad
5 \leq x_2,
\qquad
9 \leq x_3.
\end{array}
\end{equation*}

Посчитаем мощности этих множеств.
\begin{align*}
|A_1| = \binom{30+3-17}{3} = \binom{16}{3} =
\frac{16!}{3!\cdot 13!}
= \frac{16\cdot 15\cdot 14}{6} = 560.
\end{align*}
\begin{align*}
|A_2| = \binom{30+3-14}{3} = \binom{19}{3} =
\frac{19!}{3!\cdot 16!}
= \frac{19\cdot 18\cdot 17}{6} = 969.
\end{align*}
\begin{align*}
|A_3| = \binom{30+3-14}{3} = 969.
\end{align*}

Также рассмотрим все возможные пересечения этих множеств и посчитаем их мощности.
\begin{equation*}
A_1\cap A_2:\qquad
\begin{array}{c}
x_1+x_2+x_3 \leq 30,
\\
11 \leq x_1,
\qquad
13 \leq x_2,
\qquad
1 \leq x_3.
\end{array}
\end{equation*}
\begin{align*}
|A_1\cap A_2| = \binom{30+3-25}{3} = \binom{8}{3} =
\frac{8!}{3!\cdot 5!}
= \frac{8\cdot 7\cdot 6}{6} = 56.
\end{align*}

\begin{equation*}
A_1\cap A_3:\qquad
\begin{array}{c}
x_1+x_2+x_3 \leq 30,
\\
11 \leq x_1,
\qquad
5 \leq x_2,
\qquad
9 \leq x_3.
\end{array}
\end{equation*}
\begin{align*}
|A_1\cap A_3| = \binom{30+3-25}{3} = 56.
\end{align*}

\begin{equation*}
A_2\cap A_3:\qquad
\begin{array}{c}
x_1+x_2+x_3 \leq 30,
\\
0 \leq x_1,
\qquad
13 \leq x_2,
\qquad
9 \leq x_3.
\end{array}
\end{equation*}
\begin{align*}
|A_2\cap A_3| = \binom{30+3-22}{3} = \binom{11}{3} =
\frac{11!}{3!\cdot 8!}
= \frac{11\cdot 10\cdot 9}{6} = 165.
\end{align*}

\begin{equation*}
A_1\cap A_2\cap A_3:\qquad
\begin{array}{c}
x_1+x_2+x_3 \leq 30,
\\
11 \leq x_1,
\qquad
13 \leq x_2,
\qquad
9 \leq x_3.
\end{array}
\end{equation*}
\begin{align*}
|A_1\cap A_2\cap A_3| = \binom{30+3-33}{3} = 0.
\end{align*}

Теперь количество целочисленных решений исходной системы можно получить
по формуле:
\begin{align*}
&|A|-|A_1\cup A_2\cup A_3| =
|A| - (|A_1|+|A_2|+|A_3|-|A_1\cap A_2| -\\
&- |A_1\cap A_3| - |A_2\cap A_3| + |A_1\cap A_2\cap A_3|) =
2925 - 560 - 969 -\\
&- 969 + 56 + 56 + 165 = 704.
\end{align*}

Рассмотрим теперь систему с ограничением на сумму переменных снизу:
\begin{align*}
x_1&+x_2+\cdots + x_k \geq n,
\\
&a_i\leq x_i\leq b_i,\quad i=\overline{1,k}.
\end{align*}

Сделаем замену переменных $y_i = b_i - x_i$. Тогда ограничения на значения переменных трансформируются следующим образом:
<math>
a_i\leq b_i-y_i \leq b_i\quad \Rightarrow \quad 0\leq y_i \leq b_i-a_i.
</math>
Подставим замену в неравенство для суммы переменных:
<math>
(b_1 - y_1)+(b_2 - y_2) + \cdots + (b_k - y_k) \geq n,
</math>
<math>
y_1+y_2 + \cdots + y_k \leq b_1 + b_2 + \cdots + b_k - n.
</math>

Получили систему
\begin{align*}
y_1&+y_2+\cdots + y_k \leq \sum_{i=1}^k b_i - n, \\
&0\leq y_i\leq b_i-a_i,\quad i=\overline{1,k},
\end{align*}
которая может быть решена указанным выше способом.

Число целочисленных решений системы неравенств - История изменений

СВ в 14:18, 24 октября 2026

СВ в 10:40, 11 октября 2026

СВ: Новая страница: «Число решений уравнения $x_1+x_2+\cdots + x_k = n$ в неотрицательн...»