Given a countable set X (usually taken to be the natural numbers or integers), an infinite permutation, pi, of X is a linear ordering of X. This paper investigates the combinatorial complexity of infinite permutations on the natural numbers associate
d 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.
