I am trying to attempt to solve this problem but I am unsure what this equation means:
$$\frac{n!}{ r!(n-r)!}$$
What do the exclamation marks mean in the above?
Asked
Active
Viewed 327 times
0
-
2See Factorial in wikipedia. – J.-E. Pin Jul 25 '15 at 09:07
-
1The answers below all address your notation question. None discusses it as a programming question. Computing those factorials is not a good way to compute the final answer. There are lots of others. A course in data structures and algorithms will discuss the pros and cons. – Ethan Bolker Jul 25 '15 at 11:25
-
@EthanBolker why is computing the factorials not a good way? Do you know of any courses in data structures and algorithms? – dagda1 Jul 25 '15 at 12:34
-
To actually compute combinations, you can use the formula on the right-hand side of the equation in Prove that the combination formula can be reduced to…. – David K Jul 25 '15 at 13:19
-
What David K said, although (using the notation in that link) rather than using $k$ you should use the minimum of $k$ and $(m-k)$. Also, the iteration on the denominators should ascend so you can get exact results using integer division. – PM 2Ring Jul 25 '15 at 15:08
-
@dagd1 The reason you shouldn't compute it naively from the definition is that factorials get really large very quickly (50 factorial has 65 digits), so you end up either a) overflowing your machine precision and getting inaccuracies or run-time errors, or b) spending needless effort dealing with high-precision large numbers when the final answer is often much smaller. – Erick Wong Jul 25 '15 at 16:22
-
See http://www.csl.mtu.edu/cs4321/www/Lectures/Lecture%2015%20-%20Dynamic%20Programming%20Binomial%20Coefficients.htm. – Ethan Bolker Jul 26 '15 at 00:36
-
"I am unsure what this equation means." What you wrote is not an equation, but an expression. – JRN Jul 29 '15 at 00:45
5 Answers
3
As @johannesvalks said, the formula is $$n! = 1\times 2 \times 3 \times 4 \cdots \times n$$
And the function is named factorial. We define $0!=1$.
However there is also a combinatorial description. $n!$ is namely the number of ways to order $n$ different objects. We can see that as following: there are $n$ possibilities for the first place. Then we've used already 1 object, so there are $n-1$ possibilities for the second place. Then we've used already 2 objects, so there are $n-2$ possibilities for the third place. This goes on until there are no objects left, so we indeed multiply the numbers 1 through $n$.
The expression
$$\frac{n!}{(n-r)!\cdot r!}$$
Also has a combinatorial description. This is the ways to choose $r$ objects out of $n$ where the order of choosing doesn't matter.
wythagoras
- 25,026
2
They mean factorial, defined as
$$ n! = 1 \cdot 2 \cdot 3 \cdot 4 \cdots (n-1) \cdot n $$
Like $$4! = 1 \cdot 2 \cdot 3 \cdot 4 = 24 $$
johannesvalks
- 6,407
2
As explained, its a symbol meaning factorial and defined as:
$$ n! =\prod_{k=1}^{n}k = n(n-1)(n-2)\cdots 2 \cdot1 $$
e.g.
$$3! = 3\times2\times1, \ 0! = 1$$
They have very interesting applications in probability theory (see binomial theorem), series (see definition of trigonometric functions, taylor series), combinatorics, etc.
John_dydx
- 4,198
1
This means $^nC_r$. This is the formula for calculating the number of ways of "choosing" $r$ objects out of $n$ objects where order does not matter and $r$ is less than or equal to $n$. The $!$ you are asking about is called factorial. Which means the product of all the numbers before it. We define $0!=1$. Also to calculate factorials of $1, 0.5$ etc, gamma function is used. Talking about the $^nC_r$ formula, you can take the example of finding the number of ways of choosing a committee of $3$ people from $5$ people $A,B,C,D$ & $E$. So answer is $^5C_3=\frac{5!}{3!(5-3)!}=10$. So $10$ is the answer here.
You may want to take a look at these-
$0!=1$
$1!=1$
$2!=2$
$3!=6$
$4!=24$
$5!=120$
$6!=720$
$7!=5040$
$8!=40320$
Aditya Agarwal
- 4,595
-
1
-
@user21820: It is not unreasonable to define $(-n)! = \infty$ (projective infinity) when $n$ is a positive integer. This is consistent with the recursion ($0! = 0 \cdot (-1)!$ is indeterminate) and with $\Gamma(0) = \infty$. And most of the time you would even consider $(-1)!$ in a real problem either you want to know the result blows up, or you're dividing by $(-1)!$ and want to get $0$ as the result. – Jul 25 '15 at 13:40
-
@Hurkyl: Yes I know about the complex projective line (Riemann sphere) but does the asker? It would be misleading to imply that $(-1)!$ has a value, unless you know that the asker knows what kind of value you are talking about. No? By the way, since when did we need to divide by $(-1)!$? – user21820 Jul 25 '15 at 13:42
-
@user21820: It is also misleading to deny there is any such thing as $(-1)!$ :P. For a simple example of dividing by $(-1)!$, it lets us continue to use the usual formula to obtain $\binom{n}{-1} = \binom{n}{n+1} = 0$ when $n$ is a nonnegative integer. – Jul 25 '15 at 13:44
-
@Hurkyl: In my opinion we have to explain whatever is rather certainly misleading to the audience, otherwise not stating it is better. Following your lead, we have $\binom{-1}{-1} = \binom{-1}{0} = \frac{(-1)!}{(-1)!0!} = 1$. Are you sure that makes sense? $\binom{-1}{0} + \binom{-1}{-1} = 2$. How is that useful? I don't really see your point, because you are saying that you want to use the usual formula for negative numbers, but then you exclude negative $n$. – user21820 Jul 25 '15 at 13:59
-
@user21820: $\infty/\infty$ is not in the domain of division, so that formula is not defined at $\binom{-1}{-1}$ even if you wanted to use it there. Also, there is no logic in dismissing a generalization to all integer $r$ simply because it doesn't simultaneously generalize to all integer $n$: "don't let the perfect be the enemy of the good". Arbitrary integer $r$ even with nonnegative $n$ is is an important case, since the methods for doing more involved manipulations of summations are easier if you work with sums over all integers:e.g.$\sum_r\binom{n}{r}x^n$ not $\sum_{r=0}^n\binom{n}{r}x^n$ – Jul 25 '15 at 19:21
-
But anyways, the entire reason I brought up this tangent is because it is misleading to the audience to flat out say "there is no such thing as the factorial of $-1$!". – Jul 25 '15 at 19:30
-
I am so sorry, I meant to say that domain of gamma function includes $-1$. – Aditya Agarwal Jul 26 '15 at 07:49
-
@Hurkyl: I know that fact about $\infty$, but you see most people don't if you don't carefully define division and expect them to guess how you want to extend the usual division. I of course know which binomial coefficients are more useful than others, but your statement "let us continue to use the usual formula" gives the unwary reader no hint about when the usual formula can be extended. Also, my very first comment was simply a cheeky one to demonstrate the imprecision inherent in "to calculate the factorial of $-1$". To clarify my cheeky comment.. "$(-1)!$ is not a real thing." =D – user21820 Jul 26 '15 at 13:13
0
$n!$ is the factorial function, defined on natural numbers by
$$ n! = n \cdot (n-1) \cdot \ldots \cdot 2 \cdot 1 $$
(the empty product is $1$; consequently $0! = 1$).
The particular formula
$$ \frac{n!}{r!(n-r)!} $$
computes the binomial coefficient $\binom{n}{r}$ whenever $n,r$ are integers with $0 \leq r \leq n$, which has many applications, such as computing combinations: $\binom{n}{r} = {}_nC_r$, the number of ways to choose a set of $r$ elements out of a set of $n$ (distinguishable) elements.
Sometimes this notation is mildly abused to mean
$$ \frac{n}{1} \cdot \frac{n-1}{2} \cdot \frac{n-2}{3} \cdot \ldots \cdot \frac{n-r+2}{r-1} \cdot \frac{n-r+1}{r} $$
which is still the binomial coefficient $\binom{n}{r}$, but is well-defined whenever $r$ is a natural number, no matter what $n$ is. e.g. I've seen polynomials written using this.
This abuse of notation also happens with just $n! / (n-r)!$.
Sometimes, $n!$ is an abuse of notation to mean $\Gamma(n+1)$, where $\Gamma$ is the "gamma function". While $\Gamma(n+1) = n!$ for every natural number $n$, $\Gamma(z)$ is defined for all complex numbers $z$. (and has simple poles at the nonnegative integers)