# Counting Onto Functions with Different Sets

• mr_coffee
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.
mr_coffee
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!

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.

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.

As for the second one, try to interpret the multiplication: 4*2+3*2=14

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!

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

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.

Thanks for the help guys!

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

• 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