Counting-strings Counting Strings - Part 1
Post
Cancel

Counting Strings - Part 1

One day, I was solving a recurrence problem from Kenneth Rosen’s Discrete Math book.

Question 1

Find the recurrence for the number of bitstrings of length n, containing no two consecutive zeros

This is quite easy, right?

Let \(a_n\) be the number of strings of length n.

  • If the string starts with \(1\), we have \(a_{n-1}\) choices since there’s no restriction.
  • If the string starts with \(0\), we must have \(0\) after it, so \(a_{n-2}\) choices.

And since these cases don’t overlap, we can sum them to compute \(a_n\)
So, \(a_n = a_{n-1}+a_{n-2}\)

Sweet and simple fibonacci. Here comes the fun part. The next problem.

Question 2

Find a recurrence relation for the number of n-digit strings over \(\{0,9\}^*\), with an even number of zeros.

I couldn’t construct a case easily. I thought of it, (didn’t look at the solution yet) and I got an idea -

Let \(e_n\) denote the number of n-length strings with even number of zeros
Let \(o_n\) denote the number of n-length strings with odd number of zeros

If we are in \(e_n\)

  • we are looking at \(0\), then we have consumed a \(0\) and we need to consume odd number of zeros, i.e. \(o_{n-1}\)
  • we are looking at any other digit, then we consumed one digit, so we need \(9e_{n-1}\) for the other digits

If we are in \(o_n\)

  • we are looking at \(0\), then we have consumed a \(0\) and we need to consume even number of zeros, i.e. \(e_{n-1}\)
  • we are looking at any other digit, then we consumed one digit, so we need \(9o_{n-1}\) since we are still in an odd parity

So,

\[\begin{align} e_n &= o_{n-1} + 9e_{n-1} \\ o_n &= e_{n-1} + 9o_{n-1} \end{align}\]

Now, it’s time to solve them \(\begin{align} a_n &= e_n+o_n \\ &= o_{n-1}+e_{n-1}+9(o_{n-1}+e_{n-1}) \\ &= 10a_{n-1} \tag{1} \end{align}\)

Also,

\[\begin{align} d_n &= e_n - {o}_n \\ &= 9(e_{n-1} - {o}_{n-1}) - (e_{n-1} - {o}_{n-1}) \\ &= 8d_{n-1} \tag{2} \end{align}\]

The Base case:
\(\begin{align} e_1 &= 9 \\ o_1 &= 1 \\ \implies a_1 &= 10 \\ d_1 &= 8 \\ \implies a_n &= 10^n \\ d_n &= 8^n \end{align}\)

From \((1)\) and \((2)\) we have, \[ e_n = \frac{10^n+8^n}{2} \]

Why did we construct two recurrences ?

We constructed two recurrence relations since we need to count the number of zeros mod 2.
Let’s look more closely. In the problem, we are counting strings with even number of zeros, in the alphabet \(\{0-9\}^*\). Infact, this is a regular language since we can construct a DFA to accept it.

stateDiagram-v2
    [*] --> init
    init --> odd: 0
    odd --> odd: 1..9
    init --> [even]: 1..9
    [even] --> [even]: 1..9
    [even] --> odd: 0
    odd --> [even]: 0

Cool! Now let’s tweak this DFA a bit to count strings. Lets index each state with an integer \(i\) to represent the number of strings of length \(i\) accepted by that state.

Let \(s_n\) represent number of strings of length \(n\) accepted by the DFA starting at state \(s\)

So,

\([init]_n = [odd]_{n-1} + 9[even]_{n-1} \tag{1}\) because we have only one way to reach \([odd]\) and \(9\) ways to reach \([even]\) from \([init]\). In either way we consume one symbol, so \(n \rightarrow n-1\)

Similarly,
\([even]_n = 9[even]_{n-1}+[odd]_{n-1} \tag{2}\)
\([odd]_n = 9[odd]_{n-1}+[even]_{n-1} \tag{3}\)

Wait! \((2)\) and \((3)\) are the recurrences we used to solve this problem. So, we can define recurrences now, but we also need the base cases.

\([even]_0 = 1, [odd]_0 = [init]_0 = 0\) since \([even]\) is a final state (if we start at \([even]\), we can accept only \(\epsilon\)) whereas \([odd]\) and \([init]\) are non-final states.

Generalization

