Motzkinovo číslo

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 24. října 2018; kontroly vyžadují 3 úpravy .

Motzkinovo číslo pro dané číslo n je počet možných způsobů, jak spojit n různých bodů na kružnici s neprotínajícími se akordy (akordy nemusí vycházet z každého bodu). Motzkinova čísla jsou pojmenována po Theodoru Motzkinovi a mají mnoho projevů v geometrii , kombinatorice a teorii čísel .

Motzkinova čísla tvoří posloupnost:

1, 1 , 2 , 4 , 9 , 21 , 51 , 127 , 323 , 835 , 2188, 5798, 15511, 41835, 113634, 310572, 853467, 235565, 18852019, 14254759, 4007632, 18199763, 5052019, 14254759, 40076632, 181997663, 181997663, 181997663, 181997663, 181997663, 181997763, 181997663, 181997663, 181997663, 18199766, 50852019. 3197777 9043402501, 25669818476, 73007772802, 208023278209, 593742784829, ... sekvence OEIS A001006

Příklady

Uvedené obrázky demonstrují 9 způsobů, jak spojit 4 body na kružnici s neprotínajícími se tětivami:

A tyto ukazují 21 způsobů, jak spojit 5 teček:

Vlastnosti

Motzkinova čísla splňují rekurzivní vztahy

Motzkinova čísla lze vyjádřit pomocí binomických koeficientů a katalánských čísel :

Prvočíslo Motzkinovo číslo je Motzkinovo číslo, které je prvočíslo , z nichž čtyři jsou známá:

2, 127, 15511, 953467954114363 OEIS sekvence A092832

Interpretace v kombinatorice

Motzkinovo číslo pro n je také počet kladných celočíselných sekvencí délky n-1, ve kterých jsou počáteční a koncové prvky 1 nebo 2 a rozdíl mezi libovolnými dvěma po sobě jdoucími prvky je -1, 0 nebo 1.

Motzkinovo číslo pro n také určuje počet tras z bodu (0, 0) do bodu (n, 0) v n krocích, pokud je povolen pohyb pouze doprava (nahoru, dolů nebo rovně) v každém kroku. , a je zakázáno jít pod osu y = 0 .

Například následující obrázek ukazuje 9 platných Motzkinových cest od (0, 0) do (4, 0):

Existuje nejméně čtrnáct různých projevů Motzkinových čísel v různých oblastech matematiky, které uvedli Donaghy a Shapiro v (1977) ve svém přehledu Motzkinových čísel.

Guibert, Pergola a Pinzani v (2001) ukázali, že vezikulární involuce jsou vyčísleny pomocí Motzkinových čísel.

Viz také

Odkazy

Externí odkazy