Page:EB1911 - Volume 01.djvu/648

Here we have introduced a number O₍₀₎ given by

O(0)＝1

(16),

which is consistent with the relations in (i.). In this table any number is equal to the sum of the numbers which lie horizontally above it in the preceding column, and the difference of any two numbers in a column is equal to the sum of the numbers horizontally between them in the preceding column.

The coefficients in the expansion of (A+a)ⁿ for any particular value of n are obtained by reading diagonally upwards from left to right from the (n+1)th number in the first column.

(iii.) The table might be regarded as constructed by successive applications of (9) and (4); the initial data being (16) and (10). Alternatively, we might consider that we start with the first diagonal row (downwards from the left) and construct the remaining diagonal rows by successive applications of (15). Constructed in this way, the successive diagonal rows, commencing with the first, give the figurate numbers of the first, second, third, . . . order. The (r+1)th figurate number of the nth order, i.e. the (r+1)th number in the nth diagonal row, is n(n+1) . . . (n+r−1)/r!＝n^[r]/r!; this may, by analogy with the notation of §41, be denoted by n_[r]. We then have

(n+1)[r]＝(r+1)[n]＝(n+r)!/(n! r!)＝(n+r)(r)＝(n+r)(n)

(17).

(iv.) By means of (17) the relations between the binomial coefficients in the form p_(q) may be replaced by others with the coefficients expressed in the form p_(q). The table in (ii.) may be written

1[0]
	1[1]
2[0]		1[2]
	2[1]		1[3]
3[0]		2[2]		1[4]
	3[1]		2[3]		1[5]
4[0]		3[2]		2[4]		1[6]
	4[1]		3[3]		2[5]		1[7]
5[0]		4[2]		3[4]		2[6]		1[8]
			&c.,

The most important relations are

n[r]＝n[r−1]+(n−1)(r)

(18);

O[r]＝0

(19);

n[r]-(n−s)[r]＝n[r-1]+(n−1)[r-1]+...+(n−s+1)[r-1]

(20);

n[r]＝n[r−1]+(n−1)[r−1]+...+1[r−1]

(21).

(v.) It should be mentioned that the notation of the binomial coefficients, and of the continued products such as n(n−1) . . . (n−r+1), is not settled. Some writers, for instance, use the symbol n, in place, in some cases, of n_(r), and, in other cases, of n^(r). It is convenient to retain x, to denote x^r/r!, so that we have the consistent notation

x_r＝x^r/r!, n_(r)＝n^(r)/r!, n_[r]＝n^[r]/r!.

The binomial theorem for positive integral index may then be written

(x+y)_n＝x_ny₀+x_n−1y₁+ ... + x_n−ry_r+ ... + x₀y_n.

This must not be confused with the use of suffixes to denote particular terms of a series or a progression (as in § 41 (viii.) and (ix.)).

44. Permutations and Combinations.—The discussion, in § 41 (i.), of the number of terms of a particular kind in a particular product, forms part of the theory of combinatorial analysis (q.v.), which deals with the grouping and arrangement of individuals taken from a defined stock. The following are some particular cases; the proof usually follows the lines already indicated. Certain of the individuals may be distinguishable from the remainder of the stock, but not from each other; these may be called a type.

(i.) A permutation is a linear arrangement, read in a definite direction of the line. The number (_nP_r) of permutations of r individuals out of a stock of n, all being distinguishable, is n^(r). In particular, the number of permutations of the whole stock is n!.

If a of the stock are of one type, b of another, c of another, . . . the number of distinguishable permutations of the whole stock is n!÷(a!b!c! . . .).

(ii.) A combination is a group of individuals without regard to arrangement. The number (_nC_r) of combinations of r individuals out of a stock of n has in effect been proved in § 41 (i.) to be n_(r). This property enables us to establish, by simple reasoning, certain relations between binomial coefficients. Thus (4) of § 41 (ii.) follows from the fact that, if A is any one of the n individuals, the nCr groups of r consist of _n−1C_r−1 which contain A and _n−1C_r which do not contain A. Similarly, considering the various ways in which a group of r may be obtained from two stocks, one containing m and the other containing n, we find that

