  Given a countable set X (usually taken to be N or Z), an infinite permutation
$\pi$ of X is a linear ordering $<_\pi$ of X. This paper investigates the
combinatorial complexity of infinite permutations on N associated with the
image of uniformly recurrent aperiodic binary words under the letter doubling
map. An upper bound for the complexity is found for general words, and a
formula for the complexity is established for the Sturmian words and the
Thue-Morse word.
