The combinatorial function

- 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.

I presume enough familiarity with college algebra that p

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

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
^{n}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^{n}).

0! 1! 2! 3! 4! 5! 6! 7! 8! 1 1 2 6 24 120 720 5040 40320 - Explain why the definition of factorial dictates when the combinatorial function
C(n,k) is defined. State whenC(n,k) is defined, without any reference to the factorial function. All further exercises assume that all uses ofC(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) as the definition of the combinatorial function^{n}=S p_{k=0..n}C(n,k)^{k}q^{n-k}C(n,k) . Do what he did: derive the factorial definition ofC(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 aboutC(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 functionC(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 byP(n,k) . This denotes the number of ways to choose k items from n items, tracking the order of choice as well. We then haveC(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 computeC(n,k) . What are the base cases for this relation?]

Zaimoni.com site map |

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