bulgakov

17. Сколько решений у уравнения x₁+…+xₙ=k

Решение уравнения x1+x2+⋯+xn=kx_1+x_2+\dots+x_n=k в целых неотрицательных числах — это раздача kk единиц по nn переменным, то есть то же самое, что сочетание с повторениями: (n+k−1k)\dbinom{n+k-1}{k}. Положительные решения и решения с нижними границами сводятся к этому «сдвигом»: заранее отдаём то, что переменные обязаны получить, а остаток раздаём свободно.

Что пригодится из прошлого: сочетания с повторениями — слово из единиц и звёздочек, формула (n+r−1r)\dbinom{n+r-1}{r}; сочетания. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.

Решение — это раздача единиц

Сколько существует решений уравнения

x+y+z=3x+y+z=3

в целых неотрицательных числах (x,y,z≥0x,y,z\ge0)? Выпишем их все. Рядом — слово из единиц и звёздочек: сколько единиц в первом, втором и третьем блоках, столько получила каждая переменная.

(x,y,z)(x, y, z) Слово
(0, 0, 3) ∗∗111
(0, 1, 2) ∗1∗11
(0, 2, 1) ∗11∗1
(0, 3, 0) ∗111∗
(1, 0, 2) 1∗∗11
(1, 1, 1) 1∗1∗1
(1, 2, 0) 1∗11∗
(2, 0, 1) 11∗∗1
(2, 1, 0) 11∗1∗
(3, 0, 0) 111∗∗

Решений десять. Заметим, что (1,2,0)(1,2,0) и (2,1,0)(2,1,0) — разные решения: переменные x,y,zx,y,z не равноправны, у каждой своё место.

Задача 1: неотрицательные решения

Задача. Найти число целых неотрицательных решений уравнения

x1+x2+⋯+xn=k(n,k∈N).x_1+x_2+\dots+x_n=k\qquad(n,k\in\mathbb N).

Каждому решению (x1,x2,…,xn)(x_1,x_2,\dots,x_n) сопоставим слово в алфавите {1,∗}\{1,\ast\}: сначала x1x_1 единиц, затем звёздочка, затем x2x_2 единиц, звёздочка и так далее, в конце xnx_n единиц. Слово имеет длину n+k−1n+k-1 и содержит kk единиц и n−1n-1 звёздочек. По слову решение восстанавливается однозначно. Поэтому число решений совпадает с числом сочетаний с повторениями из nn элементов по kk:

(nk)~=(n+k−1k).\boxed{\widetilde{\binom nk}=\binom{n+k-1}{k}}.

Для x+y+z=3x+y+z=3: (3+3−13)=(53)=10\dbinom{3+3-1}{3}=\dbinom53=10 — как в таблице.

Задача 2: положительные решения

Задача. Найти число целых положительных решений того же уравнения (xi≥1x_i\ge1).

Теперь каждая переменная должна получить хотя бы единицу. Выдадим эту единицу заранее: yi=xi−1≥0y_i=x_i-1\ge0. Тогда

y1+y2+⋯+yn=k−n,y_1+y_2+\dots+y_n=k-n,

и это задача 1 для k−nk-n единиц:

((k−n)+n−1k−n)=(k−1k−n)=(k−1n−1).\binom{(k-n)+n-1}{k-n}=\binom{k-1}{k-n}=\binom{k-1}{n-1}.

Последнее равенство — симметрия (ab)=(aa−b)\dbinom ab=\dbinom a{a-b}: здесь (k−1)−(k−n)=n−1(k-1)-(k-n)=n-1.

Слово в алфавите {1,∗}\{1,\ast\} теперь содержит xi−1x_i-1 единиц в ii-м блоке. Его длина (x1−1)+⋯+(xn−1)+n−1=k−n+n−1=k−1(x_1-1)+\dots+(x_n-1)+n-1=k-n+n-1=k-1, звёздочек n−1n-1. Итог:

(k−1n−1).\boxed{\binom{k-1}{n-1}}.

Пример. x+y+z=6x+y+z=6 в натуральных числах. По формуле (52)=10\dbinom{5}{2}=10. Решения: (1, 1, 4), (1, 2, 3), (1, 3, 2), (1, 4, 1), (2, 1, 3), (2, 2, 2), (2, 3, 1), (3, 1, 2), (3, 2, 1), (4, 1, 1).

Задача 3: нижние границы

Задача. Найти число целых решений уравнения x1+x2+⋯+xn=kx_1+x_2+\dots+x_n=k, в которых xi≥aix_i\ge a_i (ai∈Z≥0a_i\in\mathbb Z_{\ge0}) и a1+a2+⋯+an≤ka_1+a_2+\dots+a_n\le k.

Тот же приём: каждая переменная заранее получает свои aia_i единиц. Положим yi=xi−ai≥0y_i=x_i-a_i\ge0. Тогда

y1+⋯+yn=k−∑i=1nai.y_1+\dots+y_n=k-\sum_{i=1}^{n}a_i.

Слово из единиц и звёздочек имеет длину

(x1−a1)+⋯+(xn−an)+n−1=k−∑i=1nai+n−1(x_1-a_1)+\dots+(x_n-a_n)+n-1=k-\sum_{i=1}^{n}a_i+n-1

