Question regarding counting in discrete mathematics

  • Thread starter KevinD6
  • Start date
  • #1
10
0

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

Answers and Replies

  • #2
Delta2
Homework Helper
Insights Author
Gold Member
3,540
1,364
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
10
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.
 
  • #4
Delta2
Homework Helper
Insights Author
Gold Member
3,540
1,364
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?

Your answer for c seems correct to me, it is P(A∩B)=P(AB)
 
  • #5
Delta2
Homework Helper
Insights Author
Gold Member
3,540
1,364
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
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
35,253
6,317
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?

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 44-24.
c is the "and" case.
 
  • #7
Delta2
Homework Helper
Insights Author
Gold Member
3,540
1,364
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. ?
 
  • #8
haruspex
Science Advisor
Homework Helper
Insights Author
Gold Member
2020 Award
35,253
6,317
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.
 

Related Threads on Question regarding counting in discrete mathematics

Replies
3
Views
2K
  • Last Post
Replies
2
Views
1K
Replies
9
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
1
Views
1K
Replies
1
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
2
Views
9K
Replies
4
Views
2K
Replies
10
Views
2K
Top