Number of combination if some numbers are known?

Question

Say, I have a password which is 4 digits long. Normally, the number of combination would be 10^4. But what if I know that two of the numbers are 1 and 0? What is the number of combination in this case?

Answer 1

Assuming exactly one $1$ occurs and exactly one $0$ occurs:

• Pick the location of the $1$
• Pick the location of the $0$
• From left to right, pick a digit (not $1$ and not $0$) for the first available empty space
• Pick a digit (not $1$ and not $0$) for the final remaining available space

How many options do you have for each step?

Apply multiplication principle and reach your conclusion.

There are $4$ choices for where the one goes, $3$ choices for where the zero goes, and $8$ choices for each of the remaining locations for a total of $4\cdot 3\cdot 8\cdot 8=768$ sequences with exactly one $1$ and exactly one $0$.

---

For the question if it is at least one $1$ and at least one $0$, let $A_1$ denote the possible sequences that have no $1$'s and $A_0$ the possible sequences with no $0$'s. The question is asking then to calculate $|A_1^c\cap A_0^c|$

Applying inclusion-exclusion and De Morgan's Laws:

$|A_1^c\cap A_0^c| = |(A_1\cup A_0)^c| = |S|-|A_1\cup A_0| = |S|-|A_1|-|A_0|+|A_1\cap A_0|$

How many sequences have no ones? How many sequences have no zeros? How many simultaneously have no ones and no zeros? Plug in these values and simplify for the final result.

As you mentioned above, you know $|S|=10^4$ is the number of sequences that we don't care about restrictions. $|A_1|=9^4$ is the number of sequences with no ones, $|A_0|=9^4$ is the number of sequences with no zeroes, and $|A_1\cap A_0|=8^4$ is the number of sequences with no ones and no zeroes. Simplifying then, there are $10^4-9^4-9^4+8^4=974$ sequences with at least one $1$ and at least one $0$.

You could have opted to count this directly as well as:

Count the number which have exactly one one and exactly one zero. Add this to the number which have exactly two ones and exactly one zero. Add this to the number which have exactly one one and exactly two zeroes. Add this to the number which have exactly two ones and exactly two zeroes. Add this to the number which have exactly three ones and exactly one zeroes. Add this to the number which have exactly one one and exactly three zeroes.

You can see why this process is less recommended as it is very tedious and does not work well with longer length sequences.

Applying a similar process to the first, we have a final count of $4\cdot 3\cdot 8\cdot 8 + \binom{4}{2}\cdot 2\cdot 8 + \binom{4}{2}\cdot 2\cdot 8+\binom{4}{2} +\binom{4}{3}+\binom{4}{3}= 768+96+96+6+4+4=974$

---

Another approach to direct counting:

• Pick where the furthest left one is:
• Pick where the furthest left zero is:
• Depending on the selections made in the previous steps, decide what digits fill in the remaining locations

They fall into the following categories based on the locations of the first zero and first one:

$\star~\star~\underline~\underline~~~~~~~$, $\star~\underline~\star~\underline~~~~~~~~$, $\star~\underline~\underline~\star~~~~~~~~~~~~$, $\underline~\star~\star\underline~~~~~~~~~$, $\underline~\star~\underline~\star~~~~~~~~~~~$, $\underline~\underline~\star~\star~$

Each category has two possibilities, either zero as the first star, or one as the first star.

This gives a count of $2\cdot (10^2+9\cdot 10+9^2+8\cdot 10+8\cdot 9+8^2) = 2(487)=974$, same as above.