How many mesas begin with a given string?
Ruby, 142 characters
m=-&gt;l{[*l[0].chars].repeated_permutation(l[-1].size+1).reduce(1){|s,x|l.any?{|y|x*''=~/#{[*y.chars]*'.*'}/}?s:s+m[l+[x*'']]}}
p m[[gets.chop]]

This algorithm is constructive, i.e. it builds all possible mesas for the input string and counts them. It makes the program really, really slow - but hey, it is codegolf.
Example runs:
&gt; a
1
&gt; aa
1
&gt; ab
43