Page 45 - MATINF Nr. 7

Mult , imi legate 45

Definit , ia 3. Se numes , te n-cuvˆant legat de ordin k un n-cuvˆant asociat unei mult , imi legate de
ordin k.

ˆ
k
Vom nota cu Y submult , imile lui C n formate din n-cuvinte legate de ordin k. In particular
n
Y 1 reprezint˘a mult , imea n-cuvintelor simplu legate iar Y 2 reprezint˘a mult , imea n-cuvintelor
n n
dublu legate.
ˆ
k
Vom nota de asemenea cu L , num˘arul n-cuvintelor legate de ordin k. In particular L 1
n n
2
reprezint˘a num˘arul n-cuvintelor simplu legate iar L reprezint˘a num˘arul n-cuvintelor dublu
n
legate.
Propozit , ia 1. Cu notat , iile anterioare avem urm˘atoarea relat , ie de recurent , ˘a:
1
L = L 1 + L 1 n−2 + L 1 n−4 pentru orice n ≥ 4. (1)
n−1
n
ˆ
Demonstrat¸ie. Intr-adev˘ar, num˘arul n-cuvintelor simplu legate care ˆıncep cu 0 este L 1 n−1 .
Num˘arul n-cuvintelor simplu legate care ˆıncep cu 1 ˆıl vom calcula astfel: Vom observa pentru
ˆınceput c˘a un astfel de n-cuvˆant are ˆın mod obligatoriu ˆın pozit , ia a doua elementul 1. Dac˘a la
primele dou˘a pozit , ii ad˘aug˘am toate (n − 2)- cuvintele simplu legate care se formeaz˘a cu restul
pozit , iilor dintr-un astfel de cuvˆant se obt , in n-cuvinte simplu legate. Deasemenea n-cuvinte
simplu legate mai putem obt , ine s , i dac˘a ˆın pozit , iile 3 s , i 4 punem 1 s , i respectiv 0 iar ˆın rest
(n − 4)-cuvinte simplu legate. Prin urmare num˘arul n-cuvintelor simplu legate care ˆıncep cu 1
este: L 1 n−2 + L 1 n−4 , deci relat , ia de recurent , ˘a este acum justificat˘a.
si
Folosind un program simplu de calculator am creat ˆın Excel o funct , ie de num˘arare (folosind
definit , ia) a n-cuvintelor simplu legate cu care am obt , inut urm˘atoarele rezultate:

k L 1
k
0 1
1 1
2 2
3 4
4 7
5 12
6 21
7 37
8 65
9 114
10 200
11 351
12 616
13 1081
14 1897

1
Bineˆınt , eles c˘a avˆand calculate valorile L cu 0 ≤ k ≤ 3, se poate constata us , or c˘a valorile
k
1
L cu k ≥ 4 obt , inute cu aceast˘a funct , ie verific˘a relat , ia de recurent , a de mai sus.
k
2
Vomˆıncerca acum s˘a determin˘am o relat , ie de recurent , ˘a pentru calculul lui L adic˘a num˘arului
n
de n-cuvinte dublu legate.