How many numbers are there in total?

How many 6-digit numbers can you write with 4 digits?

Posted by Erich Neuwirth on December 30th, 2018 in General | ∞

A bit of combinatorial thinking

I recently set the following task in my Twitter series #mathepuzzle:
132324 is a 6-digit number with only 4 different digits. Let's call something like this a 6-digit 4-digit number. How many 6-digit 1-digit, 2-digit,…, 5-digit and 6-digit numbers are there? Leading zeros are allowed.
How can you find out? Mathematicians tend to approach such problems in a more general way. So let's consider what related cases we can easily solve.
1-digit 1-digit is easy, there are exactly 10 numbers 0, 1, 2,…, 9
2-digit 1-digit only works 10x, 00, 11, 22,… 99 and that applies to any number of digits. There are 1-digit numbers for each $ n $ 10 $ n $; we can extend every $ n-1 $ -digit 1-digit number to a $ n $ -digit 1-digit number using the one already used digit. So we now know that there are 10 2-digit 1-digit numbers. Since there are a total of 100 2-digit numbers, there are 90 2-digit 2-digit numbers. We can calculate the number of numbers with all different digits for any number of digits. There are 10 options for the first digit, each of these 1-digit numbers can be extended to a 2-digit, 2-digit number in 9 ways.
Each of these 90 2-digit 2-digit numbers can be extended in 8 ways to a 3-digit 3-digit number, so there is $ 10 \ cdot 9 \ cdot 8 = 720 $ 3-digit 3-digit numbers.
4-digit 4-digit numbers are therefore $ 10 \ times 9 \ times 8 \ times 7 = 5040 $, and we can use this calculation recipe with up to 10-digit numbers. 11-digit numbers with lots of different digits cannot exist if only 10 digits are available. This also applies to many other cases: There are no numbers that use more different digits than they have digits. We now know that 10 3-digit 1-digit numbers and 720 3-digit 3-digit numbers. So there are $ 1000-10-720 = $ 270 3-digit 2-digit numbers.
We can summarize what we have considered so far in a table: If you click once in the table (not in the explanatory text above), the text above disappears and you see the whole table at once. The first number that we don't know yet is the number of 4-digit 2-digit numbers. Each of these numbers is an “extended” 3-digit number. It was created by adding a fourth digit to a 3-digit number. Let's imagine it this way: We have 6 boxes in which all 3-digit numbers are located, namely the 1-digit numbers in box 1, the 2-digit ones in box 2 and the 3-digit ones in box 3. Boxes 4 to 6 are empty because there are no 3-digit numbers with 4 or more different digits.
Now we set up a new row with 6 boxes (again numbered from 1 to 6). Then we create 10 copies of each slip of paper in box 1 (from the row for the 3-digit numbers) and append one of the 10 digits to the 3-digit number. This is how 4-digit numbers are created. We put these numbers in the "correct" boxes for the 4-digit numbers. If we extend the 2-digit 1-digit numbers with one digit each (e.g. 111), we get 1 4-digit 1-digit numbers (namely 1111) and 9 4-digit 2-digit numbers (1111, 1112, 1113 , ..., 1119, 1110). One of our extended numbers has the same "digit" and with 9 extended numbers the digit is 1 higher.
If we extend 3-digit 2-digit numbers (e.g. 121) with all 10 possible digits, then 2 of the extensions are again 2-digit (1211 and 1212) and the remaining 8 extensions are 3-digit. So from the 10 3-digit 1-digit numbers we have generated 90 4-digit 2-digit numbers, and from the 270 3-digit 2-digit numbers also $ 2 \ cdot 270 = 540 $ 4-digit 2-digit numbers, in total So $ 9 \ times 10 + 2 \ times 270 = 630 $ 4-digit 2-digit numbers. There is no other way to generate such numbers by extending 3-digit numbers, so these are all such numbers. With the same considerations, we can see that we can generate all 4-digit 3-digit numbers from the 3-digit 2-digit and the 3-digit 3-digit. Each 3-digit 2-digit number can be extended to a 4-digit 3-digit number in 8 ways (we simply add one of the 8 not yet used digits to the end), and each 3-digit 3-digit number can be extended in 3 ways can be extended to a 4-digit 3-digit number by adding one of the 3 already used digits to the end.
There are therefore $ 8 \ times 270 + 3 \ times 720 = 3600 $ 4-digit 3-digit numbers.
The recipe also works for the 4-digit 4-digit numbers: Each 3-digit 3-digit number can be expanded to a 4-digit 4-digit number in 7 ways (with one of the $ 10-3 $ digits not yet used) . There are no 3-digit 4-digit numbers, so the second expression in the sum that we typically calculate is simply 0. In our table we can describe the pattern of our calculation as follows: in each cell there is a sum of 2 products. The first product is the number on the left above it multiplied by (10-column number) the column from which this number comes, the second product is the number immediately above it multiplied by the column number of this column.
This calculation is valid for all 2 or more digit and 2 or more digit numbers. The completed table looks like this: You can download this Excel sheet and examine the formula more closely. If you double-click on a cell in the downloaded table, you get the following: The formula described in words above is color-coded here:
pink. green + orange. blue. The formula notation may not be what you normally see in Excel. You can switch it on in the Excel options. R [-1] C means, for example, a row above, the same column. If your Excel is set to German, then there is Z [-1] SZ3S + Z [-1] S [-1]Z3S [-1] We see in this table that there are 327600 6-digit 4-digit numbers. Translated into the "usual" mathematical notation, the solution to our problem is as follows: $$ F (1,1) = 10 \
F (n, 1) = 10 \ text {for} n> 1 \
F (1, k) = 0 \ text {for} k> 1 \
F (n, k) = (10- (k-1)) F (n-1, k-1) + k F (n-1, k) \ text {otherwise}
$$ $ F (n, k) $ is the number in the cell with row number $ n $ and column number $ k $. The content of the formula is therefore completely identical to the verbal description of the table; it expresses the arithmetic recipe only in the very compact notation customary in mathematics. Additional note:
We have calculated the number of numbers with all different digits as $ 10 $, $ 10 \ times 9 $, $ 10 \ times 9 \ times $ 8, etc. These numbers are structurally similar to powers. $ n ^ k $ means that you multiply the number $ n $ $ k $ times by itself, so we calculate
\ underbrace {n. n \ ldots n} _ \ text {k factors}
$$ The products we calculate also have k factors, but each of them is 1 less than the previous one: $$
\ underbrace {n. (n-1). (n-2) \ ldots (n-k + 1)} _ \ text {k factors}
$$ These products have their own name, they are called decreasing factorial or decreasing factorial powers. They occur so often in combinatorics that there are separate ways of writing them, namely $$ n ^ \ underline {k} \ text {or} n _ {(k)} $$ The mathematical definition is $$ n ^ \ underline { k} = \ prod_ {i = 0} ^ {k-1} (ni) $$ If you are not used to this mathematical notation, you should not be frightened by it. It means nothing else than what we have already expressed in words. The above underlined number (the exponent) indicates how many factors the product has and the number below is the first factor; all other factors are reduced by 1 per factor.

Keywords: Excel, combinatorics, recursion, spreadsheet