Motzkin nummer

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 24 oktober 2018; kontroller kräver 3 redigeringar .

Motzkin-talet för ett givet tal n är antalet möjliga sätt att koppla samman n distinkta punkter på en cirkel med icke-korsande ackord (ackorden kanske inte kommer ut från varje punkt). Motzkin-tal är uppkallade efter Theodor Motzkin och har många manifestationer inom geometri , kombinatorik och talteori .

Motzkin-numren för bildar sekvensen:

1, 1 , 2 , 4 , 9 , 21 , 51 , 127 , 323 , 835 , 2188, 5798, 15511, 41835, 113634, 310572, 853467, 2356779, 6536382, 18199284, 50852019, 14254759, 40076322, 1129760415, 3192777, 3197777, 31977777, 9043402501, 25669818476, 73007772802, 208023278209, 593742784829, ... OEIS -sekvens A001006

Exempel

De givna figurerna visar 9 sätt att koppla ihop 4 punkter på en cirkel med icke-skärande ackord:

Och dessa visar 21 sätt att ansluta 5 punkter:

Egenskaper

Motzkin-talen tillfredsställer de rekursiva relationerna

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

Ett primtal Motzkin är ett Motzkin tal som är primtal , varav fyra är kända:

2, 127, 15511, 953467954114363 OEIS -sekvens A092832

Tolkningar i kombinatorik

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

Motzkin-talet för n anger också antalet rutter från punkt (0, 0) till punkt (n, 0) i n steg, om det är tillåtet att röra sig endast åt höger (upp, ner eller rakt) vid varje steg , och det är förbjudet att gå under y-axeln = 0 .

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

Det finns minst fjorton olika manifestationer av Motzkin-tal inom olika områden av matematiken, listade av Donaghy och Shapiro (1977) i deras undersökning av Motzkin-tal.

Guibert, Pergola och Pinzani (2001) visade att vesikulära involutioner räknas upp av Motzkin-tal.

Se även

Länkar

Externa länkar