Pigeonholes and onto functions
$begingroup$
I've been scratching my head at this problem for a while and can't seem to figure out why the number of pigeonholes is
$3^5 - C(3, 2)2^5 + C(3, 1)1^5$
and not
$3^5 - C(3, 2)2^5 - C(3, 1)1^5$
Could my profs answer key be wrong or is there something that I am missing. Because I believe that you have to subtract $3$ in the end since there is a case in which only $1$ is selected from the target as range.
combinatorics functions discrete-mathematics pigeonhole-principle
edited Dec 9 '18 at 23:28
N. F. Taussig
44k93355
asked Dec 9 '18 at 22:19
Arvin AnsariArvin Ansari
132
$endgroup$
add a comment |
$begingroup$
I've been scratching my head at this problem for a while and can't seem to figure out why the number of pigeonholes is
$3^5 - C(3, 2)2^5 + C(3, 1)1^5$
and not
$3^5 - C(3, 2)2^5 - C(3, 1)1^5$
Could my profs answer key be wrong or is there something that I am missing. Because I believe that you have to subtract $3$ in the end since there is a case in which only $1$ is selected from the target as range.
combinatorics functions discrete-mathematics pigeonhole-principle
edited Dec 9 '18 at 23:28
N. F. Taussig
44k93355
asked Dec 9 '18 at 22:19
Arvin AnsariArvin Ansari
132
$endgroup$
1
$begingroup$
Welcome to MathSE. It is better to type the question than post an image since images cannot be searched. This MathJax tutorial explains how to typeset mathematics on this site.
$endgroup$
– N. F. Taussig
Dec 9 '18 at 23:06
$begingroup$
Yeah sorry I tried posting the question instead but all the format changed and it got way too messy
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:12
$begingroup$
It's inclusion exclusion. $3^5$ is all the functions period. $C(3,2)2^5$ are then number of was where $a$ or $b$ or $c$ is excluded (at least one is exclude). But if we subtract the was $a$ can be exclude and then subtract the way $b$ can be excluded, we have subtracted the way$a$ and $b$ both excluded twice. So by inclusion/exclusion we must compensate after subtracting ways at least 1 is excluded, by adding ways at least 2 are excluded. And that is $C(3,1)1^5$.
$endgroup$
– fleablood
Dec 9 '18 at 23:19
$begingroup$
Yeah I get it now. I was just not taught the inclusion-exclusion principle so that's why i was confused.
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:26
add a comment |
$begingroup$
I've been scratching my head at this problem for a while and can't seem to figure out why the number of pigeonholes is
$3^5 - C(3, 2)2^5 + C(3, 1)1^5$
and not
$3^5 - C(3, 2)2^5 - C(3, 1)1^5$
Could my profs answer key be wrong or is there something that I am missing. Because I believe that you have to subtract $3$ in the end since there is a case in which only $1$ is selected from the target as range.
combinatorics functions discrete-mathematics pigeonhole-principle
edited Dec 9 '18 at 23:28
N. F. Taussig
44k93355
asked Dec 9 '18 at 22:19
Arvin AnsariArvin Ansari
132
$endgroup$
I've been scratching my head at this problem for a while and can't seem to figure out why the number of pigeonholes is
$3^5 - C(3, 2)2^5 + C(3, 1)1^5$
and not
$3^5 - C(3, 2)2^5 - C(3, 1)1^5$
Could my profs answer key be wrong or is there something that I am missing. Because I believe that you have to subtract $3$ in the end since there is a case in which only $1$ is selected from the target as range.
combinatorics functions discrete-mathematics pigeonhole-principle
combinatorics functions discrete-mathematics pigeonhole-principle
edited Dec 9 '18 at 23:28
N. F. Taussig
44k93355
asked Dec 9 '18 at 22:19
Arvin AnsariArvin Ansari
132
edited Dec 9 '18 at 23:28
N. F. Taussig
44k93355
asked Dec 9 '18 at 22:19
Arvin AnsariArvin Ansari
132
edited Dec 9 '18 at 23:28
N. F. Taussig
44k93355
edited Dec 9 '18 at 23:28
N. F. Taussig
44k93355
edited Dec 9 '18 at 23:28
N. F. Taussig
44k93355
44k93355
asked Dec 9 '18 at 22:19
Arvin AnsariArvin Ansari
132
asked Dec 9 '18 at 22:19
Arvin AnsariArvin Ansari
132
asked Dec 9 '18 at 22:19
Arvin AnsariArvin Ansari
132
132
1
$begingroup$
Welcome to MathSE. It is better to type the question than post an image since images cannot be searched. This MathJax tutorial explains how to typeset mathematics on this site.
$endgroup$
– N. F. Taussig
Dec 9 '18 at 23:06
$begingroup$
Yeah sorry I tried posting the question instead but all the format changed and it got way too messy
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:12
$begingroup$
It's inclusion exclusion. $3^5$ is all the functions period. $C(3,2)2^5$ are then number of was where $a$ or $b$ or $c$ is excluded (at least one is exclude). But if we subtract the was $a$ can be exclude and then subtract the way $b$ can be excluded, we have subtracted the way$a$ and $b$ both excluded twice. So by inclusion/exclusion we must compensate after subtracting ways at least 1 is excluded, by adding ways at least 2 are excluded. And that is $C(3,1)1^5$.
$endgroup$
– fleablood
Dec 9 '18 at 23:19
$begingroup$
Yeah I get it now. I was just not taught the inclusion-exclusion principle so that's why i was confused.
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:26
add a comment |
1
$begingroup$
Welcome to MathSE. It is better to type the question than post an image since images cannot be searched. This MathJax tutorial explains how to typeset mathematics on this site.
$endgroup$
– N. F. Taussig
Dec 9 '18 at 23:06
$begingroup$
Yeah sorry I tried posting the question instead but all the format changed and it got way too messy
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:12
$begingroup$
It's inclusion exclusion. $3^5$ is all the functions period. $C(3,2)2^5$ are then number of was where $a$ or $b$ or $c$ is excluded (at least one is exclude). But if we subtract the was $a$ can be exclude and then subtract the way $b$ can be excluded, we have subtracted the way$a$ and $b$ both excluded twice. So by inclusion/exclusion we must compensate after subtracting ways at least 1 is excluded, by adding ways at least 2 are excluded. And that is $C(3,1)1^5$.
$endgroup$
– fleablood
Dec 9 '18 at 23:19
$begingroup$
Yeah I get it now. I was just not taught the inclusion-exclusion principle so that's why i was confused.
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:26
1
1
$begingroup$
Welcome to MathSE. It is better to type the question than post an image since images cannot be searched. This MathJax tutorial explains how to typeset mathematics on this site.
$endgroup$
– N. F. Taussig
Dec 9 '18 at 23:06
$begingroup$
Welcome to MathSE. It is better to type the question than post an image since images cannot be searched. This MathJax tutorial explains how to typeset mathematics on this site.
$endgroup$
– N. F. Taussig
Dec 9 '18 at 23:06
$begingroup$
Yeah sorry I tried posting the question instead but all the format changed and it got way too messy
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:12
$begingroup$
Yeah sorry I tried posting the question instead but all the format changed and it got way too messy
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:12
$begingroup$
It's inclusion exclusion. $3^5$ is all the functions period. $C(3,2)2^5$ are then number of was where $a$ or $b$ or $c$ is excluded (at least one is exclude). But if we subtract the was $a$ can be exclude and then subtract the way $b$ can be excluded, we have subtracted the way$a$ and $b$ both excluded twice. So by inclusion/exclusion we must compensate after subtracting ways at least 1 is excluded, by adding ways at least 2 are excluded. And that is $C(3,1)1^5$.
$endgroup$
– fleablood
Dec 9 '18 at 23:19
$begingroup$
It's inclusion exclusion. $3^5$ is all the functions period. $C(3,2)2^5$ are then number of was where $a$ or $b$ or $c$ is excluded (at least one is exclude). But if we subtract the was $a$ can be exclude and then subtract the way $b$ can be excluded, we have subtracted the way$a$ and $b$ both excluded twice. So by inclusion/exclusion we must compensate after subtracting ways at least 1 is excluded, by adding ways at least 2 are excluded. And that is $C(3,1)1^5$.
$endgroup$
– fleablood
Dec 9 '18 at 23:19
$begingroup$
Yeah I get it now. I was just not taught the inclusion-exclusion principle so that's why i was confused.
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:26
$begingroup$
Yeah I get it now. I was just not taught the inclusion-exclusion principle so that's why i was confused.
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:26
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
We want to count the number of surjective (onto) functions from a set with five elements to a set with three elements.
If there were no restrictions, each of the five elements in the domain could be mapped to one of the three elements in the codomain, so there are $3^5$ possible functions. From these, we must exclude those with fewer than three elements in their range.
There are $binom{3}{1}$ ways to exclude an element of the codomain from the range and $2^5$ ways to map the five elements of the domain to the remaining elements in the codomain. Hence, there are $binom{3}{1}2^5$ functions that exclude an element of the codomain from the range.
However, if we subtract these functions from the total, we will have subtracted each function that excludes two elements of the codomain from the range twice, once for each way we could have designated one of those elements as the excluded element. We only want to subtract them once, so we must add them back.
There are $binom{3}{2}$ ways to exclude two elements of the codomain from the range and $1^5$ ways to map the five elements of the domain to the remaining element of the codomain. Hence, there are $binom{3}{2}1^5$ functions that exclude two elements of the codomain from the range.
Hence, by the Inclusion-Exclusion Principle, the number of surjective functions from a set with five elements to a set with three elements is
$$3^5 - binom{3}{1}2^5 + binom{3}{2}1^5$$
answered Dec 9 '18 at 23:01
N. F. TaussigN. F. Taussig
44k93355
$endgroup$
1
$begingroup$
Thanks a lot. It makes more sense now. I'll also keep in mind to format my question better next time.
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:15
1
$begingroup$
Can't upvote your answer since I have too little rep points but your answer is upvoted deep in my heart
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:16
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3033112%2fpigeonholes-and-onto-functions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
We want to count the number of surjective (onto) functions from a set with five elements to a set with three elements.
If there were no restrictions, each of the five elements in the domain could be mapped to one of the three elements in the codomain, so there are $3^5$ possible functions. From these, we must exclude those with fewer than three elements in their range.
There are $binom{3}{1}$ ways to exclude an element of the codomain from the range and $2^5$ ways to map the five elements of the domain to the remaining elements in the codomain. Hence, there are $binom{3}{1}2^5$ functions that exclude an element of the codomain from the range.
However, if we subtract these functions from the total, we will have subtracted each function that excludes two elements of the codomain from the range twice, once for each way we could have designated one of those elements as the excluded element. We only want to subtract them once, so we must add them back.
There are $binom{3}{2}$ ways to exclude two elements of the codomain from the range and $1^5$ ways to map the five elements of the domain to the remaining element of the codomain. Hence, there are $binom{3}{2}1^5$ functions that exclude two elements of the codomain from the range.
Hence, by the Inclusion-Exclusion Principle, the number of surjective functions from a set with five elements to a set with three elements is
$$3^5 - binom{3}{1}2^5 + binom{3}{2}1^5$$
answered Dec 9 '18 at 23:01
N. F. TaussigN. F. Taussig
44k93355
$endgroup$
1
$begingroup$
Thanks a lot. It makes more sense now. I'll also keep in mind to format my question better next time.
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:15
1
$begingroup$
Can't upvote your answer since I have too little rep points but your answer is upvoted deep in my heart
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:16
add a comment |
$begingroup$
We want to count the number of surjective (onto) functions from a set with five elements to a set with three elements.
If there were no restrictions, each of the five elements in the domain could be mapped to one of the three elements in the codomain, so there are $3^5$ possible functions. From these, we must exclude those with fewer than three elements in their range.
There are $binom{3}{1}$ ways to exclude an element of the codomain from the range and $2^5$ ways to map the five elements of the domain to the remaining elements in the codomain. Hence, there are $binom{3}{1}2^5$ functions that exclude an element of the codomain from the range.
However, if we subtract these functions from the total, we will have subtracted each function that excludes two elements of the codomain from the range twice, once for each way we could have designated one of those elements as the excluded element. We only want to subtract them once, so we must add them back.
There are $binom{3}{2}$ ways to exclude two elements of the codomain from the range and $1^5$ ways to map the five elements of the domain to the remaining element of the codomain. Hence, there are $binom{3}{2}1^5$ functions that exclude two elements of the codomain from the range.
Hence, by the Inclusion-Exclusion Principle, the number of surjective functions from a set with five elements to a set with three elements is
$$3^5 - binom{3}{1}2^5 + binom{3}{2}1^5$$
answered Dec 9 '18 at 23:01
N. F. TaussigN. F. Taussig
44k93355
$endgroup$
1
$begingroup$
Thanks a lot. It makes more sense now. I'll also keep in mind to format my question better next time.
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:15
1
$begingroup$
Can't upvote your answer since I have too little rep points but your answer is upvoted deep in my heart
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:16
add a comment |
$begingroup$
We want to count the number of surjective (onto) functions from a set with five elements to a set with three elements.
If there were no restrictions, each of the five elements in the domain could be mapped to one of the three elements in the codomain, so there are $3^5$ possible functions. From these, we must exclude those with fewer than three elements in their range.
There are $binom{3}{1}$ ways to exclude an element of the codomain from the range and $2^5$ ways to map the five elements of the domain to the remaining elements in the codomain. Hence, there are $binom{3}{1}2^5$ functions that exclude an element of the codomain from the range.
However, if we subtract these functions from the total, we will have subtracted each function that excludes two elements of the codomain from the range twice, once for each way we could have designated one of those elements as the excluded element. We only want to subtract them once, so we must add them back.
There are $binom{3}{2}$ ways to exclude two elements of the codomain from the range and $1^5$ ways to map the five elements of the domain to the remaining element of the codomain. Hence, there are $binom{3}{2}1^5$ functions that exclude two elements of the codomain from the range.
Hence, by the Inclusion-Exclusion Principle, the number of surjective functions from a set with five elements to a set with three elements is
$$3^5 - binom{3}{1}2^5 + binom{3}{2}1^5$$
answered Dec 9 '18 at 23:01
N. F. TaussigN. F. Taussig
44k93355
$endgroup$
We want to count the number of surjective (onto) functions from a set with five elements to a set with three elements.
If there were no restrictions, each of the five elements in the domain could be mapped to one of the three elements in the codomain, so there are $3^5$ possible functions. From these, we must exclude those with fewer than three elements in their range.
There are $binom{3}{1}$ ways to exclude an element of the codomain from the range and $2^5$ ways to map the five elements of the domain to the remaining elements in the codomain. Hence, there are $binom{3}{1}2^5$ functions that exclude an element of the codomain from the range.
However, if we subtract these functions from the total, we will have subtracted each function that excludes two elements of the codomain from the range twice, once for each way we could have designated one of those elements as the excluded element. We only want to subtract them once, so we must add them back.
There are $binom{3}{2}$ ways to exclude two elements of the codomain from the range and $1^5$ ways to map the five elements of the domain to the remaining element of the codomain. Hence, there are $binom{3}{2}1^5$ functions that exclude two elements of the codomain from the range.
Hence, by the Inclusion-Exclusion Principle, the number of surjective functions from a set with five elements to a set with three elements is
$$3^5 - binom{3}{1}2^5 + binom{3}{2}1^5$$
answered Dec 9 '18 at 23:01
N. F. TaussigN. F. Taussig
44k93355
answered Dec 9 '18 at 23:01
N. F. TaussigN. F. Taussig
44k93355
answered Dec 9 '18 at 23:01
N. F. TaussigN. F. Taussig
44k93355
answered Dec 9 '18 at 23:01
N. F. TaussigN. F. Taussig
44k93355
44k93355
1
$begingroup$
Thanks a lot. It makes more sense now. I'll also keep in mind to format my question better next time.
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:15
1
$begingroup$
Can't upvote your answer since I have too little rep points but your answer is upvoted deep in my heart
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:16
add a comment |
1
$begingroup$
Thanks a lot. It makes more sense now. I'll also keep in mind to format my question better next time.
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:15
1
$begingroup$
Can't upvote your answer since I have too little rep points but your answer is upvoted deep in my heart
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:16
1
1
$begingroup$
Thanks a lot. It makes more sense now. I'll also keep in mind to format my question better next time.
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:15
$begingroup$
Thanks a lot. It makes more sense now. I'll also keep in mind to format my question better next time.
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:15
1
1
$begingroup$
Can't upvote your answer since I have too little rep points but your answer is upvoted deep in my heart
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:16
$begingroup$
Can't upvote your answer since I have too little rep points but your answer is upvoted deep in my heart
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:16
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3033112%2fpigeonholes-and-onto-functions%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
Welcome to MathSE. It is better to type the question than post an image since images cannot be searched. This MathJax tutorial explains how to typeset mathematics on this site.
$endgroup$
– N. F. Taussig
Dec 9 '18 at 23:06
$begingroup$
Yeah sorry I tried posting the question instead but all the format changed and it got way too messy
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:12
$begingroup$
It's inclusion exclusion. $3^5$ is all the functions period. $C(3,2)2^5$ are then number of was where $a$ or $b$ or $c$ is excluded (at least one is exclude). But if we subtract the was $a$ can be exclude and then subtract the way $b$ can be excluded, we have subtracted the way$a$ and $b$ both excluded twice. So by inclusion/exclusion we must compensate after subtracting ways at least 1 is excluded, by adding ways at least 2 are excluded. And that is $C(3,1)1^5$.
$endgroup$
– fleablood
Dec 9 '18 at 23:19
$begingroup$
Yeah I get it now. I was just not taught the inclusion-exclusion principle so that's why i was confused.
$endgroup$
– Arvin Ansari
Dec 9 '18 at 23:26