# Question regarding counting in discrete mathematics

1. Apr 9, 2015

### KevinD6

1. The problem statement, all variables and given/known data
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?
2. Relevant equations

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

2. Apr 9, 2015

### Delta²

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.

3. Apr 9, 2015

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

4. Apr 10, 2015

### Delta²

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?

5. Apr 10, 2015

### Delta²

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

6. Apr 10, 2015

### haruspex

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

7. Apr 10, 2015

### Delta²

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

8. Apr 11, 2015

### haruspex

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