Thus the number of combination of n things r together increases with r so long as r is less than (n+1).

T-1

If then n be even, „C, is greatest when r =

n

2'

If n be odd, „CrnCr-1 as r≤ † (n + 1), and „Cr

C, when r1⁄2 (n + 1). (n + 1). Thus, when n is odd, „C1(n-1) C+1) and these are the greatest values of C

For example, if n=10, „C, is greatest when r=5.

n

=

=

Also if n=11,

"C, is the same for the values 5 and 6 of r, and C, is greater for these values than for any other value.

244. Theorem. To prove that, if x and y be positive integers such that x+y=m, then will

any two

Suppose that m letters a, b,..., p, q,..., are divided. into two groups a, b,..., and p, q,..., there being x and y letters respectively in these groups. Then the whole number of ways in which n of the m things can be taken will clearly be equal to the sum of the number of ways of taking n out of the first group and none out of the second, n 1 out of the first group and one out of the second, n 2 out of the first group and 2 out of the second, and so on.

Now n can be taken out of the first group in C ways. Also n-1 can be taken out of the first group in any one of these sets of n-1 things can n-1 ways, and be taken with any one of the C1 ways of taking I from the second group, so that the number of ways of taking n-1 from the first group and 1 from the second is

C

n-1

Similarly, the number of ways of taking n-2 from the first group and 2 from the second is C-C.

n-2

And, in general, the number of ways of taking n-r from the first group and r from the second is C-,,C.

If x or y be less than n some of the terms on the right will vanish; for C=0 if r>n.

245.

Vandermonde's Theorem. From the last Article, if x, y and n be any positive integers such that

x+y is greater than n, we have, since „C:

n

=

m

Multiply each side of the last equation by |n, and we

The above has been proved on the supposition that x and y are positive integers such that x + y is greater than n; and by means of the theorem of Art. 91, the proposition can be proved to be true for all values of x and y.

For the two expressions which are to be proved identical are only of the nth degree in x and y. But, if y has any particular integral value greater than n, the equation is known to be true for any positive integral value of x, and thus for more than n values; and hence it must be true for that value of У and any value whatever of x. Hence the proposition is true for any particular value whatever of x, and for more than n values

of y; it must therefore be true for all values of x and for all values of y.

This proves Vandermonde's theorem :

If n be any positive integer, and x, y have any values whatever; then will

246. The number of different products each of r letters which can be made from n letters, when each letter may be repeated any number of times, is denoted by the symbol „Ä

To find H.

n

Since in each of the r-dimensional products of n things there are r letters, the total number of letters in all the products will be „H, xr; and, as each of the n letters occurs the same number of times, it follows that the number of times any particular letter, a suppose, occurs is „H,× r÷n.

Now consider all the terms which contain a at least once. If any one of these terms be divided by a the quotient will be of r-1 dimensions; and, when all the terms which contain a are so divided, we shall obtain without repetition all the possible homogeneous products of the n letters of r-1 dimensions. Now the homogeneous products of r-1 dimensions are in number H,,; and, by the above, the number of a's they contain is × H-1 Hence, taking into account the a which is

r-1

n

r-1'

n r-1

a factor of each of the „H,, terms, the total number of a's

which occur in all the r-dimensional products of the n letters

Hence equating the two expressions for the number of a's, we have

Since the above relation is true for all values of n and r, we have in succession

Also H, is obviously equal to n.

Hence, by multiplying and cancelling common factors, we have

n (n + 1)......(n + r − 1)

Ex. 1.

Find the number of combinations three at a time of the letters a, b, c, d when the letters may be repeated.

Ex. 2.

Ans. 20.

Find the number of different combinations six at a time which

247. Many theorems relating to permutations and combinations are best proved by means of the binomial theorem examples will be found in subsequent chapters.

Ex. 1. Find the number of ways in which mn different things can be divided among ʼn persons so that each may have m of them.

The number of ways in which the first set of m things can be given is mnCm; and, whatever set is given to the first, the second set can be given in mn-mCm ways; so also, whatever sets are given to the first and second, the third set can be given in

and so on.

Hence the required number is

mnCm× m(n-1)Cm × m(n-2)Cm ×

mn-2m C'm ways;