I don’t know which algorithm you used but there are basically two methods for this problem.

I’ll try to explain both by keeping it as vague as possible.

Method 1: You can find your digits from left to right:

Basically every time you increase a digit by 1 it brings 9 * 9 * 9 * … new possibilities (as many factors as the number of following digits). So while you increase your digits you can add powers of 9 to a “control number” and stop when you reach n.

Obviously there are subtleties to take into account but the main idea is here and I think where your numbers come from is pretty self explanatory if you do this method.

So more likely you went for:

Method 2: You can find your digits from right to left

There’s an algorithm that looks like base 9 conversion and you might wonder why it works. Basically a number n converted in base 9 is the (n+1)-th number you can write with only 9 symbols (0-8).

Here you’re looking for the n-th number you can write with only 9 symbols (1-9).

Hence the similarities.

(And it also explains why method 1 looks like this cause base 9 conversion is about “putting as many powers of 9 as you can”.)