Количество целых решений уравнения дискретная математика формула

Метод подсчёта количества решений

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

В этой статье нас интересует частный случай линейного уравнения с несколькими переменными. Хорошо известно, что подобное уравнение имеет бесконечное число решений. Мы наложим определённые ограничения и в значительной степени сократим количество решений.

Общая форма интересующего нас уравнения:

где n и m — положительные целые числа.

Наша задача — найти число решений этого уравнения, предполагая, что xᵢ являются целыми числами. Это предположение значительно снижает число решений заданного уравнения.

Нам нужен метод

Давайте начнём с частного случая общего уравнения:

Нетрудно найти все решения этого уравнения методом простого счёта. Решения заданы парами (x₁, x₂):

Мы видим, что уравнение имеет шесть решений. Также нетрудно предположить, что, если мы заменим правую часть определённым положительным целым числом m, решения будут выглядеть так:

и мы сможем подсчитать число решений — m+1.

Это было просто, верно?

Теперь возьмём немного более сложный вариант с тремя переменными, скажем:

С несколько большими усилиями, чем в предыдущем примере, находим решения в виде наборов из трёх чисел (x₁, x₂, x₃):

Число решений в этом случае равно 10.

Легко представить, что метод прямого счёта может стать очень утомительным для уравнения с большим количеством переменных. Он также становится утомительным, если целое число в правой части уравнения становится больше — например, если в правой части у нас будет 8, а не 3, решений будет уже 45. Разумеется, не хотелось бы искать все эти решения методом прямого счёта.

Значит, нужен эффективный метод.

Разрабатываем метод

Существует ещё один способ, которым можно решить предыдущие два уравнения. Давайте снова начнём с этого уравнения:

Одним из решений было (5, 0). Давайте преобразуем его в:

Мы разложили решение на нули и единицы, соответствующие каждому числу. Ненулевую часть (в данном случае 5) мы разложили на соответствующее число единиц, а ноль преобразовали в ноль. Таким же образом мы можем разложить и другое решение:

Мы поменяли прежнее расположение нуля, чтобы получить новое решение. Итак, два числа в парах (обозначенные красным и голубым) разделены нулём (чёрный) в разложенном виде. Таким же образом запишем оставшиеся решения:

Записав решения таким образом, видим закономерность. Кажется, все решения — это просто перестановки нулей и единиц. Вопрос о том, сколько существует решений, становится эквивалентным вопросу как много таких перестановок нулей и единиц может быть сделано, начиная с любой из конфигураций.

В данном случае у нас есть 6 местоположений в разложенной конфигурации для размещения нулей и единиц. Мы можем выбрать простейшее решение в качестве начальной конфигурации:

Теперь всё, что нам нужно найти, это общее число способов, которыми можно заполнить шесть местоположений пятью единицами и одним нулём.

Подобные задачи подсчёта мы можем решить различными способами, но наиболее эффективным будет способ, разработанный в такой области математики как комбинаторика, которая даёт нам формулу для числа способов перестановки r объектов в n местоположений:

где n! (читается как “n факториал”) определяется как произведение всех целых чисел от 1 до n, т.е. n! = 1 × 2 × 3 × ⋅ ⋅ ⋅ × n. Мы также определяем 0! = 1.

Эта формула обычно записывается в компактной форме как:

Теперь, возвращаясь к задаче, мы можем использовать эту формулу для нахождения числа способов перестановки пяти единиц в шести местоположениях:

Это то же самое число, что мы получили методом прямого счёта!

Выглядит многообещающе, поэтому давайте проверим, сможем ли мы найти таким способом число решений второго линейного уравнения:

Некоторые решения можно записать в разложенном виде:

В этот раз нам нужно заполнить тремя единицами и двумя нулями пять местоположений. Используя формулу мы можем найти число способов расположения чисел:

И опять то же число, что мы получили методом прямого счёта. Мы можем также найти число решений для нерешённого случая, где в правой части уравнения 8 вместо 3. Одним из решений будет:

а нам нужно найти число способов разместить 8 единиц в 10 местоположениях, и это будет:

как и утверждалось выше.

Если мы уверены в том, что этот метод работает для всех случаев, нам нужна общая формула. Напомним, что общее уравнение имеет вид:

Простейшее решение этого уравнения:

Поскольку существует n переменных, количество нулей в этом решении равно n-1. Таким образом, разложение выглядит так:

В разложенной конфигурации видим m и n-1 нулей (как утверждалось выше).

Следовательно, общее число местоположений, которые нужно заполнить, равно (m+n-1). Единственное, что остаётся — найти число способов, которыми можно заполнить m+n-1 местоположений m единиц, что определяется по формуле:

Как рассчитать кол-во вариантов?

Сколько решений имеет уравнение x + y + z = 8:
a) в целых неотрицательных числах;
b) в целых положительных числах?

Сколько можно составить из цифр 1, 2, 3, 4:
a) двузначных чисел;
b) двузначных чисел с различными цифрами;

• Вопрос задан более трёх лет назад
• 4767 просмотров

Вы поставили совершенно верный тег — Комбинаторика. Этот раздел математики и начинался как метод подсчета количества различных вариантов/комбинаций.

Наиболее часто задачи на комбинаторику подразумевают последовательное фиксирование количества состояний переменных одной за одной.

Давайте начнем со второй задачи — она несколько проще.

2а) Первую цифру двузначного числа с заданными условиями можно выбрать 4 способами; после того как первая цифра определена, вторую можно выбрать снова 4 способами. Итого вариантов 4х4=16.
2б) Первую цифру двузначного числа с заданными условиями можно выбрать 4 способами; после того как первая цифра определена, вторую можно выбрать уже только тремя способами, т.к. цифра не может совпасть с той которая на первой позиции. Итого вариантов 4х3=12.

1а) Целых неотрицательных, которые могут сыграть роль «x», — 9 (от 0 до 8 включительно). После того как «x» зафиксирован, «y» может быть выбран (8-x+1) способами, например, если х=7, то остается для «y» только 0 и 1. После того как «х» и «y» зафиксированы, «z» всегда можно выбрать только 1 способом, следовательно, количество вариантов решений он не увеличивает. Осталось посчитать сумму кол-ва возможных комбинаций (считаем по «y»-кам) = (9+8+7+. +1) — по формуле суммы арифметической прогрессии — 10*9/2 = 45. И соответственно, Ваш ответ неверен.

1б) Аналогично, но уменьшая кол-во «x»-ов до 6 (от 1 до 6 включительно), а кол-во «y» до (7-х) способов. Сумма (6+5+. +1) = 7*6/2 = 21.

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки

Правила форума

В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе «Помогите решить/разобраться (М)».

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

Не ищите на этом форуме халяву , правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.

Формула для числа решений данного уравнения

Здравствуйте! Возникла такая проблема: дано уравнение , где — натуральное, — действительное из , а — простое число. — обозначает целую часть от числа.
При рациональных число решений данного уравнения задается формулой

Как называется эта формула и где можно раздобыть литературу о ней?

RIP
Заслуженный участник При любом эта формула дает число решений этого уравнения в натуральных числах и простых при условии, что . Док-во тривиально: достаточно поменять местами суммирование и интегрирование и воспользоваться тем фактом, что Добавлено спустя 2 минуты 51 секунду: Например, в книге Вон Р. — Метод Харди-Литтлвуда можно почитать, как это помогает находить асимптотику числа решений для некоторых диофантовых уравнений.

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей