Patterns, Pt. 1: Permutations and Combinations

Let me tell you a story. Once upon a time there was a little girl who happened to like to walk. She would wander from one end of town to the other just about every other day of the week. On occasion her friends would ask her where she had been, and she might casually reply, "Oh, just down to the pier," or "Oh, just down to the end of Elm Avenue". Some of the girls would wonder in admiration how she had the stamina for such great journeys. Others would just roll their eyes and assume she was making the whole thing up to brag and had more likely spent the day watching TV. The fact of the matter was, however, that there was nothing about putting one foot in front of the other that especially resonated with our heroine; it was just that she liked the fresh air and had come to the realisation that she found few greater pleasures than just letting her mind wander in peace. To each their own.

One day the girl was walking by one of her favourite ponds. Floating on the water she spied a number of leaves. Some were round, some were pointed, some were yellow and some were green. She stopped for a moment to watch them float aimlessly about on the water, and she pondered how many ways there were for a floating leaf to be. She smiled - it was a simple question, but she didn't visit ponds to challenge herself. Two different colours, two different shapes. A round leaf could be green or yellow, a pointed leaf could be green or yellow; two ways to be one way and two ways to be another makes four ways. Of course, there's nothing special about leaves, and in fact they're a little mundane. If there were three shapes there would be two ways to be one shape, two for another and two for the third - 6 ways. If there were three colours and three shapes then 9 ways. It was just simple multiplication. 

The girl left the pond. She didn't much care for the floppy, soggy leaves which floated in the pond. Much better the crunchy leaves which fell on the footpath; they were so much more satisfying to step on. Soon enough she was imagining herself playing with leaves - stepping on them, kicking them around, watching the wind blow them about, crushing them with her hands, shuffling them like cards, and then finally taking a stack home in her pocket. In her mind she could see her deck of leaves sitting in her pocket, and she wondered how many ways you could put those leaves in her pocket. If she had three leaves then she could put any of the three in first, but there would only be two leaves left to choose from to put in next, and once the first two were in the final leaf was already decided by process of elimination. It struck her that this was a little like the leaves in the water - 3 'ways' for the first leaf to go in the pocket, 2 for the second and 1 for the third makes for 3×2×1=6 ways in total for her leaves to be in her pocket. Again, multiplication. How dull. 

But an inquisitive mind is never satisfied so easily, and with many steps left on her trek she decided to play a game and figure out how many ways there would be for 4 leaves to go in her pocket (4×3×2×1 = 24), then 5 (5×4×3×2×1 = 120). What the little girl didn't know was that such a sequence had a name - factorial. She had never had much reason to share her thoughts with anyone else, so the idea that her sequence had a name, or should need one, had never really occurred to her. After all, she was just playing with numbers. Sadly, we do not have her luxury, so we will use the term factorial from now on and leave the playground of her mind very briefly to introduce some dreaded notation. The factorial symbol in modern mathematical notation is an exclamation mark. If one wanted to express, say, 6×5×4×3×2×1 then one might instead write 6! (six factorial). Much neater, but back to the story.

At this point the girl thought that she was sick of leaves. How many ways would there be for, say, a deck of cards to be in her pocket? 52×51×50×49×... that was a calculation far too tedious to keep her attention. She decided it was a very big number, and that satisfied her. But then she imagined two decks, then three, and then a million (because why not?). 52 million cards would probably not fit inside her pocket, even though it was quite reasonably sized. They probably wouldn't fit even if she used her other pocket too. She wondered how many cards actually would fit inside her pocket, but when she tried to think of all the ways you could stuff cards into her pocket if they weren't neatly lined up in packets it made her mind boggle. It might be a long walk, but she wasn't so bored that she would turn to the dimensions of her pockets to amuse herself. Instead she thought about packs of cards. She could probably fit four packs in a pocket. Instead of a million, suppose she had six packs. Her pocket allowed four 'slots' for her six objects to fill. 6×5×4×3. ...That was it. 360 ways. It was just another multiplication sequence like before, but truncated.

Truncating a factorial like that seemed at first a little odd to the girl. She had become enamoured with her discovery of factorials and didn't really like the idea of cutting them short. She ruminated about this cruel fact, that her perfect factorials should be ruined when the objects outnumbered the slots, and she became a little grumpy about it, perhaps more grumpy than one would ordinarily become about such things. Just as she was about to throw her hands up in the air and think about happier topics, she had a realisation. In her mind's eye she saw a line of slots and her factorial sequence filling them, 6 5 4 3, and hanging off the end like a shadow were the remnants, 2 1. But 2×1 was a factorial sequence too! The truncated sequence 6 5 4 3 was just 6 factorial with 2 factorial lopped off the end, and since each number in the sequence is multiplied, the lopping off is really just a division. Suddenly the artificial-seeming truncation could be expressed in factorials too and the girl's day was brightened up again.

