Subsir100

Exista o bijectie intre multimea subsirurilor "interesante" din sirul dat si multimea subsirurilor "interesante" din sirul obtinut prin ordonarea sirului dat (Tema demonstratia).
Fie A[ 1 ... N ] sirul obtinut prin ordonarea sirului dat, iar X [ i ] numarul de subsiruri "interesante " din sirul 
A [ i ... N ] , oricare ar fi i un numar natural nenul cu proprietatea i<=N.
Evident X [ N ] = 1 si X [ i ] = X [ i + 1 ] + X [ j ], unde j este cel mai mic numar natural nenul ( i < j < = N ) cu proprietatea ca A [ j ] != A [ i ]. Relatia de recurenta se explica astfel:
Numarul subsirurilor "interesante" din A [ i ... N ] este egal cu numarul subsirurilor "interesante" din A [ i ... N ] care nu il contin pe A [ i ], plus numarul subsirurilor "interesante din" A [ i ... N ] care il contin pe A [ i ]. Iar numarul subsirurilor "interesante" din A [ i ... N ] care nu il contin pe A [ i ] este egal cu numarul subsirurilor "interesante" din A [ i+1 ... N ] ( A [ i+1 ... N ] nu il contine pe A[i], iar aici ma refer la termenul A[i] si nu la valoarea lui). Pentru a obtine toate subsirurile "interesante" din A [ i ... N ] care il contin pe A [ i ] trebuie sa eliminam din sirul A [ i ... N ] toti termenii care au valoarea egala cu valoarea lui A [ i ] ( Intr-un subsir "interesant" toate valorile sunt distincte ) si sa il adaugam pe A [ i ] la inceputul fiecarui subsir "interesant" din sirul ramas. Raspunsul cautat va fi in X [ 1 ].