When working on a combination problem, we usually multiply. But sometimes addition shows up -- how do we know which is which?
Here's a few mental models I use to keep them straight.
Mental Model: Different Dimensions
让我们以一个简单的情况为例:你有4件衬衫和8条裤子，你能做多少套衣服?
In essence, you are picking a spot on this grid:
Shirts and Pants exist in separate dimensions, whose area represents distinct solutions. We can pick any spotin the gridand we have 4 x 8 = 32 options.
Now, suppose we had 4 shirts and 8 pants and had to pick a single item to sell. Here, they lie along the same "clothing item" dimension:
We can randomly pick any pointalong the lineand have 4 + 8 = 12 options.
Think "different dimensions vs. same dimesion" or "grid vs. line".
Mental Model: AND vs OR
Another interpretation is AND (multiplication) vs. OR (addition).
假设我们必须从4件衬衫和8条裤子中选择一件。我们都需要远离麻烦。The scenario is:
pick among 4 shirts AND among 8 pants = 4 * 8 = 32 choices
What if McDonald's softens their regulations and allows a shirt OR pants? (But not both -- yikes.) Then, we have:
pick among 4 shirts OR among 8 pants = 4 + 8 = 12 choices
Writing out the scenario is often easier to think through, especially with numerous dimensions (shirts, pants, hats, shoes).
当你内化这些类比时，你会很快意识到到底需要乘法还是加法。
Example: Combination & Permutation Formula
Let's go meta for a minute. Thepermutation formulais:
How can we think about this?
The numerator ($n!$) is the max volume assuming each of the $n$ choices has its own dimension. The number of rearrangements of 8 people is 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1.
But suppose we only care about the first 3 decisions -- picking a Gold, Silver and Bronze among 8 contestants. In this case, we shrink our solution space by dividing out the 5 dimensions we aren't using (which has 5! options on its own). We are left with 8! / 5! = 8 * 7 * 6 = 336 choices, with the general formula $\frac{n!}{(n-k)!}$.
(If multiplication creates dimensions, then division should remove them.)
Now, let's say the medals are identical: we're giving a tin can to 3 out of 8 people. We need to further remove dimensions, because we have 3! = 3 * 2 * 1 = 6 redundancies for each permutation in our solution space. We again shrink our solution space:
(I imagine the solution space volume getting denser.)
Ah! That's what's happening with the combination and permutation formula. We create the max volume and shrink it by the dimensions we are not using. Mentally translate the scenario into a version that makes sense to you.
Example: Flipping Coins
Here's how I think through a few sample problems.
抛10次硬币。有多少种方法至少得到7次正面?
First off, the total number of possibilities is 2^10 = 1024. Intuitively, I see each flip as a decision along a different dimension, not the same number line. This means we have 2 * 2 * 2 *... possibilities, not 2 + 2+ 2 + ... possibilities.
Geometrically, this would be a 10-dimensional "choice space", or, written out:
(Heads OR tails) AND (Heads OR tails) AND (Heads OR tails) AND ...
Ok. Now, how can we get at least 7 heads? That means we had 0 tails [10 heads], 1 tails [9 heads], 2 tails [8 heads], or 3 tails [7 heads].
Switching to the written description, this becomes:
choices we want = (0 tails OR 1 tail OR 2 tails OR 3 tails)
Given our 10 flips, the number of outcomes are:
- 0 tails = 1 choice (all heads)
- 1 tail = 10 choices (exactly one flip was tails)
- 2 tails = C(10,2) =
10*9/(2*1) = 45 choicesbased on the combination formula - 3 tails = C(10,3) =
10 * 9 * 8 / (3 * 2 * 1) = 720 / 6 = 120 choices
So, the total is
choices we want = (1 + 10 + 45 + 120) = 176
And for kicks, the chance of seeing this happen is:
176 / 1024 = 17.2%
乘法不仅仅是“重复的加法”。这是一个组合的普遍概念，我还在寻找解释。Let's not get tied into a single meaning.
快乐数学。
Appendix: Computer Programming
Turning AND/OR statements into arithmetic maps nicely to Boolean logic.
If A and B are variables with the values 1 or 0, we can write:
A AND B = A * BA OR B = A + B
In most languages, a positive number evaluates to "true", so A + B = 2 is true. Note that this OR is an "inclusive OR" that allows both values to be true. To force an exclusive OR, we could take the remainder after dividing by two:
A XOR B = (A + B) % 2
Most programming languages have separate operators for AND (&&), OR (||) and XOR (^), but it's nice seeing how logic works with regular arithmetic.
Additionally, "if/then/else" statements can be converted to arithmetic.
Ifyis a variable (1 or 0) that determines a result, instead of:
if (y) { result = ResultIfTrue; } else { result = ResultIfFalse; }
we can use the single statement:
result = y * ResultIfTrue + (1 - y) * ResultIfFalse
This version avoids the needs for branching, which is expensive for a CPU, and is a formula we can optimize with Calculus (used in machine learning algorithms).
