Problem 76: Counting Summations

Mathematical Foundation

Definition 1 (Integer Partition). A partition of a non-negative integer $n$ is a multiset $\{a_1, a_2, \ldots, a_k\}$ of positive integers satisfying $\sum_{i=1}^{k} a_i = n$. Two partitions are identical if and only if they contain the same parts with the same multiplicities. The partition function $p(n)$ counts the number of partitions of $n$. By convention, $p(0) = 1$ (the empty partition).

Definition 2 (Restricted Partition). Let $p_{\le m}(n)$ denote the number of partitions of $n$ into parts each at most $m$. Equivalently, $p_{\le m}(n)$ counts the number of solutions in non-negative integers $(c_1, c_2, \ldots, c_m)$ to $\sum_{k=1}^{m} k \cdot c_k = n$, where $c_k$ represents the multiplicity of part $k$. Note that $p(n) = p_{\le n}(n)$.

Theorem 1 (Generating Function for $p(n)$). The ordinary generating function for the partition function is

Proof. For each positive integer $k$, the geometric series $\frac{1}{1-x^k} = \sum_{c_k=0}^{\infty} x^{c_k \cdot k}$ encodes the choice of $c_k \geq 0$ copies of part $k$ contributing $c_k \cdot k$ to the total. The Cauchy product of all such series over $k \geq 1$ yields

Absolute convergence for $|x| < 1$ follows from $\sum_{k=1}^{\infty} \log\frac{1}{1-|x|^k} \leq \sum_{k=1}^{\infty} \frac{|x|^k}{1-|x|^k} < \infty$, since the terms are $O(|x|^k)$ and $\sum |x|^k$ converges. $\blacksquare$

Theorem 2 (Euler’s Pentagonal Number Theorem). As formal power series (and for $|x| < 1$):

Proof (Franklin’s Involution). The coefficient of $x^n$ on the left is $\sum_{\lambda \in \mathcal{D}_n} (-1)^{\ell(\lambda)}$, where $\mathcal{D}_n$ denotes the set of partitions of $n$ into distinct parts and $\ell(\lambda)$ is the number of parts.

For $\lambda = (\lambda_1 > \lambda_2 > \cdots > \lambda_r) \in \mathcal{D}_n$, define two parameters:

• $s(\lambda) = \lambda_r$: the smallest part.
• $t(\lambda)$: the length of the maximal sequence of consecutive integers descending from $\lambda_1$. That is, $t(\lambda) = \max\{m \geq 1 : \lambda_1 - i + 1 \in \{\lambda_1, \ldots, \lambda_r\} \text{ for all } 1 \leq i \leq m\}$.

Define the map $\phi: \mathcal{D}_n \to \mathcal{D}_n$ as follows:

• Move A (applicable when $s < t$, or when $s = t$ and $\lambda_r \neq \lambda_1 - t + 1$): Remove the smallest part $\lambda_r = s$ and add $1$ to each of the $s$ largest parts $\lambda_1, \lambda_2, \ldots, \lambda_s$. This produces a partition with $r - 1$ distinct parts.
• Move B (applicable when $s > t$, or when Move A is inapplicable): Subtract $1$ from each of the $t$ largest parts $\lambda_1, \ldots, \lambda_t$, and insert $t$ as a new smallest part. This produces a partition with $r + 1$ distinct parts.

One verifies that (i) Moves A and B are mutual inverses, (ii) each changes $\ell(\lambda)$ by exactly $\pm 1$, hence reverses the sign $(-1)^{\ell(\lambda)}$, and (iii) the map $\phi$ is undefined (yielding fixed points) precisely when the two moves coincide or become degenerate. This occurs when:

• $s = t$ and $\lambda_r = \lambda_1 - t + 1$: partition is $(r, r+1, \ldots, 2r-1)$, giving $n = r(3r-1)/2$.
• $s = t + 1$ and $r = s$: gives $n = r(3r+1)/2$.

At these fixed points the sign contribution is $(-1)^r$. For all other $\lambda$, the map $\phi$ pairs each partition with one of opposite sign, so the net contribution cancels. $\blacksquare$

Theorem 3 (Partition Recurrence via Pentagonal Numbers). For $n \geq 1$:

where $p(0) = 1$, $p(m) = 0$ for $m < 0$, and the sum terminates when both pentagonal arguments become negative.

Proof. Multiplying the generating functions from Theorems 1 and 2:

Extracting the coefficient of $x^n$ for $n \geq 1$:

Rearranging and noting that $(-1)^{j} \cdot (-1) = (-1)^{j+1}$ yields the stated recurrence. $\blacksquare$

