Permutations and Combinations.

Permutations and Combinations. Permutations and Combinations, in mathematics, certain arrangements of objects or elements. In the case of combinations, no attention is paid to the order of arrangement. In permutations, however, different orderings are counted as distinct, and repetitions of the elements selected may or may not be allowed. Permutations and combinations are important in many branches of mathematics. For example, in probability theory and statistics, they can be used to count the number of possible arrangements of a system. A new branch of mathematics, called combinatorics, is founded on the formulas for permutations and combinations, and it has important applications to the design and operation of computers, as well as to the physical and social sciences. Indeed, in any area where the possible arrangements of a finite number of elements play a role, the theory of permutations and combinations is useful. The idea of permuting n number of objects is basic. For example, when n = 3 and the objects are a,b, and c, the permutations are abc,acb,bca,bac, cba, and cab. Here there are 6 permutations, or 3 · 2 · 1 = 3! of them. The product "3!" is read as "three factorial" and represents the product of all the positive integers between 1 and 3. In the general case of n elements, there are n ! = n · ( n - 1) ·...· 1 permutations. For example, if there are n teams in a league, and ties are not possible, then there are n ! possible team rankings at the end of the season. A slightly more complicated problem would be finding the number of possible rankings of the top r number of teams at the end of a season in a league of n teams. Here the formula is P(n,r) = n · (n - 1) ·...· ( n - r + 1) = n !/(n - r) ! so that the number of possible outcomes for the first four teams of an eight-team league is P(8,4) = 8 · 7 · 6 · 5 = 1680. Now suppose we are not interested in the order in which the top four teams finished, but were concerned only about the number of the possible combinations of teams that could be in the top four positions in the league at the end of the season. This is equivalent to finding the possible four-object combinations out of an eight-object set. In general, an r-combination of n objects, where n is greater than r, is the number of distinct groupings of r elements pulled from a set of n elements. The formula for this number, written C(n,r), is P(n,r)/r !. For example, the 2-combinations of the three elements a,b, and c are ab,ac, and bc; thus C (3, 2) = 3. The general formula for C (n,r) is n !/[r !(n - r) !]. The expression n !/[r !(n - r) !] is denoted ( nr); it is used to calculate the coefficients of binomials, and plays a basic role in the theory of combinations. If repetitions are allowed, so that a given element can be chosen more than once, then the last example would also include aa, bb, and cc, for a total of 6. The general formula for the number of r-combinations (with arbitrary repetitions) from an n -element set is (n + r - 1) !/[r !(n - 1) !]. For example, if a teacher must make a list containing three names from a class of 15, and if the list can contain a name two or three times and order does not matter, then there are (15 + 3 - 1) !/[3 !(15 - 1) !] = 680 possible lists. The same formula arises in counting the number of ways in which r identical objects--for example, votes in an election--can be distributed among n distinct objects--for example, among candidates in the election. In the case of r-permutations with repetition from an n -element set, the formula is n r. For example, to the six 2-permutations of a,b,c without repetitions (ab,ba,ac,ca,bc, and cb) are added the three with repetitions (aa,bb, and cc), for a total of 9, which is equal to 32. Thus, if two prizes are to be awarded among three people, and it is possible that one person could receive both prizes, then nine possible outcomes exist. Finally, suppose there are n 1 objects of one type, n 2 of another type, on to n k objects of some kth type. Let n = n 1 + n 2 + ... + n k. In how many ways can these objects be arranged, taking order into account? The answer, n !/(n 1 !n 2 ! ...n k !), is exemplified by the different ways in which the letters of the word "banana" can be arranged: 6 !/(3 !2 !1 !) = 60. This is also the coefficient of x3y2 z1 in (x + y + z)6. Contributed By: J. Lennart Berggren Microsoft ® Encarta ® 2009. © 1993-2008 Microsoft Corporation. All rights reserved.