Inverse of a factorial
I'm trying to solve hard combinatorics that involve complicated factorials with large values.
In a simple case such as $8Pr = 336$, find the value of $r$, it is easy to say it equals to this: $$frac{8!}{(8-r)!} = 336.$$
Then $(8-r)! = 336$ and by inspection, clearly $8-r = 5$ and $r = 3$.
Now this is all and good and I know an inverse function to a factorial doesn't exist as there is for functions like sin, cos and tan etc. but how would you possibly solve an equation that involves very large values compared to the above problem without the tedious guess and checking for right values.
Edit: For e.g. if you wanted to calculate a problem like this (it's simple I know but a good starting out problem)
Let's say 10 colored marbles are placed in a row, what is the minimum number of colors needed to guarantee at least $10000$ different patterns? WITHOUT GUESS AND CHECKING
Any method or explanation is appreciated!
factorial
|
show 15 more comments
I'm trying to solve hard combinatorics that involve complicated factorials with large values.
In a simple case such as $8Pr = 336$, find the value of $r$, it is easy to say it equals to this: $$frac{8!}{(8-r)!} = 336.$$
Then $(8-r)! = 336$ and by inspection, clearly $8-r = 5$ and $r = 3$.
Now this is all and good and I know an inverse function to a factorial doesn't exist as there is for functions like sin, cos and tan etc. but how would you possibly solve an equation that involves very large values compared to the above problem without the tedious guess and checking for right values.
Edit: For e.g. if you wanted to calculate a problem like this (it's simple I know but a good starting out problem)
Let's say 10 colored marbles are placed in a row, what is the minimum number of colors needed to guarantee at least $10000$ different patterns? WITHOUT GUESS AND CHECKING
Any method or explanation is appreciated!
factorial
3
Stirling approximation.
– Simply Beautiful Art
Jan 1 '17 at 1:30
1
"In a row" would seem to imply that "blue, red, red, red, red, red, red, red, red, red" and "red, blue, red, red, red, red, red, red, red, red" are different patterns. If so, factorials are not applicable. Of course there are other combinatorial problems that involve large factorials to which your question still applies.
– David K
Jan 1 '17 at 2:01
1
FWIW, I posted a Python 2 function that uses Stirling's approximation & the Newton-Raphson method to invert log factorial here.
– PM 2Ring
Jan 1 '17 at 3:11
1
@TripleA, why do you say the answer is $4$? There is nothing wrong in Ross Millikan's analysis for the add-on question as it is stated: $3^{10}=59{,}049gt10{,}000$. So unless you have some nonstandard definition of what's required for two patterns to be considered "different," the answer is $3$.
– Barry Cipra
Jan 3 '17 at 1:48
1
@TripleA, ah, I see what you mean now. It would help to edit the add-on question to clarify that the different patterns must all come from a single choice of $10$ marbles of various diffferent colors. Both Ross and I interpreted it as meaning that each pattern is simply an assignment of an allowed color to each marble.
– Barry Cipra
Jan 3 '17 at 2:52
|
show 15 more comments
I'm trying to solve hard combinatorics that involve complicated factorials with large values.
In a simple case such as $8Pr = 336$, find the value of $r$, it is easy to say it equals to this: $$frac{8!}{(8-r)!} = 336.$$
Then $(8-r)! = 336$ and by inspection, clearly $8-r = 5$ and $r = 3$.
Now this is all and good and I know an inverse function to a factorial doesn't exist as there is for functions like sin, cos and tan etc. but how would you possibly solve an equation that involves very large values compared to the above problem without the tedious guess and checking for right values.
Edit: For e.g. if you wanted to calculate a problem like this (it's simple I know but a good starting out problem)
Let's say 10 colored marbles are placed in a row, what is the minimum number of colors needed to guarantee at least $10000$ different patterns? WITHOUT GUESS AND CHECKING
Any method or explanation is appreciated!
factorial
I'm trying to solve hard combinatorics that involve complicated factorials with large values.
In a simple case such as $8Pr = 336$, find the value of $r$, it is easy to say it equals to this: $$frac{8!}{(8-r)!} = 336.$$
Then $(8-r)! = 336$ and by inspection, clearly $8-r = 5$ and $r = 3$.
Now this is all and good and I know an inverse function to a factorial doesn't exist as there is for functions like sin, cos and tan etc. but how would you possibly solve an equation that involves very large values compared to the above problem without the tedious guess and checking for right values.
Edit: For e.g. if you wanted to calculate a problem like this (it's simple I know but a good starting out problem)
Let's say 10 colored marbles are placed in a row, what is the minimum number of colors needed to guarantee at least $10000$ different patterns? WITHOUT GUESS AND CHECKING
Any method or explanation is appreciated!
factorial
factorial
edited Jan 3 '17 at 1:25
TripleA
asked Jan 1 '17 at 1:20
TripleATripleA
737934
737934
3
Stirling approximation.
– Simply Beautiful Art
Jan 1 '17 at 1:30
1
"In a row" would seem to imply that "blue, red, red, red, red, red, red, red, red, red" and "red, blue, red, red, red, red, red, red, red, red" are different patterns. If so, factorials are not applicable. Of course there are other combinatorial problems that involve large factorials to which your question still applies.
– David K
Jan 1 '17 at 2:01
1
FWIW, I posted a Python 2 function that uses Stirling's approximation & the Newton-Raphson method to invert log factorial here.
– PM 2Ring
Jan 1 '17 at 3:11
1
@TripleA, why do you say the answer is $4$? There is nothing wrong in Ross Millikan's analysis for the add-on question as it is stated: $3^{10}=59{,}049gt10{,}000$. So unless you have some nonstandard definition of what's required for two patterns to be considered "different," the answer is $3$.
– Barry Cipra
Jan 3 '17 at 1:48
1
@TripleA, ah, I see what you mean now. It would help to edit the add-on question to clarify that the different patterns must all come from a single choice of $10$ marbles of various diffferent colors. Both Ross and I interpreted it as meaning that each pattern is simply an assignment of an allowed color to each marble.
– Barry Cipra
Jan 3 '17 at 2:52
|
show 15 more comments
3
Stirling approximation.
– Simply Beautiful Art
Jan 1 '17 at 1:30
1
"In a row" would seem to imply that "blue, red, red, red, red, red, red, red, red, red" and "red, blue, red, red, red, red, red, red, red, red" are different patterns. If so, factorials are not applicable. Of course there are other combinatorial problems that involve large factorials to which your question still applies.
– David K
Jan 1 '17 at 2:01
1
FWIW, I posted a Python 2 function that uses Stirling's approximation & the Newton-Raphson method to invert log factorial here.
– PM 2Ring
Jan 1 '17 at 3:11
1
@TripleA, why do you say the answer is $4$? There is nothing wrong in Ross Millikan's analysis for the add-on question as it is stated: $3^{10}=59{,}049gt10{,}000$. So unless you have some nonstandard definition of what's required for two patterns to be considered "different," the answer is $3$.
– Barry Cipra
Jan 3 '17 at 1:48
1
@TripleA, ah, I see what you mean now. It would help to edit the add-on question to clarify that the different patterns must all come from a single choice of $10$ marbles of various diffferent colors. Both Ross and I interpreted it as meaning that each pattern is simply an assignment of an allowed color to each marble.
– Barry Cipra
Jan 3 '17 at 2:52
3
3
Stirling approximation.
– Simply Beautiful Art
Jan 1 '17 at 1:30
Stirling approximation.
– Simply Beautiful Art
Jan 1 '17 at 1:30
1
1
"In a row" would seem to imply that "blue, red, red, red, red, red, red, red, red, red" and "red, blue, red, red, red, red, red, red, red, red" are different patterns. If so, factorials are not applicable. Of course there are other combinatorial problems that involve large factorials to which your question still applies.
– David K
Jan 1 '17 at 2:01
"In a row" would seem to imply that "blue, red, red, red, red, red, red, red, red, red" and "red, blue, red, red, red, red, red, red, red, red" are different patterns. If so, factorials are not applicable. Of course there are other combinatorial problems that involve large factorials to which your question still applies.
– David K
Jan 1 '17 at 2:01
1
1
FWIW, I posted a Python 2 function that uses Stirling's approximation & the Newton-Raphson method to invert log factorial here.
– PM 2Ring
Jan 1 '17 at 3:11
FWIW, I posted a Python 2 function that uses Stirling's approximation & the Newton-Raphson method to invert log factorial here.
– PM 2Ring
Jan 1 '17 at 3:11
1
1
@TripleA, why do you say the answer is $4$? There is nothing wrong in Ross Millikan's analysis for the add-on question as it is stated: $3^{10}=59{,}049gt10{,}000$. So unless you have some nonstandard definition of what's required for two patterns to be considered "different," the answer is $3$.
– Barry Cipra
Jan 3 '17 at 1:48
@TripleA, why do you say the answer is $4$? There is nothing wrong in Ross Millikan's analysis for the add-on question as it is stated: $3^{10}=59{,}049gt10{,}000$. So unless you have some nonstandard definition of what's required for two patterns to be considered "different," the answer is $3$.
– Barry Cipra
Jan 3 '17 at 1:48
1
1
@TripleA, ah, I see what you mean now. It would help to edit the add-on question to clarify that the different patterns must all come from a single choice of $10$ marbles of various diffferent colors. Both Ross and I interpreted it as meaning that each pattern is simply an assignment of an allowed color to each marble.
– Barry Cipra
Jan 3 '17 at 2:52
@TripleA, ah, I see what you mean now. It would help to edit the add-on question to clarify that the different patterns must all come from a single choice of $10$ marbles of various diffferent colors. Both Ross and I interpreted it as meaning that each pattern is simply an assignment of an allowed color to each marble.
– Barry Cipra
Jan 3 '17 at 2:52
|
show 15 more comments
5 Answers
5
active
oldest
votes
I just wrote this answer to an old question. Using $a=1$, we get a close inverse for the factorial function:
$$
nsim eexpleft(operatorname{W}left(frac1{e}logleft(frac{n!}{sqrt{2pi}}right)right)right)-frac12tag{1}
$$
1
And I just commented about it a few minutes ago ! Funny coïcidence !
– Claude Leibovici
Jan 1 '17 at 6:13
1
Just to add a small detail, robjohn's solution is strictly exact if we use $$n=leftlceil e^{Wleft(frac{log left(frac{n!}{sqrt{2 pi }}right)}{e}right)+1}-frac{1}{2}rightrceil$$
– Claude Leibovici
Jan 2 '17 at 4:51
1
@ClaudeLeibovici: if we know that $n$ is an integer. This is also a good inverse for $Gamma(n+1)$. $$nsim eexpleft(operatorname{W}left(frac1{e}logleft(frac{Gamma(n)}{sqrt{2pi}}right)right)right)+frac12$$ is an approximate inverse for $Gamma(n)$.
– robjohn♦
Jan 2 '17 at 6:58
It is so beautiful !
– Claude Leibovici
Jan 2 '17 at 8:13
add a comment |
By Stirling's formula
$$n! sim sqrt{2pi n} left({frac{n}{e}}right)^n $$
So we can given a large $n!$ we can attempt to numerically solve,
$$n!=sqrt{2pi x} left({frac{x}{e}}right)^x$$
For $x$ by Newton's method to get an approximate inverse.
The function $mathbb{N} to mathbb{N}$ given by $f(n)=n!$ is increasing. Also,
$$sqrt{2pi}n^{n+frac{1}{2}}e^{-n} leq n! leq e n^{n+frac{1}{2}}e^{-n}$$
So by numerically solving $n!=sqrt{2pi}x^{x+frac{1}{2}}e^{-x}$ and $n!=ex^{x+frac{1}{2}}e^{-x}$ we can find bounds for $n$.
add a comment |
For equations involving
large factorials,
I find the elementary inequalities
$(n/e)^n < n! < (n/e)^{n+1}$
often useful.
Once these have been used,
you can use
Stirling's approximation.
These can be proved
by induction from
the elementary inequalities
$(1+1/n)^n < e < (1+1/n)^{n+1}$.
2
So let's say 10 coloured marbles are placed in a row for example, what is the minimum number of colours needed to guarantee atleast 10000 different patterns?
– TripleA
Jan 1 '17 at 1:36
add a comment |
Would you be fine with an algorithm instead of a mathematical function?
Solve $nPx = p$ for $x$:
x = 0
while p > 1:
p /= n
n--
x++
return x
Solve $xPr = p$ for $x$:
x = r
while p > 1:
x++
p /= x
return x
Solve $x!=y$ for $x$:
x = 1
while y > 1:
x++
y /= x
return x
Your example problem can be modeled without the factorial function pretty easily. I'm assuming two marbles with the same color are indistinguishable, that we have at least 10 marbles of each color, and that the order of the marbles matters:
$$
x^{10}ge10000\
xge10000^{1/10}approx2.512\
x=3
$$
add a comment |
The inverse function of $y = x!$ means getting x in terms of $y$ , i.e $x =$ the largest number in factorisation of y as a factorial.(Where factorising as a factorial means you divide $y$ by $2$, then $3$ and so on. You stop when you get $1$) For example let $5040 = x! , x = ?$
Factoring $5040$ as a factorial $5040= 7times 6times 5times 4times 3times 2times 1$ , and $7$ is the largest number of that factorial $implies x = 7$
In your problem $8!/336 = (8 – r)! , r = ?$
$8!/336 = 120$ , let $(8 – r) = x$ , hence $120 = x! , x = ?$
$120 = 5times 4times 3times 2times 1$, and the largest number of that factorial $ = x = 5 = (8 – r) implies r = 3.$
Welcome to MSE. Please try to use MathJax -- it makes your answer more readable and increases the chance being read by other users.
– James
Dec 10 '18 at 13:12
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%2f2078997%2finverse-of-a-factorial%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
5 Answers
5
active
oldest
votes
5 Answers
5
active
oldest
votes
active
oldest
votes
active
oldest
votes
I just wrote this answer to an old question. Using $a=1$, we get a close inverse for the factorial function:
$$
nsim eexpleft(operatorname{W}left(frac1{e}logleft(frac{n!}{sqrt{2pi}}right)right)right)-frac12tag{1}
$$
1
And I just commented about it a few minutes ago ! Funny coïcidence !
– Claude Leibovici
Jan 1 '17 at 6:13
1
Just to add a small detail, robjohn's solution is strictly exact if we use $$n=leftlceil e^{Wleft(frac{log left(frac{n!}{sqrt{2 pi }}right)}{e}right)+1}-frac{1}{2}rightrceil$$
– Claude Leibovici
Jan 2 '17 at 4:51
1
@ClaudeLeibovici: if we know that $n$ is an integer. This is also a good inverse for $Gamma(n+1)$. $$nsim eexpleft(operatorname{W}left(frac1{e}logleft(frac{Gamma(n)}{sqrt{2pi}}right)right)right)+frac12$$ is an approximate inverse for $Gamma(n)$.
– robjohn♦
Jan 2 '17 at 6:58
It is so beautiful !
– Claude Leibovici
Jan 2 '17 at 8:13
add a comment |
I just wrote this answer to an old question. Using $a=1$, we get a close inverse for the factorial function:
$$
nsim eexpleft(operatorname{W}left(frac1{e}logleft(frac{n!}{sqrt{2pi}}right)right)right)-frac12tag{1}
$$
1
And I just commented about it a few minutes ago ! Funny coïcidence !
– Claude Leibovici
Jan 1 '17 at 6:13
1
Just to add a small detail, robjohn's solution is strictly exact if we use $$n=leftlceil e^{Wleft(frac{log left(frac{n!}{sqrt{2 pi }}right)}{e}right)+1}-frac{1}{2}rightrceil$$
– Claude Leibovici
Jan 2 '17 at 4:51
1
@ClaudeLeibovici: if we know that $n$ is an integer. This is also a good inverse for $Gamma(n+1)$. $$nsim eexpleft(operatorname{W}left(frac1{e}logleft(frac{Gamma(n)}{sqrt{2pi}}right)right)right)+frac12$$ is an approximate inverse for $Gamma(n)$.
– robjohn♦
Jan 2 '17 at 6:58
It is so beautiful !
– Claude Leibovici
Jan 2 '17 at 8:13
add a comment |
I just wrote this answer to an old question. Using $a=1$, we get a close inverse for the factorial function:
$$
nsim eexpleft(operatorname{W}left(frac1{e}logleft(frac{n!}{sqrt{2pi}}right)right)right)-frac12tag{1}
$$
I just wrote this answer to an old question. Using $a=1$, we get a close inverse for the factorial function:
$$
nsim eexpleft(operatorname{W}left(frac1{e}logleft(frac{n!}{sqrt{2pi}}right)right)right)-frac12tag{1}
$$
edited Apr 13 '17 at 12:20
Community♦
1
1
answered Jan 1 '17 at 3:50
robjohn♦robjohn
265k27303626
265k27303626
1
And I just commented about it a few minutes ago ! Funny coïcidence !
– Claude Leibovici
Jan 1 '17 at 6:13
1
Just to add a small detail, robjohn's solution is strictly exact if we use $$n=leftlceil e^{Wleft(frac{log left(frac{n!}{sqrt{2 pi }}right)}{e}right)+1}-frac{1}{2}rightrceil$$
– Claude Leibovici
Jan 2 '17 at 4:51
1
@ClaudeLeibovici: if we know that $n$ is an integer. This is also a good inverse for $Gamma(n+1)$. $$nsim eexpleft(operatorname{W}left(frac1{e}logleft(frac{Gamma(n)}{sqrt{2pi}}right)right)right)+frac12$$ is an approximate inverse for $Gamma(n)$.
– robjohn♦
Jan 2 '17 at 6:58
It is so beautiful !
– Claude Leibovici
Jan 2 '17 at 8:13
add a comment |
1
And I just commented about it a few minutes ago ! Funny coïcidence !
– Claude Leibovici
Jan 1 '17 at 6:13
1
Just to add a small detail, robjohn's solution is strictly exact if we use $$n=leftlceil e^{Wleft(frac{log left(frac{n!}{sqrt{2 pi }}right)}{e}right)+1}-frac{1}{2}rightrceil$$
– Claude Leibovici
Jan 2 '17 at 4:51
1
@ClaudeLeibovici: if we know that $n$ is an integer. This is also a good inverse for $Gamma(n+1)$. $$nsim eexpleft(operatorname{W}left(frac1{e}logleft(frac{Gamma(n)}{sqrt{2pi}}right)right)right)+frac12$$ is an approximate inverse for $Gamma(n)$.
– robjohn♦
Jan 2 '17 at 6:58
It is so beautiful !
– Claude Leibovici
Jan 2 '17 at 8:13
1
1
And I just commented about it a few minutes ago ! Funny coïcidence !
– Claude Leibovici
Jan 1 '17 at 6:13
And I just commented about it a few minutes ago ! Funny coïcidence !
– Claude Leibovici
Jan 1 '17 at 6:13
1
1
Just to add a small detail, robjohn's solution is strictly exact if we use $$n=leftlceil e^{Wleft(frac{log left(frac{n!}{sqrt{2 pi }}right)}{e}right)+1}-frac{1}{2}rightrceil$$
– Claude Leibovici
Jan 2 '17 at 4:51
Just to add a small detail, robjohn's solution is strictly exact if we use $$n=leftlceil e^{Wleft(frac{log left(frac{n!}{sqrt{2 pi }}right)}{e}right)+1}-frac{1}{2}rightrceil$$
– Claude Leibovici
Jan 2 '17 at 4:51
1
1
@ClaudeLeibovici: if we know that $n$ is an integer. This is also a good inverse for $Gamma(n+1)$. $$nsim eexpleft(operatorname{W}left(frac1{e}logleft(frac{Gamma(n)}{sqrt{2pi}}right)right)right)+frac12$$ is an approximate inverse for $Gamma(n)$.
– robjohn♦
Jan 2 '17 at 6:58
@ClaudeLeibovici: if we know that $n$ is an integer. This is also a good inverse for $Gamma(n+1)$. $$nsim eexpleft(operatorname{W}left(frac1{e}logleft(frac{Gamma(n)}{sqrt{2pi}}right)right)right)+frac12$$ is an approximate inverse for $Gamma(n)$.
– robjohn♦
Jan 2 '17 at 6:58
It is so beautiful !
– Claude Leibovici
Jan 2 '17 at 8:13
It is so beautiful !
– Claude Leibovici
Jan 2 '17 at 8:13
add a comment |
By Stirling's formula
$$n! sim sqrt{2pi n} left({frac{n}{e}}right)^n $$
So we can given a large $n!$ we can attempt to numerically solve,
$$n!=sqrt{2pi x} left({frac{x}{e}}right)^x$$
For $x$ by Newton's method to get an approximate inverse.
The function $mathbb{N} to mathbb{N}$ given by $f(n)=n!$ is increasing. Also,
$$sqrt{2pi}n^{n+frac{1}{2}}e^{-n} leq n! leq e n^{n+frac{1}{2}}e^{-n}$$
So by numerically solving $n!=sqrt{2pi}x^{x+frac{1}{2}}e^{-x}$ and $n!=ex^{x+frac{1}{2}}e^{-x}$ we can find bounds for $n$.
add a comment |
By Stirling's formula
$$n! sim sqrt{2pi n} left({frac{n}{e}}right)^n $$
So we can given a large $n!$ we can attempt to numerically solve,
$$n!=sqrt{2pi x} left({frac{x}{e}}right)^x$$
For $x$ by Newton's method to get an approximate inverse.
The function $mathbb{N} to mathbb{N}$ given by $f(n)=n!$ is increasing. Also,
$$sqrt{2pi}n^{n+frac{1}{2}}e^{-n} leq n! leq e n^{n+frac{1}{2}}e^{-n}$$
So by numerically solving $n!=sqrt{2pi}x^{x+frac{1}{2}}e^{-x}$ and $n!=ex^{x+frac{1}{2}}e^{-x}$ we can find bounds for $n$.
add a comment |
By Stirling's formula
$$n! sim sqrt{2pi n} left({frac{n}{e}}right)^n $$
So we can given a large $n!$ we can attempt to numerically solve,
$$n!=sqrt{2pi x} left({frac{x}{e}}right)^x$$
For $x$ by Newton's method to get an approximate inverse.
The function $mathbb{N} to mathbb{N}$ given by $f(n)=n!$ is increasing. Also,
$$sqrt{2pi}n^{n+frac{1}{2}}e^{-n} leq n! leq e n^{n+frac{1}{2}}e^{-n}$$
So by numerically solving $n!=sqrt{2pi}x^{x+frac{1}{2}}e^{-x}$ and $n!=ex^{x+frac{1}{2}}e^{-x}$ we can find bounds for $n$.
By Stirling's formula
$$n! sim sqrt{2pi n} left({frac{n}{e}}right)^n $$
So we can given a large $n!$ we can attempt to numerically solve,
$$n!=sqrt{2pi x} left({frac{x}{e}}right)^x$$
For $x$ by Newton's method to get an approximate inverse.
The function $mathbb{N} to mathbb{N}$ given by $f(n)=n!$ is increasing. Also,
$$sqrt{2pi}n^{n+frac{1}{2}}e^{-n} leq n! leq e n^{n+frac{1}{2}}e^{-n}$$
So by numerically solving $n!=sqrt{2pi}x^{x+frac{1}{2}}e^{-x}$ and $n!=ex^{x+frac{1}{2}}e^{-x}$ we can find bounds for $n$.
edited Jan 1 '17 at 14:56
Martin Sleziak
44.7k8115271
44.7k8115271
answered Jan 1 '17 at 1:32
Ahmed S. AttaallaAhmed S. Attaalla
14.8k12049
14.8k12049
add a comment |
add a comment |
For equations involving
large factorials,
I find the elementary inequalities
$(n/e)^n < n! < (n/e)^{n+1}$
often useful.
Once these have been used,
you can use
Stirling's approximation.
These can be proved
by induction from
the elementary inequalities
$(1+1/n)^n < e < (1+1/n)^{n+1}$.
2
So let's say 10 coloured marbles are placed in a row for example, what is the minimum number of colours needed to guarantee atleast 10000 different patterns?
– TripleA
Jan 1 '17 at 1:36
add a comment |
For equations involving
large factorials,
I find the elementary inequalities
$(n/e)^n < n! < (n/e)^{n+1}$
often useful.
Once these have been used,
you can use
Stirling's approximation.
These can be proved
by induction from
the elementary inequalities
$(1+1/n)^n < e < (1+1/n)^{n+1}$.
2
So let's say 10 coloured marbles are placed in a row for example, what is the minimum number of colours needed to guarantee atleast 10000 different patterns?
– TripleA
Jan 1 '17 at 1:36
add a comment |
For equations involving
large factorials,
I find the elementary inequalities
$(n/e)^n < n! < (n/e)^{n+1}$
often useful.
Once these have been used,
you can use
Stirling's approximation.
These can be proved
by induction from
the elementary inequalities
$(1+1/n)^n < e < (1+1/n)^{n+1}$.
For equations involving
large factorials,
I find the elementary inequalities
$(n/e)^n < n! < (n/e)^{n+1}$
often useful.
Once these have been used,
you can use
Stirling's approximation.
These can be proved
by induction from
the elementary inequalities
$(1+1/n)^n < e < (1+1/n)^{n+1}$.
answered Jan 1 '17 at 1:30
marty cohenmarty cohen
72.9k549128
72.9k549128
2
So let's say 10 coloured marbles are placed in a row for example, what is the minimum number of colours needed to guarantee atleast 10000 different patterns?
– TripleA
Jan 1 '17 at 1:36
add a comment |
2
So let's say 10 coloured marbles are placed in a row for example, what is the minimum number of colours needed to guarantee atleast 10000 different patterns?
– TripleA
Jan 1 '17 at 1:36
2
2
So let's say 10 coloured marbles are placed in a row for example, what is the minimum number of colours needed to guarantee atleast 10000 different patterns?
– TripleA
Jan 1 '17 at 1:36
So let's say 10 coloured marbles are placed in a row for example, what is the minimum number of colours needed to guarantee atleast 10000 different patterns?
– TripleA
Jan 1 '17 at 1:36
add a comment |
Would you be fine with an algorithm instead of a mathematical function?
Solve $nPx = p$ for $x$:
x = 0
while p > 1:
p /= n
n--
x++
return x
Solve $xPr = p$ for $x$:
x = r
while p > 1:
x++
p /= x
return x
Solve $x!=y$ for $x$:
x = 1
while y > 1:
x++
y /= x
return x
Your example problem can be modeled without the factorial function pretty easily. I'm assuming two marbles with the same color are indistinguishable, that we have at least 10 marbles of each color, and that the order of the marbles matters:
$$
x^{10}ge10000\
xge10000^{1/10}approx2.512\
x=3
$$
add a comment |
Would you be fine with an algorithm instead of a mathematical function?
Solve $nPx = p$ for $x$:
x = 0
while p > 1:
p /= n
n--
x++
return x
Solve $xPr = p$ for $x$:
x = r
while p > 1:
x++
p /= x
return x
Solve $x!=y$ for $x$:
x = 1
while y > 1:
x++
y /= x
return x
Your example problem can be modeled without the factorial function pretty easily. I'm assuming two marbles with the same color are indistinguishable, that we have at least 10 marbles of each color, and that the order of the marbles matters:
$$
x^{10}ge10000\
xge10000^{1/10}approx2.512\
x=3
$$
add a comment |
Would you be fine with an algorithm instead of a mathematical function?
Solve $nPx = p$ for $x$:
x = 0
while p > 1:
p /= n
n--
x++
return x
Solve $xPr = p$ for $x$:
x = r
while p > 1:
x++
p /= x
return x
Solve $x!=y$ for $x$:
x = 1
while y > 1:
x++
y /= x
return x
Your example problem can be modeled without the factorial function pretty easily. I'm assuming two marbles with the same color are indistinguishable, that we have at least 10 marbles of each color, and that the order of the marbles matters:
$$
x^{10}ge10000\
xge10000^{1/10}approx2.512\
x=3
$$
Would you be fine with an algorithm instead of a mathematical function?
Solve $nPx = p$ for $x$:
x = 0
while p > 1:
p /= n
n--
x++
return x
Solve $xPr = p$ for $x$:
x = r
while p > 1:
x++
p /= x
return x
Solve $x!=y$ for $x$:
x = 1
while y > 1:
x++
y /= x
return x
Your example problem can be modeled without the factorial function pretty easily. I'm assuming two marbles with the same color are indistinguishable, that we have at least 10 marbles of each color, and that the order of the marbles matters:
$$
x^{10}ge10000\
xge10000^{1/10}approx2.512\
x=3
$$
edited Jan 1 '17 at 3:39
answered Jan 1 '17 at 3:19
TheNumberOneTheNumberOne
26818
26818
add a comment |
add a comment |
The inverse function of $y = x!$ means getting x in terms of $y$ , i.e $x =$ the largest number in factorisation of y as a factorial.(Where factorising as a factorial means you divide $y$ by $2$, then $3$ and so on. You stop when you get $1$) For example let $5040 = x! , x = ?$
Factoring $5040$ as a factorial $5040= 7times 6times 5times 4times 3times 2times 1$ , and $7$ is the largest number of that factorial $implies x = 7$
In your problem $8!/336 = (8 – r)! , r = ?$
$8!/336 = 120$ , let $(8 – r) = x$ , hence $120 = x! , x = ?$
$120 = 5times 4times 3times 2times 1$, and the largest number of that factorial $ = x = 5 = (8 – r) implies r = 3.$
Welcome to MSE. Please try to use MathJax -- it makes your answer more readable and increases the chance being read by other users.
– James
Dec 10 '18 at 13:12
add a comment |
The inverse function of $y = x!$ means getting x in terms of $y$ , i.e $x =$ the largest number in factorisation of y as a factorial.(Where factorising as a factorial means you divide $y$ by $2$, then $3$ and so on. You stop when you get $1$) For example let $5040 = x! , x = ?$
Factoring $5040$ as a factorial $5040= 7times 6times 5times 4times 3times 2times 1$ , and $7$ is the largest number of that factorial $implies x = 7$
In your problem $8!/336 = (8 – r)! , r = ?$
$8!/336 = 120$ , let $(8 – r) = x$ , hence $120 = x! , x = ?$
$120 = 5times 4times 3times 2times 1$, and the largest number of that factorial $ = x = 5 = (8 – r) implies r = 3.$
Welcome to MSE. Please try to use MathJax -- it makes your answer more readable and increases the chance being read by other users.
– James
Dec 10 '18 at 13:12
add a comment |
The inverse function of $y = x!$ means getting x in terms of $y$ , i.e $x =$ the largest number in factorisation of y as a factorial.(Where factorising as a factorial means you divide $y$ by $2$, then $3$ and so on. You stop when you get $1$) For example let $5040 = x! , x = ?$
Factoring $5040$ as a factorial $5040= 7times 6times 5times 4times 3times 2times 1$ , and $7$ is the largest number of that factorial $implies x = 7$
In your problem $8!/336 = (8 – r)! , r = ?$
$8!/336 = 120$ , let $(8 – r) = x$ , hence $120 = x! , x = ?$
$120 = 5times 4times 3times 2times 1$, and the largest number of that factorial $ = x = 5 = (8 – r) implies r = 3.$
The inverse function of $y = x!$ means getting x in terms of $y$ , i.e $x =$ the largest number in factorisation of y as a factorial.(Where factorising as a factorial means you divide $y$ by $2$, then $3$ and so on. You stop when you get $1$) For example let $5040 = x! , x = ?$
Factoring $5040$ as a factorial $5040= 7times 6times 5times 4times 3times 2times 1$ , and $7$ is the largest number of that factorial $implies x = 7$
In your problem $8!/336 = (8 – r)! , r = ?$
$8!/336 = 120$ , let $(8 – r) = x$ , hence $120 = x! , x = ?$
$120 = 5times 4times 3times 2times 1$, and the largest number of that factorial $ = x = 5 = (8 – r) implies r = 3.$
edited Dec 10 '18 at 13:25
amWhy
192k28225439
192k28225439
answered Dec 10 '18 at 12:21
A.EribaA.Eriba
1
1
Welcome to MSE. Please try to use MathJax -- it makes your answer more readable and increases the chance being read by other users.
– James
Dec 10 '18 at 13:12
add a comment |
Welcome to MSE. Please try to use MathJax -- it makes your answer more readable and increases the chance being read by other users.
– James
Dec 10 '18 at 13:12
Welcome to MSE. Please try to use MathJax -- it makes your answer more readable and increases the chance being read by other users.
– James
Dec 10 '18 at 13:12
Welcome to MSE. Please try to use MathJax -- it makes your answer more readable and increases the chance being read by other users.
– James
Dec 10 '18 at 13:12
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%2f2078997%2finverse-of-a-factorial%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
3
Stirling approximation.
– Simply Beautiful Art
Jan 1 '17 at 1:30
1
"In a row" would seem to imply that "blue, red, red, red, red, red, red, red, red, red" and "red, blue, red, red, red, red, red, red, red, red" are different patterns. If so, factorials are not applicable. Of course there are other combinatorial problems that involve large factorials to which your question still applies.
– David K
Jan 1 '17 at 2:01
1
FWIW, I posted a Python 2 function that uses Stirling's approximation & the Newton-Raphson method to invert log factorial here.
– PM 2Ring
Jan 1 '17 at 3:11
1
@TripleA, why do you say the answer is $4$? There is nothing wrong in Ross Millikan's analysis for the add-on question as it is stated: $3^{10}=59{,}049gt10{,}000$. So unless you have some nonstandard definition of what's required for two patterns to be considered "different," the answer is $3$.
– Barry Cipra
Jan 3 '17 at 1:48
1
@TripleA, ah, I see what you mean now. It would help to edit the add-on question to clarify that the different patterns must all come from a single choice of $10$ marbles of various diffferent colors. Both Ross and I interpreted it as meaning that each pattern is simply an assignment of an allowed color to each marble.
– Barry Cipra
Jan 3 '17 at 2:52