Permutation Question Help

2.5k Views Asked by At

Hexadecimal numbers are made using the sixteen digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. They are denoted by the subscript 16. For example, 9A2D$_{16}$ and BC54$_{16}$ are hexadecimal numbers.

How many hexadecimal numbers begin with one of the digits 3 through B, end with one of the digits 5 through F, and are 5 digits long?

--from Discrete Math with Applications 4th Ed.

My thoughts so far:
$16^5$ is the number of 5 hexidecimal numbers that are 5 digits long.
3 through B has 9 digits. So there are $7 \times 16^4$ digits that start with 3 through B and are 5 digits long.
5 through F has 11 digits. So there are $5 \times 16^4$ digits that end with 5 through F and are 5 digits long.

Therefore $16^5 - (7 \times 16^4) - (5 \times 16^4)$ would equal the number of digits the meet the requirements of the question.

Based on other examples that I've done in the textbook this is what I come up with.

2

There are 2 best solutions below

0
On BEST ANSWER

You could set it up as inclusion-exclusion: Let $A = \{$5digit strings with initial digit as 3 through b$\}$ and $B = \{$5digit strings with last digit as 5 through f$\}$, along with our universe set $X = \{$all 5 digit strings with no restriction$\}$.

Then $|A\cap B| = |X| - |A^c| - |B^c| + |A^c\cap B^c|$

$= 16^5 - 7\cdot 16^4 - 5\cdot 16^4 + 5\cdot7\cdot 16^3$

Following inclusion-exclusion will get you to a correct answer, however there is perhaps an easier approach. Approach it as a multiplication principle problem broken into 5 steps:

Step 1: Pick the first digit. We have a restriction on this so there are 9 choices. (3,4,5,...,a,b)

Step 2: Pick the next digit. No restriction so 16 choices (0,1,2,...e,f)

Step 3 and 4: same as step 2, 16 choices and another 16 choices

Step 5: Pick the last digit. We have a restriction on this so there are 11 choices (5,6,...,e,f)

According to the multiplication principle, if we can break it up into steps like this with the decision made at one step not affecting in any way the number of choices available to the next step, then the total number of ways to accomplish all steps simultaneously is the product of the numbers, so $9\cdot 16\cdot 16\cdot 16\cdot 11 = 9\cdot 11\cdot 16^3$


as a side note, be warned that in some questions asking about "number of 5 digit numbers" it doesn't allow $0$ to be the leading digit. We consider $01234$ to be a four digit number since $01234 = 1234$. In this specific example we didn't have to worry about it since the condition on the first digit prevented a leading zero anyways. Often times if a leading zero is allowed it is called a "string" instead of a "number"

0
On

An easier way to do this is to treat this as a "balls in bins" problem. You have five characters: $x_{1} x_{2} x_{3} x_{4} x_{5}$. The first character $x_{1}$ has $9$ possibilities, and the last character has $11$ possibilities. The middle three characters have no restrictions, and each character is independent. So by rule of product, we get $9 * 16^{3} * 11$ as our count. It's much easier to see it this way than with inclusion-exclusion, in my opinion.