For an $M^{th}$ order Markov chain, $P\left(X_n|X_{n-M}...X_{n-1}\right)$, what's the number of parameters required to know the conditionals? We have discrete variables each with $K$ states.
I think it should be $K^M\left(K-1\right)$, but some books mention $K^{M-1}\left(K-1\right)$.
Other than Markov Chains, if you need to define a probability table for $P(X|Y)$, you'll have $(K_x-1)K_y$ degrees of freedom, where $K_x$ is the total number of states for the variable $X$, and $K_y$ is the total number of states for the variable $Y$, since when $Y$ is fixed, when $K_x-1$ probabilities are computed, the last one can be found from the remaining by just subtracting from $1$. This generalizes to the following: $$P(X_1,...,X_n|Y_1,Y_2,...Y_m)\rightarrow \left[\left(\prod_{i=1}^n{K_{X_i}}\right)-1\right]\prod_{i=1}^m{K_{Y_i}}$$ where for your case, it is $(K-1)K^M$.
There is a typo in Bishop's particular edition, as reported in here.
