In each situation, write a recurrence relation, including base case(s), that des

Question

In each situation, write a recurrence relation, including base case(s), that describes the recursive structure of the problem. You do not need to solve the recurrence. Let B(n) be the number of length n bit sequences that have no three consecutive 0s (i.e., do not contain the substring "000"). Write a recurrence for B(n). Let S(n) be the number of subsets of {1, 2, ..., n} having the following property: no two elements in the subset are consecutive integers. The empty set with no elements should be included in your count. Write a recurrence for S(n). Say you are tiling a 2 times n rectangle with L-shaped tiles of area 3 (trominoes). To tile the rectangle is to cover it with tiles so that no tiles overlap and every cell is covered by some tile. Let T(n) denote the number of ways to tile the rectangle. Write a recurrence for T(n). A ternary string is like a binary string except it uses three symbols, 0, 1, and 2. For example, 12210021 is a ternary string of length 8. Let T(n) be the number of ternary strings of length n with the property that there is never a 2 appearing anywhere after a 0. For example, 12120110 has this property but 10120012 does not. Write a recurrence for T(n).

Explanation / Answer

a) B(n) be the number of length n bit sequences that have no three consecutives 0s(i.e., do not contain the substring “000”)

Any bit string that has no 000 must have a 1 in atleast one of the 1st three positions. The n we will break up all bit strings by avoiding 000 by when the first 1 occurs. i.e., each bit string of length n avoiding 000 falls into exactly any one of these cases:

Therefore, the recurrence is

B(n)=B(n-1)+ B(n-2)+ B(n-3), with B(0)=1, B(1)=2, B(2)=4

Or

B(n)=B(n-1)+ B(n-2)+ B(n-3), with B(1)=2, B(2)=4, B(3)=7

b) Let S(n)={1,2,3,…,n}. We say that a subset A of S(n) is good if A does not contain any two consecutive integers.

For any k, let a(k) be the number of good subsets of S(k).

There are two types of good subsets of S(n).

Type 1 good subsets of S(n) contain the element n,

Type 2 good subsets of S(n) do not contain n.

We first get an expression for the number of Type 1 good subsets of S(n) , where n2.Such a subset cannot contain n-1. So any Type 1 good subset of S(n)  is obtainable by adding n to a good subset of S(n-2) . Also, if we add n to a good subset of S(n-2) , we always obtain a Type 1 good subset of S(n) So there are exactly as many good Type 1 subsets of S(n) as there are good subsets of S(n-2) . By definition there are a(n-2) good subsets of S(n-2) .

A good subset of S(n)  is either of Type 1 or of Type 2. So the number of good subsets of S(n)  is a(n-2)+a(n-1)

We have therefore shown that a(n) = a(n-2)+a(n-1)

c)

In this firstly see that if n is not a multiple of 3, then there will be no way to tile the rectangle. And if n is a multiple of 3, then there are two ways to tile the 1st three coloumns:

The rest of the tilling is a tilling of a 2x(n-3) rectangle of which there are T(n-3).

Therefore the recurrence is

T(n )= {2T(n-3), with T(0)=1     if n=0(mod 3)   or 0 else

We could use the base case T(3)=2

So, the following recurrence can be aslo equivalent to T(n)= 2T(n-3), with T(0)=1, T(1)=0,T(2)=0

Or

T(n)= 2T(n-3), with T(1)=0, T(2)=0,T(3)=2

d)A ternary string is a sequence of digits, where each digit is either 0,1,or 2.

Here according to the problem in example, we cannot have 2 anywhere after a 0, and the dot represents a binary string, i.e. a string of length(n-1) with the property that we cannot use 2 anywhere after the use of 0.

For the base case we have to note that any ternary string of length 1 satisfies the required property. Hence the recurrence is

T(1)=3

T(n)=2T(n-1)+2^(n-1)

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---