h1. 'Solutia':jc2023/solutii/omida problemei 'Omida Mincinoasa':problema/omidamincinoasa

h1. Solutia problemei 'Omida Mincinoasa':problema/omidamincinoasa

Pentru inceput, observam ca $C(n,i)·i^k^$ inseamna de fapt sa alegem un subsir de lungime $i$ a multimii ${1,2,3,...,n}$, si dupa aceea sa alegem o tupla de lungime $k$ din subsirul respectiv. In acest fel, numaram toate perechile de tipul $(subsir,tupla)$, dar acest lucru este echivalent cu a numara perechi de tipul $(tupla, subsir)$. Observam in continuare ca pentru a alege un subsir care acopera o tupla de valori depinde doar de numarul de valori distincte $x$ din tupla, iar numarul de moduri sa alegem subsirul este $2^n-x^$. Astfel daca vom gasi un mod prin care sa calculam numarul de tuple cu $x$ valori distincte, am rezolvat problema.