Scribd
Upload
20 views1 page

Binomial Theorem and Pascal's Triangle

Newton's binomial theorem and Pascal's triangle describe the number of combinations and arrangements of choosing objects without repetition from a larger set. Specifically: 1) The number of combinations of choosing k unordered objects from a set of n objects is denoted as C(n,k) and can be calculated using factorials and Pascal's triangle. 2) Pascal's triangle provides a way to calculate combinations recursively by splitting the choice into mutually exclusive cases. 3) The binomial theorem expands (a + b)n as a sum involving the combinations of a and b terms, with coefficients given by the appropriate entry in Pascal's triangle.

Uploaded by

lthyagu
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
20 views1 page

Binomial Theorem and Pascal's Triangle

Newton's binomial theorem and Pascal's triangle describe the number of combinations and arrangements of choosing objects without repetition from a larger set. Specifically: 1) The number of combinations of choosing k unordered objects from a set of n objects is denoted as C(n,k) and can be calculated using factorials and Pascal's triangle. 2) Pascal's triangle provides a way to calculate combinations recursively by splitting the choice into mutually exclusive cases. 3) The binomial theorem expands (a + b)n as a sum involving the combinations of a and b terms, with coefficients given by the appropriate entry in Pascal's triangle.

Uploaded by

lthyagu
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Newtons binomial and Pascals triangle

Playing lotto: You have n numbered balls and k balls are picked out in sequence (0 k n). When picking the rst ball you have n choices. For the next ball n 1 choices remain, and so on. Thus, the number of dierent ways this can be done, denoted by An k , is n(n 1)...(n k + 1). In the special case when k = n we have An = n ( n 1) ... 1, which is denoted by n! (n factorial). This is the number of ways n n balls can be reordered (permuted). Note that since there is only one way permute no balls, 0! = 1. With this notation we have k1 n! n Ak = n(n 1)...(n k + 1) = (n i ) = (n k )! i=0 Making choices: Despite the fact that the balls are picked out in sequence, their order does not aect your success at lotto. We may consider any sequences of length k consisting of the same set of balls as equivalent. The number of such sequences is Ak k = k !. Thus, the number of truly dierent selections, n , is denoted by Ck An n! n(n 1)...(n k + 1) n Ck = k = = k Ak k! k !(n k )! Splitting choices: Factorials get huge pretty quickly, so taking their ratios is not the best way to compute. One way to ease the computation is to split the choice. If you choose k balls out of n you will either pick the rst one or not. If you pick the rst ball, you still have to choose k 1 more out the remaining n 1 balls. If you dont pick the rst ball, you must pick all k balls out of the remaining n 1. Thus,
n1 n1 n Ck = Ck 1 + Ck n This idea of recursion is behind the Pascal triangle construction which oers fast computation of C k . Here are the rst few rows of Pascals triangle 1 11 121 1331 14641 3 4 Thus, for example C1 = 3 and C2 = 6. Note how each entry is the sum of the entries above it. Also note n n the obvious symmetry Ck = Cnk . Foiling: To raise a binomial a + b to the n-th power let us write it as a product of n factors (a + b) n = (a + b)(a + b)...(a + b) and use the distributive law to multiply things out (this is called foiling). The result will be a sum of products of as and bs with the total power n. Let us collect terms with same powers of a (the power of b must be n minus the power of a). If we choose a in each factor a + b we obtain a n . If we replace one of the as with b, we can take that b out of any of the n factors a + b, so there will be n terms n an1 b. In general, if we replace k as with bs, we will have Ck terms ank bk . Thus, n n n2 2 a b + ... + bn = (a + b)n = an + nan1 b + C2 k=0 n nk k a b Ck

For example, (a + b)3 = a3 + 3a2 b + 3ab2 + b3 and (a + b)4 = a4 + 4a3 b + 6a2 b2 + 4ab3 + b4 .

Copyright 2001 Dr. Dmitry Gokhman

You might also like