и содержит n−1n-1 звёздочку. Поэтому число решений равно

( k−∑i=1nai+n−1 n−1).\boxed{\binom{\,k-\sum_{i=1}^{n}a_i+n-1\,}{n-1}}.

Как читать. Верхнее число — сколько единиц осталось раздать плюс n−1n-1 перегородок; нижнее — сколько перегородок. Условие ∑ai≤k\sum a_i\le k нужно, чтобы остаток был неотрицательным. Если ∑ai>k\sum a_i>k, решений нет.

Пример. x1+x2+x3=12x_1+x_2+x_3=12, x1≥2x_1\ge2, x2≥3x_2\ge3, x3≥1x_3\ge1. Заранее раздаём 2+3+1=62+3+1=6 единиц; остаётся 12−6=612-6=6 единиц на свободную раздачу трём переменным:

(6+3−13−1)=(82)=28.\binom{6+3-1}{3-1}=\binom82=28.

Если в условии неравенство

Уравнение удобно получать и из неравенства. Например, сколько существует пар целых неотрицательных чисел (x1,x2)(x_1,x_2), у которых x1+x2≤3x_1+x_2\le3? Добавим «запасную» переменную x3=3−x1−x2≥0x_3=3-x_1-x_2\ge0. Тогда x1+x2+x3=3x_1+x_2+x_3=3, и ответ равен числу неотрицательных решений этого уравнения: (3+3−12)=10\dbinom{3+3-1}{2}=10.

Раздача предметов

Те же формулы решают задачи про раздачу одинаковых предметов.

  • 1010 одинаковых конфет четырём детям, каждому можно и ничего: (10+4−13)=(133)=286\dbinom{10+4-1}{3}=\dbinom{13}{3}=286.
  • Те же конфеты, но каждый получает хотя бы одну: (93)=84\dbinom{9}{3}=84.

Дети разные, поэтому «кому сколько досталось» — упорядоченный набор (x1,x2,x3,x4)(x_1,x_2,x_3,x_4).

Частые ошибки

  • Спутать положительные и неотрицательные решения. Для неотрицательных (n+k−1n−1)\dbinom{n+k-1}{n-1}, для положительных (k−1n−1)\dbinom{k-1}{n-1}.
  • Считать «(1,2,0)(1,2,0) и (2,1,0)(2,1,0) — одно и то же». Решение — упорядоченный набор значений: переменные различимы.
  • Забыть вычесть нижние границы. Переходите к yi=xi−aiy_i=x_i-a_i и заменяйте kk на k−∑aik-\sum a_i.
  • Раздавать «больше, чем есть». Если ∑ai>k\sum a_i>k, решений нет, и формулу применять нельзя.

Проверь себя

1. Сколько существует целых неотрицательных решений уравнения x1+x2+x3+x4=10x_1+x_2+x_3+x_4=10?

Решение

n=4n=4, k=10k=10: (10+4−13)=(133)=286\dbinom{10+4-1}{3}=\dbinom{13}{3}=286.

2. Сколько у этого же уравнения положительных решений?

Решение

(k−1n−1)=(93)=84\dbinom{k-1}{n-1}=\dbinom93=84.

3. Сколько решений у уравнения x1+x2+x3=9x_1+x_2+x_3=9 при условиях x1≥1x_1\ge1, x2≥2x_2\ge2, x3≥0x_3\ge0?

Решение

Раздаём заранее 1+2+0=31+2+0=3 единицы; остаётся 9−3=69-3=6. Три переменные: (6+3−12)=(82)=28\dbinom{6+3-1}{2}=\dbinom82=28.

4. Сколькими способами можно разложить 88 одинаковых монет по трём карманам (в карман можно не положить ничего)?

Решение

Раздача 88 единиц трём переменным: (8+3−12)=(102)=45\dbinom{8+3-1}{2}=\dbinom{10}{2}=45.

5. Сколько существует пар целых неотрицательных чисел (x1,x2)(x_1,x_2), для которых x1+x2≤3x_1+x_2\le3?

Решение

Неравенство превращается в равенство добавлением «запасной» переменной x3≥0x_3\ge0: x1+x2+x3=3x_1+x_2+x_3=3. Значит, ответ равен числу неотрицательных решений этого уравнения: (3+3−12)=(52)=10\dbinom{3+3-1}{2}=\dbinom52=10. Проверка перечислением: при x1=0,1,2,3x_1=0,1,2,3 значений x2x_2 соответственно 4,3,2,14,3,2,1, всего 1010.

Итог

  • Неотрицательные решения x1+⋯+xn=kx_1+\dots+x_n=k: (n+k−1k)\dbinom{n+k-1}{k}.
  • Положительные решения: (k−1n−1)\dbinom{k-1}{n-1}.
  • Нижние границы xi≥aix_i\ge a_i: заменить xix_i на xi−aix_i-a_i и kk на k−∑aik-\sum a_i; ответ (k−∑ai+n−1n−1)\dbinom{k-\sum a_i+n-1}{n-1}.
  • Решения — упорядоченные наборы значений, переменные различимы.
ПрактикаЗагружаем тест…