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.