# Difference between revisions of "Combination"

m |
|||

(9 intermediate revisions by 4 users not shown) | |||

Line 1: | Line 1: | ||

− | |||

− | |||

A '''combination''' is a way of choosing <math>r</math> objects from a set of <math>n</math> where the order in which the objects are chosen is irrelevant. We are generally concerned with finding the number of combinations of size <math>r</math> from an original set of size <math>n</math> | A '''combination''' is a way of choosing <math>r</math> objects from a set of <math>n</math> where the order in which the objects are chosen is irrelevant. We are generally concerned with finding the number of combinations of size <math>r</math> from an original set of size <math>n</math> | ||

Line 21: | Line 19: | ||

Consider the set of letters A, B, and C. There are <math>3!</math> different [[permutations]] of those letters. Since order doesn't matter with combinations, there is only one combination of those three. In general, since for every permutation of <math>{r}</math> objects from <math>{n}</math> elements <math>P(n,r)</math>, there are <math>{r}!</math> more ways to permute them than to choose them. We have <math>{r}!{C}({n},{r})=P(n,r)</math>, or <math>{{n}\choose {r}} = \frac {n!} {r!(n-r)!}</math>. | Consider the set of letters A, B, and C. There are <math>3!</math> different [[permutations]] of those letters. Since order doesn't matter with combinations, there is only one combination of those three. In general, since for every permutation of <math>{r}</math> objects from <math>{n}</math> elements <math>P(n,r)</math>, there are <math>{r}!</math> more ways to permute them than to choose them. We have <math>{r}!{C}({n},{r})=P(n,r)</math>, or <math>{{n}\choose {r}} = \frac {n!} {r!(n-r)!}</math>. | ||

+ | ==Formulas/Identities== | ||

+ | * <math>\binom{n-1}{r-1}+\binom{n-1}{r}=\binom{n}{r}</math> | ||

+ | |||

+ | * <math>\binom{n}{r}=\frac{n}{r}\binom{n-1}{r-1}</math> | ||

+ | |||

+ | * <math>\sum_{x=0}^{n} \binom{n}{x} = 2^n</math> | ||

+ | |||

+ | One of the many proofs is by first inserting <math>a = b = 1</math> into the [[binomial theorem]]. Because the combinations are the coefficients of <math>2^n</math>, and a and b disappear because they are 1, the sum is <math>2^n</math>. | ||

+ | |||

+ | * <math>\sum_{i=0}^{k}\binom{m}{i}\binom{n}{k-i}=\binom{m+n}{k}</math> | ||

+ | |||

+ | * <math>\binom{n}{r}=\binom{n}{n-r}</math> | ||

+ | |||

+ | We can prove this by putting the combinations in their algebraic form. | ||

+ | <math>\binom{n}{n-r}=\frac{n!}{(n-r)!(n-(n-r))!}</math>. As we can see, <math>(n-(n-r))!=(n-n+r)=r!</math>. By the [[commutative property]], <math>\frac{n!}{(n-r)!r!}=\frac{n!}{r!(n-r)!}</math>. Because <math>\frac{n!}{r!(n-r)!}=\binom{n}{r}</math>, by the [[transitive property]], we can conclude that this is true for all non-negative integers n and r where n is greater than or equal to r. Another reason this is true is because that choosing what you don't want is the same as choosing what you do want, because by choosing what you don't want, you imply that you choose the rest. This identity is also the reason why [[Pascal's Triangle]] is symmetrical. | ||

== Examples == | == Examples == | ||

Line 32: | Line 45: | ||

* [[Combinatorics]] | * [[Combinatorics]] | ||

+ | * [[Combinatorial_identity]] | ||

* [[Permutations]] | * [[Permutations]] | ||

* [[Pascal's Triangle]] | * [[Pascal's Triangle]] | ||

+ | * [[Generating_function]] |

## Revision as of 12:26, 8 November 2007

A **combination** is a way of choosing objects from a set of where the order in which the objects are chosen is irrelevant. We are generally concerned with finding the number of combinations of size from an original set of size

## Notation

The common forms of denoting the number of combinations of objects from a set of objects is:

## Formula

## Derivation

Consider the set of letters A, B, and C. There are different permutations of those letters. Since order doesn't matter with combinations, there is only one combination of those three. In general, since for every permutation of objects from elements , there are more ways to permute them than to choose them. We have , or .

## Formulas/Identities

One of the many proofs is by first inserting into the binomial theorem. Because the combinations are the coefficients of , and a and b disappear because they are 1, the sum is .

We can prove this by putting the combinations in their algebraic form. . As we can see, . By the commutative property, . Because , by the transitive property, we can conclude that this is true for all non-negative integers n and r where n is greater than or equal to r. Another reason this is true is because that choosing what you don't want is the same as choosing what you do want, because by choosing what you don't want, you imply that you choose the rest. This identity is also the reason why Pascal's Triangle is symmetrical.