Below, a sequence of length \(N\) consisting of integers between \(1\) and \(M\) is simply called a sequence. Additionally, for a sequence \(A\), let \(A' := (A_{P_1}, A_{P_2}, \ldots, A_{P_N})\).

There are \(M^N\) sequences \(A\) in total. If \(X\) is the number of sequences \(A\) such that \(A = A'\), the number of \(A\)’s such that \(A' \lt A\) lexicographically and the number of those such that \(A' \gt A\) are equal from the symmetry, so the answer is \((M^N - X) / 2\).

Since \(X\) is the number of sequences \(A\) such that \(A_i = A_{P_i}\) for every \(i = 1, 2, \ldots, N\), if we consider an undirected graph \(G\) with the vertex set \(\lbrace 1, 2, \ldots, N \rbrace\) and the undirected edge \(\lbrace i, P_i \rbrace\) for each \(i = 1, 2, \ldots, N\), then \(X\) is equal to the number of ways to make each connected component in \(G\) correspond to an integer between \(1\) and \(M\). Thus, if \(C\) is the number of connected components in \(G\), we have \(X =M^C\).

Therefore, the answer is \((M^N - M^C)/2\).