Combinatorial and Factorial Functions: A Crash Review
The combinatorial function C(n,k) ["n choose k"]:
- 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.
The factorial function n! ["n factorial"]:
- 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.
I presume enough familiarity with college algebra that pkqn-k is recognized
as "p to the kth power, times q to the power of n-k".
Sk=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.
For all exercises involving variables, one variant is to deliberately work enough concrete
examples to develop a physical intuition for the problem statement.
EXERCISES:
Computer and Information Science
- n! grows faster than the exponential function c·an 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(an).
College Algebra
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)n = Sk=0..n C(n,k)pkqn-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?]
Opinions, comments, criticism, etc.? Let me know about it.
Return to the Math page, the Iskandria mass event resolution page, or the main page.