Combinatorics is interesting, let’s get right into it ⬇️
Let’s start with something simple:
How many 4 digit numbers can be made? (Where the first digit is nonzero)
There are 9 choices for the first digit, and no matter what you do for the first digit, there are always 10 choices for the second digit and onwards.
How many 4 digit #s have the 1st digit non zero, and no two same digits next to each other?
Starting from the left, there’s 9 choices for the 1st because possible choies range from 1–9. For the next ones, there are still 9 choices that avoid copycatting what you got before. For the next digit, you would have 10 choices (0–9), but there’s exactly 1 digit to avoid (the one right before it.)
So why is it always 9?
It’s because for the first one you just avoid 0, and for the rest of them, you have any of the 10 digits except the one that happened right before it.
Suddenly, the order matters. 😳
What would happen if you started from the right?
If you started from the very right, you’d have 10 choices 0–9. Going to the left, no matter what you did previously, you just have to avoid that. If you keep going left, you also have 9 choices.
For the left most digit, the number of options will depend on whether the hundreds digit is 0. If it is, you would have 9 choices- you could use any of the digits 1–9 because you don’t have a 0 in front and its not equal to the one next to it.
If the hundreds digit is not 0, then you have 8 choices. You originally had options 1–9, so if its not zero, you lose one of your options.
This tells you that the answer is between 10 x 9 x 9 x 8 and 10 x 9 x 9 x 9
How many four digit numbers (not starting with 0) are even and have no 2 same digits next to each other?
9 choices for the first three digits, but for the fourth digit you need to be even.
However, if the previous digit was even, then you only have 4 choices for the last digit.
So, the answer is between 9³ x 4 …. 9³ x 5
…but what is it exactly?
Let’s start from the bare bones.(even and no 2 digits next to each other)
1 digit version: (even)- The number of one digit numbers that are even (and don’t start with 0) is 4.
2 digit: You have the bad guys: 22,44,66,88. So, how many even legitimate 2 digit numbers really are there?
Total even 2 digits: 1st digit (non zero): 9. 2nd digit: 5 choices(0,2,4,6,8). 9x5=45 choices.
Then, take total choices minus bad guys to get 41.
Odd: There would be 45 choices but theres 5 bad guys (11,33,55,77,99) so 45 minus 5 = 40 choices.
Ok…interesting.
Notice that you can start to build the answer for the next number of digits using the answer from the previous number of digits. That’s recursion.
Recursion:
En = # of even digit numbers, no equal next to each other
On = # of odd digit numbers, no equal next to each other
Here’s the key: if u have a number of n digits, and ended with an even, you finish it by ending it with an even digit thats doesn’t match what’s next to it, which is why you lose an option. So whether there’s 4 or 5 options on the last digit depended on what it was ending in.
This means that 4 times previous even digits(must avoid the even next to it) + 5 times the previous odd. So,
E n+1 = (En x 4) + (On x 5)
Credits:
miro + me ❤
CMU Discrete Math lectura numero uno https://www.youtube.com/watch?v=0K540qqyJJU&ab_channel=DailyChallengewithPo-ShenLoh