To generalize this concept, we need to define some rules.

Case 1

stateDiagram-v2
    A --> B: α

Then

\[A_n = B_{n-\lvert \alpha \rvert}\]

Proof

In this step, we consume \(\alpha\) to move from \(A\) to \(B\). So if we count n-length strings from state \(A\), we have to count strings of length \(n-\lvert \alpha \rvert\) from state \(B\), as we are removing the prefix \(\alpha\) in the transition.

Case 2

stateDiagram-v2
    A --> B: α
    A --> C: β

Then

\[A_n = B_{n-\lvert \alpha \rvert} + C_{n-\lvert \beta \rvert}\]

where \(\alpha\) and \(\beta\) have no common prefix

Proof

Applying Case 1 for \(A \longrightarrow B\) and \(A \longrightarrow C \), we get the result. And since we are defining the rules for DFA, \(\alpha\) and \(\beta\) have no common prefix except \(\epsilon\), so \(B_{n-\lvert \alpha \rvert}\) and \(C_{n-\lvert \beta \rvert}\) have no strings in common

Case 3

stateDiagram-v2
    A --> A: α

Then

\[A_n = A_{n-\lvert \alpha \rvert}\]

where \(\alpha\) and \(\beta\) have no common prefix

Proof

Applying Case 1 for \(A \longrightarrow A\)

Now let’s solve a difficult recurrence using DFA

Base Cases

\[A_0 = \begin{cases} 1 &\text{if A is final} \\ 0 &\text{if A is non final} \end{cases}\]

Proof

If \(A\) is final, we accept \(\epsilon\) at \(A\).

Question 3

Find a recurrence for the number of ternary strings that do not contain consecutive symbols that are same

So, we cannot have 00, 11, and 22 as substrings.

Let’s construct the DFA first

stateDiagram-v2
    ε --> [0]: 0
    ε --> [1]: 1
    ε --> [2]: 2
    [0] --> φ: 0
    [0] --> [1]: 1
    [0] --> [2]: 2
    [1] --> [0]: 0
    [1] --> φ: 1
    [1] --> [2]: 2
    [2] --> [0]: 0
    [2] --> [1]: 1
    [2] --> φ: 2
    φ --> φ: 0,1,2

Now, let’s write the recurrences

For $n \ge 1$, we have

\[\begin{align} [\epsilon]_n &= [0]_{n-1} + [1]_{n-1} + [2]_{n-1} \\ [0]_n &= [\phi]_{n-1} + [1]_{n-1} + [2]_{n-1} \\ [1]_n &= [\phi]_{n-1} + [0]_{n-1} + [2]_{n-1} \\ [2]_n &= [\phi]_{n-1} + [0]_{n-1} + [1]_{n-1} \\ [\phi]_n &= [\phi]_{n-1} + [\phi]_{n-1} + [\phi]_{n-1} \\ &= 3[\phi]_{n-1} \end{align}\]

For $n = 0$,

\[\begin{align} [\epsilon]_0 &= [0]_0 = [1]_0 = [2]_0 = 1 \\ [\phi]_0 &= 0 \end{align}\]

We have \([\phi]_n\ = 0\), so we can simplify the above recurrences

\[\begin{align} [\epsilon]_n &= [0]_{n-1} + [1]_{n-1} + [2]_{n-1} \\ \tag{1} [0]_n &= [1]_{n-1} + [2]_{n-1} \\ \tag{2} [1]_n &= [0]_{n-1} + [2]_{n-1} \\ \tag{3} [2]_n &= [0]_{n-1} + [1]_{n-1} \\ \end{align}\]

Adding \(1\), \(2\) and \(3\), we have

\[\begin{align} [012]_n &= [0]_n + [1]_n + [2]_n \\ &= 2[012]_{n-1} \\ &= 2^{n}[012]_0 \\ &= 3\cdot 2^n \end{align}\] \[\therefore [\epsilon]_n = [012]_{n-1} = \begin{cases} 1 &\text{if n = 0} \\ 3\cdot 2^{n-1} &\text{n > 0} \end{cases}\]

Alt Proof.: We can place 0, 1, or 2 in the first place in 3 ways. And for the remaining places, we must make sure not to place the previous symbol, so, 2 ways for every other place. Implies \(3\cdot 2^{n-1}\) ways in total

This post is licensed under CC BY 4.0 by the author.