Автор задачі: | Ціцей Павло |
Задачу підготував: | Ціцей Павло |
Розбір написав: | Ціцей Павло |
Відповідь .
Для k=1, відповідь 2^n, так як це кількість підмножин. Розглянемо любий k>1. Так як нам не важливо яка множина розглядається, а важлива лише кількість елементів то можна згрупувати всі підмножини по кількості елементів. Тоді відповідь буде \sum_{i=0}^n\binom{n}{i}\cdot f(i,k-1). За припущенням f(i,k-1)=k^i, отже \sum_{i=0}^n\binom{n}{i}\cdot f(i,k-1)=\sum_{i=0}^n\binom{n}{i}\cdot k^i=(k+1)^n за формулою біномінальних коефіціентів.