• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

### Select your language

Suggested languages for you:

Americas

Europe

Q15E

Expert-verified
Found in: Page 511

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# How many ternary strings of length six do not contain two consecutive ${\mathbf{0}}{\mathbf{\text{'}}}{\mathbit{s}}$or two consecutive ${\mathbf{1}}{\mathbf{\text{'}}}{\mathbit{s}}$ ?

There are 239 ternary strings of length six that do not contain two consecutive $0\text{'}s$ or two consecutive $1\text{'}s$ .

See the step by step solution

## Step 1: Given data

A string that contains only $0\text{'}s$, $1\text{'}s$ and $2\text{'}s$ is called a ternary string.

## Step 2: Concept used of recurrence relation

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms (Expressing ${{\mathbit{F}}}_{{\mathbf{n}}}$ as some combination of ${{\mathbit{F}}}_{{\mathbf{i}}}$ with ${\mathbit{i}}{\mathbf{<}}{\mathbit{n}}{\mathbf{\right)}}$.

## Step 3: Find the number of ternary strings

We will compute ${a}_{2}$ through ${a}_{6}$ using the recurrence relation:

${a}_{2}={a}_{1}+2{a}_{0}+2=3+2·1+2=7\phantom{\rule{0ex}{0ex}}{a}_{3}={a}_{2}+2{a}_{1}+2{a}_{0}+2=7+2·3+2·1+2=17\phantom{\rule{0ex}{0ex}}{a}_{4}={a}_{3}+2{a}_{2}+2{a}_{1}+2{a}_{0}+2=17+2·7+2·3+2·1+2=41\phantom{\rule{0ex}{0ex}}{a}_{5}={a}_{4}+2{a}_{3}+2{a}_{2}+2{a}_{1}+2{a}_{0}+2=41+2·17+2·7+2·3+2·1+2=99\phantom{\rule{0ex}{0ex}}{a}_{6}={a}_{5}+2{a}_{4}+2{a}_{3}+2{a}_{2}+2{a}_{1}+2{a}_{0}+2=99+2·41+2·17+2·7+2·3+2·1+2=239$

Thus there are 239 ternary strings of length 6 that do not contain two consecutive $0\text{'}s$ or two consecutive $1\text{'}s$.

## Recommended explanations on Math Textbooks

94% of StudySmarter users get better grades.