How to calculate the number of arrangements of numbers in a string that can be obtained from the initial string by any sequence of permutations?

Question

Algorithms

I can't figure out how this can be done mathematically

Answer 1

(The full condition is in the comments to the question)
Algorithmically, here is the solution: Build a graph of n vertices, where there is an edge between all pairs of vertices that can be swapped. Calculate the sizes of the connected components and multiply their factorials. So, if there is only one component, then the answer will be n! (all possible permutations of n numbers can be obtained like this).
This works because any permutation can be obtained in each component. Proof: we build a spanning tree in the component. Then we take any leaf and drag any number there along the edges of the spanning tree. Cut a leaf from a tree. Repeat this operation until only one vertex remains.
If you need exactly a mathematical formula from P, then everything is complicated here, especially when the numbers P are large enough. For example, M=6, P1=3 P2=4. From vertices 3 and 4 there are no edges at all, and the edge P2 is only between the extreme vertices. In this way, very complex structures can be created.
However, if all P's are less than half N, then there is a simple answer. The graph will have GCD(P1+1,...,PM+1) connected components - all vertices that give the same remainder when divided by the greatest common divisor P+1. And the answer will be something like (floor(N/G)!)^G*(floor(N/G)+1)^(N%G)(where G is the greatest common divisor of all Ps increased by 1).
This is because with small enough P, you can always put them to one side or the other and so end up taking a step long G.
The proof is something like this: Consider the first half of the vertices. Of these, you can put the largest P to the right. And then any of the remaining P to the left. So we actually postponed from all these vertices any difference of two P to the right. If we first put the smaller P to the right, and then the maximum P back, then we put the same difference to the left. From considerations of symmetry, it turns out that we can postpone any difference P from all vertices in any direction. All differences are also less than half N. Continuing this process, as in the Euclidean algorithm, we get that we can deduct G from each vertex, which means that all vertices with the same remainder after dividing by G belong to the same connected component.
If some Ps are more than half (carefully look for yourself, + -1 is probably needed somewhere), then I don’t know the formula. It remains only to write DFS on the graph.