C(n,r) Seeing Negative?Date: 06/11/2010 at 09:18:53 From: Rick Subject: Combination Function for r > n The combination function nCr is defined as the number of ways that subsets containing r objects may be formed from a set containing n objects. The formula which I invariably see on the web or in textbooks for calculating nCr is n! / [r! * (n - r)!] This formula requires that r not be greater than n to avoid the error of calculating the factorial of a negative number. However, I've noticed that calculators do allow you to compute nCr for r > n. On the one hand, this is logical. If r > n, then the number of ways to form a set of r objects from the set of n objects is zero, since it can't be done. The calculators appear to use a piecewise formula for nCr, where nCr is defined as above (with factorials) for 0 < r <= n but is equal to 0 for r > n. So what is the "true" form of the combination function? Is r never supposed to be greater than n, even though the calculators are programmed to work around it? Or is r truly allowed to take any non-negative value, but this fact is usually skipped in textbooks? Date: 06/12/2010 at 01:50:39 From: Doctor Vogler Subject: Re: Combination Function for r > n Hi Rick, Thanks for writing to Dr Math. There is no "true" form of the combination function. But various formulas used to define the combination function can be extended to different types of arguments. For example, as you pointed out, nCr = n! / [r! * (n - r)!] is defined when n and r are integers and 0 <= r <= n. But nCr = n(n - 1)(n - 2)(n - 3) ... (n - (r + 1)) / r! is defined whenever r is a non-negative integer. And nCr = n(n - 1)(n - 2)(n - 3) ... (r + 1) / (n - r)! is defined whenever n - r is a non-negative integer. In fact, if n is a positive integer, and r is any integer, then at least one of those two formulas will be defined. When n >= 0, these formulas are also consistent with extending nCr by the recurrence relations nCr = (n - 1)C(r - 1) + (n - 1)C(r). Unfortunately, things break down when you try to extend to n < 0, since then the recurrence relation gives (0)C(0) = (-1)C(-1) + (-1)C(0) and all three of those values should be 1 according to the rule nCr = 1 when r = n or r = 0. We can also extend to non-integer values by using the gamma function: nCr = gamma(n + 1) / [gamma(r + 1) * gamma(n - r + 1)] That formula even makes sense for complex numbers r and n, although the gamma function is infinite at non-positive (real) integers. Fortunately, complex analysis has consistent ways of dealing with infinities, and the result is: (one infinity, in the numerator) nCr = infinity, if n is a negative integer and r is not an integer (one infinity, in the denominator) nCr = 0, if r is a negative integer, and n is not (i.e., n is either non-negative or not an integer) nCr = 0, if n - r is a negative integer, and n (equivalently, r) is not an integer (three infinities) nCr = 0, if n < r < 0 and both n and r are integers (Note that if there are two infinities in the denominator, then the numerator has one too) The last remaining cases are: (a) when n and r are both integers, and r <= n < 0 (b) when n and r are both integers, and n < 0 <= r And these both result in the same values given by the two formulas above: (a) nCr = n(n - 1)(n - 2)(n - 3) ... (r + 1) / (n - r)! (b) nCr = n(n - 1)(n - 2)(n - 3) ... (n - (r + 1)) / r! It is interesting to note that these formulas satisfy the rules nCr = 1 when r = n or r = 0, and therefore they don't always satisfy the recurrence relation. If you have any questions about this or need more help, please write back and show me what you have been able to do, and I will try to offer further suggestions. - Doctor Vogler, The Math Forum http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/