Question

Назовём упорядоченным разбиением натурального числа представление его в виде суммы натуральных чисел. Вот, например, все шесть разбиений числа 5 на сумму трёх слагаемых:
1  + 1 + 3, 1 + 2 + 2, 1 + 3 + 1,
2  + 1 + 2, 2 + 2 + 1, 3 + 1 + 1 Сколько существует упорядоченных разбиений:
а)  числа 6 на сумму трёх слагаемых;
б)  числа 7 на сумму четырёх слагаемых?

Answer 1

Дано:  
n = 6, k = 3.  

Найти:  
а) количество упорядоченных разбиений числа 6 на сумму трех слагаемых.  

Решение:  
Чтобы найти количество упорядоченных разбиений, можно использовать метод "звёзд и палочек". Мы ищем неотрицательные решения уравнения:  
x1 + x2 + x3 = 6, где x1, x2, x3 > 0.  

Перепишем уравнение, введя новые переменные:  
y1 = x1 - 1, y2 = x2 - 1, y3 = x3 - 1, где y1, y2, y3 >= 0.  
Тогда уравнение становится:  
y1 + y2 + y3 = 3.  

Количество решений уравнения можно найти по формуле:  
C(n + k - 1, k - 1) = C(3 + 3 - 1, 3 - 1) = C(5, 2) = 10.  

Ответ:  
а) 10.  

Дано:  
n = 7, k = 4.  

Найти:  
б) количество упорядоченных разбиений числа 7 на сумму четырех слагаемых.  

Решение:  
Аналогично, ищем неотрицательные решения уравнения:  
x1 + x2 + x3 + x4 = 7, где x1, x2, x3, x4 > 0.  

Вводим новые переменные:  
y1 = x1 - 1, y2 = x2 - 1, y3 = x3 - 1, y4 = x4 - 1, где y1, y2, y3, y4 >= 0.  
Уравнение становится:  
y1 + y2 + y3 + y4 = 3.  

Количество решений:  
C(n + k - 1, k - 1) = C(3 + 4 - 1, 4 - 1) = C(6, 3) = 20.  

Ответ:  
б) 20.