liveBook · Manning

Combination

As explained in Timeless Algorithms, The Foundational Ideas

A combination is a selection or grouping in which order does not matter.

A combination is a selection in which order does not matter. Three heads and two tails count as the same outcome regardless of their sequence; a particular sequence, by contrast, is ordered. section 2.3.5

In coin-change counting, let ways[n] be the number of combinations that form amount n. Each usable denomination c contributes ways[n − c]; adding these contributions counts the combinations. Processing denominations in order ensures that permutations of the same coins are not counted as distinct combinations. section 6.3.2 section 6.3.5

Making 12 with coins

With denominations {1, 5, 10}, there are four combinations: {1 × 12}, {5, 1 × 7}, {5, 5, 1, 1}, and {10, 1, 1}. Rearrangements of any combination do not add solutions. section 6.3.6

Table 6.10 Counts after adding the 10-unit coin. Processing the final denomination increases the counts for amounts 10 through 12, producing ways[12] = 4.
𝑛
0
1
2
3
4
5
6
7
8
9
10
11
12
After 𝑐 = 10
1
1
1
1
1
2
2
2
2
2
4
4
4

The table shows the final counts after processing each denomination, including ways[12] = 4. section 6.3.5

How Timeless Algorithms, The Foundational Ideas covers it

How deep it goes
Defines the distinction, gives a coin-counting recurrence, and works through tabulation and verification for amount 12.
Examples
Uses mixed heads-and-tails sequences and coin denominations {1, 5, 10} to illustrate order-insensitive counting.
What you can do after
Apply a dynamic-programming recurrence to count coin combinations and verify the count by enumerating cases.
How it connects
Connects combinations to permutations, the multiplication rule, dynamic programming, and knapsack counting.

Also explained in

Compare how 4 books explain combination →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Timeless Algorithms, The Foundational Ideas. The section links point to the parts of the book it draws on.