On matematiikka , ja erityisemmin combinatorics , Motzkin numerot muodostavat sarjan luonnollinen numeroita käytetään eri laskenta ongelmia. Ne on nimetty matemaatikko Théodore Motzkinin (1908-1970) mukaan. Motzkin-numeroilla on monia sovelluksia geometriassa , kombinaattorissa ja lukuteoriassa .
Motzkin määrä indeksi on useita tapoja valita jouset eivät leikkaavat, joukossa jouset yhdistävät pisteitä järjestetty ympyrän. Motzkin-luvut täyttävät seuraavan toistumissuhteen:
Numerot vastaavat Motzkinia OEIS: n A001006 jälkeen , ja ensimmäinen näistä numeroista on:
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | |
1 | 1 | 2 | 4 | 9 | 21 | 51 | 127 | 323 | 835 | 2188 | 5798 |
Aloitetaan todistamalla johdannossa mainittu toistuvuussuhde. Valitse ympyrälle järjestettyjen n + 1 pisteen joukosta yksi, toisin sanoen P. Kyseisten n + 1 pisteen joukosta valittujen ja kaikki P: stä erillisten pisteiden valitsemattomien sointujen valitsemisen tapojen määrä on yhtä suuri kuin . Toisaalta, jos j: lle kohdassa {1, 2, ..., n}, se merkitsee j: nnen pisteen P: n jälkeen ympyrän kiinteään kulkusuuntaan, kuinka monta tapaa valita merkkijonot, joilla on halutut ominaisuudet ja sellainen, että yksi näistä sointuista on sointu, on se, kuinka monta tapaa valita sopiva merkkijonojoukko pisteisiin nähden ja toisaalta sopiva merkkijonojoukko pisteisiin nähden . Nämä kaksi valintaa ovat toisistaan riippumattomia, ensimmäisen tavan tekemiseen on toinen tapa , joten näiden kahden valinnan tekemiseen on siis useita tapoja.
.Tähän suhteeseen yhdistettynä määritetään Motzkin-luvut. On
Motzkinin tuottava sarja. Toistumissuhde ilmaisee, että tämä sarja täyttää seuraavan yhtälön:
.Tästä yhtälöstä päätellään
ja laajentamalla saamme nimenomaisen kaavan
missä on katalaanin lukumäärä
Generaattorisarjan tutkiminen antaa meille mahdollisuuden saada seuraava ilmaisu asymptoottiselle käyttäytymiselle:
Generaattorisarja tarkistaa
Motzkin-luvuista on muitakin nimenomaisia lausekkeita kuin edellä johdettu yhtälöstä, jonka generoiva sarja tyydyttää.
Meillä on esimerkiksi
.Toisaalta, soveltamalla Lagrangen inversiolausea generoivaan sarjaan, saadaan lauseke
.Motzkin-luvut varmistavat myös seuraavan lineaarisen toistosuhteen polynomikertoimilla:
.A priori ei ole ilmeistä , että tämän suhteen määrittelemät luvut ovat kokonaislukuja.
Motzkin-luku on myös yksikaaristen binääripuiden (eli juurtuneiden tasopuiden, joissa kussakin solmussa on yksi tai kaksi lasta) määrä, jossa on kaaria. Voimme nähdä tämän suoraan tulkitsemalla toistumissuhteen tai myös luomalla bijection-merkkijonojen ja näiden puiden välille. Valitaan taas piste ympyrästä. Jos sitä ei ole sidottu köydellä, se sovitetaan puun juureen yhdellä langalla, joka vastaa yhdistettyä ympyrää. Muussa tapauksessa merkkijono leikkaa ympyrän kahteen osaan, jotka vastaavat puun vasenta ja oikeaa alipuuta, jonka juuressa on kaksi säiettä.
Motzkin numero on myös polkujen lukumäärä yhdistävät piste siihen pisteeseen , joka koostuu Koillis- tai Kaakkois- tai Itä vaiheet , polku tarvitse olla täysin oikeassa yläkulmassa neljännekseen maamerkki. Tällainen polku on Motzkinin polku . Uniaaribinaaristen puiden ja Motzkinin polkujen välinen vastaavuus saadaan suorittamalla etuliite polulle puulle ja merkitsemällä nousevalla (tai laskevalla) askeleella vasemman lapsen (tai oikealle) vierailu, kun häntä on kaksi ja vaakatasossa ainoan lapsen vierailu.
Motzkin-luku on myös niiden luonnollisten kokonaislukujen sekvenssien lukumäärä, jotka täyttävät seuraavat kaksi ehtoa: ensimmäinen ja viimeinen alkuaineet ovat yhtä suuret kuin 0 tai 1; Kahden peräkkäisen elementin välinen ero on -1, 0 tai 1. Tämä ekvivalenssi saadaan ottamalla huomioon Motzkin-polun pisteiden ordinaatit, lukuun ottamatta kahta ääripistettä, ja ottamalla huomioon kahden peräkkäisen pisteen ordinaattien ero.
Motzkin-numero on yhtä suuri kuin Motzkin-sanojen pituus , toisin sanoen sanat, joiden pituus on Motzkin-kieli . Tämä kieli on Dyckin kielen jatke sulkeissa, joka on saatu sekoittamalla Dyckin sanat uuden kirjaimen sanoihin. Tarkemmin sanottuna aakkoset, joissa on kolme kirjainta. Motzkinin kieli on yhtälön määrittämä sanaryhmä
tai vastaavalla tavalla, generoidaan algebrallisen kieliopin avulla
Kielen ensimmäiset sanat pituussuunnassa:
0 | 1 | |
1 | 1 | |
2 | 2 | |
3 | 4 | |
4 | 9 |
Motzkinin sanojen ja Motzkinin polun välinen vastaavuus saadaan merkitsemällä nouseva askel kirjaimella , laskeva askel kirjaimella ja vaakataso kirjaimella .
Ainoat neljä ensimmäistä Motzkinin tunnettua numeroa ovat seuraavan OEIS : n A092832 mukaan : 2 , 127 , 15 511 ja 953 467 954 114 363.
Donaghey ja Shapiro (1977) kuvaavat Motzkinin ja katalaanin numeroiden läheistä suhdetta neljällätoista eri Motzkin-numeron sovelluksella matematiikassa . Siitä lähtien kombinaattorista , teoreettisesta tietojenkäsittelystä ja matematiikasta on löydetty lukuisia Motzkin-numeroiden esiintymiä : MathSciNet listaa yli 100 artikkelia, joiden otsikossa on sana Motzkin .