Binary Relations Counting

214 Views Asked by At

Are these answers correct? I'm having a little trouble with $d$. and $e$.

Set $S$ has $n$ elements.

($a$) How many elements are there in $S \cdot S$? $n^2$

($b$) How many binary relations are there on $S$? $2^{n^2}$

($c$) How many binary relations on $S$ are not reflexive? $2{n^2} - 2^{n^2 - n}$

($d$) How many binary relations on $S$ are functions? $n \cdot 2^n$

($e$) How many reflexive binary relations on $S$ are functions? $1$

1

There are 1 best solutions below

1
On

(d) Every function on $S$ has a domain that is a subset of $S$: let's say a given domain has size $k$. Then for each member of the domain we choose another member of $S$ as its image under the function. That means $n^k$ possible choices for that domain. The number of domains of size $k$ is of course ${n \choose k}$. So the total number of functions is

$$\sum_{k=0}^n{n\choose k}n^k=\sum_{k=0}^n{n\choose k}n^k1^{n-k}=(n+1)^n$$

(e) Again, for the function on $S$ we choose a domain that is a subset of $S$. Then the image of a member of the domain is itself, so we have only $1$ choice for that domain. That makes the total number of reflexive binary relations that are also functions the same as the number of possible domains, which is

$$2^n$$

Of course, these answers all include the empty relation and the empty function. Be sure that is what you want.