Motzkin nummer

Motzkin nummer
Döpt efter	Theodore Motzkin
Utgivningsår	1948
Författare till publikationen	Theodore Motzkin
Antal kända termer	oändlighet
Formel	se Egenskaper
Första termerna	1, 1 , 2 , 4 , 9 , 21 , 51
OEIS index	A001006; Motzkin;

I matematik är det $n:$ e Motzkin-talet antalet olika sätt att rita ackord som inte skär varandra mellan $n$ punkter på en cirkel (som inte nödvändigtvis rör vid varje punkt med ett ackord). Motzkin-talen är uppkallade efter Theodore Motzkin och har olika tillämpningar inom geometri , kombinatorik och talteori .

Motzkin-talen $M_{n}$ för $n=0,1,\dots$ bildar sekvensen:

1, 1 , 2 , 4 , 9 , 21 , 51 , 127 , 323, 835, 2188, 5798, 15511, 41835, 113634, 310572, 853467, 310572, 853467, 853467, 393567, 593567, 5798, 5798, 15511, 41835. , 50852019, 142547559, 400763223, 1129760415, 3192727797, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829, ... (sekvens A001006 i OEIS )

Exempel

Följande figur visar de 9 sätten att rita icke-skärande ackord mellan 4 punkter på en cirkel ( $M 4 = 9$ ):

Följande figur visar de 21 sätten att rita icke-skärande ackord mellan 5 punkter på en cirkel ( $M 5 = 21$ ):

Egenskaper

Motzkin-talen tillfredsställer återkommande relationer

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

Motzkin-talen kan uttryckas i termer av binomialkoefficienter och katalanska tal :

M_{n}=\summa _{k=0}^{\lfloor n/2\rfloor }{\binom {n }{2k}}C_{k},

och omvänt,

C_{n+1}=\sum _{k=0}^{n}{\binom {n}{k}}M_{k}.

Den genererande funktionen ${\displaystyle m(x)=\summa _{n=0}^{\infty }M_{n}x^{n}} av$ Motzkin siffror uppfyller

x^{2}m(x)^{2}+(x-1)m(x)+1=0

och uttrycks uttryckligen som

m(x)={\frac {1-x-{\sqrt {1-2x-3x^{2}}}}{2x^{2}}}.

En integrerad representation av Motzkin-tal ges av

M_{n}={\frac {2}{\pi }}\int _{0 }^{\pi }\sin(x)^{2}(2\cos(x)+1)^{n}dx

.

De har det asymptotiska beteendet

M_{n}\sim {\frac {1}{2{\sqrt {\pi }}}}\left({ \frac {3}{n}}\right)^{3/2}3^{n},~n\to \infty

.

Ett Motzkin-primtal är ett Motzkin-tal som är primtal . Från och med 2019 är endast fyra sådana primtal kända:

2, 127, 15511, 953467954114363 (sekvens A092832 i OEIS )

Kombinatoriska tolkningar

Motzkin-talet för $n$ är också antalet positiva heltalssekvenser med längden $n - 1$ där öppnings- och slutelementen är antingen 1 eller 2, och skillnaden mellan två på varandra följande element är −1, 0 eller 1. Motsvarande Motzkin-tal för $n$ är antalet positiva heltalssekvenser med längden $n + 1$ där öppnings- och slutelementen är 1, och skillnaden mellan två på varandra följande element är -1, 0 eller 1.

Motzkin-talet för $n$ anger också antalet rutter i den övre högra kvadranten av ett rutnät från koordinat (0, 0) till koordinat ( $n$ , 0) i $n$ steg om man bara tillåts flytta åt höger (upp, nedåt eller rakt) vid varje steg men förbjudet att sjunka under $y$ = 0-axeln.

Till exempel visar följande figur de 9 giltiga Motzkin-vägarna från (0, 0) till (4, 0):

Det finns minst fjorton olika manifestationer av Motzkin-tal i olika grenar av matematiken, som uppräknats av Donaghey & Shapiro (1977) i deras undersökning av Motzkin-tal. Guibert, Pergola & Pinzani (2001) visade att vexillära involutioner räknas upp av Motzkin-tal.

Se även

Telefonnummer som representerar antalet sätt att rita ackord om korsningar är tillåtna
Delannoy nummer
Narayana nummer
Schröder nummer

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, LW (1977), "Motzkin numbers", Journal of Combinatorial Theory , Series A, 23 (3): 291–301, doi : 10.1016/0097-3165(77)90020-6 , MR 0505544
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 0218-0006 , S33319 , 33319 , 42MR 5319 , 42MR 5319
Motzkin, TS (1948), "Relationer mellan hyperytkorsförhållanden och en kombinatorisk formel för partitioner av en polygon, för permanent övervikt och för icke-associativa produkter", Bulletin of the American Mathematical Society, 54 ( 4): 352– 360, doi : 10.1090/S0002-9904-1948-09002-4

externa länkar

Weisstein, Eric W. "Motzkin Number" . MathWorld .