Motzkintal

Ett Motzkintal anger antalet olika sätt att i en cirkel med n punkter placera 0 till n/2 kordor som inte vidrör varandra. Motzkintalen är uppkallade efter Theodore Motzkin och har olika användningsområden inom geometri, kombinatorik och talteori.

Motzkintal ${\displaystyle M_{n}}$ för ${\displaystyle n=0,1,\dots }$ bildar talföljden:

1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, ... (talföljd A001006 i OEIS)

Exempel

Figuren visar de 9 sätten att rita icke-korsande kordor mellan 4 punkter i en cirkel.

Figuren visar de 21 sätten att rita icke-korsande kordor mellan 5 punkter i en cirkel.

Egenskaper

Motzkintal uppfyller den rekursiva funktionen:

${\displaystyle M_{n+1}=M_{n}+\sum _{i=0}^{n-1}M_{i}M_{n-1-i}={\frac {2n+3}{n+3}}M_{n}+{\frac {3n}{n+3}}M_{n-1}.}$

Motzkintal kan uttryckas som binomialkoefficienter och Catalantal:

${\displaystyle M_{n}=\sum _{k=0}^{\lfloor n/2\rfloor }{\binom {n}{2k}}C_{k}.}$

Ett Motzkinprimtal är ett Motzkintal som även är primtal. Fyra sådana primtal är kända:

2, 127, 15511, 953467954114363 (talföljd A092832 i OEIS)

Referenser

Den här artikeln är helt eller delvis baserad på material från engelskspråkiga Wikipedia, 11 augusti 2015.

• Bernhart, Frank R (1999), ”Catalan, Motzkin, and Riordan numbers”, Discrete Mathematics 204 (1-3): 73–112, doi:10.1016/S0012-365X(99)00054-0 
• Donaghey, R.; Shapiro, L. W. (1977), ”Motzkin numbers”, Journal of Combinatorial Theory, Series A 23 (3): 291–301, doi:10.1016/0097-3165(77)90020-6 
• Guibert, O.; Pergola, E.; Pinzani, R. (2001), ”Vexillary involutions are enumerated by Motzkin numbers”, Annals of Combinatorics 5 (2): 153–174, doi:10.1007/PL00001297, ISSN 0218-0006 

• Motzkin, T. S. (1948), ”Relations between hypersurface cross ratios, and a combinatorial formula for partitions of a polygon, for permanent preponderance, and for non-associative products”, Bulletin of the American Mathematical Society 54 (4): 352–360, doi:10.1090/S0002-9904-1948-09002-4