Question

Let A = {a, b, c, d}.

a. Calculate the number of subsets of A.
b. Calculate the number of permutations of A.
c. Calculate the number of permutations of A which have no fixed points.
d. Calculate the number of functions from A to A

Answer 1

Answer:

a. 16

b. 24

c.  9

d. 256

Step-by-step explanation:

Let cardinality of the set A $(=|A|) = n$.

Any subset of A can contain i elements. $i = 0,1,\ldots,n$

Now these i elements can be chosen in $\binom{n}{i}$ ways. So the number of subsets can be written as,

$\binom{n}{0} + \binom{n}{1} + \dotsc + \binom{n}{n} = 2^n$

a. Here we have n = 4. So the Total no. of subsets = $2^4 = 16$.

b. The no. of permutations is n! for any set with cardinality n. So, here it is = 4! = 24

c. Let $A_i$ denote the set consisting of all permutations of A where i is fixed, $i = 1,\dotsc,4$. Using symmetry, $|A_i| = 3!$(fix one element and permute the rest) is the same $\forall \; i =1,2,3,4$. Also $|A_i \cap A_j| = 2!$ (fix 2 elements and permute the rest).

By similar arguments, $|A_i \cap A_j \cap A_k| = 1$ and $|\bigcap_{i} A_i| = 1$.

Recall the Principle of inclusion exclusion,

$|A_1 \cup A_2 \cup \dotsc A_n| = \sum_{i=1}^n |A_i| + \sum_{i < j} |A_i \cap A_j| +  \dotsc + (-1)^{n+1} |\cap_{i}A_i|$

Note that $\cup_{i=1}^4 A_i = S$ is the set containing permutations with at least one fixed point. So we require 4! - S.

Computing S.

$S = \binom{4}{1} 3! - \binom{4}{2} 2! + \binom{4}{3} 1 - \binom{4}{4} 1 = 15$

Required answer is 4! - S = 24 - 15 = 9

d. In general the no.  of functions from A (|A| = n) to B (|B| = m) is given by, $m^n$. Any element of A can be assigned to any of the m elements in B, so the possibilities are $m \times m \times \dotsc n\; times \; = m^n$.

Here m = n = 4. So the answer is $4^4 = 256$.