# Question regarding counting in discrete mathematics

## Homework Statement

Let A = {1, 2, 3, 4} and let F be the set of all functions from A to A. Let R be the relation on F defined by:

For all functions f, g that are elements of F, (f, g) are only elements of R if and only if f(i) = g(i) for some i that is an element of A.

Let the functions α, β be elements of F, defined by α(i) = 1 and β(i) = 2, where i is an element of A.

a) How many functions f that are elements of F are there so that (f, α) is an element of R?
b) How many functions f that are elements of F are there so that (f, α) or (f, β) is an element of R?
c) How many functions f that are elements of F are there so that (f, α) and (f, β) is an element of R?

## The Attempt at a Solution

The one I'm having the most trouble with is b), but I use some numbers from part a so I just wanted to double check that.

To solve a, all I did was take the total number of functions from set A to A, which is 4^4 (each element has four choices as an output), and subtract that by the number of functions that do not output A, so 3^4. I get 175 functions that have some f(i) = 1.

For part B, so far I have figured out that I need to use the union equation that is used in statistics:
P(A U B) = P(A) + P(B) - P(AB)
However, I'm missing some method to solve for P(AB). So far, I have P(A U B) = 175 * 2 - P(AB), since the number of functions that output 1 is the same as the number of functions that output 2. Any assistance would be greatly appreciated. Thank you in advance.

Also, I solved part c by subtracting the number of functions that don't output 1 or 2 from the number of total functions, so 4^4 - 2^4 (since all four inputs can't map to 1 or 2, they can only map to 3 or 4).

Related Precalculus Mathematics Homework Help News on Phys.org
Delta2
Homework Helper
Gold Member
if i understand this correctly, it is a(i)=1 for every i and b(i)=2 for every i also. So there can be none functions that satisfy both conditions so P(AB)=0.

Hmm, that's what I thought at first too, but it seems that I was misinterpreting it the first time, I think it's saying how many ways can f(i) have some mapping to 1 and two, for example, f(1) = 1 and f(2) = 2, f(3) and f(4) can be whatever, but when I used that number, it didn't work. If I use 0 in my P(A U B) equation, it comes out as 350, which is more than my total amount of functions, which also doesn't make sense.

So yeah, my answer for c) is also wrong.

Delta2
Homework Helper
Gold Member
Ok i see so for B) you have to find the functions that have at least one 1 and at least one 2 as output which will be P(AB). 2^4 is the number of functions that dont have neither 1 neither 2 as output so it should be P(AB)=4^4-2^4?

Delta2
Homework Helper
Gold Member
Ok well this is very confusing (darn). After some overall thinking i think the answer to b) is actually 4^4-2^4 (because P(A∪B)=4^4-P(not (A∪B)) and P(not (A∪B))=P((notA)∩(notB)) by Demoivre's identity.

So the answer to c) is afterall P(A∩B)=P(A)+P(B)-P(A∪B)=...

haruspex
Homework Helper
Gold Member
2020 Award
Ok i see so for B) you have to find the functions that have at least one 1 and at least one 2 as output which will be P(AB). 2^4 is the number of functions that dont have neither 1 neither 2 as output so it should be P(AB)=4^4-2^4?

I think you mean "at least one 1 or at least one 2", but I agree with 44-24.
c is the "and" case.

Delta2
Homework Helper
Gold Member
I think you mean "at least one 1 or at least one 2", but I agree with 44-24.
c is the "and" case.
So you agree that the answer for b) is P(A∪B)=4^4-2^4. ?

haruspex