Motzkinovo číslo

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Motzkinovo číslo se dá v matematice definovat např. jako počet všech možných různých způsobů nakreslení neprotínajících se tětiv mezi n body na kružnici. (Jedním z těchto způsobů je vždy i nenakreslení žádné.) Je pojmenováno po americkém matematikovi Theodoru Motzkinovi (19081970). Motzkinovo číslo má mnoho různých aplikací v geometrii, kombinatorice a teorii čísel. První Motzkinova čísla (pro n = 1, 2, 3, ...) jsou:

1, 2, 4, 9, 21, 51, 127, 323, 835, 2 188, 5 798, 15 511, 41 835, 113 634, 310 572, 853 467, 2 356 779, 6 536 382, 18 199 284 (posloupnost A001006 v OEIS)

Následující obrázky zobrazují všech 9 možností nakreslení neprotínajících se tětiv mezi 4 body na kružnici (9 je tedy Motzkinovo číslo odpovídající n = 4):

MotzkinChords4.svg

Následující obrázky zobrazují všech 21 možností nakreslení neprotínajících se tětiv mezi 5 body na kružnici:

MotzkinChords5.svg

Někdy mluvíme taktéž o Motzkinově prvočísle což je Motzkinovo číslo, které je zároveň prvočíslem. K říjnu 2007 byla taková čísla známa čtyři: 2, 127, 15 511, 953 467 954 114 363 (posloupnost A092832 v OEIS)

Motzkinovo číslo pro n je taktéž počet kladných celočíselných posloupností s n−1 členy, v kterých první a poslední člen je 1 nebo 2 a diference mezi dvěma jakýmikoliv po sobě jdoucími členy je −1, 0 nebo 1.

Stejně tak Motzkinovo číslo pro n udává počet všech možných cest z bodu [0, 0] do bodu [n, 0] s tím, že je možno se pohybovat jen doprava, nahoru či šikmo a cesta musí být dlouhá n kroků, kde jeden krok je brán jako přesunutí se do bodu s nezápornými souřadnicemi, který sousedí s bodem, v kterém se nacházíme.

Následující obrázky ukazují všech 9 takových možných cest z bodu [0, 0] do bodu [4, 0] (n je tedy rovno čtyřem):

Motzkin4.svg

Odkazy[editovat | editovat zdroj]

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Motzkin number na anglické Wikipedii.

Externí odkazy[editovat | editovat zdroj]