Counting Combinations

This is going to touch on some more basic math, but do it in an interesting way that we can apply to more complicated problems.

The problem is this – given a set of n distinct objects (for example, the numbers 1 to n), how many ways are there to construct a subset of size k?

For example, if we take the numbers {1,2,3}, there are 3 ways of constructing a set of size 2. {1,2}, {2,3}, {3,1}. Note that in dealing with sets, order doesn’t matter. {1,2,3} is the same set as {2,1,3}.

So, given the numbers {1,…,n}, we’ll say that there are  many sets of size k. We’re going to solve for .

Consider the set of permutations on the n objects. There are n! ways of ordering the numbers 1 to n. These are the total permutations on the whole set of objects. The 6 permutations of the numbers {1,2,3} are [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].

We can group those n! many permutations based on the first k elements of that permutation. There are  sets of size k, so consider the i-th such set, we’ll call . Let be the set of all permutations of the numbers 1 to n that start with the k numbers in .

Two things to note first – Every permutation on the numbers 1 to n has -some- numbers as its first k elements. The first k elements form some k-sized subset of the numbers 1 to n. This means that every permutation occurs in one of the sets.

Second, a given permutation can’t occur in two different sets. Being in one of those sets fixes what the first k elements of that permutation are. The first k elements can’t be in two different k sets!

So those two facts, that every permutation is in some , and only one of the , allow us to say the following.

That is, we can count the total number of permutations by counting the size of each of the sets.

For a given then, we can ask how big it is. We know what the first k elements of any permutation in that set are, which means that the last n-k elements must be everything else. Any permutation in must be composed of some ordering of those k elements, and then some ordering of the n-k elements remaining. There are k! ways of ordering those k elements, and then (n-k)! ways of ordering the last n-k elements. Thus, there are k!*(n-k)! possible permutations that have a given set of k elements at the beginning.

Notice, nicely, that is independent of the choice of the first k elements. Going back to our previous equation, we get

So, by partitioning the total set of permutations based on what the first k elements are, we can count the total number of possible k element sets.

There are definitely easier ways of arriving at the same formula, but this technique allows us to solve a number of related problems as well. Which … I might talk about later.

Interesting stuff.

A Bit Of Randomness Now And Then

Here is a simple, if inane game. Someone gives you a sequence of 2*n letters. Half of them are A’s, half of them are B’s, all arranged in some order. You have the ability to look at any position, and determine what letter is there, and do this as many times as you like. Your goal is to find the location of one of the A’s. Any one of the n-many of them. You just have to locate one.

How do you do it?

One approach would be to simply start at the first letter, look at it, and if it isn’t an A, go to the second. Continue on, in order, until you find an A. This is very straightforward, and should, in general, find an A fairly quickly.

In the worst case, all the B’s occur before all the A’s, and you’re forced to check n + 1 letters, finding an A on the last try.

But if we assume that the string was constructed by some Adversary acting against our best interest, then it is guaranteed that they will use that ordering, and force you to use the full n + 1 checks. Moreover, any approach we take to finding an A that relies on a deterministic search will have -some- ordering that the Adversary can use to force you to make the full n + 1 checks.

And, needless to say, as n gets large, that can be a large number of checks.

One of the most important questions that can be asked is this – can we do things better?

Consider the following algorithm – just pick locations at random, uniformly along the string, stopping when you find an A.

One issue with this is that it is possible this would result in using more than n + 1 checks. You could keep visiting the same B’s, over and over again. If we wanted to tighten this, we could say, pick random locations without revisiting old locations, until we find an A. This guarantees that we find an A in at most n + 1 checks. However, it simplifies the analysis, and the result is just as cool, if we don’t forbid revisiting.

If we allow revisiting, then the probability of getting an A, with any randomly chosen position, is 1/2.

So that is our algorithm – randomly look at sites, until you find an A. There are many interesting questions to ask at this point. On average, how many checks are needed to find an A? What is the probability of needing the full n + 1 checks to find an A? What’s the probability of needing more than 10 checks?

First, we need the probability that k checks are needed. That requires finding k-1 B’s, and then a single A. Since each check is independent, the probability of getting k-1 B’s is . And of course, that last A has a probability of 1/2 occurring. This gives a total probability of of needing k checks to find an A. If S is the number of checks needed to find the first A, we have

And with that, we have everything we need.

Two!

Stop for a moment to think about that. As n increases, the deterministic algorithm increases in the same way. However, the randomized algorithm needs two tries on average. No matter how big n is! 2! n could be a million. A billion. 2.

And that is incredible.

