1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question regarding counting in discrete mathematics

  1. Apr 9, 2015 #1
    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. jcsd
  3. Apr 9, 2015 #2
    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.
     
  4. Apr 9, 2015 #3
    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.
     
  5. Apr 10, 2015 #4
    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)
     
  6. Apr 10, 2015 #5
    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)=...
     
  7. Apr 10, 2015 #6

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    I think you mean "at least one 1 or at least one 2", but I agree with 44-24.
    c is the "and" case.
     
  8. Apr 10, 2015 #7
    So you agree that the answer for b) is P(A∪B)=4^4-2^4. ?
     
  9. Apr 11, 2015 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Yes. Rereading your post, maybe you meant that ("and") as a step on the way to the answer.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted