Counting Strings - Part 3
Post
Cancel

# Counting Strings - Part 3

I strongly recommend you to read Part-1 and Part-2 before proceeding into this section.

In this part, we will derive a general formula for solving linear recurrences.

Find the recurrence for the number of strings generated by the regular expression ${(a+bb+ccc)}^\ast$

From Part-2, we have

$[R^\ast]_n = \begin{cases} [R^\ast]_{n-1} + [R^\ast]_{n-2} + [R^\ast]_{n-3} &\text{n} \geq 3 \\ 1 &\text{n = 0, 1} \\ 2 &\text{n = 2} \end{cases} \tag{eg.1.2}$

So we have the recurrence $r_n = r_{n-1}+r_{n-2}+r_{n-3}$ This corresponds to the strings generated by the regular expression ${(a+bb+ccc)}^\ast$

In other words, $r_n$ is equal to number of strings of length n generated by ${(a+bb+ccc)}^\ast$. Now suppose we have to construct a string using a, bb, and ccc only

Let’s place ccc $g_c$ times, bb $g_b$ times and a $g_a$ times to make the string. We have,

$n = 3 g_c + 2 g_b + g_a$

And, now we place $g_a$, $g_b$, and $g_c$ into groups in

$\sum_{\substack{0 \leq g_a, g_b, g_c \leq n}}{\binom{g_a+g_b+g_c}{g_a}\binom{g_b+g_c}{g_b}\binom{g_c}{g_c}}$

Simplifying,

$r_n = \sum_{\substack{0 \leq g_a, g_b, g_c \leq n}}{\frac{(g_a+g_b+g_c)!}{g_a!\space g_b!\space g_c!}}$

This sums up the article! I hope you had fun :)