Theorem 4 (Correctness of Partition DP). Define the array $\mathrm{dp}[0..n]$ by $\mathrm{dp}[0] = 1$, $\mathrm{dp}[j] = 0$ for $1 \leq j \leq n$. For $k = 1, 2, \ldots, n$ and for $j = k, k+1, \ldots, n$, perform $\mathrm{dp}[j] \mathrel{+}= \mathrm{dp}[j - k]$. Then upon termination, $\mathrm{dp}[n] = p(n)$.

Proof. We prove by induction on $k$ that after processing part size $k$, the value $\mathrm{dp}[j]$ equals $p_{\le k}(j)$ for all $0 \leq j \leq n$.

Base case ($k = 0$): Before any updates, $\mathrm{dp}[0] = 1 = p_{\le 0}(0)$ and $\mathrm{dp}[j] = 0 = p_{\le 0}(j)$ for $j \geq 1$. This is correct since the only partition using parts $\leq 0$ is the empty partition of $0$.

Inductive step: Assume $\mathrm{dp}[j] = p_{\le k-1}(j)$ for all $j$ before processing part size $k$. The update loop sets $\mathrm{dp}[j] \leftarrow \mathrm{dp}[j] + \mathrm{dp}[j - k]$ for $j = k, k+1, \ldots, n$. After this pass, $\mathrm{dp}[j]$ accumulates:

since the forward iteration (increasing $j$) allows the value $\mathrm{dp}[j - k]$ to already reflect uses of part $k$. This telescopes to the partition identity $p_{\le k}(j) = \sum_{m=0}^{\lfloor j/k \rfloor} p_{\le k-1}(j - mk)$, which counts partitions of $j$ with parts $\leq k$ by conditioning on the multiplicity $m$ of part $k$. After $k = n$, we have $\mathrm{dp}[n] = p_{\le n}(n) = p(n)$. $\blacksquare$

Remark. The problem asks for partitions into at least two parts, which excludes the trivial partition $n = n$. The answer is therefore $p(100) - 1$.

Editorial

This is the standard partition DP in unbounded-knapsack form. We process possible part sizes in increasing order, and after part size $k$ is handled, the table entry for a sum $j$ represents the number of partitions of $j$ that use only parts up to $k$.

The update is natural: every partition of $j-k$ can be extended by adding one more part of size $k$, so we add the number of ways to make $j-k$ into the number of ways to make $j$. Because part sizes are introduced in sorted order, the same multiset is never counted in different orders. That is exactly why the DP counts partitions rather than compositions. At the end we subtract one to remove the trivial partition consisting of $100$ alone.

Pseudocode

Create a table for sums from 0 to 100 and fill it with zeros.
Set the entry for sum 0 to 1.

For each allowed part size from 1 to 100:
    For each target sum that can include this part:
        add the number of ways to form the remaining sum after taking one such part

Subtract one to exclude the single-part partition 100.
Return the resulting count.

Complexity Analysis

Time: The nested loops execute $\sum_{k=1}^{n}(n - k + 1) = \sum_{i=1}^{n} i = n(n+1)/2 = O(n^2)$ iterations, each performing $O(1)$ arithmetic. For $n = 100$, this is $5050$ operations.

Space: The one-dimensional DP array requires $n + 1 = O(n)$ entries.

Alternative: The pentagonal number recurrence (Theorem 3) computes each $p(k)$ in $O(\sqrt{k})$ time, yielding $O(n\sqrt{n})$ total time.

Answer

#include <bits/stdc++.h>
using namespace std;

int main() {
    const int N = 100;
    vector<long long> dp(N + 1, 0);
    dp[0] = 1;

    // Partition DP: for each part size k, update dp[j] += dp[j - k]
    for (int k = 1; k <= N; k++)
        for (int j = k; j <= N; j++)
            dp[j] += dp[j - k];

    // p(100) - 1: exclude the trivial partition 100 = 100
    cout << dp[N] - 1 << endl;
    return 0;
}

"""
Problem 76: Counting Summations

How many different ways can 100 be written as a sum of at least two positive integers?
Answer: p(100) - 1 = 190569291
"""


def partition_count(n):
    """Compute p(n) via the standard unbounded-knapsack partition DP."""
    dp = [0] * (n + 1)
    dp[0] = 1
    for k in range(1, n + 1):
        for j in range(k, n + 1):
            dp[j] += dp[j - k]
    return dp[n]


def main():
    N = 100
    answer = partition_count(N) - 1  # exclude the trivial partition n = n
    print(answer)


if __name__ == "__main__":
    main()