Of course, you won’t always get it in 2 tries. But consider the event of needing more than 10. To need more than 10 tries, you need to find 10 B’s in a row. But the probability of that is , or approximately 0.00098. Imagine that – only one in a thousand times would you need more than 10 checks, independent of how large n is.

And using this approach, there is nothing your Adversary can do to force you to do anything, since he has no way of predicting the positions you will check. But the probability of needing the full set of n + 1 checks your Adversary could force is , impossibly small as n becomes large.

These are phenomenal gains, just by introducing randomness.

In actually implementing such an approach, a better way would be to forbid revisiting sites, as discussed. This will give you an improvement in the expected values, and generally make it less likely you will need larger numbers of checks. Interestingly, though, as the number of letters goes to infinity, the limiting behavior of the revisitless system is the same as the visiting system described here. If the number of letters is very large, the number of sites eliminated by forbidding revisiting isn’t enough to change the probability of finding a B very much from 1/2. In effect, the calculations I lay out here are the same as for an algorithm that forbids revisiting, for an infinitely sized string. Very clever.

I really used to hate probability, and avoid it like death itself. But, more and more, I find you can do incredible things with it.

Rare Events and Better Button Pressing

Suppose, for a moment, we have a device that can generate a sequence of random real numbers based on a standard normal distribution at the push of a button. The density is given by

Plotting it gives the familiar bell curve,

If we wanted to be precise, we could calculate the probability of one of the values being greater than 0 in the following way. Calling the result of one button press Z,

However, that integral cannot be evaluated in a nice way. It requires several tricks that I don’t want to go into here, but the integral evaluates to 1/2. And you can see that in the symmetry of the graph, really. Equal area under the curve on either side of z = 0 leads to an equal probability of being above 0 and below.

But it’s the matter of evaluating that integral that interests me.

Suppose we were interested in, at the very least, -estimating- the probability that Z was greater than 0. One way to do it would be to press the button a million times, and count the fraction of times the result was greater than 0. This gives an estimate for the frequency at which the result is above 0.

One thing that the advent of computers has allowed us to do better than ever before is press buttons. Using Mathematica to generate a million standard normal values, I get an approximate probability of 0.49981. Which is a very good estimate!

However, let us do something a little more extreme. If you evaluate the relevant integrals, you find that 99.7% of the time, standard normal values fall between -3 and 3. A tiny fraction of the time, they fall outside that interval. Which means that an impossibly small fraction of the time, Z takes a value greater than 5.

And that is the extreme event we are interested in. We want to calculate, or at least estimate, the probability that . Using Mathematica to evaluate the actual integral, we find,

A tiny, tiny fraction of a probability.

But again, we mere mortals would not be able to evaluate that integral. But if we were interested in estimating that probability, we might try a similar scheme as before. Using the same million standard normals in Mathematica, however, only one of them was greater than 5. This gives an approximate probability of . And that is an absolutely horrible estimate for the value we are after.

More than that, it’s disappointing as well. It feels like you’re effectively throwing away 999,999 of your button presses. Wasted. The relevant events are just too rare.

So, can we do better?

Press the button, and generate a value of Z. Then, take the absolute value of it, . The absolute value is a random variable, with a distribution

Note, by eliminating half the possible range (the negatives), we’ve had to double the density on the other half to account for it.

Then define a new variable, . This shifts the distribution up by 5, giving

Notice that now we’ve constructed a variable, Z’, that falls entirely in the range we’re interested in. Values greater than 5.

Backing up a little bit, we are interested in the integral

Consider the following modification.

The fraction cancels, and the value of the integral is left unchanged. But we can do something incredible with this.

Bit of tedious algebra, do do dooo…

And we arrive at the nice result,

But that second integral, that’s interesting. Because that is actually the expected value of , with respect to Z’.

The button allows us to generate a sequence of Z values. We can easily transform them to Z’ values. From that point, we can estimate the above expected value as the average of that function, over the generated Z’ values.

Using the same million standard normals we generated earlier, transforming them to Z’s, and evaluating that function for each of them, that averages out to a value of . And, especially in comparison to the previous estimate, that is an absolutely brilliant approximation. Using the same data! Using -all- of the data! Every single button press contributes to that approximation.

Even using as few as 10 of the standard normals gives an estimate, using this method, of . Ten! I find that utterly remarkable.

By shifting the area we look at from the whole number line to just that interval, above 5, we dramatically improve our approximation, and require much less work in the process.

Absolutely brilliant. Ten values! Smashing.

That is so much of what math is about, in my opinion. A better way of doing things. Brilliant ways of doing things. It borders on the magical, at times.

I love it so.

Number Coverings

