I think we can do it this way... We will prove with mathematical induction that for $n$ girls, there are $2^{n-1}$ ways to arrange the girls. First, for $n=1$, it's obvious. Assume for $n=k$ it's true. WLOG assume the new girl to be taller than everyone else. This is acceptable, as the following illustration shows: Let the girls be $1,2,3,\cdots,k$ in increasing height. Let the new girl be $A$ that is taller than $m$ but shorter than $m+1$ for some non-negative integer $m$ less than $k$. Take the tallest girl out, adjust all girls whose numbers are more than $m$ so girl $i$ assumes the $i+1$-th girl's position, and $A$ assumes $m+1$-th position. This way, the remaining girl is the tallest, and the remaining girls have the same relative height position as before. Now, the tallest girl can only be at the front or the back of the line (otherwise that girl has a shorter girl both in front of and behind her), giving two possible positions. Multiply this with the number of positions with $k$ girls which is $2^{k-1}$ to get $2^k$, satisfying the claim. So with $19$ girls, there are $\boxed{2^{18} = 262144}$ ways to line them.

Hi; To generate all the sequences that do have a smaller girl in front and in back we have the recurrence: $ a(n) = n! - 2^{n-1} $ with a(3) = 2 So for the sequences that do not. $ a(n) = 2^{n-1} $ http://oeis.org/search?q=2%2C16%2C104%2C688&sort=&language=english&go=Search Bottom one is the one you want.