  The 321,hexagon-avoiding (321-hex) permutations were introduced and studied
by Billey and Warrington in as a class of elements of S_n whose Kazhdan-Lusztig
and Poincare polynomials and the singular loci of whose Schubert varieties have
certain fairly simple and explicit descriptions. This paper provides a 7-term
linear recurrence relation leading to an explicit enumeration of the 321-hex
permutations. A complete description of the corresponding generating tree is
obtained as a by-product of enumeration techniques used in the paper, including
Schensted's 321-subsequences decomposition, a 5-parameter generating function
and the symmetries of the octagonal patterns avoided by the 321-hex
permutations.