_m+nC_r＝_mC_r·_nC₀+_mC_r−1·_nC₁+ ... + _mC₀·_nC_r,

which gives

(m+n)(r)＝m(r)·n(0)+m(r-1)·n(1)+...+m(0)·n(r)

(22).

This may also be written

(m+n)(r)＝m(r)·n(0)+r(1)·m(r-1)·n(1)+...+r(r)·m(0)·n(r)

(23).

If r is greater than m or n (though of course not greater than m+n), some of the terms in (22) and (23) will be zero.

(iii.) If there are n types, the number of individuals in each type being unlimited (or at any rate not less than r), the number (_nH_r) of distinguishable groups of r individuals out of the total stock is n_[r]. This is sometimes called the number of homogeneous products of r dimensions formed out of n letters; i.e. the number of products such as x^r, x^r−3y³ x^r−2z², . . . that can be formed with positive integral indices out of n letters x, y, z, . . ., the sum of the indices in each product being r.

(iv.) Other developments of the theory deal with distributions, partitions, &c. (see Combinatorial Analysis).

(v.) The theory of probability (q.v.) also comes under this head. Suppose that there are a number of arrangements of r terms or elements, the first of which a is always either A or not-A, the second b is B or not-B, the third c is C or not-C, and so on. If, out of every N cases, where N may be a very large number, a is A in pN cases and not-A in (1−p)N cases, where p is a fraction such that pN is an integer, then p is the probability or frequency of occurrence of A. We may consider that we are dealing always with a single arrangement abc . . .. and that the number of times that a is made A bears to the number of times that a is made not-A the ratio of p to 1−p; or we may consider that there are N individuals, for pN of which the attribute a is A, while for (1−p)N it is not-A. If, in this latter case, the proportion of cases in which b is B to cases in which b is not-B is the same for the group of pN individuals in which a is A as for the group of (1−p)N in which a is not-A, then the frequencies of A and of B are said to be independent; if this is not the case they are said to be correlated. The possibilities of a, instead of being A and not-A, may be A₁, A₂, . . ., each of these having its own frequency; and similarly for b, c, . . . If the frequency of each A is independent of the frequency of each B, then the attributes a and b are independent; otherwise they are correlated.

45. Application of Binomial Theorem to Rational Integral Functions.—An expression of the form c₀xⁿ+c₁xⁿ⁻¹+c_n, where c₀, c₁, . . . do not involve x, and the indices of the powers of x are all positive integers, is called a rational integral function of x of degree n.

If we represent this expression by f(x), the expression obtained by changing x into x+h is f(x+h); and each term of this may be expanded by the binomial theorem. Thus we have

f(x+)h＝c₀xⁿ+nc₀xⁿ⁻¹h/1!+n(n−1)c₀xⁿ⁻²h²/2!+...

⁠+c₁xⁿ⁻¹+(n−1)c₁xⁿ⁻²h/1!+(n−1)(n−2)c₁xⁿ⁻³h²/2!+...

⁠+c₂xⁿ⁻²+(n−2)c₂xⁿ⁻³h/1!+(n−2)(n−3)c₂xⁿ⁻⁴h²/2!+...

⁠+ &c.

⁠= {c₀xⁿ+c₁xⁿ⁻¹+c₂xⁿ⁻²+...}

⁠+$\scriptstyle {\left\{{\begin{matrix}\ \end{matrix}}\right.}$nc₀xⁿ⁻¹+(n−1)c₁xⁿ⁻²+(n−2)c₂xⁿ⁻³ + ... $\scriptstyle {\left.{\begin{matrix}\ \end{matrix}}\right\}\,}$h/1!

⁠+$\scriptstyle {\left\{{\begin{matrix}\ \end{matrix}}\right.}$n(n−1)c₀xⁿ⁻²+(n−1)(n−2)c₁xⁿ⁻³ + ... $\scriptstyle {\left.{\begin{matrix}\ \end{matrix}}\right\}\,}$h²/2!

⁠+ &c.

It will be seen that the expression in curled brackets in each line after the first is obtained from the corresponding expression in the preceding line by a definite process; viz. x^r is replaced by