Amount of k-partitions of a number
You can solve this with DP. Let $DP[n][k][m]$ denote the number of partitions of $n$ into $k$ numbers, all of which are distinct and at most $m$. Then we have the recurrence

\begin{align}
DP[n][k][m] &amp;= \sum_{v = 1}^{m} DP[n-v][k-1][v-1]\\
&amp;= DP[n][k][m-1] + DP[n-m][k-1][v-m]
\end{align}

Since we can take the numbers forming the partition from largest to smallest, so whenever we take some number, all numbers we take after it must be strictly smaller. The base case is $DP[0][0][m] = 1$ for any $m$ and $DP[x][y][m] = 0$ whenever $x &lt; 0$ or $y &lt; 0$. If you care about the order of the elements in the partition, multiply the result by $k!$.

We can calculate this recurrence in $\mathcal{O}(n^{2} k)$, but tighter analysis gives an even better bound:

For a state $(n', k', m')$ to be reachable by this recurrence from $DP[n][k][n]$, we must have $m' \leq \frac{n-n'}{k-k'} \leq \frac{n}{k-k'}$ (since our number decreased by $n - n'$, so some number in the current partition of sum $n - n'$ and size $k - k'$ must be at most $\frac{n - n'}{k - k'}$). But this means that for any fixed $k'$, there are at most $\frac{n^{2}}{k-k'}$ reachable DP states, and

\begin{equation*}
\sum_{k' = 0}^{k-1} \frac{n^2}{k-k'} = \mathcal{O}(n^2 \log k)
\end{equation*}

Thus the actual complexity is $\mathcal{O}(n^2 \log k)$.