Combinatorial and Factorial Functions: A Crash Review

• Is used to enable a concise statement of the Binomial Theorem using symbolic notation.
• Denotes the number of ways to choose k items from n items, regardless of order.

• Is used to define C(n,k).
• Denotes the number of possible orders [permutations] for n distinct items.
• Shows up in other formulae that ultimately come from statistics.

S_k=0..m means the sum of the terms indexed by k, where k is an integer from 0 to the (positive) integer m>0. If the pattern for the terms is declared elsewhere, it may be replaced with +...+ .

The combinatorial function C(n,k) is defined as n!/[k!(n-k)!], where n! is the factorial function.

In turn, the factorial function n! is defined as the product of the consecutive integers from 1 to n.

• This definition applies to positive integers n.
• If n is 0, we presume that taking a product with no terms in it evaluates to the number 1. This is a typical 'definition' from Abstract Algebra, but it doesn't always work in non-algebraic contexts.
• n! is not defined for negative integers n, or for real numbers not already mentioned.
• The gamma function G(x) is used to generalize the factorial function to all other real numbers. This is not worth going into here...although I should mention that n!=G(n+1) for all non-negative integers n. G(x) is undefined for (and unbounded near) all non-positive integers x.

EXERCISES:
Computer and Information Science

• n! grows faster than the exponential function c·aⁿ for sufficiently large n, for any constant real base a>1 and positive real constant c. This means that O(n!) is a worse algorithm class than O(aⁿ).

• 0!	1!	2!	3!	4!	5!	6!	7!	8!
  1	1	2	6	24	120	720	5040	40320

  Verify that this factorial table is correct. Then memorize it.
• Explain why the definition of factorial dictates when the combinatorial function C(n,k) is defined. State when C(n,k) is defined, without any reference to the factorial function. All further exercises assume that all uses of C(n,k) are defined.
• [This requires familiarity with (weak) natural induction.] Blaise Pascal was familiar with C(n,k) as the binomial coefficients. He took the binomial theorem (for real numbers p,q) (p+q)ⁿ = S_k=0..n C(n,k)p^kq^n-k as the definition of the combinatorial function C(n,k). Do what he did: derive the factorial definition of C(n,k) from the binomial theorem.
• [This requires familiarity with (weak) natural induction.] To complete the verification that the two "definitions" are equally effective, derive the binomial theorem using the factorial definition for C(n,k). Implicit exercise for all exercises about C(n,k): determine which "definition" [the binomial theorem, or the definition in terms of factorial] is simpler to use for verification. You must work it both ways before deciding. This particular implicit exercise doesn't have 'right' or 'wrong' answers; it's more to give you a chance to exercise your sense of mathematical aesthetics. [If you don't understand (weak) natural induction, you may use the implicit exercise anyway.]
• Explain why C(n,k)=C(n,n-k). After working this, an implicit exercise for all exercises using the combinatorial function C(n,k) is to determine when this identity may be used to construct an alternate exercise.
• C(n,0)=1
• C(n,1)=n
• In general, C(n,k) is the product of the integers from n to n-k+1 (inclusive, in decreasing order), divided by k!. [We can denote the product of the integers from n to n-k+1 by P(n,k). This denotes the number of ways to choose k items from n items, tracking the order of choice as well. We then have C(n,k) = P(n,k)/k! . P(n,0) is always a product with zero factors, so we assume it evaluates to 1.]
• C(n,k) = C(n-1,k-1)+C(n-1,k) [This is a recursion relation i.e. recurrence relation that can be used to compute C(n,k). What are the base cases for this relation?]

Return to the Math page, the Iskandria mass event resolution page, or the main page.