Assignment 5 Solution

Q.1 Suppose that n    1 is an integer.

    (a) How many functions are there from the set f1; 2; : : : ; ng to the set f1; 2; 3g?
    (b) How many of the functions in part (a) are one-to-one functions?

    (c) How many of the functions in part (a) are onto functions?


Q.2 How many functions are there from the set f1; 2; : : : ; ng, where n is a positive integer, to the set f0; 1g
    (a) that are one-to-one?

    (b) that assign 0 to both 1 and n?

    (c) that assign 1 to exactly one of the positive integers less than n?


Q.3 Suppose that p and q are prime numbers and that n = pq. Use the principle of inclusion-exclusion to nd the number of positive integers not exceeding n that are relatively prime to n, i.e., the Euler function (n).

Q.4 How many bit strings of length 6 have at least one of the following properties:

start with 010 start with 11 end with 00

State clearly how you count and get your answer.

Q.5

Consider all permutations of the letters A; B; C; D; E; F; G.


1





    (a) How many of these permutations contains the strings ABC and DE (each as consecutive substring)?

    (b) In how many permutations does A precede B? (not necessary imme-diately)


Q.6 Alice is going to choose a selection of 12 chocolates. There are 25 di erent brands of them and she can have as many as she wants of each brand (but can only choose 12 pieces). How many ways can she make this selection?

Q.7 16 points arepchosen inside a 5 3 rectangle. Prove that two of these points lie within 2 of each other.


Q.8 Let (xi; yi), i = 1; 2; 3; 4; 5, be a set of ve distinct points with integer coordinates in the xy plane. Show that the midpoint of the line joining at least one pair of these points has integers coordinates.

Q.9 Prove that at a party where there are at least two people, there are two people who know the same number of other people there.

Q.10 Show that
pif p is a prime and k is an integer such that 1   k   p  1,
then p divides
k  .







Q.11 Prove the hockeystick identity





r

k

=

+ r


k=0








X

n + k


n
r + 1










whenever n and r are positive integers,

    (a) using a combinatorial argument

    (b) using Pascal’s identity.


Q.12

Solve the recurrence relation

an = 2an  1 + an  2    2an  3

2





with initial conditions a0 = 1, a1 = 0, and a2 = 7.

Q.13 Solve the recurrence relation

an = 4an  2;

with initial conditions a0 = 3, a1 = 2.

Q.14

    (a) Find all solutions of the recurrence relation an = 2an  1 + 2n2.

    (b) Find the solution of the recurrence relation in part (a) with initial condition a1 = 4.


Q.15

Use generating functions to prove Pascal’s identity:  C(n; r) = C(n

1; r) + C(n    1; r    1) when n and r are positive integers with r < n. [Hint:
Use the identity (1 + x)n = (1 + x)n  1 + x(1 + x)n  1.]

Q.16 How many relations are there on a set with n elements that are

    (a) symmetric?

    (b) antisymmetric?

    (c) irre exive?

    (d) re exive and symmetric?

    (e) neither re exive nor irre exive?


Q.17 Suppose that the relation R is symmetric. Show that R is symmetric.

Q.18 Suppose that the relation R is irre exive. Is the relation R2 necessarily irre exive?

Q.19 Let R be the relation on the set of ordered pairs of positive integers such that ((a; b); (c; d)) 2 R if and only if ad = bc. Show that R is an equivalence relation.

3