How many relations R are there on a set such that at least one ordered pair in R has a(a particular element) as its first element?

Question

I don't know what to do with this question...spacially the part that says "at least"... I know that the number of possible relations on a set with n elements is: 2^(n^2) Can anyone tell me how can I answer this problem? Thank you so much!

Answer 1

The number of times "at least one" thing occurs, is: The total number of possible cases (where the thing may or may not occur any number of times) minus the number of times the thing never occurs. What's left is the number of times the thing occurs at least once. SO... The number of all relations minus the number of relations where there are no ordered pairs starting with $a$ = the number of relations where there is at least one such ordered pair.

......

If the set has $n$ elements and $a \in$ the set:

There are $n\times n=n^2$ ordered pairs $1\times n=n$ of them have have $a$ as their first element and $(n-1)\times n = n(n-1)$ of them do not have $a$ as their first elements.

......

So the number of relations where any ordered pair may or may not occur is $2^{n^2}$.

And the number of relations where any ordered pair $(a,x)$ can never occur is $2^{n(n-1)}$.

And the number of relations where an ordered pair $(a,x)$ must occur at least once is:

$2^{n^2} - 2^{n(n-1)}$.

That's it.

Answer 2

Let $A$ be a set with $n$ elements. You already know that there are $2^{n^2}$ possible relations on $A$. Now fix a particular $a\in A$. Instead of trying to count directly the relations on $A$ that do contain one or more ordered pairs with $a$ as first element, try counting the relations that do not contain such an ordered pair. That is, you want to calculate the number of relations $R\subseteq A\times A$ such that for each $x\in A$, the ordered pair $\langle a,x\rangle$ is not in $R$.

HINT: This says that $R\cap(\{a\}\times A)=\varnothing$, i.e., that $R\subseteq(A\setminus\{a\})\times A$.

Answer 3

If we take the matrix representation of a relation $R$, the relations where $(a,x)$ is not in $R$ for any $x$ and the specified element $a$ are those with the row corresponding to $a$ completely blank. This still leaves $n^2-n$ cells to be filled as we please. So the number of relations satisfying the given conditions is the complement, or $2^{n^2}-2^{n^2-n}=2^{n^2-n}(2^n-1)$.