\documentclass[12pt]{article} \usepackage{amsmath,mathrsfs,bbm} \usepackage{amssymb} \textwidth=4.825in \overfullrule=0pt \thispagestyle{empty} \begin{document} \noindent % % {\bf Emily Allen, F. Blanchet-Sadri, Cameron Byrum, Mihai Cucuringu and Robert Merca\c s} % % \medskip \noindent % % {\bf Counting Bordered Partial Words by Critical Positions} % % \vskip 5mm \noindent % % % % A {\em partial word}, sequence over a finite alphabet that may have some undefined positions or holes, is {\it bordered} if one of its proper prefixes is {\em 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 known. It turns out that all borders of a full word are {\em 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 {\em nonsimple}. Here, we give recursive formulas based on our approach of the so-called {\em simple and nonsimple critical positions}. \end{document} .