Номер 4.42, страница 113 - гдз по алгебре 10 класс учебник Шыныбеков, Шыныбеков

4.42 Сколько целых неотрицательных решений имеет уравнение $x_1 + x_2 + \dots + x_n = k$?

Данная задача заключается в поиске количества целых неотрицательных решений для линейного уравнения. Это классическая задача комбинаторики, которая решается с помощью метода, известного как "шары и перегородки" (или "stars and bars").

Мы ищем количество наборов $(x_1, x_2, \ldots, x_n)$, где каждое $x_i$ является целым числом и $x_i \ge 0$, таких что их сумма равна $k$.

Представим, что у нас есть $k$ одинаковых единиц (назовем их "шарами"), которые нужно распределить между $n$ переменными (назовем их "ящиками"). Чтобы разделить шары на $n$ групп, нам потребуется $n-1$ "перегородка".

Например, для уравнения $x_1 + x_2 + x_3 = 5$, одно из возможных решений $x_1=2, x_2=1, x_3=2$ можно визуализировать как последовательность из 5 шаров (●) и $3-1=2$ перегородок (|):

Здесь 2 шара до первой перегородки соответствуют $x_1=2$, 1 шар между перегородками — $x_2=1$, и 2 шара после второй перегородки — $x_3=2$. Другое решение, например $x_1=4, x_2=0, x_3=1$, будет выглядеть так:

Таким образом, каждое решение уравнения однозначно соответствует расположению $k$ шаров и $n-1$ перегородок в ряд. Задача сводится к нахождению числа таких расположений.

Всего у нас имеется $k + (n-1)$ позиций в ряду. Нам нужно выбрать из этих $k+n-1$ позиций те $n-1$ мест, куда мы поставим перегородки (остальные места автоматически будут заняты шарами). Число способов сделать это равно числу сочетаний из $k+n-1$ по $n-1$.

Формула для числа сочетаний без повторений из $N$ по $K$ имеет вид: $C_N^K = \binom{N}{K} = \frac{N!}{K!(N-K)!}$.

В нашей задаче общее число позиций $N = k+n-1$, а число выбираемых позиций для перегородок $K = n-1$. Подставляя эти значения, получаем:

$C_{k+n-1}^{n-1} = \binom{k+n-1}{n-1} = \frac{(k+n-1)!}{(n-1)!((k+n-1)-(n-1))!} = \frac{(k+n-1)!}{(n-1)!k!}$

Эта величина также известна как число сочетаний с повторениями из $n$ по $k$ и обозначается как $\overline{C}_n^k$. Заметим, что $C_{n+k-1}^{n-1} = C_{n+k-1}^{k}$, так как выбор $n-1$ мест для перегородок эквивалентен выбору $k$ мест для шаров.

Ответ: Уравнение имеет $C_{n+k-1}^{k} = \frac{(n+k-1)!}{k!(n-1)!}$ целых неотрицательных решений.