kth.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Counting words avoiding patterns of length three with generating functions
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.).
KTH, Skolan för teknikvetenskap (SCI), Matematik (Inst.).
2015 (Engelska)Självständigt arbete på grundnivå (kandidatexamen), 10 poäng / 15 hpStudentuppsats (Examensarbete)
Abstract [en]

The set of 123-avoiding words with exactly r occurrences of each letter was recently enumerated by N. Shar and D. Zeilberger. This paper enumerates more complicated sets of pattern avoiding words, such as those allowing 1, 2, ... or r occurrences of each letter, or those for which the numbers of occurrences of each individual letter follow a repeating sequence. The results are also generalized to apply to all patterns of length three with distinct letters. The generating functions enumerating the words are shown to be algebraic, for all investigated sets of words. A notable number of coefficients for the relevant generating functions have been found and the first few confirmed by independent methods. The asymptotic behaviour of these coefficients has been established as exponential. The employed strategy involves partitioning words into subwords which allow for the construction of equations relating the generating functions.

Abstract [sv]

Mängden av 123-undvikande ord med exakt r förekomster av varje bokstav enumererades nyligen av N. Shar och D. Zeilberger. Detta arbete enumererar mer komplicerade mängder av mönsterundvikande ord, såsom de som tillåter 1,2, ... eller r förekomster av varje bokstav, eller de för vilka antalet förekomster av varje enskild bokstav följer en upprepande sekvens. Resultaten generaliseras även till att gälla alla mönster av längd tre med distinkta bokstäver. De genererande funktionerna som enumererar orden bevisas vara algebraiska, för alla undersökta ordmängder. Ett ansenligt antal koefficienter för de relevanta genererande funktionerna har beräknats och de första av dessa har bekräftats med oberoende metoder. Dessa koefficienters asymptotiska beteende har visats vara exponentiellt. Metoden som utnyttjas involverar en uppdelning i delord som tillåter konstruerandet av ekvationer som relaterar de genererande funktionerna.

Ort, förlag, år, upplaga, sidor
2015. , s. 48
Nationell ämneskategori
Matematik
Identifikatorer
URN: urn:nbn:se:kth:diva-168019OAI: oai:DiVA.org:kth-168019DiVA, id: diva2:813933
Handledare
Tillgänglig från: 2015-05-25 Skapad: 2015-05-25 Senast uppdaterad: 2022-06-23Bibliografiskt granskad

Open Access i DiVA

fulltext(369 kB)434 nedladdningar
Filinformation
Filnamn FULLTEXT01.pdfFilstorlek 369 kBChecksumma SHA-512
05013b91ba6aa07e06d689ea411b5ff205b3de95bd61e5468758be80783cdcc8adb970ece0937d52d30db26cb8c364b4bd528ad81f01c77ea80d90079408b0f1
Typ fulltextMimetyp application/pdf

Av organisationen
Matematik (Inst.)
Matematik

Sök vidare utanför DiVA

GoogleGoogle Scholar
Totalt: 434 nedladdningar
Antalet nedladdningar är summan av nedladdningar för alla fulltexter. Det kan inkludera t.ex tidigare versioner som nu inte längre är tillgängliga.

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 481 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf