Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Combination"
 
(34 intermediate revisions by 17 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''', sometimes called a '''binomial coefficient''', 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>
  
 +
==Video==
 +
This video goes over what Permutations & Combinations are, their various types, and how to calculate each type! It serves as a great introductory video to combinations, permutations, and counting problems in general! [https://bit.ly/CombinationsAndPermutations Permutations & Combinations Video]
 +
https://youtu.be/MWNe0qbBwu4
 +
 +
This video is a great introduction to permutations, combinations, and constructive counting:
 +
https://www.youtube.com/watch?v=t6a4uHEwQnM&
  
 
== Notation ==
 
== Notation ==
−
 
 
The common forms of denoting the number of combinations of <math>{r}</math> objects from a set of <math>{n}</math> objects is:
 
The common forms of denoting the number of combinations of <math>{r}</math> objects from a set of <math>{n}</math> objects is:
−
 
+
* <math>\binom{n}{r}</math>
−
* <math>{n}\choose {r}</math>
 
 
* <math>{C}(n,r)</math>
 
* <math>{C}(n,r)</math>
 
* <math>\,_{n} C_{r}</math>
 
* <math>\,_{n} C_{r}</math>
Line 12: Line 16:
  
 
== Formula ==
 
== Formula ==
 +
<math>{{n}\choose {r}} = \frac {n!} {r!(n-r)!}</math>
 +
 +
=== Derivation ===
 +
 +
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.(<math>ABC,ACB,BAC,BCA,CAB,CBA</math> are all equivalent in combination but different in permutation.) 
 +
 +
In general, since for every permutation of <math>{r}</math> objects from <math>{n}</math> elements <math>P(n,r)</math> which is <math>\frac{n!}{n-r!}</math>.Now since in permutation the order of arrangement matters(<math>ABC</math> is not same as <math>ACB</math>) but in combinations the order of arrangement does not matter(<math>ABC</math> is equivalent to <math>ACB</math>).For its derivation see this [http://www.artofproblemsolving.com/Videos/external.php?video_id=181 video].
 +
 +
Suppose <math>r</math> elements are selected out.For permutation <math>r</math> elements can be arranged in <math>r!</math> ways.We have overcounted the number of combinations by <math>r!</math> times.So 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>
  
−
<math>{{n}\choose {r}} = \frac {n!} {r!(n-r)!}</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>.
  
−
== Derivation ==
+
* <math>\sum_{i=0}^{k}\binom{m}{i}\binom{n}{k-i}=\binom{m+n}{k}</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>.
+
* <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 ==
  
 
* [[2005_AIME_II_Problems/Problem_1 | 2005 AIME II Problem 1]]
 
* [[2005_AIME_II_Problems/Problem_1 | 2005 AIME II Problem 1]]
−
* [http://www.artofproblemsolving.com/Forum/resources.php?c=182&cid=45&year=2000&p=385889 AIME 2000II/5]
 
−
 
  
 
== See also ==
 
== See also ==
  
 
* [[Combinatorics]]
 
* [[Combinatorics]]
 +
* [[Combinatorial identity]]
 
* [[Permutations]]
 
* [[Permutations]]
 
* [[Pascal's Triangle]]
 
* [[Pascal's Triangle]]
 +
* [[Generating function]]
 +
 +
[[Category:Combinatorics]]
 +
[[Category:Definition]]

Latest revision as of 10:43, 21 May 2021

A combination, sometimes called a binomial coefficient, is a way of choosing $r$ objects from a set of $n$ where the order in which the objects are chosen is irrelevant. We are generally concerned with finding the number of combinations of size $r$ from an original set of size $n$

Video

This video goes over what Permutations & Combinations are, their various types, and how to calculate each type! It serves as a great introductory video to combinations, permutations, and counting problems in general! Permutations & Combinations Video https://youtu.be/MWNe0qbBwu4

This video is a great introduction to permutations, combinations, and constructive counting: https://www.youtube.com/watch?v=t6a4uHEwQnM&

Notation

The common forms of denoting the number of combinations of ${r}$ objects from a set of ${n}$ objects is:

  • $\binom{n}{r}$
  • ${C}(n,r)$
  • $\,_{n} C_{r}$
  • $C_n^{r}$

Formula

${{n}\choose {r}} = \frac {n!} {r!(n-r)!}$

Derivation

Consider the set of letters A, B, and C. There are $3!$ different permutations of those letters. Since order doesn't matter with combinations, there is only one combination of those three.($ABC,ACB,BAC,BCA,CAB,CBA$ are all equivalent in combination but different in permutation.)

In general, since for every permutation of ${r}$ objects from ${n}$ elements $P(n,r)$ which is $\frac{n!}{n-r!}$.Now since in permutation the order of arrangement matters($ABC$ is not same as $ACB$) but in combinations the order of arrangement does not matter($ABC$ is equivalent to $ACB$).For its derivation see this video.

Suppose $r$ elements are selected out.For permutation $r$ elements can be arranged in $r!$ ways.We have overcounted the number of combinations by $r!$ times.So We have ${r}!{C}({n},{r})=P(n,r)$, or ${{n}\choose {r}} = \frac {n!} {r!(n-r)!}$.

Formulas/Identities

  • $\binom{n-1}{r-1}+\binom{n-1}{r}=\binom{n}{r}$
  • $\binom{n}{r}=\frac{n}{r}\binom{n-1}{r-1}$
  • $\sum_{x=0}^{n} \binom{n}{x} = 2^n$

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

  • $\sum_{i=0}^{k}\binom{m}{i}\binom{n}{k-i}=\binom{m+n}{k}$
  • $\binom{n}{r}=\binom{n}{n-r}$

We can prove this by putting the combinations in their algebraic form. $\binom{n}{n-r}=\frac{n!}{(n-r)!(n-(n-r))!}$. As we can see, $(n-(n-r))!=(n-n+r)=r!$. By the commutative property, $\frac{n!}{(n-r)!r!}=\frac{n!}{r!(n-r)!}$. Because $\frac{n!}{r!(n-r)!}=\binom{n}{r}$, 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

See also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Combination&oldid=154047"