Algebra

Permutations and Combinations

Permutations

Permutations of all at a time

The number of permutations of 𝑛 things taken all at a time: =𝑛(𝑛−1)(𝑛−2)⋯3⋅2⋅1≡𝑛! or 𝑛^(𝑛)

Proof

Proof by Induction. Assume the formula to be true for 𝑛 things. Now take 𝑛+1 things. After each of these the remaining 𝑛 things may be arranged in 𝑛! ways, making in all 𝑛×𝑛!, that is (𝑛+1)!, permutations of 𝑛+1 things; therefore, ⋯.

Permutations of 𝑟 thing at a time

The number of permutations of 𝑛 things taken 𝑟 at a time is denoted by 𝑃(𝑛,𝑟). 𝑃(𝑛,𝑟)=𝑛(𝑛)(𝑛−1)(𝑛−2)⋯(𝑛−𝑟+1)≡𝑛^(𝑟).

Proof

Proof. By permutations of 𝑛 things; for (𝑛−𝑟) things are left out of each permutation; therefore 𝑃(𝑛,𝑟)=𝑛!÷(𝑛−𝑟)!. Observe that 𝑟=the number of factors.

Combinations

Combinations of 𝑟 thing at a time

The number of combinations of 𝑛 things taken 𝑟 at a time is denoted by 𝐶(𝑛,𝑟).

𝐶(𝑛,𝑟)=𝑛(𝑛)(𝑛−1)(𝑛−2)⋯(𝑛−𝑟+1)1⋅2⋅3⋯𝑟≡𝑛^(𝑟)𝑟!
             =𝑛!𝑟!(𝑛−𝑟)!=𝐶(𝑛,𝑛−𝑟)

For every combination of 𝑟 things admits of 𝑟! permutations; therefore 𝐶(𝑛,𝑟)=𝑃(𝑛,𝑟)÷𝑟!. 𝐶(𝑛,𝑟) is greatest when 𝑟=12𝑛 or 12(𝑛±1) according as 𝑛 is even or odd.

Homogeneous Products

The number of homogeneous products of 𝑟 dimensions of 𝑛 things is denoted by 𝐻(𝑛,𝑟). 𝐻(𝑛,𝑟)=𝑛(𝑛)(𝑛+1)(𝑛+2)⋯(𝑛+𝑟−1)1⋅2⋅3⋯𝑟≡(𝑛+𝑟−1)^(𝑟)𝑟! When 𝑟 is >, this reduces to (𝑟+1)(𝑟+2)⋯(𝑛+𝑟−1)(𝑛−1)!

Proof

𝐻(𝑛,𝑟) is equal to the number of terms in the product of the expansions by the Binomial Theorem of the 𝑛 expressions (1−𝑎𝑥)⁻¹, (1−𝑏𝑥)⁻¹, (1−𝑐𝑥)⁻¹, ⋯. Put 𝑎=𝑏=𝑐=⋯=1. The number will be the coefficient of 𝑥^𝑟 in (1−𝑥)^−𝑛.

Permutations of alike things

The number of permutations of 𝑛 things taken all together, when 𝑎 of them are alike, 𝑏 of them alike, 𝑐 alike, ⋯. =𝑛!𝑎!𝑏!𝑐!⋯ For, if the 𝑎 things were all different, they would form 𝑎! permutations where there is now but one. so of 𝑏, 𝑐, ⋯.

Combinations of 𝑝 things found

The number of combinations of 𝑛 things 𝑟 at a time, in which any 𝑝 of them will always be found, is =𝐶(𝑛−𝑝,𝑟−𝑝) For, if the 𝑝 things be set on one side, we have to add to them 𝑟−𝑝 things taken from the remaining 𝑛−𝑝 things in every possible way.

Theorem of Combination

𝐶(𝑛−1,𝑟−1)+𝐶(𝑛−1,𝑟)=𝐶(𝑛,𝑟) Proof by induction or as follows: Put one out of 𝑛 letters aside; there are 𝐶(𝑛−1,𝑟) combinations of the remaining 𝑛−1 letters 𝑟 at a time. To complete the total 𝐶(𝑛,𝑟), we must place with the excluded letter all the combinations of the remaining 𝑛−1 letters 𝑟−1 at a time.

Combination of Different Things

If ther be one set of 𝑃 things, another of 𝑄 things, another of 𝑅 things, and so on; the number of combinations formed by taking one out of each set is =𝑃𝑄𝑅⋯, the product of the numbers in the several sets.
For one of the 𝑃 things will form 𝑄 combinations with the 𝑄 things. A second of the 𝑃 things will form 𝑄 more combinations; ans so on. In all, 𝑃𝑄 combinations of two things. Similarly there will be 𝑃𝑄𝑅 combinations of three things; and so on.
On the same principle, if 𝑝, 𝑞, 𝑟, ⋯ things be taken out of each set respectively, the number of combinations will be the product of the numbers of the separate combinations; that is, =𝐶(𝑃𝑝)⋅𝐶(𝑄𝑞)⋅𝐶(𝑅𝑟)⋅⋯ The number of combinations of 𝑛 things taken 𝑚 at a time, when 𝑝 of the 𝑛 things are alike, 𝑞 of them alike, 𝑟 of them alike, ⋯, will be the sum of all the combinations of each possible form of 𝑚 dimensions, and this is equal to the coefficient of 𝑥^𝑚 in the expansion of (1+𝑥+𝑥²+⋯+𝑥^𝑝)(1+𝑥+𝑥²+⋯+𝑥^𝑞)(1+𝑥+𝑥²+⋯+𝑥^𝑟)⋯ The total number of possible combinations under the same circumstances, when the 𝑛 things are taken in all ways, 1, 2, 3, ⋯, 𝑛 at a time, =(𝑝+1)(𝑞+1)(𝑟+1)⋯−1 The number of permutations when they are taken 𝑚 at a time in all possible ways will be equal to the product of 𝑚! and the coefficient of 𝑥^𝑚 in the expansion of ~~1+𝑥+𝑥²2!+𝑥³3!+⋯+𝑥^𝑝𝑝!1+𝑥+𝑥²2!+𝑥³3!+⋯+𝑥^𝑞𝑞!~~⋯