Множини#8

Множини (Розбір)

Автор задачі:

Ціцей Павло

Задачу підготував:

Ціцей Павло

Розбір написав:

Ціцей Павло

Відповідь .

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