Selecting conditional states depending on previous states

Question

I've seen a post which was started as a joke saying : "Well, Guess the code ?" (4 digit code)

Apart from the joke , I was thinking , well , how many combinations do we have here , knowing that 8 and 0 are a must.

Sure ,the logic says :

2^4 minus (bad options which is 0000,8888) = 14

But this is not a mathematical calculation but a human logic being involved.

I was thinking about something like this:

Let's take 8. It has 4 places to be one or more times But if it appears first , then at least one 0 must be on the other 3 places ... and so on and so on

Same for the 0 : It has 4 places to be one or more times But if it appears first , then at least one 8 must be on the other 3 places ... and so on and so on

Question:

How can I yield 14 by a mathematical proof ? (and not by a human logic : "let's take all the options and remove the bad combinations")

EDIT (after some answers) The demo above was an easy part. But I'm after more generalized formula :

Say not only $8$ and $0$ were bold. let's say $0$, $8$, $5$, $2$ were bold and the password was $5$ length long . So then what? removing the count of all $00000$, $88888$, $55555$, $22222$ AND $08555$ (becuase $2$ and $0$ must be present also)? and $08222$? ( becuase $5$ and $0$ must be present also).......?? Do you see what I mean ? Human logic is more complicated here. It is not a general formula , but specific to this case. I'm after a generalized formula

In other words the question can be reduced to :

How many options can we select from $N$ numbers , at length of $L$ ( $L\geq N$) where at least each number from $N$ must appear

so N = 0,8,5,2
   L = 5

08520 valid
85200 valid
08555 invalid (missing 2)
08222 invalid (missing 5)
etc...

Answer 1

First of all, your original argument looks like a mathematical proof to me; you want to count all sequences of $0$'s and $8$'s of length $4$ that contain at least one $0$ and one $8$. That's the same as all sequences of length $4$ that aren't all $0$'s or all $8$'s, and so you get $2^4-2=14$.

But your second line of thought gives another way to reach the same conclusion, albeit more roundabout:

A sequence must start with either $0$ or $8$:

• If it starts with $8$, then the remainder of the sequence is a sequence of length $3$ that is not all $8$'s. There are $2^3-1=7$ such sequences.
• If it starts with $0$, then the remainder of the sequence is a sequence of length $3$ that is not all $0$'s. There are $2^3-1=7$ such sequences.

This yields a total of $7+7=14$ sequences. Of course this is in essence the same reasoning as your original argument, with a small adjustment by distinguishing cases based on the first digit. You could also keep distinguishing cases for the second, third and fourth digit and in this way count all sequences separately. This comes down to drawing a tree diagram of all possible sequences.

---

For the more general case in the edit, the inclusion-exclusion principle is of great help. The generality in which it is stated on the linked page may be a bit intimidating, but the idea is the following;

1. You count the total number of sequences, let's call this $N$. For your example, this would be all sequences consisting of $0$, $2$, $5$ and $8$; there are $4^4=256$ such sequences, so $N=256$. We want to subtract from this the number of sequences that do not contain one of the digits.
2. You don't want the sequences that do not contain a $0$, do not contain a $2$, do not contain a $5$ and do not contain an $8$. There are $N_0=3^4=81$ sequences that do not contain a $0$, and similarly $N_2=N_5=N_8=81$ sequences that do not contain a $2$, a $5$ or and $8$. Now we could compute the number of sequences that contain each digit as $$N-(N_0+N_2+N_5+N_8)=256-4\times81=-68,$$ which is clearly wrong, because we have counted the sequences that do not contain a $0$ and do not contain a $2$ twice.
3. So next add the number of sequences that do not contain a $0$ and a $2$; there are $N_{0,2}=2^4=16$ such sequences, and similarly $$N_{0,5}=N_{0,8}=N_{2,5}=N_{2,8}=N_{5,8}=16.$$ Adding these back we get \begin{eqnarray*} N&-&(N_0+N_2+N_5+N_8)+(N_{0,2}+N_{0,5}+N_{0,8}+N_{2,5}+N_{2,8}+N_{5,8})\\ &=&256-4\times81+16\times6=28. \end{eqnarray*} But now we have a problem with the sequences that are missing three digits; we first subtracted them three times, then added them back three times, so we should subtract them again. To clarify, for example the sequence $8888$ was counted in $N_0$ and $N_2$ and $N_5$ and subtracted, and then counted in $N_{0,2}$ and $N_{0,5}$ and $N_{2,5}$ and added again.
4. Finally we count the sequences that do not contain a $0$, a $2$ and a $5$; there is of course only $N_{0,2,5}=1$ such sequence which is $8888$. Similarly $N_{0,2,8}=N_{0,5,8}=N_{2,5,8}=1$. Then the total number of sequences is \begin{eqnarray*} N&-&(N_0+N_2+N_5+N_8)+(N_{0,2}+N_{0,5}+N_{0,8}+N_{2,5}+N_{2,8}+N_{5,8})\\ &-&(N_{0,2,5}+N_{0,2,8}+N_{0,5,8}+N_{2,5,8})\\ &=&256-4\times81+6\times16-4\times1=24. \end{eqnarray*} And this is easily verified; if a $4$-digit sequence must contains each of the $4$ digits once, then it is a permutation of the $4$ digits. There are $4!=4\times3\times2\times1=24$ permutations, as there are $4$ choices for the first digit, then $3$ for the second, then $2$ for the third and then only $1$ for the last.

EDIT: I just saw that the example in your edit concerns sequences of length $5$, whereas my example treats sequences of length $4$. The number of such sequences of length $5$ is $240$, which you can verify yourself with this method.

EDIT2: I just saw that you asked for a formula for the number of sequences of length $L$ that contain each of $N$ digits at least once, with $N\leq L$. The above shows that the number of possible sequences is $$\sum_{i=0}^N(-1)^i\binom{N}{i}(N-i)^L.$$ In particular, for the original question on the number of sequences of length $L=4$ with the $N=2$ digits $0$ and $8$, we indeed get $$\sum_{i=0}^N(-1)^i\binom{N}{i}(N-i)^L=\binom{2}{0}2^4-\binom{2}{1}1^4+\binom{2}{0}0^4=1\times16-2\times1+1\times0=14.$$

Answer 2

Your "human logic" IS a mathematical proof : here, it's definitely easier to compute the number of codes that don't have at least a 0 and a 8.

Let's note

• $\Omega$ the set of all codes,
• $A_0$ the set of codes with at least one $0$,
• $A_8$ the set of codes with at least one $8$.

You want $\#(A_0\cap A_8)$. The complementary of this set is $\overline{A_0}\cup\overline{A_8}$, and with Poincaré formula : $$\#(\overline{A_0}\cup\overline{A_8}) = \#(\overline{A_0}) + \#(\overline{A_8}) - \#(\overline{A_0}\cap\overline{A_8})$$ $\overline{A_0}$ is the set of codes with no $0$, there are $9^4$ such codes. Similarly, $\#(\overline{A_8})=9^4$. And $\overline{A_0}\cap\overline{A_8}$ is the set of codes that contain neither $0$ nor $8$, there are $8^4$ of them. So $$\#(\overline{A_0}\cup\overline{A_8}) = 2\times9^4-8^4=9026$$ Finally $\#(\Omega)=10^4$, so $$\#(A_0\cap A_8) = 10^4-9026=74$$