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.

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 .
You can still ask an expert for help

Want to know more about Discrete math?

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Answers (1)

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 :
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 .
Did you like this example?
Subscribe for all access

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

You might be interested in

asked 2021-07-28

Let A, B, and C be sets. Show that (AB)C=(AC)(BC)
image

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)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: 

asked 2021-08-06
Let R be a relation on Z defined by (x.y) 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 × B and B × A
Let A = { x , 3 } and B = { y , 3 , z } . List all of the elements in the set ( A × B ) ( B × 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 × B has in common with B × A? That is,
A × B = { x , 3 } × { y , 3 , z } = { ( x , y ) , ( x , 3 ) , ( x , z ) , ( 3 , y ) , ( 3 , 3 ) , ( 3 , z ) } B × A = { y , 3 , z } × { x , 3 } = { ( y , x ) , ( y , 3 ) , ( 3 , x ) , ( 3 , 3 ) , ( z , x ) , ( z , 3 ) }
giving ( A × B ) ( B × 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:
μ ( a 1 ) = 4 μ ( a 2 ) = 0 μ ( a 3 ) = 0, we can do this 3 times. μ ( a 1 ) = 3 μ ( a 2 ) = 1 μ ( a 3 ) = 0 we can do this 2 3 2 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 ( n + r 1 r ) .
Is it correct if I use stirling number here: S(4,3)

New questions

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question