Pick a number. Let that number be 127. We say that a number ‘covers’ 127 if it contains the digits of 127, in order. Though not necessarily together. So, 127, of course, covers 127. 701220212987 also covers 127. 301742 does not.

Question: Given a k-digit number, how many n-digit numbers cover that k-digit number?

My first thought was this. If an (n+1)-digit number covers a k-digit number, the covering either occurs in the last n-many digits, or the covering includes the first digit. 1209 vs 4127, for example. Suppose that f(n,k) is the number of n-digit numbers that cover a k-digit number. If, in the (n+1)-digit number, the covering includes the first digit, then that digit is fixed since it must be the same as the first digit of the k-digit number, and the remaining n-many digits must must cover the remaining (k-1)-many digits, of which there are f(n,k-1) ways to do. If, in the (n+1)-digit number, the covering does not include the first digit, then that first digit can be anything except for 0, and whatever the first digit of the k-digit number is – thus giving 8 choices for that first digit. Since the first digit isn’t included in the covering, then the k-digit number must be covered by the remaining n-many digits, of which there are f(n,k) ways to do so.

This suggests the recurrence,

But this is, in fact, wrong.

The problem is that if you take an (n+1)-digit number, and pop off the highest digit, you are not guaranteed that what remains is an n-digit number. Consider 10029, for example. Pop off the 1, and you’re left with 29. Same goes for popping off the first digit of the k-digit number. But if f(n,k) is counting numbers based on a given length, this causes a problem.

The solution is to look at the problem from the other side. If you take an (n+1)-digit number and pop off the lowest digit, you are always guaranteed that the result is an n-digit number. 10030, popping off the lowest digit, gives 1003, a 5-digit number becoming a 4-digit number. Looking at the problem this way, you never run into the same issue.

So, let’s apply the same logic, except from the back.

Given an (n+1)-digit number, either the last digit is involved in covering the k-digit number, or it is not. If it is not, then the first n-many digits form an n-digit number that covers the k-digit number, and the last digit of the (n+1)-digit number can be anything. This suggests f(n,k)*9 ways of going about this, f(n,k) choices for the first n-many digits, and 9 choices for the last digit. If the last digit is involved in the k-digit number covering, then that last digit must be the same as the last digit of the k-digit number, which means there is 1 choice for it. That, and the first n-many digits of the number must cover the first (k-1) digits of the k-digit number. This suggests f(n,k-1)*1 ways of going about this. This leads to the recurrence,

This solves our 0-padding problem, and is in fact correct.

But, this isn’t enough. Notice that in our recurrence, we call f for a lesser value of n, as well as a lesser value of k. We need some initial conditions, fixed values of f that the higher values reference. For example, F(n+1) = F(n) + F(n-1) is not the Fibonacci numbers, until we define F(1) = 1 and F(2) = 1.

In our case, notice that f(n,k) = 1 if n = k. Given a k-digit number, there is only one k-digit number that covers it. Namely, itself.

This isn’t quite enough – it gives an initial condition for n. Basically, if we keep calculating f(n,k) for lower values of n, we can stop when we have n = k. But we need an initial condition for k, as well. If we calculate f(n,k) for lower values of k in the same way, for fixed n, when would we stop?

Consider f(n,0). That is, the number of n-digit numbers that cover a 0-digit number. That doesn’t sound like it makes much sense, but notice that, in a sense, -any- n-digit number covers a 0-digit number. So f(n,0) is just the number of n-digit numbers. How many is that? The first digit can be anything but 0, leaving 9 choices, and we have 10 choices for the remaining (n-1)-many digits. Thus,

For convenience, let us define f(0,0) = 1. That is, there is 1 way to cover a 0-digit number with a 0-digit number. And that is to do nothing at all. This is in-keeping with our f(k,k) = 1 restriction.

And this is enough. Bringing everything together, we have

Coding that up relatively quickly in a small ruby script, we find that there are 26010 many 7-digit numbers that cover any given 4-digit number.

Which is interesting. Though not half as interesting as the derivation of that recursive function, I think.

Now, you could theoretically solve for the closed form of f(n,k), but it looks relatively nasty. Something much more interesting is to define the following function.

The idea is that we take all the numbers f(n,k), for a given k, and string them out as the coefficients of a sum of powers of x. Then, even though we can’t express f(n,k) in a nice, convenient way, you can show using the above recurrence that

Which, at the very least, is interesting in its simplicity. To find the value of f(n,k), simply take the coefficient on the term of the series expansion of F(x,k). All the information of that sequence, wrapped up in one convenient function. Neat : )

New Year! School, That Is

So, I got back from Alaska. A … long time ago. Pictures will be forthcoming. After that, it was pretty much straight back to CMU. And back into the thick of things.

