|
|
| Line 129: |
Line 129: |
| ===Binomial Coefficients=== | | ===Binomial Coefficients=== |
|
| |
|
| The combinations of n objects taken k at a time are the possible choices of k different elements from a collection of n items.
| | See [[AOCP/Binomial Coefficients]] |
| | |
| The number of combinations is described by the binomial coefficient <math>\binom{n}{k}</math>
| |
| | |
| <math>
| |
| \binom{n}{k} = \dfrac{n!}{k! (n-k)!}
| |
| </math>
| |
| | |
| We can define the binomial coefficient for the case when n is not an integer. Define:
| |
| | |
| <math>
| |
| \binom{r}{k} = \dfrac{r(r-1)(\dots)(r-k+1)}{k(k-1)\dots(1)} = \prod_{1 \leq j \leq k} \left( \frac{r+1-j}{j} \right) \qquad k \in \mathbb{Z}, k \geq 0
| |
| </math>
| |
| | |
| <math>
| |
| \binom{r}{k} = 0 \qquad k < 0
| |
| </math>
| |
| | |
| Computing these numbers in a table leads to Pascal's Triangle.
| |
| | |
| Binomial coefficients satisfy thousands of identities; these can be classified as follows:
| |
| * Representation by factorials
| |
| * Symmetry condition
| |
| * Moving in and out of brackets
| |
| * Addition formulas
| |
| * Summation formulas
| |
| * Binomial theorem
| |
| * negating upper index
| |
| * Sums of products
| |
| | |
| ====Representation by Factorials====
| |
| | |
| <math>
| |
| \binom{n}{k} = \dfrac{n!}{k! (n-k)!}
| |
| </math>
| |
| | |
| Holds for integers n and k >= 0
| |
| | |
| ====Symmetry Condition====
| |
| | |
| <math>
| |
| \binom{n}{k} = \binom{n}{n-k}
| |
| </math>
| |
| | |
| Holds for all integers k.
| |
| | |
| ====Moving In and Out of Brackets====
| |
| | |
| <math>
| |
| \binom{r}{k} = \frac{r}{k} \binom{r-1}{k-1} \qquad k \neq 0
| |
| </math>
| |
| | |
| This is useful for combining binomial coefficient with other parts of an expression.
| |
| | |
| By elementary transformation, we have:
| |
| | |
| <math>
| |
| k \binom{r}{k} = r \binom{r-1}{k-1}
| |
| </math>
| |
| | |
| valid for all integers k, and
| |
| | |
| <math>
| |
| \frac{1}{r} \binom{r}{k} = \frac{1}{k} \binom{r-1}{k-1}
| |
| </math>
| |
| | |
| valid when not dividing by zero.
| |
| | |
| Similarly:
| |
| | |
| <math>
| |
| \binom{r}{k} = \dfrac{r}{r-k} \binom{r-1}{k}
| |
| </math>
| |
| | |
| for k != r.
| |
| | |
| ====Addition formulas====
| |
| | |
| To add binomials, we have
| |
| | |
| <math>
| |
| \binom{r}{k} = \binom{r-1}{k} + \binom{r-1}{k-1}
| |
| </math>
| |
| | |
| for integer k. This is equivalent to summing the two entries in Pascal's triangle above to the left and above to the right.
| |
| | |
| Alternatively, we have:
| |
| | |
| <math>
| |
| r \binom{r-1}{k} + r \binom{r-1}{k-1} = (r-k) \binom{r}{k} + k \binom{r}{k} = r \binom{r}{k}
| |
| </math>
| |
| | |
| This is useful for proofs by induction on r, when r is an integer.
| |
| | |
| ====Summation formulas====
| |
| | |
| Two important summation formulas. The first comes from applying the summation identity given above, repeatedly:
| |
| | |
| <math>
| |
| \sum_{0 \leq k \leq n} \binom{r+k}{k} = \binom{r}{0} + \binom{r+1}{1} + \dots + \binom{r+n}{n} = \binom{r+n+1}{n} \qquad n \geq 0
| |
| </math>
| |
| | |
| We also have:
| |
| | |
| <math>
| |
| \sum_{0 \geq k \geq m} \binom{k}{m} = \binom{0}{m} + \binom{1}{m} + \dots + \binom{n}{m} = \binom{n+1}{m+1}
| |
| </math>
| |
| | |
| Valid for integer m and integer n, both >= 0.
| |
| | |
| ====Deriving summation identities====
| |
| | |
| Suppose we wish to compute the sum <math>1^2 + 2^2 + \dots + n^2</math>.
| |
| | |
| Solve this by recognizing that <math>k^2 = 2 \binom{k}{2} + \binom{k}{1}</math>
| |
| | |
| Therefore, we have:
| |
| | |
| <math>
| |
| \sum_{0 \leq k \leq n} k^2 = \sum_{0 \leq k \leq n} \left( 2 \binom{k}{2} + \binom{k}{1} \right) = 2 \binom{n+1}{3} + \binom{n+1}{2}
| |
| </math>
| |
| | |
| This simplifies back to polynomial notation as:
| |
| | |
| <math>
| |
| \sum_{0 \leq k \leq n} k^2 = 2 \dfrac{(n+1)n(n-1)}{6} + \dfrac{(n+1)n}{2}
| |
| </math>
| |
| | |
| which becomes:
| |
| | |
| <math>
| |
| \sum_{0 \leq k \leq n} k^2 = \dfrac{1}{3} n (n + \dfrac{1}{2})(n+1)
| |
| </math>
| |
| | |
| Any polynomial of the form <math>a_0 + a_1 k + a_2 k^2 + \dots + a_m k^m</math> can be expressed as <math>b_0 \binom{k}{0} + b_1 \binom{k}{1} + \dots + b_m \binom{k}{m}</math>.
| |
| | |
| ====Binomial Theorem====
| |
| | |
| The binomial theorem is extremely useful:
| |
| | |
| <math>
| |
| \left( x + y \right)^n = \sum_{0 \leq k \leq r} \binom{r}{k} x^k y^{r-k}
| |
| </math>
| |
| | |
| for integer r >= 0.
| |
| | |
| Note that we can also express
| |
| | |
| <math>
| |
| \sum_{0 \leq k \leq r} = \sum_{k}
| |
| </math>
| |
| | |
| since if k < 0 or k > r the expressions go to zero.
| |
| | |
| The caes of y = 1 is:
| |
| | |
| <Math>
| |
| \sum_k \binom{r}{k} x^k = \left( 1 + x \right)^r
| |
| </math>
| |
| | |
| for integer r >= 0 or |x| < 0
| |
| | |
| Isaac Newton discovered the binomial theorem in 1676. First attempted proof was by Euler in 1774. Gauss gave first actual proof in 1812.
| |
| | |
| Abel found a generalization of the formula:
| |
| | |
| <math>
| |
| (x+y)^r = \sum_k \binom{r}{k} x (x-kz)^{k-1} (y+kz)^{r-k}
| |
| </math>
| |
| | |
| for integer r>=0, x != 0
| |
| | |
| ====Negating Upper Index====
| |
| | |
| <math>
| |
| \binom{-r}{k} = (-1)^k \binom{r+k-1}{k} \qquad k \in \mathbb{Z}
| |
| </math>
| |
| | |
| This can be used, for example, to show:
| |
| | |
| <math>
| |
| \sum_{k \leq n} \binom{r}{k} (-1)^k = \binom{r}{0} - \binom{r}{1} + \dots + (-1)^n \binom{r}{n}
| |
| </math>
| |
| | |
| and therefore, for integer n >= 0, we have
| |
| | |
| <math>
| |
| \sum_{k \leq n} \binom{r}{k} (-1)^k = (-1)^n \binom{r-1}{n}
| |
| </math>
| |
| | |
| Prove this by showing:
| |
| | |
| <math>
| |
| \sum_{k \leq n} \binom{r}{k} (-1)^k = \sum_{k \leq n} \binom{-r+k-1}{k} = \binom{-r+n}{n} = (-1)^n \binom{r-1}{n}
| |
| </math>
| |
| | |
| further, when r is an integer, we can also write:
| |
| | |
| <math>
| |
| \binom{n}{m} = (-1)^{n-m} \binom{-(m+1)}{n-m} \qquad m, n \in \mathbb{Z}, n \geq 0
| |
| </math>
| |
| | |
| ====Simplifying Products====
| |
| | |
| <math>
| |
| \binom{r}{m} \binom{m}{k} = \binom{r}{k} \binom{r-k}{m-k}
| |
| </math>
| |
| | |
| This holds for integer m and integer k.
| |
| | |
| If we know <math>r \geq m, 0 \leq k \leq m</math>, then the following identity holds:
| |
| | |
| <math>
| |
| \begin{align}
| |
| \binom{r}{m}{m}{k} &=& \dfrac{r! m!}{ m! (r-m)! k! (m-k)! } \\
| |
| &=& \dfrac{r!(r-k)!}{k!(r-k)! (m-k)! (r-m)!}
| |
| \end{align}
| |
| </math>
| |
| | |
| all of which leads to:
| |
| | |
| <math>
| |
| \binom{r}{m} \binom{m}{k} = \binom{r}{k} \binom{r-k}{m-k}
| |
| </math>
| |
| | |
| ====Sums of Products====
| |
| | |
| If we need to sum over the products of binomial coefficients, we have several identities, of which the most important is:
| |
| | |
| <math>
| |
| \sum_k \binom{r}{k} \binom{s}{n-k} = \binom{r+s}{n}
| |
| </math>
| |
| | |
| This should be memorized. Interpret the right hand side as the number of ways to select n people from among r men and s women.
| |
| | |
| Each term on the left side is a number of ways to choose k of the men and n-k of the women.
| |
| | |
| Vandermonde's convolution - published by Vandermonde in 1772.
| |
| | |
| Further identities:
| |
| | |
| <math>
| |
| \sum_{k} \binom{r}{k} \binom{s}{n+k} = \binom{r+s}{r+n} \qquad r, n \in \mathbb{Z}, r \neq 0
| |
| </math>
| |
| | |
| <math>
| |
| \sum_{k} \binom{r}{k} \binom{s+k}{n} (-1)^k = (-1)^r \binom{s}{n-r} \qquad n, r \in \mathbb{Z}, r \geq 0
| |
| </math>
| |
|
| |
|
| =Flags= | | =Flags= |
Volume 1
Chapter 1: Basic Concepts
Permutations and Factorials
If we have n distinct objects to arrange in a row, and order of placement matters, we can arrange these things in n! different ways.
For the first object, we have n choices of places to put it. For the second object, we have n-1 choices of places to put it. And so on.
In general, if we have to choose k objects out of n total, and arrange them in a row, we have the number of possibilities as:
$ p_{n,k} = n(n-1)(\dots)(n-k+1) $
The total number of permutations is
$ p_{n,n} = n (n-1) \dots (2)(1) $
The process of constructing a permutation of n objects, given all permutations of n-1 objects, is important. If we consider the case of three objects $ \{1, 2, 3\} $,
Here are permutations of order 3:
$ (1 2 3), (1 3 2), (2 1 3), (2 3 1), (3 1 2), (3 2 1) $
Now, how to get to permutations of 4 objects?
Method 1:
For each permutation of n-1 elements, form n additional permutations by inserting the nth element in every possible open slot
Adding 4 to our set of objects and using method 1 gives:
$ (4 2 3 1), (2 4 3 1), (2 3 4 1), (2 3 1 4) $
Method 2:
For each permutation of the n-1 elements, form n new permutations by first constructing the array:
$ \begin{align} a_1 a_2 \dots a_{n-1} &\quad& \frac{1}{2} \\ a_1 a_2 \dots a_{n-1} &\quad& \frac{3}{2} \\ &\dots& \\ a_1 a_2 \dots a_{n-1} &\quad& (n - \frac{1}{2}) \end{align} $
Aaaaaand... yeah. No idea.
Factorial Identities
Factorial definition:
$ n! = 1 \cdot 2 \dots n = \prod_{1 \leq k \leq n} k $
$ 0! = 1 $
and with this convention,
$ n! = (n-1)! n $
for all positive integers n.
10! is a useful benchmark - it is around 3.5 million.
$ 10! = 3,628,800 $
10! represents an upper ceiling on computable tasks.
To tell how large a very big factorial is going to be, use Stirling's formula:
$ n! \approx \sqrt{2 \pi n} \left(\frac{n}{e} \right)^n $
Thus, for 8! = 40320:
$ 8! \approx 4 \sqrt{\pi} \left( \frac{8}{e} \right)^8 \approx 39902 $
Relative error of Stirling's formula is approximately $ \dfrac{1}{12n} $
To obtain the exact value of n! factored into primes, we can use some useful identities. First, the prime p is a divisor of n! with multiplicity:
$ \begin{align} \mu &=& \mbox{floor}(\frac{n}{p}) + \mbox{floor}(\frac{n}{p^2}) + \mbox{floor}(\frac{n}{p^3}) + \dots \\ &=& \sum_{k>0} \mbox{floor}(\frac{n}{p^k}) \end{align} $
As an example, for n = 1000, p = 3,
$ \mu = \mbox{floor}(\frac{1000}{3}) + \mbox{floor}(\frac{1000}{9}) + \mbox{floor}(\frac{1000}{27}) + \mbox{floor}(\frac{1000}{81}) + \mbox{floor}(\frac{1000}{243}) $
which gives
$ \mu = 333 + 111 + 37 + 12 + 4 + 1 = 498 $
Therefore, $ 1000! $ is divisible by $ 3^{498} $, but not by $ 3^{499} $.
Furthermore, to speed up the calculation of the above, we can use the identity
$ \mbox{floor}\left(\frac{n}{p^{k+1}} \right) = \mbox{floor}\left( \frac{\mbox{floor}( \frac{n}{p^k} )}{p} \right) $
Binomial Coefficients
See AOCP/Binomial Coefficients
Flags
