Este posibila determinarea unei formule/relatii de recurenta pentru a afla cate numere mai mici decat

au suma cifrelor s?

Iata si problema originala(ONI 2004)
Ionel este elev în clasa a IV-a şi părinţii s-au gândit la o metodă eficientă prin care el să înveţe numerele mari şi modul lor de formare. În acest scop i-au cumpărat un joc cu jetoane. Pentru fiecare cifră există câte 10 jetoane inscripţionate pe una din feţe cu cifra respectivă. Ionel poate forma numere prin aşezarea jetoanelor unul lângă altul. Părinţii îi cer lui Ionel să formeze numere, pe rând, care să aibă suma cifrelor S şi să fie mai mici decât 10a. Pentru că este dificil să-l urmărească în formarea numerelor, părinţii doresc să ştie câte astfel de numere distincte ştie Ionel să formeze.

Cerinţă
Câte numere distincte a format Ionel?

Date de intrare
În fişierul jetoane.in, pe prima linie se găseşte numărul S iar pe a doua linie numărul a.

Date de ieşire
În fişierul jetoane.out se va scrie pe un singur rând numărul cerut.

Restricţii
1 ≤ S < 10
1 ≤ a < 10
S şi a sunt numere naturale.

Exemple
jetoane.in jetoane.out
2
3 6
jetoane.in jetoane.out
5
5 126

Explicaţii
În cazul primului exemplu (S=2 şi a=3) Ionel formează numerele: 2, 11, 20, 101, 110, 200.

....
Cu numere de 1,2,3 cifre ne-am descurcat,la 4 cifre am gasit o formula oribila care nu ne ajuta sa mergem mai departe....

in ipoteza s<10.
Pentru s>9, e mai complicat, trebuie folosit principiul includerii si excluderii, etc.

[Citat] in ipoteza s<10. Pentru s>9, e mai complicat, trebuie folosit principiul includerii si excluderii, etc.

Multumim frumos!
Ne ajutati,va rugam,sa ne prindem si cum se ajunge la formula asta...
Evident,problema informatica a rezolvat-o folosind formula data de dv;mai ramane problema matematica,ca ne-am tot gandit de ce s+a-1...
In paranteza fie spus,problema a fost propusa la clasa a 7-a,ne-am uitat si la rezultatele din acel an,nu a prea fost abordata.

[Citat] Explicaţii În cazul primului exemplu (S=2 şi a=3) Ionel formează numerele: 2, 11, 20, 101, 110, 200.

Este bine sa ne gandim la realizarile de mai sus ca partitii ale lui 2 in trei multimi, scriind in locul numerelor din baza zece mai bine numere de telefon intai:

002
011
020
101
110
200

Si deja ordinea in care punem numerele este alta:

002
020
200
011
101
110

poate.
Acum facem trucajul urmator.
In loc sa ne legam de partitia cu cifrele / jetoanele

s,t,u

ne legam de

s, s+t, s+t+u=2

si facem bijectiv rost de un sir finit crescator pana la 2.

In toate numerele de a=trei cifre de mai sus adunam:
- pe prima pozitie 1
- pe a doua pozitie 2
- pe a treia si ultima pozitie a=3.

Dam bijectiv de un sir finit strict crescator cu a-1 = 3-1 termeni (s+1 si s+t+2) intre 1 si s+t+u + a-1 = S + a-1 .

In acest mod mergem de la numarat partitii la numarat submultimi cu fix a-1 elemente ale multimii 1 , ... , S+a-1 ...

Si pe clasa a VI-a se stie deja ca obtinem
Combinari( S+a-1, a-1 ) = Combinari( S+a-1, S ) elemente...

Chiar daca nu se stie, cei ce propun problema stiu ca se stie.

Mihai si cu mine va multumim frumos!
E totul ok acum!