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

C_n = \frac1{(n+1)} \; {2n \choose n} = \frac{(2n)!}{(n+1)!\,n!} \, (där ! står för fakultetsfunktionen och {2n \choose n}\, är en binomialkoefficient).

Catalantalen kan också beskrivas rekursivt:

 C_0 = 1 ~~ C_{n+1} =  \sum_{i=0}^n  C_iC_{n-i}

eller:

 C_0 = 1 ~~ C_{n+1} = \frac{2(2n+1)}{n+2}C_n.

Tillämpningar[redigera | redigera wikitext]

I. C_n ä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. C_n är antalet sätt en konvex polygon med n+2 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 C_n. 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 {6 \choose  3} = 20. 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å {6 \choose 2} = 15. Alltså är antalet tillåtna sekvenser  20 - 15 = 5 = C_3. Generellt får man således att C_n = {2n \choose n} - {2n \choose {n-1}}.

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.