Abstract
The Collatz map, a function from the set of positive integers to itself, maps an integer x to x/2 if x is even, and to 3x+1 if x is odd. The Collatz conjecture states that when the map is iterated the number one is eventually reached. We study permutations that arise as sequences from this iteration. We show that permutations of this type of length up to 14 are enumerated by the Fibonacci numbers. Beyond that, excess permutations appear. We will explain the appearance of these excess permutations and give an upper bound on their exact number.