Theoretically, this semester was supposed to be easy. Four classes: Intro to Psychology, Special Topics in Thermal Physics, Probabilistic Simulations, and a graduate course in Discrete Mathematics.

Four courses. Nothing, compared to things I’ve done previously.

So, my prolonged silence might cause you to ask … what happened?

And what happened, for the most part, seems to be this. I agreed to TA a section of Calculus in 3D. That sucks up a large percentage of my time, grading and preparing. Discrete Mathematics, by the nature of the course, takes a -tremendous- amount of time. I basically spent a week thinking about 3 problems and didn’t get anywhere, only to get them all in the last two days before it was due. Those two by themselves seem to be the largest contributors, plus scads and scads of psych reading, which is driving me nuts.

But … so much math. Fascinating, exciting, beautiful math.

Some problems I’d like to discuss, when I have the time, would be …

Suppose you were to color the edges of a complete graph on n vertices with k many different colors. Let f(k) be the largest value such that you can color the complete graph on f(k) vertices with k colors – such that no three edges form a monochromatic triangle. The problem is to show that . I relish, absolutely relish, interesting constants falling out in unexpected places.

Similar setup, but in this case show that . This is very, very long … but very rewarding.

One problem I've been trying to write up, for a very long time (and my inability to complete it basically started this trend towards little to no writing), is calculating Graham's Number – one of the largest numbers ever put to practical use. It is big. So big you can't really comprehend it in terms of value. And yet … we can calculate it! And that, in my opinion, is very exciting.

Plus! Some interesting recursions, and some simulation tricks … We're doing some very interesting things in thermal I would love to share, but I'm struggling with the 'how', without teaching thermal physics from the ground up. I'm sure I will figure something out. But, in any case … interesting maths ahead.

Vacation Vacation

I’m taking a vacation from my vacation … going to Alaska for a week or so! No maths until I get back, and hopefully some new maths then. Feel free to leave any interesting math problems. Or, perhaps, where you would go and what you would do if you could travel through time and space. I’ll see you all on the other side! With pictures.

Many Integrations By Parts

In the spirit of the previous post, one thing that you do in calculus of variations – a lot – is integration by parts. It’s incredible how useful that one trick is. See, they teach you these things in calculus for a reason!

But, I was fiddling around yesterday, and got this nice result, applying many integrations by parts. For integers n, m,

Which I thought was kind of nice.

Calculus of Variations and the Italian Challenge

One thing I did this summer was a course on the so called ‘Calculus of Variations’. A good example question would go something like this.

Consider the set of all functions y, continuous with continuous derivatives, such that y(0) = 0, and y(1) = 1. Find the function y that minimizes the value of

J is called a functional, taking a function and returning a real number.

Taking, for example, y(x) = x (notice that it satisfies the smoothness requirements, and the boundary conditions), the above integral comes out to 4/3. So we know that the minimum value of the integral is, at most, 4/3.

Suppose you thought that the minimzing function were a quadratic polynomial, . The smoothness conditions are necessarily satisfied. For y(0) = 0, that requires c = 0. y(1) = a + b, so y(1) = 1 requires b = 1 – a. So we’re looking for a function of the form . If you evaluate the integral for that function, you get

If you minimize the above expression with respect to a, you find that the minimum value occurs when a = 5/22, and that J(y) = 347/264, or approximately 1.314, ever so slightly less than 4/3. So,

performs slightly better than y(x) = x … but that isn’t enough to show it’s an absolute minimizer.

You could continue on in this way, checking other functions but – let’s be honest. You’re really shooting blindly, because you don’t know the form of the function. Expanding out polynomial minimizers, it may lead you to the taylor expansion of the actual minimizer, but it would be messy and unsatisfying.

Using techniques in the Calculus of Variations, you can solve the problem with some degree of elegance. Elegance that I won’t put forth in detail here – I really just meant for this to be a brief introduction. But you can turn such a minimization problem into an associated differential equation problem. The nice thing about this is that, in comparison to these beasts, differential equations are relatively well understood. The associated problem is as follows. If y(x) minimizes J(y), then y(x) must satisfy this differential eqation problem, with boundary conditions y(0) = 0, y(1) = 1,

You can solve that using your favorite technique to yield the function,

Evaluating J(y), this yields

And this, you can show, is the absolute minimizer of J. Notice, interestingly, the quadratic solution was actually quite close to being the real minimizer. Neat!

