Probleme

Fie un șir S format din literele a și b, grupate ca blocuri consecutive după următoarea regulă: 4 de a, apoi 7 de b, apoi 5 de a, apoi 6 de b, apoi 8 de a, apoi 4 de b, apoi 6 de a, apoi 9 de b, adică șirul format după regula descrisă arată astfel: S = aaaabbbbbbbaaaaabbbbbbaaaaaaaabbbbaaaaaabbbbbbbbb. Un subșir al lui S este numit valid dacă conține același număr de caractere a și b și toate caracterele a sunt consecutive și toate caracterele b sunt consecutive (de exemplu subșirurile de forma aaaabbbb, bbbbaaaa, aaabbb, ab, etc. sunt valide). Câte subșiruri valide sunt în S?

a) $34$; b) $34!$; c) $26$; d) $2^{17}$; e) $17$; f) $37$.

Fie o mulțime de $k$ simboluri cu care se pot forma șiruri distincte de lungime $n$ ($n\ge k$). Fiecare dintre cele $k$ simboluri apare în fiecare șir de $f_1, f_2, \ldots, f_k$ ori, $f_i\ge 1$, $1\le i\le k$. Pentru simbolurile $\{A, B, C\}$ care apar de $1$, $3$ și, respectiv, $2$ ori, primele $4$ șiruri generate cu metoda backtracking sunt: ABBBCC, ABBCBC, ABBCCB, ABCBBC. Care este următorul șir care va fi generat?

a) ACCBBB; b) ABCBCB; c) ABCCBB; d) ABCBBC; e) ACBBBC; f) BABCCB.