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].