"kahendpuude" - 1 õppematerjal

ITT0030 Diskreetne matemaatika II - eksamikonspekt

kombinatoorika vallas. Näiteid: a).Catalani arv Cn on erinvate Dycki sõnade arv pikkusega 2n. (Dycki sõnad on lahtistest ning kinnistavatest sulgudest koosnevad stringid, kusjuures kõik eelnevalt ,,avatud sulud" peavad sõna lõpuks saama ka ,,suletud" ning stringi alguses ei tohi kinnistavaid sulge olla rohkem, kui lahtiseid sulge). b).Catalani arv Cn on kõigi erinevate n+1 lehega täielike kahendpuude arv. c). Catalani arv Cn on kõigi võimalike teede arv N x N dimensionaalse võrgu külgi mööda liikumiseks vastastippude vahel nii, et ei ületataks diagonaali. d). Catalani arv Cn on kõikide erinevate võimaluste arv lõikamaks n + 2 küljega hulknurka tükkideks, kui tippe ühendada sirgjoontega. n'indat Catalani arvu on võimalik leida väga mitmest erinvast valemist. Nende hulgas: Rekurrentsest seosest: Cn = Cn-1, kus algväärtuseks C0 = 1;