对于一个大小为 $n$ 的多重集, 求有多少多重集排列使得相邻元素不等

具体的, 对于多重集 $S = \{a_1, a_2, a_3, \cdots , a_n\}$ , 求一组 $1 \sim n$ 的排列 $p$ , 使得 $\forall i \in [1, n), a_{p_i} \neq a_{p_i + 1}$