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 $M_n$ för $n=0,1,\dots$ bildar talföljden:

1, 1, 2, 4, 9, 21, 51, 127, 323, 835, 2188, ... Mall: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:

$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:

$M_n=\sum _{k=0}^{\lfloor n/2\rfloor }(\genfrac{}{}{0ex}{}{n}{2k})C_k.$

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

2, 127, 15511, 953467954114363 Mall:OEIS

Referenser

• Mall:Enwp

• Mall:Citation
• Mall:Citation
• Mall:Citation

• Mall:Citation