Let ${C}_{n}$ be the number of sequences with a length of n, which their elements belong to {0,1,2}, and they don't contain the following sequences: 11,21. Find a recursion formula with starting conditions for ${C}_{n}$.

MMDCCC50m
2022-11-05
Answered

Find a recursion formula for combinatorial problem

Let ${C}_{n}$ be the number of sequences with a length of n, which their elements belong to {0,1,2}, and they don't contain the following sequences: 11,21. Find a recursion formula with starting conditions for ${C}_{n}$.

Let ${C}_{n}$ be the number of sequences with a length of n, which their elements belong to {0,1,2}, and they don't contain the following sequences: 11,21. Find a recursion formula with starting conditions for ${C}_{n}$.

You can still ask an expert for help

Aliya Moore

Answered 2022-11-06
Author has **17** answers

Step 1

If the last digit is a 0 or a 2, any sequence of length $n-1$ works before that, and if the last digit is a 1, the rest of the sequence has to end in a 0, which in turn means that the first $n-2$ digits have to form an arbitrary valid sequence. From there we immediately arrive at the recursive formula ${C}_{n}=2{C}_{n-1}+{C}_{n-2}$.

Now as promised the more complicated approach considering the first digit: Let ${x}_{n}^{(k)}$ denote the number of sequences of length n that start with the digit k, obviously we have ${C}_{n}={x}_{n}^{(0)}+{x}_{n}^{(1)}+{x}_{n}^{(2)}$. Let's find recursive formulas for the ${x}_{n}^{(k)}$. For $k=0$, we have

$${x}_{n}^{(0)}={x}_{n-1}^{(0)}+{x}_{n-1}^{(1)}+{x}_{n-1}^{(2)}={C}_{n-1}$$

since a 0 can be added to every sequence of length $n-1$. For $k=1$ and $k=2$, the rest of the sequence may not start with a 1, so we have

$${x}_{n}^{(1)}={x}_{n}^{(2)}={x}_{n-1}^{(0)}+{x}_{n-1}^{(2)}.$$

Step 2

Now we put this together and calculate a formula for ${C}_{n}$:

$$\begin{array}{rl}{C}_{n}& ={x}_{n}^{(0)}+{x}_{n}^{(1)}+{x}_{n}^{(2)}={C}_{n-1}+2({x}_{n-1}^{(0)}+{x}_{n-1}^{(2)})\\ & ={C}_{n-1}+{x}_{n-2}^{(0)}+{x}_{n-2}^{(1)}+{x}_{n-2}^{(2)}+{x}_{n-1}^{(0)}+2{x}_{n-1}^{(2)}\\ & ={C}_{n-1}+{x}_{n-1}^{(1)}+{x}_{n-2}^{(1)}+{x}_{n-1}^{(0)}+{x}_{n-1}^{(2)}+{x}_{n-1}^{(2)}\\ & =2{C}_{n-1}+{x}_{n-2}^{(1)}+{x}_{n-2}^{(0)}+{x}_{n-2}^{(2)}\\ & =2{C}_{n-1}+{C}_{n-2}.\end{array}$$

If the last digit is a 0 or a 2, any sequence of length $n-1$ works before that, and if the last digit is a 1, the rest of the sequence has to end in a 0, which in turn means that the first $n-2$ digits have to form an arbitrary valid sequence. From there we immediately arrive at the recursive formula ${C}_{n}=2{C}_{n-1}+{C}_{n-2}$.

Now as promised the more complicated approach considering the first digit: Let ${x}_{n}^{(k)}$ denote the number of sequences of length n that start with the digit k, obviously we have ${C}_{n}={x}_{n}^{(0)}+{x}_{n}^{(1)}+{x}_{n}^{(2)}$. Let's find recursive formulas for the ${x}_{n}^{(k)}$. For $k=0$, we have

$${x}_{n}^{(0)}={x}_{n-1}^{(0)}+{x}_{n-1}^{(1)}+{x}_{n-1}^{(2)}={C}_{n-1}$$

since a 0 can be added to every sequence of length $n-1$. For $k=1$ and $k=2$, the rest of the sequence may not start with a 1, so we have

$${x}_{n}^{(1)}={x}_{n}^{(2)}={x}_{n-1}^{(0)}+{x}_{n-1}^{(2)}.$$

Step 2

Now we put this together and calculate a formula for ${C}_{n}$:

$$\begin{array}{rl}{C}_{n}& ={x}_{n}^{(0)}+{x}_{n}^{(1)}+{x}_{n}^{(2)}={C}_{n-1}+2({x}_{n-1}^{(0)}+{x}_{n-1}^{(2)})\\ & ={C}_{n-1}+{x}_{n-2}^{(0)}+{x}_{n-2}^{(1)}+{x}_{n-2}^{(2)}+{x}_{n-1}^{(0)}+2{x}_{n-1}^{(2)}\\ & ={C}_{n-1}+{x}_{n-1}^{(1)}+{x}_{n-2}^{(1)}+{x}_{n-1}^{(0)}+{x}_{n-1}^{(2)}+{x}_{n-1}^{(2)}\\ & =2{C}_{n-1}+{x}_{n-2}^{(1)}+{x}_{n-2}^{(0)}+{x}_{n-2}^{(2)}\\ & =2{C}_{n-1}+{C}_{n-2}.\end{array}$$

