CS206 - DISCRETE MATHEMATICS II
Instructor: Chitoor V. Srinivasan
PROBLEM SET 0 SOLUTIONS

  1. A function defined over the range of inputs tex2html_wrap_inline22 , would take any input and map it to one of the possible two outputs. Thus for each input, it has two choices. Since it is going to map n inputs, the total number of different functions = tex2html_wrap_inline24 .
  2. We have to CHOOSE 2 numbers from the set 1, 2, ... n - 1, since the numbers have to be positive integers and less than n. Note that these numbers do not have to be greater than 1, that restriction only applies to n. Since these numbers are being chosen as a set, the order in which they are being chosen does not matter. Hence, number of ways of doing the above = C(n-1, 2) .

  3. Total number of subsets of a set with n elements = tex2html_wrap_inline28 . Since the number of subsets with odd number of elements = no. of subsets with even number of elements (accept this without proof), the number of subsets with odd cardinality = tex2html_wrap_inline30 = tex2html_wrap_inline32 .
  4. Seat one person at a fixed place first. The other n - 1 can be seated now in (n-1)! ways, and all the seating arrangements would be different.

  5. In the first place in any of these words, we can have 26 + 26 + 1 characters = 53 characters. In the other places, we can have 53 + 10 = 63 characters. The next observation is that having a variable at one place in a word does not preclude its occurence at any other place, that is, the characters can be repeated. Therefore, number of words = tex2html_wrap_inline44 .
  6. A truth table represents a function. So, the problem is to find out the number of different functions that take as its input a composition of the n different propositions and produces either T or F as output. With n propositions, the number of different compositions that can be constructed = tex2html_wrap_inline28 (since each proposition can be assigned one of the two values, T or F.) . So, the function takes each of these tex2html_wrap_inline28 compositions as its input, and produces either T or F as the output. By analogy to problem 1, the number of different functions is therefore tex2html_wrap_inline50 .

  7. There are two increasing subsequences of maximal length, (5 7 15 21) and (5 7 15 17). There are two decreasing subsequences of maximal length, (22 5 2 1) and (22 7 2 1).

  8. Follows straight from one of the theorems in the Rosen book (the one which deals with sequences of length tex2html_wrap_inline52 .)
  9. Consider this assignment of friends and enemies. There are no 3 mutual friends or enemies here.

    tabular14