Amount of k-partitions of a number

Question

I'm stuck on writing an algorithm for getting the amount of distinct partitions for a number $n$ with the partition being size $k$. It's important that there isn't any repetition in the partitions. For example:

The partitions of size 2 for number 5 are:

• [4, 1]
• [3, 2]

The partitions of size 3 for number 6 exists only of:

• [3, 2, 1]

Notice that [2, 2, 2] isn't a partition because it has a repeating use of 2.

I currently have implemented a dynamic algorithm that finds the amount of partitions that allow repetition. Here $m$ is is the number and $n$ is the size of the partitions.

def count_partitions(m, n):


    def e_at(i,j):
        if i == j and j == -1:
            return 1
        if i < j:
            return 0
        else:
            return p[i][j]

    p = [[-1 for _ in range(n)] for _ in range(m)]
    for i in range(m):
        p[i][0] = 1

    for i in range(m):
        for j in range(1, min(i + 1, n)):
            if i < 2*j:
                p[i][j] = e_at(i-1,j-1)
            else:
                p[i][j] = e_at(i-1, j-1) + e_at(i-j-1,j)

    return p[m-1][n-1]

I've also got a program to generate all the different distinct k-partitions of a number $n$

def generate_partitions(n, k):
    if n == 0:
        return []


    def rec_partition(m, b, n, a, l):
        if m == 0:
            l.append(conj_partition(a[:n]))
        else:
            c = a[n]
            for i in range(1, min(b,m) + 1):
                a[n] = i
                rec_partition(m-i, i, n+1, a, l)
            a[n] = c


    def has_double(l):
        for i in range(len(l) - 1):
            if l[i] == l[i+1]:
                return True
        return False

    l = []
    a = [0] * n

    a[0] = k
    rec_partition(n - k, k,1, a, l)

    return sorted([p for p in l if not has_double(p)], reverse=True)

So far the only way I found to get the number of distinct k-partitions is to generate them all and take the length of the returned list.

However I feel like there would be a better way to get the amount without generating them all by modifying the dynamic programming algorithm above. But I haven't had any luck with that.

Anyone has any idea that would help?

Answer 1

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] &= \sum_{v = 1}^{m} DP[n-v][k-1][v-1]\\ &= 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 < 0$ or $y < 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)$.