Pigeonholes and onto functions












2












$begingroup$


surjective_functions_problem



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







share|cite|improve this question











$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
















2












$begingroup$


surjective_functions_problem



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







share|cite|improve this question











$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














2












2








2


1



$begingroup$


surjective_functions_problem



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







share|cite|improve this question











$endgroup$




surjective_functions_problem



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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Dec 9 '18 at 23:28









N. F. Taussig

44k93355




44k93355










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














  • 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










1 Answer
1






active

oldest

votes


















1












$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$$






share|cite|improve this answer









$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











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
});


}
});














draft saved

draft discarded


















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









1












$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$$






share|cite|improve this answer









$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
















1












$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$$






share|cite|improve this answer









$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














1












1








1





$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$$






share|cite|improve this answer









$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$$







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










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














  • 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


















draft saved

draft discarded




















































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.




draft saved


draft discarded














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





















































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







-

Popular posts from this blog

Berounka

Image
Berounka.mw-parser-output .entete.map{background-image:url("//upload.wikimedia.org/wikipedia/commons/7/7a/Picto_infobox_map.png")} Caractéristiques Longueur 139  km Bassin 8 861  km 2 Bassin collecteur Elbe Débit moyen ? Cours Source Confluence de la Mže et de la Radbuza · Localisation Pilsen · Altitude 305  m · Coordonnées 49° 45′ 13″ N, 13° 23′ 24″ E Confluence Vltava · Localisation Prague · Altitude 187  m · Coordonnées 49° 59′ 43″ N, 14° 24′ 04″ E Géographie Pays traversés   République tchèque modifier   La Berounka est une rivière de la République tchèque. Elle porte le nom de Mže depuis sa source en Allemagne près de la frontière jusqu'à sa confluence avec la Radbuza à Plzeň. Elle continue ensuite sous le nom de Berounka jusqu'à sa confluence avec la Vltava, près de Prague. La rivière est une destination prisée pour les amateurs de canoë, qui appréc...
Read more

Sphinx de Gizeh

Image
Pour les articles homonymes, voir Sphinx. Sphinx de Gizeh.mw-parser-output .entete.egypte-antique{background-image:url("//upload.wikimedia.org/wikipedia/commons/c/cc/Picto_infobox_ancient_Egypt.png")} Site d'Égypte antique Le visage du sphinx de Gizeh. Noms en arabe أبو الهول , Abou al-Hôl Localisation Région Basse-Égypte Coordonnées 29° 58′ 31″ nord, 31° 08′ 16″ est Géolocalisation sur la carte : Égypte Sphinx de Gizeh modifier   Le sphinx de Gizeh est la statue thérianthrope qui se dresse devant les grandes pyramides du plateau de Gizeh, en Basse-Égypte. Sculpture monumentale monolithique la plus grande du monde [ 1 ] avec 73,5 mètres de longueur, 14 mètres de largeur et 20,22 mètres de hauteur, elle représente un sphinx couchant. Réalisée vers -2500, elle serait attribuée à Djédefrê, l'un des pharaons de la IV e  dynastie, représentant son père le pharaon Khéops. Sommaire 1 Étymologie 2 Desc...
Read more

Different font size/position of beamer's navigation symbols template's content depending on regular/plain...

Image
3 Let's suppose I'd like to divert the navigation symbols template (e.g. in order replace them by the frame numbers, see this bug report ;) I would be facing troubles regarding the font size/position, depending on regular/plain frames, as shown by the following MCE. How could I get rid of these troubles? documentclass{beamer} usetheme{PaloAlto} setbeamertemplate{navigation symbols}{insertframenumber/inserttotalframenumber} begin{document} begin{frame} frametitle{A regular frame} end{frame} begin{frame}[plain] frametitle{A plain frame} end{frame} end{document} beamer header-footer share | improve this question asked Dec 10 '18 a...
Read more