Possible partitions, for k-means problem(k=2)
If $(P_1, P_2)$ is a partition of $P$, that means that $P_2 = P\setminus P_1$.
That means that is suffices to count the number of possible choices of $P_1$, which is the cardinal of the powerset of $P$, $|\mathcal{P}(P)| = 2^{|P|}$.
If $P_1$ and $P_2$ have symmetrical roles, you can divide the result by $2$ (but it does not change the asymptotical complexity).