combination

American Heritage Dictionary:

com·bi·na·tion

(kŏm'bə-nā'shən) pronunciation

The act of combining or the state of being combined.
The result of combining.
An alliance of persons or parties for a common purpose; an association.
A sequence of numbers or letters used to open a combination lock.
Mathematics. One or more elements selected from a set without regard to the order of selection.

combinational com'bi·na'tion·al adj.

Search unanswered questions...

Browse: Unanswered questions | Most-recent questions | Reference library

combination

Top

An unordered selection of r objects from a set of n (≥r) different objects. The number of different combinations is often denoted by ⁿC_r. In fact,

is the binomial coefficient. Special values are ⁿC₀=1, ⁿC_n=1, ⁿC₁=n.

A frequently used relationship is

ⁿ⁺¹C_r=ⁿC_r+ⁿC_r−1,

which is the defining relationship for Pascal's triangle. For ordered selection, see permutation.

Barron's Finance & Investment Dictionary:

combination

Top

1. arrangement of options involving two long or two short positions with different expiration dates or strike (exercise) prices. A trader could order a combination with a long call and a long put or a short call and a short put.

2. joining of competing companies in an industry to alter the competitive balance in their favor is called a combination in restraint of trade.

3. joining two or more separate businesses into a single accounting entity; also called business combination. See also Merger.

Previous:	Colts, College Savings Plan
Next:	Combination Annuity, Combination Bond

Roget's Thesaurus:

combination

Top

noun

The state of being associated: affiliation, alliance, association, conjunction, connection, cooperation, partnership. See near/far/distance.
The result of combining: composite, compound, conjugation, unification, union, unity. See assemble/disassemble.
A group of individuals united in a common cause: bloc, cartel, coalition, combine, faction, party, ring. See group.

Antonyms by Answers.com:

combination

Top

Definition: alliance, association
Antonyms: dissolution, disunion, separation, severance

n

Definition: mixture, blend
Antonyms: detachment, division, parting, separation

West's Encyclopedia of American Law:

Combination

Top

This entry contains information applicable to United States law only.

In criminal law, an agree- ment between two or more people to act jointly for an unlawful purpose; a conspiracy. In patent law, the joining together of several separate inventions to produce a new invention.

An illegal combination in restraint of trade, defined under the Sherman Anti-Trust Act, is one in which the conspirators agree expressly or impliedly to use devices such as price-fixing agreements to eliminate competition in a certain locality, e.g., when a group of furniture manufacturers refuse to deliver goods to stores that sell their goods for under a certain price.

In patent law a combination is distinguishable from an aggregation in that it is a joint operation of elements that produces a new result as opposed to a mere grouping together of old elements. This is important in determining whether or not something is patentable, since no valid patent can extend to an aggregation.

Investopedia Financial Dictionary:

Combination

Top

When an investor holds a position in both call and put options on the same asset.

Investopedia Says:
There are various types of combination spreads, including straddles and strangles.

Related Links:
An introduction to the world of options, covering everything from primary concepts to how options work and why you might use them. Options Basics Tutorial
Volume should inform your use of this indicator in confirming trends and reversals. Discovering Open Interest - Part 2
Moving from equities to currencies requires you to adjust how you interpret quotes, margin, spreads and rollovers. A Primer On The Forex Market
Learn about this aggressive trading strategy that can be used to generate income as part of a diversified portfolio. Peekaboo! Call Writing Gets Naked
Options are not only trading instruments but also predictive tools that can help us gauge the feelings of traders. Forecasting Market Direction With Put/Call Ratios
There's one simple hurdle in the transition from stock to futures options: learning about product specifications. Options On Futures: A World Of Potential Profit

Word Tutor:

combination

Top

IN BRIEF: The process of putting things together.

Coffee and milk is Jim's favorite combination.

LearnThatWord.com is a free vocabulary and spelling program where you only pay for results!

Random House Word Menu:

categories related to 'combination'

Top

Random House Word Menu by Stephen Glazier

For a list of words related to combination, see:

Chemical Properties and Reactions - combination: union of substances to form chemical compound
Ballet - combination: several movements in succession
Boxing and Wrestling

Bradford's Crossword Solver's Dictionary:

combination

Top

See crossword solutions for the clue Combination.

Wikipedia on Answers.com:

Combination

Top

