17. Сколько решений у уравнения x₁+…+xₙ=k
Решение уравнения в целых неотрицательных числах — это раздача единиц по переменным, то есть то же самое, что сочетание с повторениями: . Положительные решения и решения с нижними границами сводятся к этому «сдвигом»: заранее отдаём то, что переменные обязаны получить, а остаток раздаём свободно.
Что пригодится из прошлого: сочетания с повторениями — слово из единиц и звёздочек, формула ; сочетания. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Решение — это раздача единиц
Сколько существует решений уравнения
в целых неотрицательных числах ()? Выпишем их все. Рядом — слово из единиц и звёздочек: сколько единиц в первом, втором и третьем блоках, столько получила каждая переменная.
| Слово | |
|---|---|
| (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: положительные решения
Задача. Найти число целых положительных решений того же уравнения ().
Теперь каждая переменная должна получить хотя бы единицу. Выдадим эту единицу заранее: . Тогда
и это задача 1 для единиц:
Последнее равенство — симметрия : здесь .
Слово в алфавите теперь содержит единиц в -м блоке. Его длина , звёздочек . Итог:
Пример. в натуральных числах. По формуле . Решения: (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: нижние границы
Задача. Найти число целых решений уравнения , в которых () и .
Тот же приём: каждая переменная заранее получает свои единиц. Положим . Тогда
Слово из единиц и звёздочек имеет длину
и содержит звёздочку. Поэтому число решений равно
Как читать. Верхнее число — сколько единиц осталось раздать плюс перегородок; нижнее — сколько перегородок. Условие нужно, чтобы остаток был неотрицательным. Если , решений нет.
Пример. , , , . Заранее раздаём единиц; остаётся единиц на свободную раздачу трём переменным:
Если в условии неравенство
Уравнение удобно получать и из неравенства. Например, сколько существует пар целых неотрицательных чисел , у которых ? Добавим «запасную» переменную . Тогда , и ответ равен числу неотрицательных решений этого уравнения: .
Раздача предметов
Те же формулы решают задачи про раздачу одинаковых предметов.
- одинаковых конфет четырём детям, каждому можно и ничего: .
- Те же конфеты, но каждый получает хотя бы одну: .
Дети разные, поэтому «кому сколько досталось» — упорядоченный набор .
Частые ошибки
- Спутать положительные и неотрицательные решения. Для неотрицательных , для положительных .
- Считать « и — одно и то же». Решение — упорядоченный набор значений: переменные различимы.
- Забыть вычесть нижние границы. Переходите к и заменяйте на .
- Раздавать «больше, чем есть». Если , решений нет, и формулу применять нельзя.
Проверь себя
1. Сколько существует целых неотрицательных решений уравнения ?
Решение
, : .
2. Сколько у этого же уравнения положительных решений?
Решение
.
3. Сколько решений у уравнения при условиях , , ?
Решение
Раздаём заранее единицы; остаётся . Три переменные: .
4. Сколькими способами можно разложить одинаковых монет по трём карманам (в карман можно не положить ничего)?
Решение
Раздача единиц трём переменным: .
5. Сколько существует пар целых неотрицательных чисел , для которых ?
Решение
Неравенство превращается в равенство добавлением «запасной» переменной : . Значит, ответ равен числу неотрицательных решений этого уравнения: . Проверка перечислением: при значений соответственно , всего .
Итог
- Неотрицательные решения : .
- Положительные решения: .
- Нижние границы : заменить на и на ; ответ .
- Решения — упорядоченные наборы значений, переменные различимы.
