Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: Counting Bordered Partial Words by Critical Positions. | Counting Bordered Partial Words by Critical Positions Emily Allen Department of Mathematical Sciences Carnegie Mellon University 5032 Forbes Ave. Pittsburgh PA 15289 USA eaallen@ Cameron Byrum Department of Mathematics University of Mississippi . Box 1848 University MS 38677 USA ctbyrum@ F. Blanchet-Sadri Department of Computer Science University of North Carolina . Box 26170 Greensboro NC 27402-6170 USA blanchet@ Mihai Cucuringu Department of Mathematics Princeton University Washington Road Princeton NJ 08544-1000 USA mcucurin@ Robert Mercas GRLMC Universitat Rovira i Virgili Campus Catalunya Departament de Filologies Romaniques Av. Catalunya 35 Tarragona 43002 Spain robertmercas@ Submitted Nov 10 2010 Accepted Jun 14 2011 Published Jul 1 2011 Mathematics Subject Classification 68R15 68Q45 05A05 This paper is dedicated to Professor Pal Domosi on the occasion of his 65th birthday. Abstract A partial word sequence over a finite alphabet that may have some undefined positions or holes is bordered if one of its proper prefixes is compatible with one of its suffixes. The number theoretical problem of enumerating all bordered full words the ones without holes of a fixed length n over an alphabet of a fixed size k is well This material is based upon work supported by the National Science Foundation under Grants DMS-0452020 and DMS-0754154. The Department of Defense is also gratefully acknowledged. THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P138 1 known. It turns out that all borders of a full word are simple and so every bordered full word has a unique minimal border no longer than half its length. Counting bordered partial words having h holes with the parameters k n is made extremely more difficult by the failure of that combinatorial property since there is now the possibility of a minimal border that is nonsimple. Here we give recursive formulas based on our approach of the so-called simple and .
