Binomial Numbers

In general, the number of ways we can draw a set of k unordered objects out of a set of n objects without replacement is

Подпись: (1.1)/ n def. n!

Ы = k!(n — k)!

These (binomial) numbers,[3] read as “n choose k,” also appear as coefficients in the binomial expansion

Подпись: (1.2)n / n

(a + b)n = ^( kJakbn—k

k=0

The reason for defining 0! = 1 is now that the first and last coefficients in this binomial expansion are always equal to 1:

Подпись: — = 1. 0! n / n n!

0/ = W =

For not too large an n, the binomial numbers (1.1) can be computed recursively by hand using the Triangle of Pascal:

1

1 1

1 2 1

13 3 1 (1.3)

1 4 6 4 1

1 5 10 10 5 1

1 ………………………………………….. 1

Except for the 1’s on the legs and top of the triangle in (1.3), the entries are the sum of the adjacent numbers on the previous line, which results from the following easy equality:

image008for n > 2, k = 1,…,n — 1. (1.4)

Thus, the top 1 corresponds to n = 0, the second row corresponds to n = 1, the third row corresponds to n = 2, and so on, and for each row n + 1, the entries are the binomial numbers (1.1) for k = 0,…,n. For example, for n = 4 the coefficients of akbn—k in the binomial expansion (1.2) can be found on row 5 in (1.3): (a + b)[4] = 1 x a4 + 4 x a3b + 6 x a2b2 + 4 x ab3 + 1 x b4.

Leave a reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>