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

Число решений уравнения $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]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ 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]\displaystyle{ |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]\displaystyle{ |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]\displaystyle{ |\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]\displaystyle{ a_i\leq b_i-y_i \leq b_i\quad \Rightarrow \quad 0\leq y_i \leq b_i-a_i. }[/math] Подставим замену в неравенство для суммы переменных: [math]\displaystyle{ (b_1 - y_1)+(b_2 - y_2) + \cdots + (b_k - y_k) \geq n, }[/math] [math]\displaystyle{ 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*} которая может быть решена указанным выше способом.