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

h1. 'Soluţia':jc2023/solutii/omidamincinoasa problemei 'Omida Mincinoasa':problema/omidamincinoasa

Pentru început, observăm că $C(n,i)·i^k^$ înseamnă de fapt să alegem un subşir de lungime $i$ a mulţimii ${1,2,3,...,n}$, şi după aceea să alegem o tuplă de lungime $k$ din subşirul respectiv. În acest fel, numărăm toate perechile de tipul $(subşir, tuplă)$, dar acest lucru este echivalent cu a număra perechi de tipul $(tuplă, subşir)$. Observăm în continuare că pentru a alege un subşir care acoperă o tuplă de valori depinde doar de numărul de valori distincte $x$ din tuplă, iar numărul de moduri să alegem subşirul este $2^n-x^$. Astfel, dacă vom găsi un mod prin care să calculăm numărul de tuple cu $x$ valori distincte, am rezolvat problema.