Product rule - finding formula to represent number of valid decimal strings

M

MaryStew

New member
Joined
Jan 23, 2020
Messages
18
Can anyone explain how to create a formula for the following question? I can sort of see the general pattern but I just don't know how to translate my answer into a neat formula.

A dec-string is a sequence of characters from the 10-character aIphabet {0,1,2,3,4,5,6,7,8,9}. For example, these are dec-strings:

0

3235734

Let n≥0 be an integer.


1. A dec-string d1,…,dn is k-bad if di=dm or di+dm=9 for some i<m≤i+k and is k-good otherwise. What is the number of k-good dec-strings of Iength n?

Let's say I'm looking for decimal strings of 5 characters (n = 5). The search range (k) is 2 characters. A string is '2-bad' if the digits that are up to 2 away are the same, or they add to 9. It is '2-good' otherwise.

CASE 1:

There are 10 choices for the first digit.

Let's say I pick 2.

The next digit can't be the same (2) or add to nine (7), so that leaves 8 choices. Let's say I pick 5.

The third digit can't be the same as the first (2) or the second (5) and not adding to nine for either (7 or 4). So that leaves 6 choices. I'm gonna pick 0.

The fourth digit can't be the same as the two prior digits (5 or 0) or the digits that make a sum of nine (4 or 9). So again there are 6 choices. Let's say I pick 2.

Finally, by similar logic the last digit has 6 choices.

So for n=5 and k=2 I have:

10 * 8 * 6 * 6 * 6

CASE 2:

Now let's try n=7 and k=3:

10 choices for the first digit.

8 choices for the second digit.

6 choices for the third digit.

4 choices for all the remaining digits.

10 * 8 * 6 * 4 * 4 * 4 * 4


I tested it with some other numbers and usually get 10 * 8 * 6 * 6... *6 or something like that. I'm not quite sure how to translate this into a neat formula though and was hoping for some help.
 
Last edited:
My friend who finished this question told me there were only 5 cases so I'm a little confused and not sure if I'm doing this right either.
 
Let's get some terminology squared away before I dive into this one.

You've got a string of base 10 digits of length \(\displaystyle n\)

This string is called "k-bad" if in any of the [MATH]n-k+1[/MATH] sequential subsequences of length \(\displaystyle k\)
there exist either repeated digits, or digits such that their sum is 9.

So for example

0 4 3 1 5

is 2 good, 3 good, but 4 bad

Is all that correct?
 
Last edited:
Romsek said:
Let's get some terminology squared away before I dive into this one.

You've got a string of base 10 digits of length \(\displaystyle n\)

This string is called "k-bad" if in any of the [MATH]n-k+1[/MATH] sequential subsequences of length \(\displaystyle k\)
there exist either repeated digits, or digits such that their sum is 9.

So for example

0 4 3 1 5

is 2 good, 3 good, but 4 bad

Is all that correct?
Click to expand...

0 4 3 1 5 work perfectly.

First digit I have 10 choices, 0 was picked.

Second digit I have 8 choices. I cannot pick 0 since that was already picked before, and I cannot pick 9 since that adds up to nine. 4 is picked.

Third digit I have 6 choices. I cannot pick 0 or 4 as they were already picked and are only two digits down. I cannot pick 9 or 5 as those add up the previous digits to nine. 3 was picked.

Fourth digit also has 6 choices. I cannot pick 4, 3, as they were already picked. I cannot pick 5 or 6 either cause those add up to 9. I pick 1.

Fifth digit has 6 choices. I cannot pick 3, 1, as those were already picked. I cannot pick 6 or 8 either cause those add up to 9. 5 was picked.

Basically, a string is '2-bad' if the digits that are up to 2 spaces away are the same or the 2 digits picked prior and the one about to be picked add up to 9 as three different individual calculations. It is '2-good' otherwise.

As a side note, the number of dec-strings of length n is 10^n.

Some people I know represented the formulas as a piece wise function. I don't know if there is just a way to represent it as a one-line equation? Eitherway, I can't seem to figure out a way to write a solution past 10*8*6. I don't know what should come after that part.
 
Last edited:
someone told me it turns out the cases for n≥5 are trivial since they're all the same case. I just can't figure out a way to represent it as a formula or formulas. there's only finitely many relevant values of n so there's finitely many single variable formulas
 
What's going on is that the decimal digits can be paired into 5 groups such that the pairs each sum to 9.
If you want a k-good string of digits each group can be used only once in every k length substring.

As there are only 5 groups available it should be clear that there are no k-good strings with \(\displaystyle k>5\)

So let's look at each length k-good string in a sequence looks like.

1-good strings are just digits, but not 9. So the group (0,9) only has 1 element.
It's easier to think of 1-good strings as just any length string without the digit 9.
There are \(\displaystyle 9^n\) of these.

Looking at 2-good strings is a bit more revealing.
We start with a group. We have 5 choices.
The next digit must be from one of the other 4 groups, thus we have 4 choices for the next digit group.
At each succeeding digit we continue to have 4 choices for the next group.
In a string of \(\displaystyle n\) digits that gets us \(\displaystyle 5\cdot 4^{n-1}=5\cdot 2^{2(n-1)}\) sequences of groups.
Each group can be 1 of 2 digits and thus we append a factor of \(\displaystyle 2^n\)
Thus there are [MATH]5 \cdot 2^{2(n-1)+n} = 5 \cdot 2^{3n-2}[/MATH] 2-good strings of length \(\displaystyle n\)

3 good strings is a bit different than 2-good strings. We have to start taking into account 2 previous groups when selecting the next digit group.
The second digit gets 4 groups to choose from, but the 3rd digit only gets 3, and similarly all the rest only get 3 choices.
So we end up with [MATH]5\cdot 4 \cdot 3^{n-2}\cdot 2^n[/MATH] 3-good strings of length \(\displaystyle n\)

4 and 5-good strings are similar to 3-good strings.

There are \(\displaystyle 5\cdot 4\cdot 3 \cdot 2^{n-3} \cdot 2^n = 60\cdot 2^{2n-3}\) 4-good strings of length \(\displaystyle n\), and
\(\displaystyle 120 \cdot 2^n\) 5-good strings of length \(\displaystyle n\)
 
Last edited:
Romsek said:
Thus there are [MATH]5 \cdot 2^{2(n-1)+n} = 5 \cdot 2^{3n-2}[/MATH] 2-good strings of length \(\displaystyle n\)
So we end up with [MATH]5\cdot 4 \cdot 3^{n-2}\cdot 2^n[/MATH] 3-good strings of length \(\displaystyle n\)
There are \(\displaystyle 5\cdot 4\cdot 3 \cdot 2^{n-3} \cdot 2^n = 60\cdot 2^{2n-3}\) 4-good strings of length \(\displaystyle n\), and
\(\displaystyle 120 \cdot 2^n\) 5-good strings of length \(\displaystyle n\)
Click to expand...

Ok, I had to go before finishing this. Ok, Ignoring n=1, as it's a bit nonsensical compared to the others we have.

[MATH]N_k(n) = \dfrac{5!}{6-k}!(6-k)^{n-k+1} \cdot 2^n,~k=2,3,4,5,~n\geq k[/MATH]
 
You must log in or register to reply here.
Top