Number of functions with certain property
$begingroup$
Let $f : {1,2,3}rightarrow{1,2,3}$ be a function. Then the number of functions $g : {1,2,3}rightarrow {1,2,3}$ such that $f(x) = g(x)$ for at least one $x$ belonging to ${1,2,3}$ is what?
My reasoning was that total number of functions $f$ will be $3^3$ and for each of these functions I can have $g$ take exactly the same values as $f$ does so the answer would be $27$ but this answer is not correct, can someone please provide the solution.
combinatorics permutations
$endgroup$
add a comment |
$begingroup$
Let $f : {1,2,3}rightarrow{1,2,3}$ be a function. Then the number of functions $g : {1,2,3}rightarrow {1,2,3}$ such that $f(x) = g(x)$ for at least one $x$ belonging to ${1,2,3}$ is what?
My reasoning was that total number of functions $f$ will be $3^3$ and for each of these functions I can have $g$ take exactly the same values as $f$ does so the answer would be $27$ but this answer is not correct, can someone please provide the solution.
combinatorics permutations
$endgroup$
add a comment |
$begingroup$
Let $f : {1,2,3}rightarrow{1,2,3}$ be a function. Then the number of functions $g : {1,2,3}rightarrow {1,2,3}$ such that $f(x) = g(x)$ for at least one $x$ belonging to ${1,2,3}$ is what?
My reasoning was that total number of functions $f$ will be $3^3$ and for each of these functions I can have $g$ take exactly the same values as $f$ does so the answer would be $27$ but this answer is not correct, can someone please provide the solution.
combinatorics permutations
$endgroup$
Let $f : {1,2,3}rightarrow{1,2,3}$ be a function. Then the number of functions $g : {1,2,3}rightarrow {1,2,3}$ such that $f(x) = g(x)$ for at least one $x$ belonging to ${1,2,3}$ is what?
My reasoning was that total number of functions $f$ will be $3^3$ and for each of these functions I can have $g$ take exactly the same values as $f$ does so the answer would be $27$ but this answer is not correct, can someone please provide the solution.
combinatorics permutations
combinatorics permutations
edited Jan 25 at 10:58
N. F. Taussig
44.6k103357
44.6k103357
asked Jan 25 at 3:55
user601297user601297
36919
36919
add a comment |
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
In general, the number of functions ${1,...,n} to {1,...,m}$ is $m^n$.
Hence the number of functions in this case is $3^3$.
Remember $f$ is one specific function.
It is easier to count the number of $g$s that do not equal $f$ anywhere.
In particular, the range of such a $g$ must have size $2$ not $3$, hence the number
of such functions is $2^3$.
Hence the number of the other $g$s, which is what you are looking for, is
$3^3-2^3$.
Elaboration: What I mean is that $g(k)$ takes the values ${1,2,3} setminus {f(k)}$, and for all $k$ we have $| {1,2,3} setminus {f(k)} | = 2$.
$endgroup$
$begingroup$
By size do you mean the number of values $g$ takes ???
$endgroup$
– user601297
Jan 25 at 4:11
$begingroup$
@user601297: Yes, excuse my tired wording. The point is at any $x$, we remove the value $f(x)$ from $g$s range. We don't care about the particular value here, just how many remain, which is $2$ for each value of $x$.
$endgroup$
– copper.hat
Jan 25 at 4:12
$begingroup$
But the example that @Bram28 gave has $g$ take all 3 values.
$endgroup$
– user601297
Jan 25 at 4:20
$begingroup$
In the example $g(1)$ must be one of $2,3$, $f(2)$ must be one of $1,3$ and $g(3)$ must be one of $1,2$. In all cases, the size of the range is $3-1=2$.
$endgroup$
– copper.hat
Jan 25 at 4:23
$begingroup$
Your answer is definitely correct, I’m just having a hard time understanding this, thanks anyways.
$endgroup$
– user601297
Jan 25 at 4:34
|
show 2 more comments
$begingroup$
It is more important to understand why your answer does not work.
Let's say that $f(1)=1, f(2)=2$ and $f(3)=3$
Then if you have $g(1)=2, g(2)=3$ and $f(3)=1$ (this is one of the $27$ possble functions for $g$), you have no $x$ such that $f(x)=g(x)$. So, not all $27$ possible functions for $g$ will have at least one 'match' with $f$.
Do you see how you can correct for this?
$endgroup$
$begingroup$
I’m sorry but I still don’t get it, why can’t I just change one of the $g$ values to match with $f$?
$endgroup$
– user601297
Jan 25 at 4:03
$begingroup$
@user601297 Yes, you can, but that would be a different $g$: one of the other $26$. So, for some of the $27$ possible $g$'s you get a match, but for others you do not.
$endgroup$
– Bram28
Jan 25 at 4:04
$begingroup$
I would really be grateful if you could provide me with the process to come to the right number, I will probably understand it better that way.
$endgroup$
– user601297
Jan 25 at 4:06
add a comment |
$begingroup$
Probably it is easier to count the number $a$ of functions $g$ such that $g(x)not=f(x)$ for all $xin{1,2,3}$ first. Then the set of functions you are looking has cardinality $b-a$ where $b$ denotes the number of all functions mapping ${1,2,3}$ Info itself.
$endgroup$
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%2f3086681%2fnumber-of-functions-with-certain-property%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
In general, the number of functions ${1,...,n} to {1,...,m}$ is $m^n$.
Hence the number of functions in this case is $3^3$.
Remember $f$ is one specific function.
It is easier to count the number of $g$s that do not equal $f$ anywhere.
In particular, the range of such a $g$ must have size $2$ not $3$, hence the number
of such functions is $2^3$.
Hence the number of the other $g$s, which is what you are looking for, is
$3^3-2^3$.
Elaboration: What I mean is that $g(k)$ takes the values ${1,2,3} setminus {f(k)}$, and for all $k$ we have $| {1,2,3} setminus {f(k)} | = 2$.
$endgroup$
$begingroup$
By size do you mean the number of values $g$ takes ???
$endgroup$
– user601297
Jan 25 at 4:11
$begingroup$
@user601297: Yes, excuse my tired wording. The point is at any $x$, we remove the value $f(x)$ from $g$s range. We don't care about the particular value here, just how many remain, which is $2$ for each value of $x$.
$endgroup$
– copper.hat
Jan 25 at 4:12
$begingroup$
But the example that @Bram28 gave has $g$ take all 3 values.
$endgroup$
– user601297
Jan 25 at 4:20
$begingroup$
In the example $g(1)$ must be one of $2,3$, $f(2)$ must be one of $1,3$ and $g(3)$ must be one of $1,2$. In all cases, the size of the range is $3-1=2$.
$endgroup$
– copper.hat
Jan 25 at 4:23
$begingroup$
Your answer is definitely correct, I’m just having a hard time understanding this, thanks anyways.
$endgroup$
– user601297
Jan 25 at 4:34
|
show 2 more comments
$begingroup$
In general, the number of functions ${1,...,n} to {1,...,m}$ is $m^n$.
Hence the number of functions in this case is $3^3$.
Remember $f$ is one specific function.
It is easier to count the number of $g$s that do not equal $f$ anywhere.
In particular, the range of such a $g$ must have size $2$ not $3$, hence the number
of such functions is $2^3$.
Hence the number of the other $g$s, which is what you are looking for, is
$3^3-2^3$.
Elaboration: What I mean is that $g(k)$ takes the values ${1,2,3} setminus {f(k)}$, and for all $k$ we have $| {1,2,3} setminus {f(k)} | = 2$.
$endgroup$
$begingroup$
By size do you mean the number of values $g$ takes ???
$endgroup$
– user601297
Jan 25 at 4:11
$begingroup$
@user601297: Yes, excuse my tired wording. The point is at any $x$, we remove the value $f(x)$ from $g$s range. We don't care about the particular value here, just how many remain, which is $2$ for each value of $x$.
$endgroup$
– copper.hat
Jan 25 at 4:12
$begingroup$
But the example that @Bram28 gave has $g$ take all 3 values.
$endgroup$
– user601297
Jan 25 at 4:20
$begingroup$
In the example $g(1)$ must be one of $2,3$, $f(2)$ must be one of $1,3$ and $g(3)$ must be one of $1,2$. In all cases, the size of the range is $3-1=2$.
$endgroup$
– copper.hat
Jan 25 at 4:23
$begingroup$
Your answer is definitely correct, I’m just having a hard time understanding this, thanks anyways.
$endgroup$
– user601297
Jan 25 at 4:34
|
show 2 more comments
$begingroup$
In general, the number of functions ${1,...,n} to {1,...,m}$ is $m^n$.
Hence the number of functions in this case is $3^3$.
Remember $f$ is one specific function.
It is easier to count the number of $g$s that do not equal $f$ anywhere.
In particular, the range of such a $g$ must have size $2$ not $3$, hence the number
of such functions is $2^3$.
Hence the number of the other $g$s, which is what you are looking for, is
$3^3-2^3$.
Elaboration: What I mean is that $g(k)$ takes the values ${1,2,3} setminus {f(k)}$, and for all $k$ we have $| {1,2,3} setminus {f(k)} | = 2$.
$endgroup$
In general, the number of functions ${1,...,n} to {1,...,m}$ is $m^n$.
Hence the number of functions in this case is $3^3$.
Remember $f$ is one specific function.
It is easier to count the number of $g$s that do not equal $f$ anywhere.
In particular, the range of such a $g$ must have size $2$ not $3$, hence the number
of such functions is $2^3$.
Hence the number of the other $g$s, which is what you are looking for, is
$3^3-2^3$.
Elaboration: What I mean is that $g(k)$ takes the values ${1,2,3} setminus {f(k)}$, and for all $k$ we have $| {1,2,3} setminus {f(k)} | = 2$.
edited Jan 25 at 4:25
answered Jan 25 at 4:06
copper.hatcopper.hat
127k559160
127k559160
$begingroup$
By size do you mean the number of values $g$ takes ???
$endgroup$
– user601297
Jan 25 at 4:11
$begingroup$
@user601297: Yes, excuse my tired wording. The point is at any $x$, we remove the value $f(x)$ from $g$s range. We don't care about the particular value here, just how many remain, which is $2$ for each value of $x$.
$endgroup$
– copper.hat
Jan 25 at 4:12
$begingroup$
But the example that @Bram28 gave has $g$ take all 3 values.
$endgroup$
– user601297
Jan 25 at 4:20
$begingroup$
In the example $g(1)$ must be one of $2,3$, $f(2)$ must be one of $1,3$ and $g(3)$ must be one of $1,2$. In all cases, the size of the range is $3-1=2$.
$endgroup$
– copper.hat
Jan 25 at 4:23
$begingroup$
Your answer is definitely correct, I’m just having a hard time understanding this, thanks anyways.
$endgroup$
– user601297
Jan 25 at 4:34
|
show 2 more comments
$begingroup$
By size do you mean the number of values $g$ takes ???
$endgroup$
– user601297
Jan 25 at 4:11
$begingroup$
@user601297: Yes, excuse my tired wording. The point is at any $x$, we remove the value $f(x)$ from $g$s range. We don't care about the particular value here, just how many remain, which is $2$ for each value of $x$.
$endgroup$
– copper.hat
Jan 25 at 4:12
$begingroup$
But the example that @Bram28 gave has $g$ take all 3 values.
$endgroup$
– user601297
Jan 25 at 4:20
$begingroup$
In the example $g(1)$ must be one of $2,3$, $f(2)$ must be one of $1,3$ and $g(3)$ must be one of $1,2$. In all cases, the size of the range is $3-1=2$.
$endgroup$
– copper.hat
Jan 25 at 4:23
$begingroup$
Your answer is definitely correct, I’m just having a hard time understanding this, thanks anyways.
$endgroup$
– user601297
Jan 25 at 4:34
$begingroup$
By size do you mean the number of values $g$ takes ???
$endgroup$
– user601297
Jan 25 at 4:11
$begingroup$
By size do you mean the number of values $g$ takes ???
$endgroup$
– user601297
Jan 25 at 4:11
$begingroup$
@user601297: Yes, excuse my tired wording. The point is at any $x$, we remove the value $f(x)$ from $g$s range. We don't care about the particular value here, just how many remain, which is $2$ for each value of $x$.
$endgroup$
– copper.hat
Jan 25 at 4:12
$begingroup$
@user601297: Yes, excuse my tired wording. The point is at any $x$, we remove the value $f(x)$ from $g$s range. We don't care about the particular value here, just how many remain, which is $2$ for each value of $x$.
$endgroup$
– copper.hat
Jan 25 at 4:12
$begingroup$
But the example that @Bram28 gave has $g$ take all 3 values.
$endgroup$
– user601297
Jan 25 at 4:20
$begingroup$
But the example that @Bram28 gave has $g$ take all 3 values.
$endgroup$
– user601297
Jan 25 at 4:20
$begingroup$
In the example $g(1)$ must be one of $2,3$, $f(2)$ must be one of $1,3$ and $g(3)$ must be one of $1,2$. In all cases, the size of the range is $3-1=2$.
$endgroup$
– copper.hat
Jan 25 at 4:23
$begingroup$
In the example $g(1)$ must be one of $2,3$, $f(2)$ must be one of $1,3$ and $g(3)$ must be one of $1,2$. In all cases, the size of the range is $3-1=2$.
$endgroup$
– copper.hat
Jan 25 at 4:23
$begingroup$
Your answer is definitely correct, I’m just having a hard time understanding this, thanks anyways.
$endgroup$
– user601297
Jan 25 at 4:34
$begingroup$
Your answer is definitely correct, I’m just having a hard time understanding this, thanks anyways.
$endgroup$
– user601297
Jan 25 at 4:34
|
show 2 more comments
$begingroup$
It is more important to understand why your answer does not work.
Let's say that $f(1)=1, f(2)=2$ and $f(3)=3$
Then if you have $g(1)=2, g(2)=3$ and $f(3)=1$ (this is one of the $27$ possble functions for $g$), you have no $x$ such that $f(x)=g(x)$. So, not all $27$ possible functions for $g$ will have at least one 'match' with $f$.
Do you see how you can correct for this?
$endgroup$
$begingroup$
I’m sorry but I still don’t get it, why can’t I just change one of the $g$ values to match with $f$?
$endgroup$
– user601297
Jan 25 at 4:03
$begingroup$
@user601297 Yes, you can, but that would be a different $g$: one of the other $26$. So, for some of the $27$ possible $g$'s you get a match, but for others you do not.
$endgroup$
– Bram28
Jan 25 at 4:04
$begingroup$
I would really be grateful if you could provide me with the process to come to the right number, I will probably understand it better that way.
$endgroup$
– user601297
Jan 25 at 4:06
add a comment |
$begingroup$
It is more important to understand why your answer does not work.
Let's say that $f(1)=1, f(2)=2$ and $f(3)=3$
Then if you have $g(1)=2, g(2)=3$ and $f(3)=1$ (this is one of the $27$ possble functions for $g$), you have no $x$ such that $f(x)=g(x)$. So, not all $27$ possible functions for $g$ will have at least one 'match' with $f$.
Do you see how you can correct for this?
$endgroup$
$begingroup$
I’m sorry but I still don’t get it, why can’t I just change one of the $g$ values to match with $f$?
$endgroup$
– user601297
Jan 25 at 4:03
$begingroup$
@user601297 Yes, you can, but that would be a different $g$: one of the other $26$. So, for some of the $27$ possible $g$'s you get a match, but for others you do not.
$endgroup$
– Bram28
Jan 25 at 4:04
$begingroup$
I would really be grateful if you could provide me with the process to come to the right number, I will probably understand it better that way.
$endgroup$
– user601297
Jan 25 at 4:06
add a comment |
$begingroup$
It is more important to understand why your answer does not work.
Let's say that $f(1)=1, f(2)=2$ and $f(3)=3$
Then if you have $g(1)=2, g(2)=3$ and $f(3)=1$ (this is one of the $27$ possble functions for $g$), you have no $x$ such that $f(x)=g(x)$. So, not all $27$ possible functions for $g$ will have at least one 'match' with $f$.
Do you see how you can correct for this?
$endgroup$
It is more important to understand why your answer does not work.
Let's say that $f(1)=1, f(2)=2$ and $f(3)=3$
Then if you have $g(1)=2, g(2)=3$ and $f(3)=1$ (this is one of the $27$ possble functions for $g$), you have no $x$ such that $f(x)=g(x)$. So, not all $27$ possible functions for $g$ will have at least one 'match' with $f$.
Do you see how you can correct for this?
answered Jan 25 at 4:00
Bram28Bram28
63.3k44793
63.3k44793
$begingroup$
I’m sorry but I still don’t get it, why can’t I just change one of the $g$ values to match with $f$?
$endgroup$
– user601297
Jan 25 at 4:03
$begingroup$
@user601297 Yes, you can, but that would be a different $g$: one of the other $26$. So, for some of the $27$ possible $g$'s you get a match, but for others you do not.
$endgroup$
– Bram28
Jan 25 at 4:04
$begingroup$
I would really be grateful if you could provide me with the process to come to the right number, I will probably understand it better that way.
$endgroup$
– user601297
Jan 25 at 4:06
add a comment |
$begingroup$
I’m sorry but I still don’t get it, why can’t I just change one of the $g$ values to match with $f$?
$endgroup$
– user601297
Jan 25 at 4:03
$begingroup$
@user601297 Yes, you can, but that would be a different $g$: one of the other $26$. So, for some of the $27$ possible $g$'s you get a match, but for others you do not.
$endgroup$
– Bram28
Jan 25 at 4:04
$begingroup$
I would really be grateful if you could provide me with the process to come to the right number, I will probably understand it better that way.
$endgroup$
– user601297
Jan 25 at 4:06
$begingroup$
I’m sorry but I still don’t get it, why can’t I just change one of the $g$ values to match with $f$?
$endgroup$
– user601297
Jan 25 at 4:03
$begingroup$
I’m sorry but I still don’t get it, why can’t I just change one of the $g$ values to match with $f$?
$endgroup$
– user601297
Jan 25 at 4:03
$begingroup$
@user601297 Yes, you can, but that would be a different $g$: one of the other $26$. So, for some of the $27$ possible $g$'s you get a match, but for others you do not.
$endgroup$
– Bram28
Jan 25 at 4:04
$begingroup$
@user601297 Yes, you can, but that would be a different $g$: one of the other $26$. So, for some of the $27$ possible $g$'s you get a match, but for others you do not.
$endgroup$
– Bram28
Jan 25 at 4:04
$begingroup$
I would really be grateful if you could provide me with the process to come to the right number, I will probably understand it better that way.
$endgroup$
– user601297
Jan 25 at 4:06
$begingroup$
I would really be grateful if you could provide me with the process to come to the right number, I will probably understand it better that way.
$endgroup$
– user601297
Jan 25 at 4:06
add a comment |
$begingroup$
Probably it is easier to count the number $a$ of functions $g$ such that $g(x)not=f(x)$ for all $xin{1,2,3}$ first. Then the set of functions you are looking has cardinality $b-a$ where $b$ denotes the number of all functions mapping ${1,2,3}$ Info itself.
$endgroup$
add a comment |
$begingroup$
Probably it is easier to count the number $a$ of functions $g$ such that $g(x)not=f(x)$ for all $xin{1,2,3}$ first. Then the set of functions you are looking has cardinality $b-a$ where $b$ denotes the number of all functions mapping ${1,2,3}$ Info itself.
$endgroup$
add a comment |
$begingroup$
Probably it is easier to count the number $a$ of functions $g$ such that $g(x)not=f(x)$ for all $xin{1,2,3}$ first. Then the set of functions you are looking has cardinality $b-a$ where $b$ denotes the number of all functions mapping ${1,2,3}$ Info itself.
$endgroup$
Probably it is easier to count the number $a$ of functions $g$ such that $g(x)not=f(x)$ for all $xin{1,2,3}$ first. Then the set of functions you are looking has cardinality $b-a$ where $b$ denotes the number of all functions mapping ${1,2,3}$ Info itself.
answered Jan 25 at 4:10
Jens SchwaigerJens Schwaiger
1,631138
1,631138
add a comment |
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%2f3086681%2fnumber-of-functions-with-certain-property%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