permutations andcombinations, the various ways in which objects from aset may be selected, generally without replacement, to form subsets. This selection of subsets is called a permutation when the order of selection is a factor, a combination when order is not a factor. By considering theratio of the number of desired subsets to the number of all possible subsets for many games of chance in the 17th century, the French mathematiciansBlaise Pascal andPierre de Fermat gaveimpetus to the development ofcombinatorics andprobability theory.

The concepts of and differences between permutations and combinations can be illustrated by examination of all the different ways in which a pair of objects can be selected from five distinguishable objects—such as the letters A, B, C, D, and E. If both the letters selected and the order of selection are considered, then the following 20 outcomes are possible:

Each of these 20 different possible selections is called a permutation. In particular, they are called the permutations of five objects taken two at a time, and the number of such permutations possible isdenoted by the symbol₅P₂, read “5 permute 2.” In general, if there aren objects available from which to select, and permutations (P) are to be formed usingk of the objects at a time, the number of different permutations possible is denoted by the symbol_nP_k. A formula for its evaluation is_nP_k =n!/(n −k)! The expressionn!—read “nfactorial”—indicates that all the consecutive positive integers from 1 up to and includingn are to be multiplied together, and 0! is defined to equal 1. For example, using this formula, the number of permutations of five objects taken two at a time is

Britannica Quiz

Numbers and Mathematics

(Fork =n,_nP_k =n! Thus, for 5 objects there are 5! = 120 arrangements.)

For combinations,k objects are selected from a set ofn objects to produce subsets without ordering. Contrasting the previous permutation example with the corresponding combination, the AB and BA subsets are no longer distinct selections; by eliminating such cases there remain only 10 different possible subsets—AB, AC, AD, AE, BC, BD, BE, CD, CE, and DE.

The number of such subsets is denoted by_nC_k, read “n choosek.” For combinations, sincek objects havek! arrangements, there arek! indistinguishable permutations for each choice ofk objects; hence dividing the permutation formula byk!yields the following combination formula:

This is the same as the (n,k) binomial coefficient (seebinomial theorem; these combinations are sometimes calledk-subsets). For example, the number of combinations of five objects taken two at a time is

Access for the whole family!

Bundle Britannica Premium and Kids for the ultimate resource destination.

Subscribe

The formulas for_nP_k and_nC_k are calledcounting formulas since they can be used to count the number of possible permutations or combinations in a given situation without having to list them all.