Ordered Triples Summing to 20

Combinatorics · Easy · Free problem

How many ordered triples $(a, b, c)$ of positive integers satisfy $a + b + c = 20$?

Hints

  1. This is a constrained integer partition problem. Think about how to reduce "positive integers" to "non-negative integers."
  2. Substitute $a' = a - 1$, $b' = b - 1$, $c' = c - 1$ so that $a', b', c' \geq 0$ and apply stars and bars.
  3. After substitution you need the number of non-negative integer solutions to $a' + b' + c' = 17$, which is $\binom{19}{2}$.

Worked Solution

How to Think About It: This is a textbook stars-and-bars problem. You are distributing 20 identical units among 3 labeled bins, each bin getting at least 1. The "at least 1" constraint is the only wrinkle -- handle it by substituting away the minimum.

Quick Estimate: With 3 variables summing to 20, the answer should be on the order of

0^2 / 2 \approx 200$. The exact formula will be a binomial coefficient close to this.

Approach: Reduce to the standard stars-and-bars form by shifting variables.

Formal Solution:

Since $a, b, c \geq 1$, substitute $a' = a - 1$, $b' = b - 1$, $c' = c - 1$, where $a', b', c' \geq 0$. The constraint becomes:

$a' + b' + c' = 20 - 3 = 17$

By stars and bars, the number of non-negative integer solutions to $x_1 + x_2 + \cdots + x_k = n$ is $\binom{n + k - 1}{k - 1}$. Here $n = 17$ and $k = 3$:

$\binom{17 + 2}{2} = \binom{19}{2} = \frac{19 \times 18}{2} = 171$

Answer: $\boxed{171}$

Intuition

Stars and bars is one of the most fundamental counting tools in combinatorics. The core idea is a bijection: distributing $n$ identical objects into $k$ bins is the same as placing $k - 1$ dividers among $n$ objects, giving $\binom{n + k - 1}{k - 1}$ arrangements. The "positive integer" constraint just means each bin starts with one object already in it, so you subtract $k$ from $n$ first.

This pattern appears constantly in quant interviews -- any time you are counting compositions, allocating resources, or distributing indistinguishable items. It is also the backbone of multinomial coefficient arguments. The quick sanity check is that the answer should scale roughly as $n^{k-1}/(k-1)!$, which for $n = 17, k = 3$ gives

7^2/2 \approx 144.5$ -- in the right ballpark of 171.

Open the full interactive solver →