\(\\qquad\)Для кожного натурального \(n\) позначимо через \(P(n)\) число способів розбити число \(n\) в суму натуральних доданків (розбиття, що відрізняються лише порядком доданків, вважаються однаковими, наприклад, \(P(4) = 5\), тому що \(4 = 4 = 1 + 3 = 2 + 2 = 1 + 1 + 2 = 1 + 1 + 1 + 1\) - п'ять способів). Кількість різних чисел в даному розбитті назвемо його розсіюванням (наприклад, розбиття \(4 = 1 + 1 + 2\) має розсіювання \(2\), тому що в цьому розбитті два різних числа). \(\\\qquad\)Доведіть, що сума \(Q(n)\) всіх розсіювань всіх розбиттів числа \(n\) дорівнює $$1 + P(1) + P (2) + \ldots + P(n-1).$$
| Source | Тимошкевич Тарас (лекції, МАН) (Ukraine) |
|---|---|
| Year | 2021 |
| Difficulty | 10.0 |
| Themes | Комбінаторика, Підрахунок двома способами |