What is the number of functions $f$ from the set ${1, 2, . . . , 2n}$ to ${1, 2, . . . , n}$ so that $f(x)...
Is it dangerous to install hacking tools on my private linux machine?
Can two people see the same photon?
How many time has Arya actually used Needle?
Did pre-Columbian Americans know the spherical shape of the Earth?
Can humans save crash-landed aliens?
Special flights
Can you force honesty by using the Speak with Dead and Zone of Truth spells together?
How does TikZ render an arc?
Why not use the yoke to control yaw, as well as pitch and roll?
Mounting TV on a weird wall that has some material between the drywall and stud
Asymptotics question
Why is std::move not [[nodiscard]] in C++20?
How were pictures turned from film to a big picture in a picture frame before digital scanning?
Is it possible for SQL statements to execute concurrently within a single session in SQL Server?
Why complex landing gears are used instead of simple,reliability and light weight muscle wire or shape memory alloys?
Trying to understand entropy as a novice in thermodynamics
In musical terms, what properties are varied by the human voice to produce different words / syllables?
How to change the tick of the color bar legend to black
As a dual citizen, my US passport will expire one day after traveling to the US. Will this work?
Monty Hall Problem-Probability Paradox
Nose gear failure in single prop aircraft: belly landing or nose-gear up landing?
Delete free apps from Play Store library
What does the writing on Poe's helmet say?
Co-worker has annoying ringtone
What is the number of functions $f$ from the set ${1, 2, . . . , 2n}$ to ${1, 2, . . . , n}$ so that $f(x) leq lceil x/2 rceil$ for all $x$?
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 23, 2019 at 23:30 UTC (7:30pm US/Eastern)Number of functions on finite setHow many distinct functions can be defined from set A to P(B)?Number of functions from n-element set to {1, 2, …, m}Let F denote the set of all functions from {1,2,3} to {1,2,3,4,5}, find the following:…?Use a generating function to evaluate the sum $ a_k=sum_{j=lceil k/2rceil}^k {j choose k-j}$.Number of ways to break $n$ into $lceil n/krceil$ positive integers each at most $k$Prove: If n is an odd natural number, there are $ s = lceil frac{n}{2} rceil $ odd integers less than or equal to nNumber of ternary sequences of length $n$ with the property that $|x_i - x_{i - 1}| = 1$ for each $i$ such that $2 leq i leq n$Proof lower bound of $lceil{n/2}rceil$ comparisons for finding smallest and second smallest elementWhat is the number of one-to-one functions from the set ${1, 2,dots , n}$ to the set ${1, 2, dots , 2n}$
$begingroup$
What is the number of functions $f$ from the set ${1, 2, . . . , 2n}$ to ${1, 2, . . . , n}$ so that $f(x) leq lceil x/2 rceil$ for all $x$?
I'm a complete beginner at solving something like this, and I tried to use the product rule. I'm 99% sure I've done it wrong.
So for elements $1, 2, 3, 4, 5, 6, 7, 8$, there are $1,1,2,2,3,3,4,4$ possibilities respectively (if I'm understanding this right)
If this continues for element $2n$ there will be $n$ possibilities. I'm not sure how to continue to how many functions there are from here. If I had to guess since there are $1/2$ as many possibilities as the element number.
There are $n^{m}$ functions from $m$ elements to $n$ elements so would the answer be $frac{n^{m}}{2}$ ? Is my logic correct?
combinatorics discrete-mathematics computer-science
edited Mar 26 at 1:47
Brian
1,495416
asked Mar 26 at 1:43
BrownieBrownie
3447
$endgroup$
add a comment |
$begingroup$
What is the number of functions $f$ from the set ${1, 2, . . . , 2n}$ to ${1, 2, . . . , n}$ so that $f(x) leq lceil x/2 rceil$ for all $x$?
I'm a complete beginner at solving something like this, and I tried to use the product rule. I'm 99% sure I've done it wrong.
So for elements $1, 2, 3, 4, 5, 6, 7, 8$, there are $1,1,2,2,3,3,4,4$ possibilities respectively (if I'm understanding this right)
If this continues for element $2n$ there will be $n$ possibilities. I'm not sure how to continue to how many functions there are from here. If I had to guess since there are $1/2$ as many possibilities as the element number.
There are $n^{m}$ functions from $m$ elements to $n$ elements so would the answer be $frac{n^{m}}{2}$ ? Is my logic correct?
combinatorics discrete-mathematics computer-science
edited Mar 26 at 1:47
Brian
1,495416
asked Mar 26 at 1:43
BrownieBrownie
3447
$endgroup$
1
$begingroup$
This is equivalent to the accepted answer but with a different presentation: The number of possibilites (and you almost got there) $=1 times 1 times 2 times 2 times 3 times 3 times cdots times n times n$, which can be easily rearranged into $(1times 2times cdots times n) times (1times 2times cdots times n) = (n!)^2$
$endgroup$
– antkam
Mar 26 at 14:12
add a comment |
$begingroup$
What is the number of functions $f$ from the set ${1, 2, . . . , 2n}$ to ${1, 2, . . . , n}$ so that $f(x) leq lceil x/2 rceil$ for all $x$?
I'm a complete beginner at solving something like this, and I tried to use the product rule. I'm 99% sure I've done it wrong.
So for elements $1, 2, 3, 4, 5, 6, 7, 8$, there are $1,1,2,2,3,3,4,4$ possibilities respectively (if I'm understanding this right)
If this continues for element $2n$ there will be $n$ possibilities. I'm not sure how to continue to how many functions there are from here. If I had to guess since there are $1/2$ as many possibilities as the element number.
There are $n^{m}$ functions from $m$ elements to $n$ elements so would the answer be $frac{n^{m}}{2}$ ? Is my logic correct?
combinatorics discrete-mathematics computer-science
edited Mar 26 at 1:47
Brian
1,495416
asked Mar 26 at 1:43
BrownieBrownie
3447
$endgroup$
What is the number of functions $f$ from the set ${1, 2, . . . , 2n}$ to ${1, 2, . . . , n}$ so that $f(x) leq lceil x/2 rceil$ for all $x$?
I'm a complete beginner at solving something like this, and I tried to use the product rule. I'm 99% sure I've done it wrong.
So for elements $1, 2, 3, 4, 5, 6, 7, 8$, there are $1,1,2,2,3,3,4,4$ possibilities respectively (if I'm understanding this right)
If this continues for element $2n$ there will be $n$ possibilities. I'm not sure how to continue to how many functions there are from here. If I had to guess since there are $1/2$ as many possibilities as the element number.
There are $n^{m}$ functions from $m$ elements to $n$ elements so would the answer be $frac{n^{m}}{2}$ ? Is my logic correct?
combinatorics discrete-mathematics computer-science
combinatorics discrete-mathematics computer-science
edited Mar 26 at 1:47
Brian
1,495416
asked Mar 26 at 1:43
BrownieBrownie
3447
edited Mar 26 at 1:47
Brian
1,495416
asked Mar 26 at 1:43
BrownieBrownie
3447
edited Mar 26 at 1:47
Brian
1,495416
edited Mar 26 at 1:47
Brian
1,495416
edited Mar 26 at 1:47
Brian
1,495416
1,495416
asked Mar 26 at 1:43
BrownieBrownie
3447
asked Mar 26 at 1:43
BrownieBrownie
3447
asked Mar 26 at 1:43
BrownieBrownie
3447
3447
1
$begingroup$
This is equivalent to the accepted answer but with a different presentation: The number of possibilites (and you almost got there) $=1 times 1 times 2 times 2 times 3 times 3 times cdots times n times n$, which can be easily rearranged into $(1times 2times cdots times n) times (1times 2times cdots times n) = (n!)^2$
$endgroup$
– antkam
Mar 26 at 14:12
add a comment |
1
$begingroup$
This is equivalent to the accepted answer but with a different presentation: The number of possibilites (and you almost got there) $=1 times 1 times 2 times 2 times 3 times 3 times cdots times n times n$, which can be easily rearranged into $(1times 2times cdots times n) times (1times 2times cdots times n) = (n!)^2$
$endgroup$
– antkam
Mar 26 at 14:12
1
1
$begingroup$
This is equivalent to the accepted answer but with a different presentation: The number of possibilites (and you almost got there) $=1 times 1 times 2 times 2 times 3 times 3 times cdots times n times n$, which can be easily rearranged into $(1times 2times cdots times n) times (1times 2times cdots times n) = (n!)^2$
$endgroup$
– antkam
Mar 26 at 14:12
$begingroup$
This is equivalent to the accepted answer but with a different presentation: The number of possibilites (and you almost got there) $=1 times 1 times 2 times 2 times 3 times 3 times cdots times n times n$, which can be easily rearranged into $(1times 2times cdots times n) times (1times 2times cdots times n) = (n!)^2$
$endgroup$
– antkam
Mar 26 at 14:12
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
As you state in your question, there is $1$ place the value $1$ can map to.
There is $1$ place that $2$ can map to.
There is $i$ place that $2i-1$ can map to & $i$ places that $2i$ can map to.
So there will be $color{red}{(n!)^2}$ such mappings.
answered Mar 26 at 1:58
Donald SplutterwitDonald Splutterwit
23.1k21446
$endgroup$
$begingroup$
Could you explain how you got n!? I though that there were n! possibilities if possibilities kept decreasing by 1 for each element. i.e Element 1, 2, 3 , n would have n, n-1, n-2, n! possibilities respectively. I'm not sure how n! works in this case
$endgroup$
– Brownie
Mar 26 at 2:04
$begingroup$
Edit- Actually I may be understanding, is correct to say that for all even elements there are n! mappings. Then for all the odd elements since they map the same way there are also n! mappings. Thus $(n!)^{2}$
$endgroup$
– Brownie
Mar 26 at 2:18
1
$begingroup$
Yeah, That would be another way to see it. $n!$ for the odd elements & $n!$ for the even elements. See figure $1$ here oeis.org/A110501/a110501.pdf
$endgroup$
– Donald Splutterwit
Mar 26 at 2:39
add a comment |
Your Answer
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%2f3162588%2fwhat-is-the-number-of-functions-f-from-the-set-1-2-2n-to-1%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$
As you state in your question, there is $1$ place the value $1$ can map to.
There is $1$ place that $2$ can map to.
There is $i$ place that $2i-1$ can map to & $i$ places that $2i$ can map to.
So there will be $color{red}{(n!)^2}$ such mappings.
answered Mar 26 at 1:58
Donald SplutterwitDonald Splutterwit
23.1k21446
$endgroup$
$begingroup$
Could you explain how you got n!? I though that there were n! possibilities if possibilities kept decreasing by 1 for each element. i.e Element 1, 2, 3 , n would have n, n-1, n-2, n! possibilities respectively. I'm not sure how n! works in this case
$endgroup$
– Brownie
Mar 26 at 2:04
$begingroup$
Edit- Actually I may be understanding, is correct to say that for all even elements there are n! mappings. Then for all the odd elements since they map the same way there are also n! mappings. Thus $(n!)^{2}$
$endgroup$
– Brownie
Mar 26 at 2:18
1
$begingroup$
Yeah, That would be another way to see it. $n!$ for the odd elements & $n!$ for the even elements. See figure $1$ here oeis.org/A110501/a110501.pdf
$endgroup$
– Donald Splutterwit
Mar 26 at 2:39
add a comment |
$begingroup$
As you state in your question, there is $1$ place the value $1$ can map to.
There is $1$ place that $2$ can map to.
There is $i$ place that $2i-1$ can map to & $i$ places that $2i$ can map to.
So there will be $color{red}{(n!)^2}$ such mappings.
answered Mar 26 at 1:58
Donald SplutterwitDonald Splutterwit
23.1k21446
$endgroup$
$begingroup$
Could you explain how you got n!? I though that there were n! possibilities if possibilities kept decreasing by 1 for each element. i.e Element 1, 2, 3 , n would have n, n-1, n-2, n! possibilities respectively. I'm not sure how n! works in this case
$endgroup$
– Brownie
Mar 26 at 2:04
$begingroup$
Edit- Actually I may be understanding, is correct to say that for all even elements there are n! mappings. Then for all the odd elements since they map the same way there are also n! mappings. Thus $(n!)^{2}$
$endgroup$
– Brownie
Mar 26 at 2:18
1
$begingroup$
Yeah, That would be another way to see it. $n!$ for the odd elements & $n!$ for the even elements. See figure $1$ here oeis.org/A110501/a110501.pdf
$endgroup$
– Donald Splutterwit
Mar 26 at 2:39
add a comment |
$begingroup$
As you state in your question, there is $1$ place the value $1$ can map to.
There is $1$ place that $2$ can map to.
There is $i$ place that $2i-1$ can map to & $i$ places that $2i$ can map to.
So there will be $color{red}{(n!)^2}$ such mappings.
answered Mar 26 at 1:58
Donald SplutterwitDonald Splutterwit
23.1k21446
$endgroup$
As you state in your question, there is $1$ place the value $1$ can map to.
There is $1$ place that $2$ can map to.
There is $i$ place that $2i-1$ can map to & $i$ places that $2i$ can map to.
So there will be $color{red}{(n!)^2}$ such mappings.
answered Mar 26 at 1:58
Donald SplutterwitDonald Splutterwit
23.1k21446
answered Mar 26 at 1:58
Donald SplutterwitDonald Splutterwit
23.1k21446
answered Mar 26 at 1:58
Donald SplutterwitDonald Splutterwit
23.1k21446
answered Mar 26 at 1:58
Donald SplutterwitDonald Splutterwit
23.1k21446
23.1k21446
$begingroup$
Could you explain how you got n!? I though that there were n! possibilities if possibilities kept decreasing by 1 for each element. i.e Element 1, 2, 3 , n would have n, n-1, n-2, n! possibilities respectively. I'm not sure how n! works in this case
$endgroup$
– Brownie
Mar 26 at 2:04
$begingroup$
Edit- Actually I may be understanding, is correct to say that for all even elements there are n! mappings. Then for all the odd elements since they map the same way there are also n! mappings. Thus $(n!)^{2}$
$endgroup$
– Brownie
Mar 26 at 2:18
1
$begingroup$
Yeah, That would be another way to see it. $n!$ for the odd elements & $n!$ for the even elements. See figure $1$ here oeis.org/A110501/a110501.pdf
$endgroup$
– Donald Splutterwit
Mar 26 at 2:39
add a comment |
$begingroup$
Could you explain how you got n!? I though that there were n! possibilities if possibilities kept decreasing by 1 for each element. i.e Element 1, 2, 3 , n would have n, n-1, n-2, n! possibilities respectively. I'm not sure how n! works in this case
$endgroup$
– Brownie
Mar 26 at 2:04
$begingroup$
Edit- Actually I may be understanding, is correct to say that for all even elements there are n! mappings. Then for all the odd elements since they map the same way there are also n! mappings. Thus $(n!)^{2}$
$endgroup$
– Brownie
Mar 26 at 2:18
1
$begingroup$
Yeah, That would be another way to see it. $n!$ for the odd elements & $n!$ for the even elements. See figure $1$ here oeis.org/A110501/a110501.pdf
$endgroup$
– Donald Splutterwit
Mar 26 at 2:39
$begingroup$
Could you explain how you got n!? I though that there were n! possibilities if possibilities kept decreasing by 1 for each element. i.e Element 1, 2, 3 , n would have n, n-1, n-2, n! possibilities respectively. I'm not sure how n! works in this case
$endgroup$
– Brownie
Mar 26 at 2:04
$begingroup$
Could you explain how you got n!? I though that there were n! possibilities if possibilities kept decreasing by 1 for each element. i.e Element 1, 2, 3 , n would have n, n-1, n-2, n! possibilities respectively. I'm not sure how n! works in this case
$endgroup$
– Brownie
Mar 26 at 2:04
$begingroup$
Edit- Actually I may be understanding, is correct to say that for all even elements there are n! mappings. Then for all the odd elements since they map the same way there are also n! mappings. Thus $(n!)^{2}$
$endgroup$
– Brownie
Mar 26 at 2:18
$begingroup$
Edit- Actually I may be understanding, is correct to say that for all even elements there are n! mappings. Then for all the odd elements since they map the same way there are also n! mappings. Thus $(n!)^{2}$
$endgroup$
– Brownie
Mar 26 at 2:18
1
1
$begingroup$
Yeah, That would be another way to see it. $n!$ for the odd elements & $n!$ for the even elements. See figure $1$ here oeis.org/A110501/a110501.pdf
$endgroup$
– Donald Splutterwit
Mar 26 at 2:39
$begingroup$
Yeah, That would be another way to see it. $n!$ for the odd elements & $n!$ for the even elements. See figure $1$ here oeis.org/A110501/a110501.pdf
$endgroup$
– Donald Splutterwit
Mar 26 at 2:39
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%2f3162588%2fwhat-is-the-number-of-functions-f-from-the-set-1-2-2n-to-1%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$
This is equivalent to the accepted answer but with a different presentation: The number of possibilites (and you almost got there) $=1 times 1 times 2 times 2 times 3 times 3 times cdots times n times n$, which can be easily rearranged into $(1times 2times cdots times n) times (1times 2times cdots times n) = (n!)^2$
$endgroup$
– antkam
Mar 26 at 14:12