What is the number of $6$-digit numbers that have got all odd digits and for which every $9$ is followed by a $1$?

Question

What is the number of $6$-digit numbers that have got all odd digits and for which every $9$ is followed by a $1$?

Answer 1

Using some simple combinatorics :

• The set of digits to choose from is : $\{1,3,5,7,9\}$
• $9$ is always followed by $1$, thus the real set is $\{1,3,5,7,91\}$
• The problem is the $91$ which has two digits.

Question 1: How many 6 digit numbers can be made from $n$ two digit numbers and $6-2n$ single digit numbers? This is essentially the Stars and Bars problem

$$\frac{(n+(6-2n))!}{n!(6-2n)!}$$

Question 2: How many $6-2n$ digit numbers can be created from $4$ single digit numbers?

$$4^{6-2n}$$

Answer: Sum and multiply the above :

$$\sum_{n=0}^3 \frac{(n+(6-2n))!}{n!(6-2n)!} \cdot 4^{6-2n} = 5473$$

A simple mathematica program to confirm:

(* list of possible numbers *)
IntegerDigits/@Range[100001, 999999, 2];
(* delete numbers with even digits *)
DeleteCases[%, {___, a_ /; EvenQ[a], ___}];
(* delete numbers with a nine not followed by one *)
DeleteCases[%, {___, 9, a_ /; (a != 1), ___}];
(* delete all numbers with a nine in the end *)
DeleteCases[%, {___, 9}];
Length@%

5473

Answer 2

The first important thing is: A digit $9$ must be followed by a $1$, but it is not necessary that the digit right before $1$ must be $9$.

First case: The $6$-digit numbers only contain $1;3;5;7$.

The number of possible numbers for this case is obvious: $4^6=4096$ numbers.

Second case: The $6$-digit numbers contain at least one $9$. There are three sub-cases:

• The $6$-digit numbers contain exactly one $9$, so the possible form of numbers must be either of these: $\overline{91cdef};\overline{a91def};\overline{ab91ef};\overline{abc91f};\overline{abcd91};\overline{abcde9}.$ For each form except the last form, because the $6$-digit numbers contain exactly one $9$, the rest $4$ numbers can only be $1;3;5;7$, so each of the forms have $4^4=256$ numbers. For the last form, there are $5$ spare digits instead of $4$, so there are $4^5=1024$ numbers. The total of numbers for this sub-case is $256\times 5+1024=2304$ numbers.

• The $6$-digit numbers contain exactly two $9$'s, so the possible form of numbers must be either of these: $\overline{9191ef};\overline{91c91f};\overline{91cd91};\overline{91cde9};\overline{a9191f};\overline{a91d91};\overline{a91de9};\overline{ab9191};\overline{ab91e9};\overline{abc919}$. For each form except the $4$th, $7$th, $9$th and $10$th forms, there are $2$ spare digits that can only be $1;3;5;7$, so each of these forms has $4^2=16$ numbers. For the $4$th, $7$th, $9$th and $10$th forms however, there are $3$ spare digits instead of $2$ that can only be $1;3;5;7$, so each of these forms have $4^3=64$ numbers. The total of numbers for this sub-case is $16 \times 6+ 64 \times 4=352$ numbers.

• The $6$-digit numbers contain exactly three $9$'s, so the possible form of numbers must be either of these: $919191;\overline{9191e9};\overline{91c919};\overline{a91919}$. Similar to above, $919191$ only has one case, while the other three forms each has four cases, so the total of numbers for this case is: $4 \times 3+1=13$ numbers.

• You can easily prove that the numbers can't have more than three $9$'s.

The total of numbers satisfy is: $4096+2304+352+13=6765$ numbers.

If a $9$ at the end is not allowed, you can just eliminate some of the forms above to get the final answer, which should be $5473$ numbers.