CS206 - DISCRETE MATHEMATICS II
Instructor: Chitoor V. Srinivasan
PROBLEM SET 0 SOLUTIONS
- A function defined over the range of inputs
, 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 =
. - 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) .
- Total number of subsets of a set with n elements =
.
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 =
=
. - 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.
- 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 =
. - 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 =
(since each proposition can be assigned one of the
two values, T or F.) . So, the function takes each of these
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
. - 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).
- Follows straight from one of the theorems in the Rosen book (the one
which deals with sequences of length
.) - Consider this assignment of friends and enemies. There are no 3 mutual
friends or enemies here.