1
$\begingroup$

I've been working on these two practice problems, I'm not really sure whether my solutions are right or not.

  1. What is the counting sequence for all words on the $\{a, b, c\}$ that contain exactly one $a$?

    For this question I've come to the conclusion that the sequence is $\binom{n}{1}\cdot2^{n-1}$

  2. We have $\{a, b\}$, no consecutive "b"s are allowed.

    How does the counting sequence begin (at least up to size $6$)?

I think I should take the combination with no repetition approach, but I have no idea where to begin with.

A step by step guide for this problem is appreciated.

$\endgroup$
3
  • $\begingroup$ @bburGsamohT: The original question stated "2^n-1", which I have fixed to $2^n-1$. I think your fix is not aligned with OP's intention. $\endgroup$ – barak manos Jan 14 '16 at 8:05
  • $\begingroup$ bburGsamohT's fix is the right version. Yours would be wrong. Thanks for reformatting it though, couldn't find the ones for combinatorics. $\endgroup$ – Andrew Jan 14 '16 at 23:47
  • $\begingroup$ No problem, but when you say "Yours would be wrong", keep in mind that it is in fact yours, not mine. $\endgroup$ – barak manos Jan 15 '16 at 11:08
2
$\begingroup$

For part 2: let $c_n$ denote the number of $n$ letter words satisfying your restraints. Let $w=l_1l_2\dots l_n$ be such a word, where $l_i\in\{a,b\}$ for $1\leq i\leq n$. If $l_1=a$, then this induces no restrictions on the remaining letters $l_2\dots l_n$. This means that $l_2\dots l_n$ is a word of length $n-1$ satisfying the repetition requirements, i.e. there are exactly $c_{n-1}$ words of length $n$ which satisfy the rules and whose first letter is $a$. Now if $l_1=b$, we must have that $l_2=a$, otherwise we would have two consecutive $b$'s. Once we place the $a$, there are no other affects that $l_1$ has on the rest of your word. This means that $l_3\dots l_n$ is a word of length $n-2$ satisfying your requirements. So there are $c_{n-2}$ words of length $n$ which have no consecutive $b$'s and whose first letter is a $b$. As each word can only start with $a$ or $b$, we have exhausted all possibilities. Thus we have the recurrence $$ c_n=c_{n-1}+c_{n-2}, $$ with the obvious initial conditions $c_1=2$ given by the words $a$ and $b$, and $c_2=3$ given by the words $aa$, $ab$, and $ba$. Can you go from here?

$\endgroup$
1
  • $\begingroup$ Thanks a lot, I understand the situation now. However, I still don't get the Cn notation. How do you get 2 if n is 1 using the formula? It's obvious that it's 2 by trying out, but what do I get when I put 1 for n? c1-1 + c1-2 How does this equal to 2? I don't get the c notation thing. $\endgroup$ – Andrew Jan 14 '16 at 18:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.