0
$\begingroup$

I have always had trouble solving this kind of problem - forming numbers involving zero.

In how many ways can we form a 2-digit number using only 0 and 1

This one is fairly easy. The first one must be 1, thus the second one must be 0.

In how many ways can we form a 3-digit number using only 0, 1 and 2

  1. I choose the first digit in $2$ ways ($1$ or $2$)
  2. Then I have $2$ numbers remaining which I distribute in $2!$ ways: $4$ numbers in total

(...) 4-digit number using only 0, 1, 2 and 3

  1. First digit: $3$ ways
  2. Remaining digits: $3!$ ways, $18$ numbers in total

(...) $n\le9$ -digit number using only $0,1,...,n-1%$

  1. First digit: $(n-1)$ ways
  2. Remaining digits: $(n-1)!$ ways
  3. Total: $(n-1)(n-1)!$ numbers

Is it the right and the most appropriate way to do this or is there a different approach?

Apart from that, if the task were like this:

In how many ways can we form a 7-digit number using only 0,1,2

  1. First digit: $2$ ways
  2. Every other digit: $3$ ways
  3. Options where only 1 digit is used: $2$
  4. Options where only 2 digits are used: $2^7$ ways
  5. Total: $2\cdot3^6-2-2^7= 1328$

Could you please review this method?

$\endgroup$
  • $\begingroup$ The method is described systematically in these videos (about 18 mins total time): youtube.com/watch?v=1nD2aDDK09Q&t=5s $\endgroup$ – avs May 8 '17 at 18:51
  • 1
    $\begingroup$ Your answer makes sense only in the situation that every digit must be used. The answer is incorrect if you are allowed to repeat digits. For example, there is of course the two-digit number $11$ in addition to the two-digit number $10$. If every digit must be used at least once, for the problem where you have a longer number than available digits, use inclusion-exclusion on whether or not a digit appears in the number. $\endgroup$ – JMoravitz May 8 '17 at 18:56
  • $\begingroup$ @JMoravitz Thank you! You are right, I should have included the fact that all digits must be used in my post. $\endgroup$ – ILoveChess May 8 '17 at 19:01
2
$\begingroup$

As mentioned in the comments above, your answer is correct for the first few examples (after making the correction to the problem statement that every digit must be used at least once).

To elaborate on my comment for the later problem, let $A_0$ be the set of 7-digit numbers where all digits are taken from $\{0,1,2\}$ such that there is at least one $0$. Similarly, $A_1$ and $A_2$ have at least one $1$ and at least one $2$ respectively.

You are then tasked with counting $|A_0\cap A_1\cap A_2|$.

Letting $\Omega$ represent the set of $7$ digit numbers with digits taken from $\{0,1,2\}$ with no other restrictions, recognize that $A_0^c=\Omega\setminus A_0$ represents the set of $7$ digit numbers with no zeroes and digits taken from $\{0,1,2\}$. Similarly for $A_1^c$ and $A_2^c$. Recognize then that the total we wish to count can be rewritten as $|\Omega\setminus(A_0^c\cup A_1^c\cup A_2^c)|$ which expands via inclusion-exclusion as

$|\Omega|-|A_0^c|-|A_1^c|-|A_2^c|+|A_0^c\cap A_1^c|+|A_0^c\cap A_2^c|+|A_1^c\cap A_2^c|-|A_0^c\cap A_1^c\cap A_2^c|$

Each term of the above should be straightforward to calculate.

$|A_0^c\cap A_2^c|$ for example is the set of seven digit numbers with no zeroes and no twos with all digits from $\{0,1,2\}$. There is only one such number, $1111111$. On the other hand $|A_1^c\cap A_2^c|$ is the set of seven digit numbers with no ones and no twos with all digits from $\{0,1,2\}$. There are no such numbers since $0000000$ doesn't qualify as a seven digit number (only as a seven digit string).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.