Definitions
Let $(G, \cdot)$ be a finite group, and let $\{g_i\}_{i=1}^{|G|-1}$ be a sequence of elements in $G$.
Let $p_n$ denote the "partial product" $g_1 \cdot g_2 \cdots g_n$ with $p_0 = e_G$, the identity element of $G$.
Call the sequence $\{g_i\}_{i=1}^{|G|-1}$ Hamiltonian if $G = \{p_0, p_1, \dots, p_{|G| - 1}\}$ as sets.
Call a sequence $\{g_i\}_{i=1}^{|G|-1}$ palindromic if $g_k = g_{|G|-k}$ for all $1 \leq k < |G|$.
Example for $S_3$
The symmetric group $S_3$ has twelve palindromic sequences: $$ \begin{alignat}{6} 1) \hspace{2em} && (1~2), && (1~3), && (1~2), && (1~3), && (1~2). \\ 2) \hspace{2em} && (1~2), && (2~3), && (1~2), && (2~3), && (1~2). \\ 3) \hspace{2em} && (1~3), && (1~2), && (1~3), && (1~2), && (1~3). \\ 4) \hspace{2em} && (1~3), && (2~3), && (1~3), && (2~3), && (1~3). \\ 5) \hspace{2em} && (1~2~3), && \hspace{1em} (1~2~3), && \hspace{1em} (1~2), && \hspace{1em} (1~2~3), && \hspace{1em} (1~2~3). \\ 6) \hspace{2em} && (1~2~3), && (1~2~3), && (1~3), && (1~2~3), && (1~2~3). \\ 7) \hspace{2em} && (1~2~3), && (1~2~3), && (2~3), && (1~2~3), && (1~2~3). \\ 8) \hspace{2em} && (1~3~2), && (1~3~2), && (1~2), && (1~3~2), && (1~3~2). \\ 9) \hspace{2em} && (1~3~2), && (1~3~2), && (1~3), && (1~3~2), && (1~3~2). \\ 10) \hspace{2em} && (1~3~2), && (1~3~2), && (2~3), && (1~3~2), && (1~3~2). \\ 11) \hspace{2em} && (2~3), && (1~2), && (2~3), && (1~2), && (2~3). \\ 12) \hspace{2em} && (2~3), && (1~3), && (2~3), && (1~3), && (2~3). \end{alignat} $$ In particular, the first sequence has "partial products":
- $p_0 = e$,
- $p_1 = (1~2)$,
- $p_2 = (1~2)(1~3) = (1~2~3)$,
- $p_3 = (1~2~3)(1~2) = (2~3)$,
- $p_4 = (2~3)(1~3) = (1~3~2)$,
- $p_5 = (1~3~2)(1~2) = (1~3)$,
which are a rearrangement of the elements of $S_3$.
Question
I'm interested in counting the number of palindromic Hamiltonian sequences on the symmetric group $S_4$. I'm okay with a solution that requires a computer, but even better would be an argument that can be modified to also count the number of palindromic Hamiltonian sequences for $S_5$, $S_6$, and so on.
Naively, there are $(4! - 1)^{12} > 10^{16}$ palindromic sequences to check for $S_4$—so trying to solve this problem with brute force is hopeless. The optimizations that I can think of (e.g. if $g_i$ is a transposition, then $g_{i+1} \neq g_i$.) don't do enough to shrink the search space.