Question regarding counting in discrete mathematics

[KevinD6]

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?

Homework Equations

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).

 

[Delta2]

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.

 

[KevinD6]

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]

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 don't have neither 1 neither 2 as output so it should be P(AB)=4^4-2^4?

Your answer for c seems correct to me, it is P(A∩B)=P(AB)

 

[Delta2]

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]

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 don't have neither 1 neither 2 as output so it should be P(AB)=4^4-2^4?

Your answer for c seems correct to me, it is P(A∩B)=P(AB)

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

 

[Delta2]

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

So you agree that the answer for b) is P(A∪B)=4^4-2^4. ?

 

[haruspex]

So you agree that the answer for b) is P(A∪B)=4^4-2^4. ?

Yes. Rereading your post, maybe you meant that ("and") as a step on the way to the answer.