Let T(n) be the set of all strings of 1\'s and 2\'s that add up to n. For exampl

Question

Let T(n) be the set of all strings of 1's and 2's that add up to n. For example 21221 epsilon T(8) because it is a string of 1's and 2's that add up to 8. Show that |T (0)| = 1 and |T(1)| = 1 and by using a combinatorial argument, show that |T(n)| = |T (n - 1)| + |T(n - 2)|. (This shows that |T(n)| is the nth Fibonacci number!) List all 13 elements of T(6) in lexicographic ordering, labeling them from 0 to 12. (Notice that all strings that start with 1 occur before all strings that start with 2.) If we list all elements of T(n) in lexicographic ordering, then all the strings that start with 1 will be in positions before |T(n - 1)| and all strings that start with 2 will be in positions at or after |T(n - 1)|. Consider the following encoding algorithm that uses this fact: procedure LexEncode (s_1 s_2 ellipsis s_k, n) (s_1 s_2 ellipsis s_k is a sequence of 1's and 2's that add up to n.) if n == 0: return 0 if s_1 == 1: return LexEncode(s_2, ellipsis, s_k, n - 1) if s_1 == 2 return F_n-1 + LexEncode (s_2, ellipsis, s_k, n - 2) Where F_n is the nth Fibonacci number: F_0 = 1, F_1 = 1, F_2 = 2, F_3 =3, F_4 = 5, F_5 = 8, F_6 = 13, F_7 = 21, F_8 = 34, F_9 = 55, F_10 = 89, ellipsis Use this encoding algorithm to compute LexEncode(1221212, 11).

Explanation / Answer

(a) The only element in T(0) is {}. Therefore T(0) = 1.

The only element in T(1) is {1}. Therefore T(1) = 1.

T(n) is a set that can be formed in two ways:

1. The ones that begin with 2. Excluding the leading two, there are |T(n-2)| elements.

2. The ones that begin with 1. Excluding the leading two, there are |T(n-1)| elements.

The number of elements in case 1 = |T(n-2)|

The number of elements in case 2 = |T(n-1)|

=> |T(n)| = |T(n-1)| + |T(n-2)|

(b) The lexicographic orderings of T(6) are:

0 : 111111

1: 11112

2: 11121

3: 11211

4: 1122

5: 12111

6: 1212

7: 1221

8: 21111

9: 2112

10: 2121

11: 2211

12: 222

(c) Using LexEncode recursively,

LexEncode(1221212,11)

s1 = 1

=> Lexcode (221212,10)

s1 = 2

=> F9 + Lexcode (21212,8)

s1 = 2

=> F9 + F7 + Lexcode (1212,6)

s1 = 1

=> F9 + F7 + Lexcode (212,5)

s1 = 2

=> F9 + F7 + F4 + Lexcode (12,3)

s1 = 1

=> F9 + F7 + F4 + Lexcode (2,2)

s1 = 2

=> F9 + F7 + F4 + F1 + Lexcode (0,0)

n = 0 and stop.

So the final result is F9 + F7 + F4 + F1

= 55 + 21 + 5 + 1

= 82

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.