Urged on by this new discovery, the girl tried to think about how to make this object-slot-fitting working for any amount of objects and any amount of slots, just in case the need should ever arise (but really because she was properly enjoying herself now). The girl didn't know much about algebra except that it was something older kids on TV seemed to complain about a lot. She did, however, understand perfectly well the notion of an unspecified amount. Because we have the advantage of modern mathematical notation, we will use n and k to represent respectively what she thought of as 'some number' and 'some other number (which might be the same as the other one but might not be)' and follow her reasoning with those replacements made. We will let n represent the number of objects and let k represent the number of slots. If that's the case then we'll start off with n! and truncate it by dividing by the leftover factorial. If there are k slots, and we are implicitly assuming that k is the same as or smaller than n, then the leftover factorial must start at n-k, resulting in the final expression n!/(n-k)!. 

The girl was cautious and picked an example to make sure her expression was right.
6×5×4×3 = 360.
n = 6 (6 objects) and 6! = 6×5×4×3×2×1 = 720.
k = 4 (4 slots) and n-k = 6-4 = 2 and 2! = 2.
6!/2! = 720/2 = 360. It worked! She was over the Moon. Having long since left the pond behind she skipped along the footpath, which now took her by the local sports oval not too far from her house. She picked different numbers for n and k and checked that the answer she got was right. Every time it was, and every time she smiled gleefully. What a fun little rule she had worked out for herself!

She soon realised that there was more to the story. If she had four slots and six objects, let’s call them A, B, C, D, E and F for convenience, then even though she had a choice of 6 for the first slot, 5 for the second and so on, she could just as easily end up with A B C D one time and B A D C another, and those would be counted as two separate cases. That’s all well and good if these objects are special and it matters what order they are in, but what about if she doesn’t care what the order is? Her mind turned back to the crunchy leaves in her pocket. What is the difference between one leaf going in first and another going in second compared to the other leaf going in first and the first leaf going in second? They’re all just leaves...

And so it was apparent that if the order of the objects didn’t matter then the girl’s formula wasn’t quite right – it was over-counting ways of putting those objects into slots and she wasn’t quite sure how to change it. She turned back to her six objects A through F and her four slots. She picked four of her objects at random (not that it made a difference) and came up with A, C, D and E. If the order of the objects doesn’t matter then D E A C is just as good as A C D E or C A E D or any other ordering. But how many orderings are there? This problem seemed familiar to the girl... there were 4 objects that could go in the first slot, 3 that could go in the second... it was just another factorial! If there were k slots and k objects available then there were k! different sortings that were being counted by her formula. By her reasoning, all of the sortings for a given combination of k objects should only count once. Her old formula was n!/(n-k)!, and for any k objects there were k! different orderings, so in order for the formula to count only one ordering for those k objects rather than all of them she would have to divide by k!. That would make a new formula, n!/(k!(n-k)!). Excellent!

At this point the girl realised she was quite tired and the Sun was about to set soon, and so she headed for home, ready and eager to enjoy her dinner. This is the end of the little girl’s story, but it is not quite the end of ours. Before we retire to our own dinners we must first address this small addendum. We will find it useful in future tales to name the two expressions which the girl derived, n!/(n-k)! and n!/(k!(n-k)!), and we will name them using function notation, keeping in mind that in these formulas k is never larger than n. In actual fact there are many different notations for writing these expressions but we will not confuse ourselves by trying to use all of them.

If we have a function of two variables f(x,y) then what we mean to say is we have a machine called f which, when you input any two numbers x and y, outputs a number. For example, consider the function f(x,y) = (x+y)². If we choose our inputs to be x = 1 and y = 2 then the machine f will spit out (1+2)² = 3² = 9. Now, of the girl's two expressions the first we will call P(n,k), where we will use n and k for the inputs instead of x and y because we have written the cogs and gears of this machine as n!/(n-k)! which happens to involve the letters n and k (although we could just as easily have picked any other letters). The second expression we will call C(n,k). As a matter of interest, the names P and C were chosen to stand for permutation and combination. The first expression is for counting the different orderings you can make for k objects chosen from a set of n objects and to ‘permute’ two objects is to change their order. The second expression is for counting the different combinations of k objects you can make when they are chosen from a set of n objects. C in particular is going to appear again soon and not necessarily in the places you would expect, but isn’t that always the way.