Thursday, February 28, 2013

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)2. If we choose our inputs to be x = 1 and y = 2 then the machine f will spit out (1+2)2 = 32 = 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.


Tuesday, January 29, 2013

Nothingness

The question is often posed (and likely has been since questions were invented), "Why is there something rather than nothing?". This question has special philosophical and religious importance and of course I am not about to suggest that I am in any position to provide a definitive answer. With that said, I must admit that I find the question a peculiar one. In order to explain why, a slight diversion is required.

I have typically reserved this blog for musings of a strictly philosophical nature in the past, especially with regards to ethics. However, physics is my trade, and my original intention was never that the blog was to be exclusively philosophical. It is therefore with no guilt (but plenty of fore-warning) that I am about to introduce an element of physics to this particular musing, and I will have to ask that the less scientifically-minded of my readers bear with me as I will try to keep things as simple as possible.

In the popular literature one of the more commonly referred to principles of quantum mechanics is the Heisenberg Uncertainty Principle, which is commonly expressed as meaning that a particle's position and momentum cannot be simultaneously known to arbitrary precision or, as it is usually misleadingly rendered: one can either know a particle's position but not its velocity, or its velocity but not its position. Mathematically this is understood by the equation ΔxΔp ≥ ħ/2: the product of the uncertainty in position (Δx) and the uncertainty in momentum (Δp) is greater than or equal to half the reduced Planck constant (a very small but importantly non-zero number).

What is less well-known is that the Uncertainty Principle applies to many other pairs of properties, perhaps the next most common pair of which is energy and time -- ΔEΔt ≥ ħ/2. This equation has far-reaching implications. Suppose we consider a small patch of empty space and contemplate the energy content there, if any. We know from the Uncertainty Principle that for any finite amount of time that you care to measure you will find your portion of 'empty' space has a decidedly non-zero energy (this energy is called the vacuum energy). This is not a question of the accuracy of your tools, it is a direct consequence of the wave-like nature of particles in quantum mechanics and is fundamentally built-in to the way the Universe works.

So our little region of space has a little bit of a buzz to it, so what? We now turn to the most famous equation in the world, Einstein's equation of mass-energy equivalence E = mc2. This suggests that from the vacuum energy matter can be created, although only in the form of virtual particles (vacuum fluctuations) with short lifespans as the Uncertainty Principle prohibits 'borrowing' energy from the vacuum indefinitely. (Sidenote: this is slightly misleading, as the relation E = mc2 only applies to real particles, with virtual particles lying slightly "off-shell" where E  mc2. Even so, mass-energy equivalence remains valid and interestingly, the further off-shell a virtual particle is the shorter its lifetime, exactly as the Uncertainty Principle demands.) This means that out there in space, a sea of virtual particles are constantly flashing in and out of existence. This may sound like the ramblings of a madman, but so far as modern physics can tell it is an accepted fact.

Now, to give relevance to this slight digression, let's return to the question that sparked this blog post - why is there something rather than nothing? Well, what is nothing? A typical immediate response is to think of some small region of space deep in the void with nothing remotely nearby -- a classical vacuum. As I hope I have just demonstrated, however, this notion of nothingness is flawed as this region of space is not truly empty but is populated by virtual particles, fluctuations in the various quantum fields that permeate the universe. It seems we will have to reconsider what nothingness is, then.

Let us put aside quantum concerns for the moment. Even still the argument can be made that this does not constitute a reasonable view of nothingness. Wheeler's famous summary of general relativity (a purely classical theory) is: "Spacetime tells matter how to move; matter tells spacetime how to curve". We have forgotten that our region of empty space in a classical universe still contains, or rather consists of spacetime. In fact, we can do away with relativity altogether and still argue that we are envisioning a Universe endowed with space and time. Some may be reluctant to call these 'something', but since they have properies they are most definitely not nothing. Thus we must abandon our picture of a Universe with any notion of distance or duration, as nothingness precludes any such concept.

Now we are confronted with trying to conceive of a Universe which is literally nothing in the senses I have described above. There is so light, no matter, no particles of any description, not even space or time. Though it may seem unlikely, modern physics has the tools to deal with such a scenario, albeit in a somewhat imperfect way given our current knowledge of physics is not complete. What quantum field theory (perhaps the most accurate theory of physics ever discovered) suggests is that this nothingness is an unstable state and will inevitably and spontaneously turn into something. It seems that the way physics works just precludes nothingness from being a viable possibility. Problem solved, right?

Not quite. There is is one last resort for the hold-out, and that is to claim that nothingness is not only the absence of objects, fields, space, time and the rest, but also of physical law. While there is nothing wrong with this definition in principle, in practice it is nonsense. It only seems reasonable in my opinion that if someone is to establish their own definition of what constitutes 'nothingness' they should do so in an explicable way. This is simply not possible as it is so far outside of human experience that there is no reasonable way to explain it. Any analogy will fall short, any visualisation will falter; we had enough trouble trying to imagine a Universe with no notion of space or time!

What's more, how can we prove or disprove that such a nothingness can actually exist if we have deprived ourselves of all our tools for answering such a question? The typical recourse is to the supernatural, perhaps explaining that God somehow creates something from this absolute nothingness, which is established by hypothesis. But if this nothingness is so perfect, how can there be a God there at all? What meaning does the concept of God hold in such a scenario? Clearly He must have no physical properties as there are no physical laws, and cannot be within the Universe as it is by hypothesis nothing, so He must reside outside the nothingness, and yet be able to change it. It is at this point that I throw my hands up in the air and ask in exasperation what such a statement means, not in a deep or mystical sense but rather as a basic statement in the English language. It seems that this desperate endeavour has led us down a path which is, as I suggested earlier, nonsensical. We might as well discuss the colour of a red green, or the weight of an idea for all the progress such an approach can yield.

It may seem disingenuous to argue that we limit our definition of nothingness to what we, as flawed people, can comprehend, but in fact we have no other recourse than abandoning the question altogether. Given the curious nature of human beings, I doubt we will be able to withstand the temptation to revisit it, and so our hand is forced. It seems to me at least that we must restrict ourselves to discussing the question of why there is something rather than nothing in strictly physical terms, and that is why the question of why there is something rather than nothing strikes me as being especially peculiar in contrast to other important philosophical questions.