Calculating decimal strings using product rule help

Eagerissac

New member
So I'm trying to calculate the number of valid decimal-strings under certain conditions related to the product rule, and was hoping for some clarification. I have a copy and paste solution from my teacher for a similar question below, and I was basing my solution of #2 off of that but I can't seem to get the formula right. I would really appreciate some help.

GIVEN QUESTION:

A decimaI-string is a sequence of characters consisting of {0,1,2,3,4,5,6,7,8,9}.

Etc:

0

3463412398

Let n≥0 be an integer.

1. Calculate the number of decimaI-strings of Iength n.

So I know the answer to this is 10^n

2. Calculate the number of decimal-strings d1,…,dn of length n such that d1d2≠00 and d2d3≠01?

Following my teacher's example below, I counted 981 valid decimal-strings when n = 3. However, when I tried to test the formula I got for n = 4, I counted 9801 decimal strings when the formula should give me 9810 valid decimal-strings. I re-counted the valid strings from each length multiple times, but I can't get the formula to work for n>= 4. I was wondering if someone could explain what I'm doing wrong?

981 x 10^(n-3)

3. Calculate the number of decimal-strings d1,…,dn of length n such that d1d2=00 or d1d2d3=111

This one I'm a little confused as to how the "or" would change my calculations and was hoping for some help.

-------------------------------------
TEACHER'S SOLUTION FOR SIMILAR QUESTION THAT I WAS BASING MY WORK OFF OF:

An n-bit binary string is a sequence of length n over the alphabet {0,1}.

1. How many n-bit binary strings are there?

2^n

2. How many n-bit binary strings b1,…,bn are there such that b1b2≠00 and such that b2b3≠01?

These are the valid choices of b1b2b3: {011, 010, 100, 110, 111}. (The invalid choices are {000, 001, 101}.) After choosing b1b2b3 we have 2 choices for each of b4, . . . , bn. Therefore, by the Product Rule, the number of strings we are interested in is
5 × 2^(n−3)

Dr.Peterson

Elite Member
How did you obtain 981? And more important, how did you obtain 9801? Did you actually list out all the strings, or what?

Mr. Bland

Junior Member
1. Calculate the number of decimaI-strings of Iength n.

So I know the answer to this is 10^n
This is correct. Each digit contributes 10 values for each of the combinations of the other digits, giving $$\displaystyle 10^n$$ combinations at length $$\displaystyle n$$.

2. Calculate the number of decimal-strings d1,…,dn of length n such that d1d2≠00 and d2d3≠01?
If a digit doesn't exist (d2 when $$\displaystyle n = 1$$ and d3 when $$\displaystyle n < 3$$), is it considered "not a match"? What process did you use to determine the number of satisfying combinations at $$\displaystyle n = 3$$ and $$\displaystyle n = 4$$?

This problem asks you to disqualify certain combinations based on the exact contents of three of the digits. Under both conditions, d2 must be 0, so any string where d2 is not 0 will not be filtered. d2 does not contribute a full 10 values to the satisfying combinations, but rather 9 values. The remaining $$\displaystyle n - 1$$ digits (in the context of d2 in isolation) continue to contribute 10 values. The total number of combinations where d2 is not 0 can be found with $$\displaystyle 10^{n - 1} * 9$$. Bear in mind that some combinations where d2 is 0 are still valid.

Further filtering where d1 is 0 or d3 is 1 will use a similar approach.

3. Calculate the number of decimal-strings d1,…,dn of length n such that d1d2=00 or d1d2d3=111

This one I'm a little confused as to how the "or" would change my calculations and was hoping for some help.
This one differs from #2 in two key ways: it uses $$\displaystyle =$$ instead of $$\displaystyle \ne$$, and uses "or" instead of "and". Rather than filtering out specific combinations, you will only be allowing specific combinations. Otherwise, the logic regarding how many total combinations satisfy the conditions is very similar.

Eagerissac

New member
981 was obtained by figuring out which values were invalid and subtracting them from the total of 1000. The same was done with 9801. I counted by 10s. It's possible I'm counting wrong but I've tried several times and those are the values I keep getting.

Values like 1011 and 003 would not be valid.

Dr.Peterson

Elite Member
I would say that 9810 is obviously correct. Please show specifically how you got 9801, so we can see what went wrong; a general description doesn't help.