What Is Combination Sum?
A combination sum adds several binomial coefficients: the sum of C(n, k) for k from a to b. It counts, for example, the subsets of an n-item set that contain between a and b items. Summing over every k from 0 to n gives 2ⁿ, the number of all subsets.
Enter n and the first and last k. The calculator returns the sum, the share of all subsets, the sums over even and odd k, the central coefficient, and a table with every term and its running total. A bar chart of C(n, k) highlights your range.
The article below gives the formulas, variables, a worked example and answers to questions about sums of binomial coefficients.
How to Use the Combination Sum Calculator
- Enter n, the total number of items.
- Enter the first and last k to include.
- Read the total and its share of all subsets.
- Check each term in the table.
Combination Sum Formula
Combination
Sum over a range
Full sum
Combination Sum Variables Explained
| Symbol | Meaning | Notes |
|---|---|---|
| n | Number of items in the set | |
| k | Number of items chosen | |
| C(n, k) | Number of ways to choose k from n | n! ÷ (k!(n − k)!) |
| 2ⁿ | Total number of subsets |
Combination Sum Worked Example
For n = 10, the number of ways to choose at most 3 items is C(10,0) + C(10,1) + C(10,2) + C(10,3) = 1 + 10 + 45 + 120 = 176. The total number of subsets is 2¹⁰ = 1024, so 176 ÷ 1024 = 17.2 % of all subsets have at most 3 items.
With the example values loaded in the calculator above, the steps are:
- Each term is C(n, k) = n! ÷ (k!(n − k)!).
- Terms for n = 10: C(10,0) = 1, C(10,1) = 10, C(10,2) = 45, C(10,3) = 120.
- Sum = 176.
- Check: the full sum over k = 0 to 10 equals 2^10 = 1,024.
Result: Σ C(10, k) for k = 0 to 3 = 176; Share of all subsets = 17.1875 %.
How to Read a Sum of Combinations
The sum C(n, 0) + C(n, 1) + … + C(n, r) counts the subsets of size r or fewer. For n = 10 and r = 3 that is 1 + 10 + 45 + 120 = 176 subsets. The total number of subsets is 2¹⁰ = 1024, so 176 is about 17.2% of all of them.
The terms rise to a peak at the middle, k = n ÷ 2, and fall again. That is why the sum over the first few k is small compared with 2ⁿ unless the range reaches the middle.
Where Combination Sum Is Used
"At most r" counts
Count the ways to pick at most r items from n, such as a team of at most 3 from 10 people.
Subset counting
Check the identity that all subsets number 2ⁿ, and see what share a chosen range makes up.
Probability
Divide the sum by 2ⁿ to get the chance that a fair coin lands heads at most r times in n flips.
Discrete maths
Verify the even and odd sums of the binomial coefficients, which are equal for n ≥ 1.
Common Combination Sum Mistakes to Avoid
- Include k = 0 when you count "at most r". It is the empty selection.
- Order does not matter in a combination. If order matters, use permutations instead.
- The sum over a full range from 0 to n is always 2ⁿ, which is a useful sanity check.
- Large n gives huge numbers. The calculator shows exact integers up to a limit.
Combination Sum Terms and Definitions
- Binomial coefficient
- Another name for C(n, k), the number of k-element subsets of an n-element set.
- Subset
- A selection of items from a set, in any order.
Combination Sum FAQs
How do you find the sum of combinations?
Add C(n, k) for each k in your range. For n = 10 and k from 0 to 3, the terms are 1, 10, 45 and 120, which add to 176.
What is the sum of all C(n, k)?
It is 2ⁿ, the total number of subsets of an n-element set. For n = 10 that is 1024.
How many ways can I choose at most r items from n?
Add C(n, 0) through C(n, r). It is the number of subsets with r or fewer elements, including the empty set.
Why is the sum of even-k terms equal to the sum of odd-k terms?
Expanding (1 − 1)ⁿ gives 0 for n ≥ 1, which means the even-k and odd-k coefficients cancel exactly. Each group therefore adds to 2ⁿ⁻¹.