Combinari cu o proprietate

[•mihai.plesa]

Salut!

Am o multime data M cu cardinalul n iar in vectorul C generez pe rand combinarile de n luate cate t. Vreau sa calculez NUMARUL tuturor combinarilor care au urmatoarele proprietati:
1.C[1]-2<=2*k
2.C-C[i-1]<=2*k
3.2*n-C[t]<=2*k unde k este dat. Intrebarea mea este daca ppot calcula NUMARUL combinarilor FARA a le genera? Si in general, daca imi cere intr-o problema sa calculez numarul combinarilor cu o anumita proprietate pot sa "scap" de generarea lor?

Multumesc

[•PlayLikeNeverB4]

E cam vaga intrebarea. Uneori da, alteori nu.

Uneori poti deduce o formula, alteori merge cu programare dinamica. In cazul asta, din cauza conditiei 2, suspectez ca exista o solutie cu programare dinamica.

[•klamathix]

Editeaza-ti indicii aia un pic ca nu inteleg nimic.

[•mihai.plesa]

Acesta este exemplul concret: am multimea {2, 4, 6, 8, 10, 12 ,14, 16, 18, 20}. Cardinalul multimii este de 10. In vectorul C generez pe rand toate combinarile de 10 luate cate 2 cu urmatoarele proprietati:
1.

Cod:

C[1]-2<=2*k

2.

Cod:

C-C[i-1]<=2*k 

3.

Cod:

2*n-C[t]<=2*k

n este cardinalul multimii si k un numar dat...in cazul nostrum k=4 si n=10.

Una dintre posibilitati este:4 12 alta este 6 12 etc. Intrebarea mea este daca pot gasi NUMARUL combninarilor fara sa le generez?