Now, you can do all kinds of nice things with this. For example, describing shapes with functions, you can find the shape a hanging cable of fixed length assumes. You can find the curve that minimizes the amount of time it takes to slide a bead along a wire of that curve (the assumption here is, sliding under gravity). And suppose you were an ancient African queen, promised howevermuch land you could encompass with a bull hide, you might be interested in maximizing the total area you could encompass with a fixed amount of material. Many many things.

Of course, Mathematicians always have to go and take things to the next level, which brings me to the Italian Challenge. Now, as the story was presented to me, in Italy, they have these tests for professorships at universities. However, if the administration has a particular candidate in mind, they’ll tailor the test for their strengths. Some candidate must’ve been an expert at calculus of variations, because we have the following problem.

Consider the set of functions, continuous with a continuous first derivative, over the range of x from 0 to 1. We also have the restriction that y(0) = 0, and y(1) = 1. Given

Prove that J(y) has no minimizer of that set of functions.

I’m fascinated. In essence, given any function y(x), you can always find a function w(x) such that J(y) is greater than J(w).

This is interesting on a number of levels. Notice, for instance, that each term of the integrand is positive. Thus we know that, for any function y(x), J(y) is strictly greater than 0. So the values of J are bound from below, but have no minimum! Very interesting.

The associated differential equation problem goes as follows. If y(x) minimizes J(y), y(x) must satisfy y(0) = 0, y(1) = 1, and

Notice, interestingly, you’re not guaranteed that y”(x) exists or is continuous.

But, if J(y) has no mimimizer, and we know that if y(x) minimizes J(y) it satisfies that differential equation, there must be something wrong with that differential equation. It can’t have a solution – because then J(y) has a minimizer. But why?

I don’t know…

A Nice Substitution

I wasn’t always a math person. I used to be much more into reading books. I would read just about anything. Fast, too. But then … I stopped. I remember, the first book I bought but distinctly didn’t read was P.D. James’ Death of an Expert Witness. I picked it up again yesterday, years after the fact, and so far … it’s not bad. Maybe I will get into this ‘reading’ thing again.

But, a small calculation is in order, one that has been bothering me.

Consider the function,

An infinite power tower of x’s. I’ve done some things with this function before, but not this, I believe.

It is certainly questionable, what such a power tower actually means. For the purpose of this calculation, we imagine taking a number x, then raising x to that power, then raising x to the resulting power, then raising x again, etc. This creates a sequence of finite power towers, and we define f(x) to be the limit of that sequence, as the height of the tower goes to infinity.

For some values of x, clearly this sequence diverges to infinity. 2 to the 2nd, etc, etc, etc, rapidly becomes unmanagable. 2^2^2^2^2 has 19729 digits. f(x) for values such as these can be taken as infinite.

But! Over some x, f(x) is actually well defined, finite, seemingly smooth, and many other nice things as well. Consider f(1), which equals 1. f(0) is another matter all together…

That being so, what is the maximal x for which f(x) is finite, and what is f(x) at that point?

My thinking went something like this: I have no idea. But it might be kind of cool to calculate the derivative of f(x).

Looking at the definition of f(x), there’s one substitution that’s just itching to be made.

If we have an infinite power tower of x’s, and drop one off (the bottom most), we still have an infinite power tower of x’s, and the substitution can be made. The rest is standard implicit differentiation.

While the above isn’t really a nice looking function, it’s certainly much more reasonable that having infinitely tall towers flopping about.

And it does suggest something interesting. Notice, being a rational function, if the denominator goes to zero, f’(x) is going to explode to infinity. If that happens, f(x) is going to, effectively, explode as well.

At the very least, if the denominator goes to zero … it would be bad. This all suggests it might have some bearing on our problem. Letting the denominator go to zero, we can solve for f(x) at that point as

This, along with our initial definition of f(x), gives us something to work with.

So, at the above x value, the derivative blows up, and the function goes to infinity. Interestingly, our condition on the denominator of f’(x) also gives us an easy way of calculating f(x) at that point.

And, fiddling with Mathematica seems to confirm all this.

But … what’s bothering me is that I feel like I did too much work. The first time I saw this problem, this quiet little Asian kid whipped out the e^(1/e) like it was a trivial and self evident result. Was he seeing something that I’m not seeing? I don’t know…

I think it’s worth thinking about, in any case. Not too long, perhaps, but worth thinking about. And now, back to murder and mayhem. After all, isn’t that what summer is all about?

Open to Interpretation

This is a more open ended thing. I’m trying to cram and finish a presentation in these last couple of days, so I don’t have much time for my own maths. But, looking at this picture, lifted from Mathworld,

What are some questions that immediately spring to mind? One in particular springs out at me.

Increasingly, I find that being able to ask interesting questions is as important a skill, if not more so, than being able to answer them.

So, interesting math questions – go.