Catalantal

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

C₀, C₁, C₂, C₃, C₄,... = 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

Algebraiskt kan catalantalen definieras genom

$C_{n}={\frac {1}{(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_{i}C_{n-i}$

eller:

$C_{0}=1~~C_{n+1}={\frac {2(2n+1)}{n+2}}C_{n}.$

Tillämpningar

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.

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

• Donald Knuth, The Art of Computer Programming, Fundamental Algorithms, volume 1, 1973.

Externa länkar

• Wikimedia Commons har media som rör Catalantal.
  Bilder & media