"Combin" redirects here. For the mountain massif, see Grand Combin.

For other uses, see Combination (disambiguation).

In mathematics a combination is a way of selecting several things out of a larger group, where (unlike permutations) order does not matter. In smaller cases it is possible to count the number of combinations. For example given three fruit, say an apple, orange and pear, there are three combinations of two that can be drawn from this set: an apple and a pear; an apple and an orange; or a pear and an orange. More formally a k-combination of a set S is a subset of k distinct elements of S. If the set has n elements the number of k-combinations is equal to the binomial coefficient

$\binom nk = \frac{n(n-1)\ldots(n-k+1)}{k(k-1)\dots1},$

which can be written using factorials as $\frac{n!}{k!(n-k)!}$ whenever $k\leq n$ , and which is zero when $k > n$ . The set of all k-combinations of a set S is sometimes denoted by $\binom Sk\,$ .

Combinations can refer to the combination of n things taken k at a time without or with repetitions.^[1] In the above example repetitions were not allowed. If however it was possible to have two of any one kind of fruit there would be 3 more combinations: one with two apples, one with two oranges, and one with two pears.

With large sets, it becomes necessary to use more sophisticated mathematics to find the number of combinations. For example, a poker hand can be described as a 5-combination (k = 5) of cards from a 52 card deck (n = 52). The 5 cards of the hand are all distinct, and the order of cards in the hand does not matter. There are 2,598,960 such combinations, and the chance of drawing any one hand at random is 1 / 2,598,960.

Contents

1 Number of k-combinations
- 1.1 Example of counting combinations
- 1.2 Enumerating k-combinations
2 Number of combinations with repetition
- 2.1 Example of counting multicombinations
3 Number of k-combinations for all k
4 Probability: sampling a random combination
5 See also
6 References
7 External links

Number of k-combinations

3-element subsets of a 5-element set

Main article: Binomial coefficient

The number of k-combinations from a given set S of n elements is often denoted in elementary combinatorics texts by C(n, k), or by a variation such as $C^n_k$ , $n C k$ , $n C k$ or even $C_n^k$ (the latter form is standard in French, Russian, and Polish texts). The same number however occurs in many other mathematical contexts, where it is denoted by $\tbinom nk$ ; notably it occurs as coefficient in the binomial formula, hence its name binomial coefficient. One can define $\tbinom nk$ for all natural numbers k at once by the relation

$\textstyle(1+X)^n=\sum_{k\geq0}\binom nk X^k,$

from which it is clear that $\tbinom n0=\tbinom nn=1$ and $\tbinom nk=0$ for k > n. To see that these coefficients count k-combinations from S, one can first consider a collection of n distinct variables X_s labeled by the elements s of S, and expand the product over all elements of S:

$\textstyle\prod_{s\in S}(1+X_s);$

it has 2ⁿ distinct terms corresponding to all the subsets of S, each subset giving the product of the corresponding variables X_s. Now setting all of the X_s equal to the unlabeled variable X, so that the product becomes (1 + X)ⁿ, the term for each k-combination from S becomes X^k, so that the coefficient of that power in the result equals the number of such k-combinations.

Binomial coefficients can be computed explicitly in various ways. To get all of them for the expansions up to (1 + X)ⁿ, one can use (in addition to the basic cases already given) the recursion relation

$\binom nk=\binom{n-1}{k-1}+\binom{n-1}k,\text{ for }0<k<n,$

which follows from (1 + X)ⁿ = (1 + X)^{n − 1}(1 + X); this leads to the construction of Pascal's triangle.

For determining an individual binomial coefficient, it is more practical to use the formula

$\binom nk = \frac{n(n-1)(n-2)\cdots(n-k+1)}{k!}.$

The numerator gives the number of k-permutations of n, i.e., of sequences of k distinct elements of S, while the denominator gives the number of such k-permutations that give the same k-combination when the order is ignored.

When k exceeds n/2, the above formula contains factors common to the numerator and the denominator, and canceling them out gives the relation

$\binom nk = \binom n{n-k},\text{ for }0 \le k \le n.$

This expresses a symmetry that is evident from the binomial formula, and can also be understood in terms of k-combinations by taking the complement of such a combination, which is an (n − k)-combination.

Finally there is a formula which exhibits this symmetry directly, and has the merit of being easy to remember:

$\binom nk = \frac{n!}{k!(n-k)!},$

