Page 40 - MATINF Nr. 13-14

40 C. B˘alc˘au, D. Constantin

3 4 3 4 3 4 3 4

2 2 2 2

1 1 1 1

3 4 3 4 3 4 3 4

2 2 2 2

1 1 1 1

a
a
Exemplul 4. Aplicˆand teorema anterioar˘ rezult˘ c˘ num˘arul arborilor part , iali ai grafului evantai
a
F 4 este

2 −1 0 0

−1 3 −1 0

t(F 4 ) = det[M] 11 = .
0 −1 3 −1

0 0 −1 2
Dezvoltˆand determinantul dup˘a linia 1, obt , inem

3 −1 0 −1 −1 0

t(F 4 ) = (−1) 1+1 · 2 · −1 3 −1 + (−1) 1+2 · (−1) · 0 3 −1 = 2 · 13 − 5 = 21.

0 −1 2 0 −1 2

Rezultatele principale
∗
Definit , ia 3. Pentru orice n ∈ N , not˘am
t n = t(F n )

num˘arul de arbori part ,iali ai grafului evantai F n .
Propozit , ia 1 (Relat , ia de recurent , ˘ a numerelor t n ). Avem t 1 = 1, t 2 = 3 s , i
a
t n = 3t n−1 − t n−2 , ∀ n ≥ 3. (1)

Å ã
1 −1
Demonstrat ,ie. Matricea de admitant , ˘a a grafului F 1 este M = , deci conform
−1 1

Teoremei 1 avem t 1 = det[M] 11 = 1 = 1.
Ñ é
2 −1 −1
a
Matricea de admitant , ˘ a grafului F 2 este M = −1 2 −1 , deci conform Teoremei 1
−1 −1 2

2 −1

avem t 2 = det[M] 11 = = 3.
−1 2

Conform Exemplelor 3 s , i 4 avem t 3 = 8 s , i t 4 = 21, deci relat , ia (1) este verificat˘a pentru
n = 3 s , i n = 4.