permutations and combinations

Number of ways a subset of objects can be selected from a given set of objects.

In a permutation, order is important; in a combination, it is not. Thus, there are six permutations of the letters A, B, C selected two at a time (AB, AC, BC, BA, CA, CB) yet only three combinations (AB, AC, BC). The number of permutations of r objects chosen from a set of n objects, expressed in factorial notation, is n! ÷ (n -r)! The number of combinations is n! ÷ [r!(n -r)!]. The (r + 1)st coefficient in the binomial expansion of (x + y)n coincides with the combination of n objects chosen r at a time (see binomial theorem). Probability theory evolved from the study of gambling, including figuring out combinations of playing cards or permutations of win-place-show possibilities in a horse race, and such counting methods played an important role in its development in the 17th century.

* * *

      the various ways in which objects from a set 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 the ratio of the number of desired subsets to the number of all possible subsets for many games of chance in the 17th century, the French mathematicians Blaise Pascal (Pascal, Blaise) and Pierre de Fermat (Fermat, Pierre de) gave impetus to the development of combinatorics and probability 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 is denoted by the symbol 5P2, read “5 permute 2.” In general, if there are n objects available from which to select, and permutations (P) are to be formed using k of the objects at a time, the number of different permutations possible is denoted by the symbol nPk. A formula for its evaluation is

nPk = n!/(n − k)!
The expression n!—read “n factorial”—indicates that all the consecutive positive integers from 1 up to and including n 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

      (For k = n, nPk = n! Thus, for 5 objects there are 5! = 120 arrangements.)

      For combinations, k objects are selected from a set of n 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 nCk, read “n choose k.” For combinations, since k objects have k! arrangements, there are k! indistinguishable permutations for each choice of k objects; hence dividing the permutation formula by k! yields the following combination formula:

      This is the same as the (nk) binomial coefficient (see binomial theorem). For example, the number of combinations of five objects taken two at a time is

      The formulas for nPk and nCk are called counting 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.

* * *

Universalium. 2010.

Look at other dictionaries:

  • Timeline of numerals and arithmetic — A timeline of numerals and arithmetic Before 2000 BC * ca. 20,000 BC Nile Valley, Ishango Bone: possibly the earliest reference to prime numbers and Egyptian multiplication. * ca. 3400 BC Mesopotamia, the Sumerians invent the first numeral system …   Wikipedia

  • Timeline of algebra and geometry — A timeline of algebra and geometryBefore 1000 BC* ca. 2000 BC Scotland, Carved Stone Balls exhibit a variety of symmetries including all of the symmetries of Platonic solids. * 1800 BC Moscow Mathematical Papyrus, findings volume of a frustum *… …   Wikipedia

  • Herbart and Herbartianism — • Article on the life and philosophy of Johann Friedrich Herbart, by Michael Maher Catholic Encyclopedia. Kevin Knight. 2006. Herbart and Herbartianism     Herbart and Herbartianism …   Catholic encyclopedia

  • Married and maiden names — Née redirects here. For other uses, see Née (disambiguation). A married name is the family name adopted by a person upon marriage. When a person assumes the family name of her spouse, the new name replaces the maiden name. The term maiden name is …   Wikipedia

  • Chord names and symbols (jazz and pop music) — CΔ7, or major seventh chord on C  Play ( …   Wikipedia

  • Notation in probability and statistics — Probability theory and statistics has some commonly used conventions of its own, in addition to standard mathematical notation and mathematical symbols. Contents 1 Probability theory 2 Statistics 3 Critical values …   Wikipedia

  • Permutation — For other uses, see Permutation (disambiguation). The 6 permutations of 3 balls In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging) objects or values.… …   Wikipedia

  • algebra — /al jeuh breuh/, n. 1. the branch of mathematics that deals with general statements of relations, utilizing letters and other symbols to represent specific sets of numbers, values, vectors, etc., in the description of such relations. 2. any of… …   Universalium

  • combinatorics — /keuhm buy neuh tawr iks, tor , kom beuh /, n. (used with singular v.) See combinatorial analysis. * * * Branch of mathematics concerned with the selection, arrangement, and combination of objects chosen from a finite set. The number of possible… …   Universalium

  • mathematics — /math euh mat iks/, n. 1. (used with a sing. v.) the systematic treatment of magnitude, relationships between figures and forms, and relations between quantities expressed symbolically. 2. (used with a sing. or pl. v.) mathematical procedures,… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.