CritPt / Challenge_50_main / Let S_(n) be the permutation group of order n, where n is a positive…

# Problem setup:
Let S_(n) be the permutation group of order n, where n is a positive integer. Consider the following splitting and merging events:
1. At t=0, there is one permutation w₀=(123⋯n)∈S_(n).
2. At t=1, w₀ splits into w₁w₂.
3. At t=2, first w₁ splits into w₃w_(4−), and w₂ splits into w_(4+)w₅. Then w_(4±) merge into w₄=w_(4−)w_(4+).
4. At t=3, the first splitting event is
  \begin{equation}
  w_3 = w_6 w_{7-}, \quad w_4 = w_{7+} w_{8-}, \quad w_5 = w_{8+} w_{9-},
  \end{equation}
 which is followed by the merging event
  \begin{equation}
  w_7 = w_{7-} w_{7+}, \quad w_8 = w_{8-} w_{8+}.
  \end{equation}
5. This process continues.

All the w's are permutations in S_(n). The pattern is such that at the boundary the permutation just splits, but in the middle the neighboring permutations labeled with − and + will merge. Thus, one will end up with one more permutation each time.

Suppose all of these splittings are minimal decompositions defined as follows: Let d(g) be the minimal number of transpositions in g. g=g₁g₂ is a minimal decomposition when the total minimal number of transpositions does not change, i.e.,
\begin{equation}
d(g) = d(g_1) + d(g_2).
\end{equation}
This holds for any product decomposition in this problem.

Let the number of configurations at time t be a_(n)(t).

# Main problem:

Compute a₄₀(3). Note that there may be multiple configurations that lead to the same w₅, w₆, w₇ and w₈ at t=3. You should count all of them. Return your answer as an integer.

# Problem setup:
Let $S_n $ be the permutation group of order $n$, where $n$ is a positive integer. Consider the following splitting and merging events:
1. At $ t = 0 $, there is one permutation $ w_0 = (123 \cdots n) \in S_n$.
2. At $ t = 1 $, $ w_0 $ splits into $ w_1 w_2 $.
3. At $ t = 2 $, first $ w_1 $ splits into $ w_3 w_{4-} $, and $ w_2 $ splits into $ w_{4+} w_5 $. Then $ w_{4\pm} $ merge into $ w_4 = w_{4-} w_{4+} $.
4. At $ t = 3 $, the first splitting event is
  \begin{equation}
  w_3 = w_6 w_{7-}, \quad w_4 = w_{7+} w_{8-}, \quad w_5 = w_{8+} w_{9-},
  \end{equation}
 which is followed by the merging event
  \begin{equation}
  w_7 = w_{7-} w_{7+}, \quad w_8 = w_{8-} w_{8+}.
  \end{equation}
5. This process continues.

All the $w$'s are permutations in $S_n$. The pattern is such that at the boundary the permutation just splits, but in the middle the neighboring permutations labeled with $ - $ and $ + $ will merge. Thus, one will end up with one more permutation each time.

Suppose all of these splittings are minimal decompositions defined as follows: Let $ d(g) $ be the minimal number of transpositions in $ g $. $ g = g_1 g_2 $ is a minimal decomposition when the total minimal number of transpositions does not change, i.e.,
\begin{equation}
d(g) = d(g_1) + d(g_2).
\end{equation}
This holds for any product decomposition in this problem.

Let the number of configurations at time $ t $ be $ a_n(t) $.

# Main problem:

Compute $ a_{40}(3) $. Note that there may be multiple configurations that lead to the same $w_5 $, $ w_6 $, $ w_7$ and $w_8$ at $t = 3$. You should count all of them. Return your answer as an integer.