Just some math fun because I noticed a random observation this week while thinking through 2 unrelated problems.
Combinations
If you recall the formula for a combination where n is total items and r is how many you are choosing from the set:
So if you have 12 musical notes how many 3 note chords can you create?
12! / (3! * 9!) or 220.
If you have spent time playing games the combination formula is as ingrained as the Pythagorean theorem (We are doing some backyard remodeling, I literally needed to compute a hypotenuse this weekend so Pythagoras was top of mind).
Anyway, here’s the random thing I noticed.
Suppose the question was how many 2 note chords can we create out of 12 notes? Well, a correlation matrix answers the same question when r = 2. A correlation matrix is a bunch of pairs. Pairs are just combinations of 2.
Look at the matrix. The grey boxes are just double-counting the green ones. A,E is the same chord as E,A. And the diagonal axis is not a pair so they don’t count either. So if you add up the green boxes you get 66 boxes.
But if we used the combination formula you also get 66 because 12! / (2! x 10!) = 66
Very neat. This makes sense. Let’s break it down.
Generalizing
If you need to compute a combination of 12 notes choosing 2 you can just visualize the matrix.
- Start with 12 x 12 boxes = 144
- Subtract 12 diagonal boxes to arrive at 132.
- Divide by 2 because of double counting. 66.Generalizing that process. (N²-N)/2 or N(N-1)/2
To prove that it’s equivalent you can notice that:
C(N,2) = N!/ ((N-2)! x 2)
Substitute N!/(N-2!) for N(N-1). That is kosher since 12×11 is the same as 12!/10!
So N!/ ((N-2)! x 2) == (N²-N)/2
Permutations
With permutations, we say that “order matters”. A,D and D,A are distinct. They must be counted as 2 pairs, not just 1. So if you go back to the correlation matrix you start with the N² terms and subtract the N diagonals. You’re done! No need to divide the duplicates by 2 since A,D and D,A both need to be counted as distinct pairs.
To check you can look at the permutation formula which is the same as the combination formula but you don’t need to divide by r. You don’t need to divide out the number of ways the chosen items can be re-arranged as you do with the combination formula which doesn’t care about order.
So the permutation formula says there are 12×11 permutations or 132. Same as the matrix method which says there are 144 pairs minus 12 diagonal boxes.
When it comes to music chords permutations might be the more relevant count if you consider chord inversions.
One last trick
Remember when you were summing the green boxes…the columns were made of 11 boxes, 10 boxes, 9 boxes and so on…
Here’s the trick to summing the numbers 1 through N or in this case 1 thru 11.
N(N+1)/2
So 11×12/2 = 66
Let’s try another. Sum the numbers 1 through 100.
100×101/2 = 5050
Why does this work?
Pair the ends off.
100 + 0
99 + 1
98 + 2
97 + 3
96+4
…continue until 51+49
What do you end up with:
- 50 pairs summing to 100
- The middle “50” left over.50×100+50 = 5050.
That maps to (N/2) x N+1 or “the middle number occurs N + 1 times”. That 1 term is the “middle 50”.
The first time I encountered that question was playing a game that required us to sum the ranks of a suit of cards. So Jacks are 11, Queens 12, Kings are 13 and Aces are 1s. So 13 total ranks.
What’s the sum of 1 to 13?
Perhaps another time I will explain how we used to mock trade options on the sum of ranks of cards held in people’s hands as cards were “flopped” into collective view. (Susq alum are having flashbacks to “after-work mock” now).