Catalantal

Från Wikipedia
Hoppa till: navigering, sök

Catalantalen, vilka utgör en talföljd som börjar

C0, C1, C2, C3, C4,... = 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324 …

Följden är uppkallad efter den belgiska matematikern Eugène Charles Catalan (1814–1894). Catalantalen har visats ange antalen för en mycket stor uppsättning olika kombinatoriskt intressanta familjer av mängder.

Egenskaper[redigera | redigera wikitext]

Algebraiskt kan catalantalen definieras genom

(där ! står för fakultetsfunktionen och är en binomialkoefficient).

Catalantalen kan också beskrivas rekursivt:

eller:

Tillämpningar[redigera | redigera wikitext]

I. är antalet monotona vägar genom ett n × n-rutnät av kvadrater som inte går ovanför diagonalen i rutnätet. En monoton väg är en väg som börjar i nedre vänstra hörnet och rör sig upp till övre högra hörnet, genom att i varje steg antingen röra sig uppåt eller åt höger.

Catalan number 4x4 grid example.svg

II. är antalet sätt en konvex polygon med sidor kan delas in i trianglar genom att dra linjer mellan hörn.

III. Det antal permutationer av talen: 1,2.....n, som kan åstadkommas med hjälp av en stack är lika med . Med beteckningarna S, för att stacka ett tal och X, för exit av talet, får man om n = 3 en permutation med exempelvis exekveringssträngen: SXSSXX. Antalet sådana strängar är . Vissa av dessa strängar är otillåtna, exempelvis SXSXXS; Om stacken är tom kan operationen X inte utföras. Om man fram till och med den position i strängen, där antalet X överskrider antalet S, substituerar S och X mot varandra, får man här sekvensen: XSXSSS, som således innehåller 4 stycken S och 2 stycken X. Generellt fås n + 1 stycken S och n - 1 stycken X. Antalet otillåtna strängar blir då . Alltså är antalet tillåtna sekvenser . Generellt får man således att .

Källor[redigera | redigera wikitext]

  • Donald Knuth, The Art of Computer Programming, Fundamental Algorithms, volume 1, 1973.
Venn A intersect B.svg Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia.