Problem 1660

Solution:
We decompose into cycle types of $\sigma$. Note that within each cycle, all vertices have the same degree; also note that the tree has total degree $14$ across its vertices (by all its seven edges).

For any permutation that has a $1$ in its cycle type (i.e., it has a fixed point), let $1 \leq a \leq 8$ be a fixed point. Consider the tree that consists of the seven edges from $a$ to the seven other vertices—this permutation (with $a$ as a fixed point) is an automorphism of this tree.

For any permutation that has cycle type $2+6$, let $a$ and $b$ be the two elements in the $2$-cycle. If the $6$-cycle consists of $c, d, e, f, g, h$ in that order, consider the tree with edges between $a$ and $b, c, e, g$ and between $b$ and $d, f, h$. It's easy to see $\sigma$ is an automorphism of this tree.

For any permutation that has cycle type $2+2+4$, let $a$ and $b$ be the two elements of the first two-cycle. Let the other two-cycle consist of $c$ and $d$, and the four-cycle be $e, f, g, h$ in that order. Then consider the tree with edges between $a$ and $b$, $a$ and $c$, $b$ and $d$, $a$ and $e$, $b$ and $f$, $a$ and $g$, $b$ and $h$. It's easy to see $\sigma$ is an automorphism of this tree.

For any permutation that has cycle type $2+3+3$, let $a$ and $b$ be the vertices in the $2$-cycle. One of $a$ and $b$ must be connected to a vertex distinct from $a, b$ (follows from connectedness), so there must be an edge between a vertex in the $2$-cycle and a vertex in a $3$-cycle. Repeatedly applying $\sigma$ to this edge leads to a cycle of length $4$ in the tree, which is impossible (a tree has no cycles). Therefore, these permutations cannot be automorphisms of any tree.

For any permutation that has cycle type $3+5$, similarly, there must be an edge between a vertex in the $3$-cycle and a vertex in the $5$-cycle. Repeatedly applying $\sigma$ to this edge once again leads to a cycle in the tree, which is not possible. So these permutations cannot be automorphisms of any tree.

The only remaining possible cycle types of $\sigma$ are $4+4$ and $8$. In the first case, if we let $x$ and $y$ be the degrees of the vertices in each of the cycles, then $4x+4y=14$, which is impossible for integer $x, y$. In the second case, if we let $x$ be the degree of the vertices in the $8$-cycle, then $8x=14$, which is not possible either.

So we are looking for the number of permutations whose cycle type is not $2+2+3$, $8$, $4+4$, $3+5$. The number of permutations with cycle type $2+2+3$ is $\binom{8}{2} \frac{1}{2} \binom{6}{3}(2!)^{2}=1120$, with cycle type $8$ is $7!=5040$, with cycle type $4+4$ is $\frac{1}{2}\binom{8}{4}(3!)^{2}=1260$, with cycle type $3+5$ is $\binom{8}{3}(2!)(4!)=2688$. Therefore, by complementary counting, the number of permutations that ARE automorphisms of some tree is $8!-1120-1260-2688-5040=30212$.