[SOLVED] COMP9020-Set 7 Counting

Description

1. (Inclusion-Exclusion)

Let S = {a,b,c,d} and T = {e,f,g}.

1. How many different relations on S × S are there?
2. How many different antireflexive relations on S × S are there?
3. How many different functions f : S ⟶ T are there?
4. How many different onto functions f : S ⟶ T are there?

2. (Combinations)

A management panel at a hospital needs to include at least one member from each of the following three professions: a doctor, a lawyer and an accountant. How many different panels can be formed in each of the following situations?

3. Each profession offers 5 possible candidates. The panel size is 3.
4. Each profession offers 4 possible candidates, but A. Brent (doctor) refuses to serve with C. David (lawyer). The panel size is 3.
5. Each profession offers 5 possible candidates. The panel size is 5.
6. Each profession offers 4 possible candidates, but A. Brent (doctor) refuses to serve with C. David (lawyer). The panel size is 5.

3. (Sequences)

How many sequences of 10 coin flips have at most 3 heads?

4. (Advanced Counting)

How many 5-letter words over the alphabet Σ = {a, c, e, n, s}

1. include the substring ace?
2. include all letters from Σ with a before e (for example, canes)?
3. have all their letters in alphabetical order (for example, aceen)? [show answer]

5. Challenge Exercise

In a movie theatre, 4 couples are sitting in one row with men and women alternating. If no couple is sitting together, how many arrangements are possible?