  We present a new class of binary words: the prefix normal words. They are
defined by the property that for any given length $k$, no factor of length $k$
has more $a$'s than the prefix of the same length. These words arise in the
context of indexing for jumbled pattern matching (a.k.a. permutation matching
or Parikh vector matching), where the aim is to decide whether a string has a
factor with a given multiplicity of characters, i.e., with a given Parikh
vector. Using prefix normal words, we give the first non-trivial
characterization of binary words having the same set of Parikh vectors of
factors. We prove that the language of prefix normal words is not context-free
and is strictly contained in the language of pre-necklaces, which are prefixes
of powers of Lyndon words. We discuss further properties and state open
problems.