where n! denotes the factorial of n. It is obtained from the previous formula by multiplying denominator and numerator by (n − k)!, so it is certainly inferior as a method of computation to that formula.

The last formula can be understood directly, by considering the n! permutations of all the elements of S. Each such permutation gives a k-combination by selecting its first k elements. There are many duplicate selections: any combined permutation of the first k elements among each other, and of the final (n − k) elements among each other produces the same combination; this explains the division in the formula.

From the above formulas follow relations between adjacent numbers in Pascal's triangle in all three directions:

$\binom nk = \binom n{k-1} \frac {n-k+1}k,\text{ for }k>0$ ,

$\binom nk = \binom {n-1}k \frac n{n-k},\text{ for }{k<n}$ ,

$\binom nk = \binom {n-1}{k-1} \frac nk,\text{ for }n,k>0$ .

Together with the basic cases $\tbinom n0=1=\tbinom nn$ , these allow successive computation of respectively all numbers of combinations from the same set (a row in Pascal's triangle), of k-combinations of sets of growing sizes, and of combinations with a complement of fixed size n − k.

Example of counting combinations

As a concrete example, one can compute the number of five-card hands possible from a standard fifty-two card deck as:

${52 \choose 5} = \frac{52\times51\times50\times49\times48}{5\times4\times3\times2\times1} = \frac{311,875,200}{120} = 2,598,960.$

Alternatively one may use the formula in terms of factorials and cancel the factors in the numerator against parts of the factors in the denominator, after which only multiplication of the remaining factors is required:

$\begin{alignat}{2}{52 \choose 5} &= \frac{52!}{5!47!} \\ &= \frac{52\times51\times50\times49\times48\times\cancel{47!}}{5\times4\times3\times2\times\cancel{1}\times\cancel{47!}} \\ &= \frac{52\times51\times50\times49\times48}{5\times4\times3\times2} \\ &= \frac{(26\times\cancel{2})\times(17\times\cancel{3})\times(10\times\cancel{5})\times49\times(12\times\cancel{4})}{\cancel{5}\times\cancel{4}\times\cancel{3}\times\cancel{2}} \\ &= {26\times17\times10\times49\times12} \\&= 2,598,960.\end{alignat}$

Another alternative computation, almost equivalent to the first, is based on writing

${n \choose k} = \frac { ( n - 0 ) }1 \times \frac { ( n - 1 ) }2 \times \frac { ( n - 2 ) }3 \times \cdots \times \frac { ( n - (k - 1) ) }k,$

which gives

${52 \choose 5} = \frac{52}1 \times \frac{51}2 \times \frac{50}3 \times \frac{49}4 \times \frac{48}5 = 2,598,960.$

When evaluated as $52 \div 1 \times 51 \div 2 \times 50 \div 3 \times 49 \div 4 \times 48 \div 5$ , this can be computed using only integer arithmetic. The reason that all divisions are without remainder is that the intermediate results they produce are themselves binomial coefficients.

Using the symmetric formula in terms of factorials without performing simplifications gives a rather extensive calculation:

$\begin{align} {52 \choose 5} &= \frac{n!}{k!(n-k)!} = \frac{52!}{5!(52-5)!} = \frac{52!}{5!47!} \\ &= \tfrac{80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000}{120\times258,623,241,511,168,180,642,964,355,153,611,979,969,197,632,389,120,000,000,000} \\ &= 2,598,960. \end{align}$

Enumerating k-combinations

One can enumerate all k-combinations of a given set $S$ of n elements in some fixed order, which establishes a bijection from an interval of $\tbinom nk$ integers with the set of those k-combinations. Assuming $S$ is itself ordered, for instance $S = {1,2, ..., n$ }, there are two natural possibilities for ordering its k-combinations: by comparing their smallest elements first (as in the illustrations above) or by comparing their largest elements first. The latter option has the advantage that adding a new largest element to $S$ will not change the initial part of the enumeration, but just add the new k-combinations of the larger set after the previous ones. Repeating this process, the enumeration can be extended indefinitely with k-combinations of ever larger sets. If moreover the intervals of the integers are taken to start at 0, then the k-combination at a given place i in the enumeration can be computed easily from i, and the bijection so obtained is known as the combinatorial number system. It is also known as "rank"/"ranking" and "unranking" in computational mathematics.^[2]^[3]

Number of combinations with repetition

Example of counting multicombinations

For example, if you have ten types of donuts (n = 10) on a menu to choose from and you want three donuts (k = 3), the number of ways to choose can be calculated as

$\binom{10+3-1}3 = \binom{12}3 = \frac{12\times11\times10}{3\times2\times1} = 220.$

The analogy with the k-combination case can be stressed by writing the numerator as a rising power

$\binom{n + k - 1}{k} = \frac{n(n+1)\cdots(n+k-1)}{k!}.$

There is an easy way to understand the above result. Label the elements of S with numbers 0, 1, ..., n − 1, and choose a k-combination from the set of numbers { 1, 2, ..., n + k − 1 } (so that there are n − 1 unchosen numbers). Now change this k-combination into a k-multicombination of S by replacing every (chosen) number x in the k-combination by the element of S labeled by the number of unchosen numbers less than x. This is always a number in the range of the labels, and it is easy to see that every k-multicombination of S is obtained for one choice of a k-combination.

A concrete example may be helpful. Suppose there are 4 types of fruits (apple, orange, pear, banana) at a grocery store, and you want to buy 12 pieces of fruit. So n = 4 and k = 12. Use label 0 for apples, 1 for oranges, 2 for pears, and 3 for bananas. A selection of 12 fruits can be translated into a selection of 12 distinct numbers in the range 1,...,15 by selecting as many consecutive numbers starting from 1 as there are apples in the selection, then skip a number, continue choosing as many consecutive numbers as there are oranges selected, again skip a number, then again for pears, skip one again, and finally choose the remaining numbers (as many as there are bananas selected). For instance for 2 apples, 7 oranges, 0 pears and 3 bananas, the numbers chosen will be 1, 2, 4, 5, 6, 7, 8, 9, 10, 13, 14, 15. To recover the fruits, the numbers 1, 2 (not preceded by any unchosen numbers) are replaced by apples, the numbers 4, 5, ..., 10 (preceded by one unchosen number: 3) by oranges, and the numbers 13, 14, 15 (preceded by three unchosen numbers: 3, 11, and 12) by bananas; there are no chosen numbers preceded by exactly 2 unchosen numbers, and therefore no pears in the selection. The total number of possible selections is

$\binom{4+12-1}{12} = \binom{15}{12} = \binom{15}3 = \frac{15\times14\times13}{3\times2\times1} = 455.$

Number of k-combinations for all k

The number of k-combinations for all k, $\sum_{0\leq{k}\leq{n}}\binom nk = 2^n$ , is the sum of the nth row (counting from 0) of the binomial coefficients. These combinations are enumerated by the 1 digits of the set of base 2 numbers counting from 0 to $2 n - 1$ , where each digit position is an item from the set of n.

Probability: sampling a random combination

There are various algorithms to pick out a random combination from a given set or list. Rejection sampling is extremely slow for large sample sizes. One way to select a k-combination efficiently from a population of size n is to iterate across each element of the population, and at each step pick that element with a dynamically changing probability of $\frac{k-\mathrm{\#\,samples\ chosen}}{n-\mathrm{\#\,samples\ visited}}$ .

References

^ Erwin Kreyszig, Advanced Engineering Mathematics, John Wiley & Sons, INC, 1999
^ http://www.site.uottawa.ca/~lucia/courses/5165-09/GenCombObj.pdf
^ http://www.sagemath.org/doc/reference/sage/combinat/subset.html

External links

C code to generate all combinations of n elements chosen as k
Many Common types of permutation and combination math problems, with detailed solutions
The Unknown Formula For combinations when choices can be repeated and order does NOT matter
[1] Combinations with repetitions (by: Akshatha AG and Smitha B)

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

Translations:

Combination

Top

Dansk (Danish)
n. - kombination, forening, gruppe, kode, koncern, forbindelse, undertøj ud i et

idioms:

combination lock kombinationslås

Nederlands (Dutch)
combinatie, (motor met) zijspan, ondergoed uit een stuk

Français (French)
n. - combinaison, conjonction, mélange, association (avec), combinaison (de nombres, chimiques), (GB, Aut) side-car

idioms:

combination lock serrure à combinaison, serrure à code

Deutsch (German)
n. - Kombination, Verbindung, Beiwagenmaschine

idioms:

combination lock Kombinationsschloß

Ελληνική (Greek)
n. - συνδυασμός, μοτοσικλέτα με καλάθι, (ενδυμ.) κορμάκι, (οικον.) κοινοπραξία, καρτέλ

idioms:

combination lock κλειδαριά συνδυασμού

Italiano (Italian)
combinazione, sidecar

idioms:

combination lock lucchetto cifrato

Português (Portuguese)
n. - combinação (f), acordo (m), cartel (m), segredo (m) de cofre

idioms:

combination lock fechadura (f) de combinação

Русский (Russian)
комбинация, мотоцикл с коляской

idioms:

combination lock замок с секретом

Español (Spanish)
n. - combinación, asociación, motocicleta con sidecar

idioms:

combination lock cerradura de combinación

Svenska (Swedish)
n. - kombination, sammanslutning, förbindelse

中文（简体）(Chinese (Simplified))
结合, 团体, 联合, 联盟

idioms:

combination lock 号码锁

中文（繁體）(Chinese (Traditional))
n. - 結合, 團體, 聯合, 聯盟

idioms:

combination lock 號碼鎖

한국어 (Korean)
n. - 결합, 아래위가 붙은 속옷, 단체행동

日本語 (Japanese)
n. - 結合, 組み合わせ, 連合, 組み合わせ文字, 化合, コンビネーション

idioms:

combination lock 文字合わせ錠

العربيه (Arabic)
‏(الاسم) جمع, مزج, ضم, مزيج, خليط‏

עברית (Hebrew)
n. - ‮אופנוע עם סירה, איחוד, צירוף, קומבינציה, אופנוע עם סירה (בריטניה), מבחר, פעולה מאוחדת, סדרת מהלכים בשחמט‬

If you are unable to view some languages clearly, click here.

To select your translation preferences click here.

Best of the Web:

combination

Top

Some good "combination" pages on the web:

Math
mathworld.wolfram.com

		American Heritage Dictionary. The American Heritage® Dictionary of the English Language, Fourth Edition Copyright © 2007, 2000 by Houghton Mifflin Company. Updated in 2009. Published by Houghton Mifflin Company. All rights reserved. Read more
		Oxford Dictionary of Statistics. A Dictionary of Statistics. Second edition revised. Copyright © Oxford University Press, 2008. All rights reserved. Read more
		Barron's Finance & Investment Dictionary. Dictionary of Finance and Investment Terms. Copyright © 2010 by Barron's Educational Series, Inc. All rights reserved. Read more
		Roget's Thesaurus. Roget's II: The New Thesaurus, Third Edition by the Editors of the American Heritage® Dictionary Copyright © 1995 byHoughton Mifflin Company. Published by Houghton Mifflin Company. All rights reserved. Read more
		Antonyms by Answers.com. © 1999-present by Answers Corporation. All rights reserved. Read more
		West's Encyclopedia of American Law. West's Encyclopedia of American Law. Copyright © 1998 by The Gale Group, Inc. All rights reserved. Read more
		Investopedia Financial Dictionary. Copyright ©2010, Investopedia.com - Owned and Operated by Investopedia US, A Division of ValueClick, Inc. All rights reserved. Read more
		Word Tutor. Copyright © 2004-present by eSpindle Learning, a 501(c) nonprofit organization. All rights reserved. eSpindle provides personalized spelling and vocabulary tutoring online; sign up free. Read more
		Random House Word Menu. © 2010 Write Brothers Inc. Word Menu is a registered trademark of the Estate of Stephen Glazier. Write Brothers Inc. All rights reserved. Read more
		Bradford's Crossword Solver's Dictionary. Collins Bradford's Crossword Solver's Dictionary © Anne Bradford, 1986, 1993, 1997, 2000, 2003, 2005, 2008 HarperCollins Publishers All rights reserved. Read more
		Wikipedia on Answers.com. This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article Combination. Read more
		Translations. Copyright © 2007, WizCom Technologies Ltd. All rights reserved. Read more

	compound
	comb. (abbreviation)
	Business Combination S (in banking)

	How do you get the combination to a combination lock when the combination was forgotten? Read answer...
	How do you change the combination on a combination lock? Read answer...
	How do you find out the combination to a combination lock? Read answer...

	Why is the combination higher in the parallel combination than the series combination?
	What are combinations?
	Why is a Combination square called combination?