Counting Onto Functions with Different Sets

  • Thread starter mr_coffee
  • Start date
  • Tags
    Functions
In summary, the conversation discusses the process of determining the number of onto functions from a set with four elements to a set with three elements. It involves breaking down the problem into smaller subsets and using the multiplication rule to determine the total number of functions. The final answer is 36.
  • #1
mr_coffee
1,629
1
Hello everyone.

The question is:
How many onto functions are there from a set with four elements to a set with threee elements?

If i let x = {a,b,c,d,}
y = {x,y,z}

Step 1: construct an onto function from {a,b,c} to {x,y,z}
step 2:
choose whether to send d to x or to y or to z. I directly found there are 9 ways to perorm step 1, and 3 ways to perform step 2. Thus by the multiplication rule (9)(2) = 18 ways to define functions in the first category. But the book did a similar example and then ended up adding an additional 2 to their answer after doing the multiplication rule. So would it be 18 + 2 = 20?

The question in the book was the following:
How many onto functions are there from a set with 4 elements to a set with 2 elements?
they got an answer of 14 orginally 12 then added 2 more at the end for some reason.
THanks!
 
Physics news on Phys.org
  • #2
You can't just add 2 for no reason. Unless you know why the book did it, why would you do it? Also, there's a problem with your answer, because you are only counting the functions where d maps to the same thing that something else maps to. Of course, there will alyaws be 2, and only 2, elements of x which map to the same thing, but d doesn't always have to be one of those element.
 
  • #3
It is better, I think, to first determine the number of distinct 2-subsets that must map to the same element. This is seen to be 3+2+1=6 subsets.
Now, for each such subset there will exist 3*2*1=6 onto functions, since the subset itself may map onto 3 different numbers, and so on.
Thus, there should exist 6*6=36 such onto functions in total.
 
  • #4
As for the second one, try to interpret the multiplication: 4*2+3*2=14
 
  • #5
thanks for the responces guys, arildno, im' going to try to see if I understand exactly what you ment to fully get the problem... when you said:
It is better, I think, to first determine the number of distinct 2-subsets that must map to the same element. This is seen to be 3+2+1=6 subsets.
Are you saying break the domain down into the following subsets:
x = {a,b,c,d,}
y = {x,y,z}

x = { {a,b},{b,c},{c,d},{a,d},{b,d}, {c,a} }
I think I got al the possible combinations, but what made you choose groups of 2?
Also can you tell me your thought process when you borke it down into 3 + 2 + 1 = 6, rather than writing out all the possible combinations like i did?

Thanks again!
 
  • #6
Your book probably does it with inclusion and exclusion. First you count how many functions in total there are (3^4). Then you subtract the number of functions that do not map to each of the 3 elements (2^4 * 3). But this subtracts too much, so you add the number of functions that do not map to two of the 3 elements (1^4 * 3) and then this might have added too much so you subtract the number of functions that do not map to any of the 3 elements (0). So the answer is 3^4 - 3 * 2^4 + 3 = 36
 
  • #7
I chose groups of two, since necessarily, two elements will map to the same element in the value domain.
Each such two-group defines a set of functions distinct from the other two-group's sets of functions.
As for 3+2+1=6,
note that a will be present in 3 groups, b will be in two groups not including a, and c and d may form a two-group as well.
 
  • #8
Thanks for the help guys!
 

Related to Counting Onto Functions with Different Sets

1. What is a function in computer programming?

A function in computer programming is a block of code that performs a specific task. It is used to organize and modularize code, making it easier to read, reuse, and maintain.

2. What is the syntax for creating a function in most programming languages?

The syntax for creating a function in most programming languages includes the function keyword, followed by the function name, a set of parentheses, and curly braces that contain the code to be executed.

3. What is the difference between parameters and arguments in a function?

Parameters are the variables defined in a function's declaration, while arguments are the actual values passed into the function when it is called.

4. How can I return a value from a function?

To return a value from a function, you can use the return keyword followed by the value you want to return. This value can then be assigned to a variable or used in other parts of your code.

5. Can a function call another function?

Yes, a function can call another function. This is known as function composition, where the output of one function becomes the input for another function.

Similar threads

  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
555
  • Calculus and Beyond Homework Help
Replies
12
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
240
  • Calculus and Beyond Homework Help
Replies
8
Views
543
  • Calculus and Beyond Homework Help
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
561
  • Calculus and Beyond Homework Help
Replies
7
Views
410
  • Calculus and Beyond Homework Help
Replies
3
Views
851
Back
Top