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.
a) 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).
b) 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).
c) 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).
d) 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).

Answer 1

Explanation:

a) Given B(n) is the number of the length 'n' bit sequences which have no three consecutive 0s(i.e., they does not contain substring “000”)

Any bit string which has no 000 should have a 1 in at least one of the 1st three positions. Then, the n we will break all the bit strings by avoiding the 000 by when the 1st 1 occurs. i.e., each of the bit of string of the length of n will avoid 000 falls into the exactly any one of these cases:

1 is followed by the bit string of the length of (n-1) avoiding the 000.

01 is followed by some bit string of the length of (n-2) avoiding a 000.

001 which is followed by any bit string of the length(n-3) avoiding the 000.

Therefore, 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 the S(n)={1,2,3,…,n}. We will say that the subset A of S(n) is very good if A does not have any of the two integers that are consecutive.

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

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

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

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

We will first get an expression for a number of Type 1 of good subsets of the S(n) , where n≥2. This a subset does not contain n-1. So any Type 1 of the good subset of the S(n)  is obtainable when adding n to good subset of the S(n-2) . Also, on adding n to a good subset of the S(n-2) , we always get a Type 1 good subset of the S(n). Thus there are exactly as many good Type 1 of subsets of S(n) as there is good subsets of S(n-2) . By the definition there are a(n-2) good subsets of S(n-2) .

A good subset of a S(n)  is either Type 1 or Type 2. Thus the number of the 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). Here firstly see that if the n is not the multiple of a 3, then there will be no chance to tile the rectangle. And also if n is a multiple of a 3, then there may be two ways to tile the 1st three columns:

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

So, 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 may be defined as a sequence of some digits, where each digit has either 0,1,or 2.

According to the problem given, we do not have a 2 anywhere after  0, and the dot which represents the binary string of length(n-1) with the property which we cannot use 2 anywhere after we use the 0.

Now for base case,  we should note that any of the ternary string which has a length of 1 satisfies the given required property. Hence the recurrence is

T(1)=3

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