asked 2021-07-28

Let A, B, and C be sets. Show that

asked 2020-11-09

Use proof by Contradiction to prove that the sum of an irrational number and a rational number is irrational.

asked 2021-08-18

Discrete Mathematics Basics

1) Find out if the relation R is transitive, symmetric, antisymmetric, or reflexive on the set of all web pages.where $(a,b)\in R$ if and only if

I)Web page a has been accessed by everyone who has also accessed Web page b.

II) Both Web page a and Web page b lack any shared links.

III) Web pages a and b both have at least one shared link.

asked 2021-08-02

Suppose that A is the set of sophomores at your school and B is the set of students taking discrete mathematics at your school. Express each of these sets in terms of A and B.

a) the set of sophomores taking discrete mathematics in your school

b) the set of sophomores at your school who are not taking discrete mathematics

c) the set of students at your school who either are sophomores or are taking discrete mathematics

Use these symbols: $\cap \cup$

asked 2021-08-06

Let R be a relation on Z defined by (x.y) $\in$ R if and only if 5(x-y)=0. Formally state what it means for R to be a symmetric relation. Is R an equivalence relation? If so, prove it discrete math and if not, explain why it is not.

asked 2022-09-04

Finding the intersection of $A\times B$ and $B\times A$

Let $A=\{x,3\}$ and $B=\{y,3,z\}$. List all of the elements in the set $(A\times B)\cap (B\times A)$.

Is the Cartesian product of the two sets listed above a set of 2-ordered tuples? And the intersection is just the elements that $A\times B$ has in common with $B\times A$? That is,

$$\begin{array}{rl}A\times B& =\{x,3\}\times \{y,3,z\}=\{(x,y),(x,3),(x,z),(3,y),(3,3),(3,z)\}\\ B\times A& =\{y,3,z\}\times \{x,3\}=\{(y,x),(y,3),(3,x),(3,3),(z,x),(z,3)\}\end{array}$$

giving $(A\times B)\cap (B\times A)=\{(3,3)\}$

Is there some higher order of precedence? And I assume order matters, right?

Let $A=\{x,3\}$ and $B=\{y,3,z\}$. List all of the elements in the set $(A\times B)\cap (B\times A)$.

Is the Cartesian product of the two sets listed above a set of 2-ordered tuples? And the intersection is just the elements that $A\times B$ has in common with $B\times A$? That is,

$$\begin{array}{rl}A\times B& =\{x,3\}\times \{y,3,z\}=\{(x,y),(x,3),(x,z),(3,y),(3,3),(3,z)\}\\ B\times A& =\{y,3,z\}\times \{x,3\}=\{(y,x),(y,3),(3,x),(3,3),(z,x),(z,3)\}\end{array}$$

giving $(A\times B)\cap (B\times A)=\{(3,3)\}$

Is there some higher order of precedence? And I assume order matters, right?

asked 2022-06-22

All possible multi sets out of a 3 element set

We want to know how many possible multi sets can be formed from a set that has only 3 elements.

My try:

If we look at the multiplicities we get:

$\mu ({a}_{1})=4\phantom{\rule{thickmathspace}{0ex}}\u27f9\phantom{\rule{thickmathspace}{0ex}}\mu ({a}_{2})=0\phantom{\rule{thickmathspace}{0ex}}\u27f9\phantom{\rule{thickmathspace}{0ex}}\mu ({a}_{3})=0$, we can do this 3 times. $\mu ({a}_{1})=3\phantom{\rule{thickmathspace}{0ex}}\u27f9\phantom{\rule{thickmathspace}{0ex}}\mu ({a}_{2})=1\phantom{\rule{thickmathspace}{0ex}}\u27f9\phantom{\rule{thickmathspace}{0ex}}\mu ({a}_{3})=0$ we can do this $2\cdot 3$ $2\cdot 3$ times.

However I know there is a faster way. So if we distinguish between the three elements, I guess we can't use ${x}_{1}+{x}_{2}+{x}_{3}=4$, with formula $(}\genfrac{}{}{0ex}{}{n+r-1}{r}{\textstyle )$.

Is it correct if I use stirling number here: S(4,3)

We want to know how many possible multi sets can be formed from a set that has only 3 elements.

My try:

If we look at the multiplicities we get:

$\mu ({a}_{1})=4\phantom{\rule{thickmathspace}{0ex}}\u27f9\phantom{\rule{thickmathspace}{0ex}}\mu ({a}_{2})=0\phantom{\rule{thickmathspace}{0ex}}\u27f9\phantom{\rule{thickmathspace}{0ex}}\mu ({a}_{3})=0$, we can do this 3 times. $\mu ({a}_{1})=3\phantom{\rule{thickmathspace}{0ex}}\u27f9\phantom{\rule{thickmathspace}{0ex}}\mu ({a}_{2})=1\phantom{\rule{thickmathspace}{0ex}}\u27f9\phantom{\rule{thickmathspace}{0ex}}\mu ({a}_{3})=0$ we can do this $2\cdot 3$ $2\cdot 3$ times.

However I know there is a faster way. So if we distinguish between the three elements, I guess we can't use ${x}_{1}+{x}_{2}+{x}_{3}=4$, with formula $(}\genfrac{}{}{0ex}{}{n+r-1}{r}{\textstyle )$.

Is it correct if I use stirling number here: S(4,3)