Множини

Автор задачі: | Ціцей Павло
Задачу підготував: | Ціцей Павло
Розбір написав: | Ціцей Павло

Відповідь $$$(k+1)^n$$$.

Для $$$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$$$ за формулою біномінальних коефіціентів.