I’m teaching a third year Combinatorics module this term, which has led me to revisit some old friends: permutations and combinations. I thought I knew them well, but have already learned something new!
First a quick refresher course:
Combinations: say (C(n,k)) is the the number of subsets of size (k) from a collection of size (n). So if you select 3 pieces of fruit from a total of 6 (all different), and don’t care about the order, then the number of selections you might make is (C(6,3)). The formula[1] here is (C(n,k) = frac{n!}{k!(n-k)!}) and (C(6,3)=20).
Permutations: If you do care about the order of selection (maybe you want to arrange your fruit into military columns so that “strawberry, apple, pear” is different from “apple, pear, strawberry”), then the number you need is (P(n,k)), the number of permutations of (k) objects from (n). Its formula is (P(n,k) = frac{n!}{(n-k)!}) and (P(6,3)=120).
Total numbers of combinations: A set of size (n) has (2^n) subsets in total. To say the same thing another way, (C(n,0)+C(n,1)+…+C(n,n)= 2^n). So the total number of collections of fruit you could take from the box of 6 is (2^6=64) (this includes both the empty-plate option and the take-everything option).
All of the above I have known for many years. But I recently discovered something new (to me):
Total numbers of permutations: if you pick between (0) and (n) objects, in order, from a set of size (n), how many choices can you make? To ask the same thing another way, what is (P(n,0)+P(n,1)+…+P(n,n))? And the answer turns out to be ( lfloor n! cdot e rfloor ), that is the number you get if you round (n! cdot e) down to a whole number. So the number of military columns of fruit (including the empty column) you could make from your six are ( lfloor 6! cdot e rfloor = 1957).
I think this is very cool, and the proof of this is not hard. It’s been written out very nicely here by Michael Lugo. (When I first saw this result I assumed that it would be a consequence of Stirling’s approximation – but that’s not required.)
[1] These formulae all use factorial (! ) notation where (7!=7times 6 times 5 times 4 times 3 times 2 times 1)
Simple City 