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 
