Weird permutations

@Khang Nguyen Thanh 's solution is more explanatory.But I will try to make it simplify.

First of all we will find the numbers which can occupy the position $1$ .Let it will be $a$ .As $1$ divides every $\{2,3,...32\}$ So, $a$ will divide every numbers in this position.If we consider any number excluding $1$ then there will be a time when we need to consider greater number than $32$ .So, $1$ position will always be occupied by $1$ .

Now comes to position $2$ .As $2$ divides $4,6,8,,,,,,,30,32$ .So, there will be a number in position two which will divide all the numbers in even positions.If we take greater than two then one time will come when we need to consider a number which will greater than $32$ .So, in position two $2$ will be there always.

The same logic is for all the numbers whose multiples are present in the range.Now consider the primes whose multiples are not present in this range.This primes are $\{17,19,23,29,31\}$ .These can permute with $5!=120$ ways.

Now , it's time to consider the primes whose number of multiples are same in the given range.So, we can exchange them. These primes are $11,13$ and multiples are $22,26$ .So, in position $11,22$ and $13,26$ we can made it fix or exchange them i.e in position $11,22$ we can write $13,26$ and in position $13,26$ we can write $11,22$ .So, there will be two ways.

So, total ways $120 \times 2=240$

We write $\{1, 2, \ldots, 32\}$ as $[32]$ . Let $f$ be a permutation on $[32]$ for which $a \mid b \implies f(a) \mid f(b)$ .

Lemma 1. For all $n \in [32]$ , $\left\lfloor \dfrac{32}{f(n)} \right\rfloor = \left\lfloor \dfrac{32}{n} \right\rfloor$ .

Proof: Suppose that $m \in [32]$ with $n \mid m$ . Then $f(n) \mid f(m)$ , so there is an injective mapping from multiples of $n$ to multiples of $f(n)$ . Thus, $f(n)$ has at least as many multiples in $[32]$ as $n$ does, so for all $n$ , $\lfloor 32/f(n) \rfloor \ge \lfloor 32/n \rfloor$ . But summing over all $n$ , we get $\sum_{n=1}^{32} \left\lfloor \dfrac{32}{f(n)} \right\rfloor \ge \sum_{n=1}^{32} \left\lfloor \dfrac{32}{n} \right\rfloor,$ and equality must hold because $f$ permutes $[32]$ . This forces equality for all $n$ , so $\left\lfloor \dfrac{32}{f(n)} \right\rfloor = \left\lfloor \dfrac{32}{n} \right\rfloor$ for all $n$ .

Lemma 2. For all $n$ , $\tau(f(n)) = \tau(n)$ .

Proof: Suppose that $m \in [32]$ with $m \mid n$ . Then $f(m) \mid f(n)$ , so there is an injective mapping from divisors of $n$ to divisors of $f(n)$ . Thus, $f(n)$ has at least as many divisors as $n$ does, so for all $n$ , $\tau(f(n)) \ge \tau(n)$ . But summing over all $n$ , we get $\sum_{n=1}^{32} \tau(f(n)) \ge \sum_{n=1}^{32} \tau(n),$ and equality must hold because $f$ permutes $[32]$ . This forces equality for all $n$ , so $\tau(f(n)) = \tau(n)$ for all $n$ .

The power behind Lemmas 1-2 is that, if $a$ permutes to $b$ under $f$ (that is, if $f(a) = b$ ), then $\lfloor 32/a \rfloor = \lfloor 32/b \rfloor$ and $\tau(a) = \tau(b)$ . This should force many $a$ to permute to themselves (i.e. to be fixed points under $f$ ). Our method is as follows: for each $n$ , compute $\lfloor 32/n \rfloor$ , isolate the blocks with equal value of $\lfloor 32/n \rfloor$ and use $\tau(n)$ as a "tiebreaker" of sorts:

This immediately forces $f(n) = n$ for $n = 1, 2, \ldots, 6$ . Now we tiebreak each of the four remaining blocks by computing $\tau(n)$ for each $n$ in each block:

Due to having unique values of $\tau$ , we see that $7, 8, 9, 10, 12, 16, 25$ must also be fixed points of $f$ (along with the $1, 2, 3, 4, 5, 6$ we found earlier). For the rest, we'll do a little more work. We have $(11, 13)$ , $(14, 15)$ , $(17, 19, 23, 29, 31)$ , $(18, 20, 28)$ , and $(22, 24, 26, 27)$ to resolve.

We know that $2 = f(2) \mid f(14)$ , so $f(14)$ cannot be $15$ . Thus, $14$ is a fixed point, as is $15$ .

We know that $3 = f(3) \mid f(18)$ and $5 = f(5) \mid f(20)$ , so $18, 20, 28$ are all fixed points as well.

We know that $8 = f(8) \mid f(24)$ and $9 = f(9) \mid f(27)$ , so $24, 27$ are also fixed points.

Now all that's left are $(11, 13)$ , $(17,19,23,29,31)$ , and $(22,26)$ (and this is where we can actually start making choices!) Since $(17,19,23,29,31)$ are primes with no other multiples in $[32]$ , any arbitrary permutation of them works for $f$ , so we have $5!=120$ choices here. Also, either permutation of $(11,13)$ works, but since $f(11) \mid f(22)$ and $f(13) \mid f(26)$ , each permutation of $(11,13)$ determines which permutation of $(22,26)$ must be used. Thus, there are only $2$ choices for $(11,13,22,26)$ .

In total, this gives $120 \times 2 = 240$ possible functions $f$ .

Step 1

1 is mapped to 1, prime numbers to prime numbers, squares to squares, products of two primes to products of two primes, etc. More rigorously, we can show by induction that if $n = p_1^{e_1}\cdot p_2^{e_2}\cdot p_3^{e_3} \cdots,$ then $f(n) = f(p_1)^{e_1}\cdot f(p_2)^{e_2}\cdot f(p_3)^{e_3}\cdots.$ Thus we only need to consider the restriction of the permutation to prime numbers; it determines the rest of the permutation.

Step 2

Prime numbers 2, 3, and 5 can be distinguished from the others based on their powers. The set $\{1,\dots,32\}$ contains $2^2$ through $2^5$ (but not $2^6$ ); $3^2$ and $3^3$ (but not $3^4$ ); $5^2$ (but not $5^3$ ); and no other powers of primes. Therefore the primes 2, 3, and 5 must be mapped to themselves.

Prime number 7 is distinguishable by the fact that $3\cdot 7$ is contained in the set, but not $3\cdot p$ for any greater prime $p$ . Therefore 7 must be mapped to itself.

Prime numbers 11 and 13 stand out because $2\cdot 11$ and $2\cdot 13$ are in the set, but not $2\cdot p$ for any greater prime $p$ . Thus $f(\{11,13\}) = \{11,13\}$ ; however, we have no way of distinguishing 11 and 13 in this fashion .

Finally, prime numbers 17, 19, 23, 29, and 31 have no multiples in the set. Therefore they can freely be swapped around. All we know is that $f(\{17,19,23,29,31\}) = \{17,19,23,29,31\}$ .

Step 3

Considering $f$ as a permutation on the prime numbers only, we know it is of the form $f(2,3,5,\dots,31) = (2)(3)(5)(7)\sigma(11,13)\tau(17,19,23,29,31),$ where $\sigma$ and $\tau$ are any permutations of the elements that follow. The number of permutations of this kind is $2!\cdot 5! = 2 \cdot 120 = \boxed{240}.$