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/