Page 43 - MATINF Nr. 13-14

Num˘ararea arborilor part , iali ai grafului evantai 43

a
Presupunem acum egalitatea adev˘arat˘ pentru n − 2 s , i n − 1, adic˘a

t n−2 = f 2n−4 s , i t n−1 = f 2n−2 ,

s , i o demonstr˘am pentru n, unde n ≥ 3.
ˆ a a
Intr-adev˘ar, folosind relat , iile de recurent , ˘ ale celor dou˘ s , iruri s , i ipoteza de induct , ie, avem

t n = 3t n−1 − t n−2 = 3f 2n−2 − f 2n−4

= 2f 2n−2 + f 2n−2 − f 2n−4 = 2f 2n−2 + f 2n−3
= f 2n−2 + f 2n−2 + f 2n−3 = f 2n−2 + f 2n−1
= f 2n ,

ceea ce ˆıncheie demonstrat , ia.

Bibliografie

[1] C. B˘alc˘au, Combinatoric˘a s , i teoria grafurilor, Editura Universit˘at , ii din Pites , ti, Pites , ti, 2007.

[2] A.J.W. Hilton, The number of spanning trees of labeled wheels, fans and baskets, Combina-
torics (Proc. Conf. Combinatorial Math., Math. Inst., Oxford, 1972), pp. 203–206 Institute
of Mathematics and its Applications, Southend-on-Sea, 1972.

[3] C. Merino, The number of quasi-trees in fans and wheels, Electron. J. Combin. 30 (2023),
no. 1, Paper No. 1.46, 16 pp.

[4] D.R. Popescu, R. Marinescu-Ghemeci, Combinatoric˘a s , i teoria grafurilor prin exercit ,ii s , i
probleme, Editura Matrix Rom, Bucures , ti, 2014.
a
a
[5] I. Tomescu, Probleme de combinatoric˘ s , i teoria grafurilor, Editura Didactic˘ s , i Pedagogic˘a,
Bucures , ti, 1981.
[6] ***, Handbook of discrete and combinatorial mathematics, edited by K.H. Rosen, J.G.
Michaels, J.L. Gross, J.W. Grossman and D.R. Shier, CRC Press, Boca Raton, 2000.